智能优化算法：遗传算法(GA)

遗传算法是一种模拟自然选择和遗传机制的优化方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统本身，也要研究与之相关的环境，因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到20世纪70年代初，Holland教授提出了“模式定理”（schema theorem），一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》一书，这是第一部系统论述遗传算法的专著。因此，也有学者把1975年作为遗传算法的诞生年。

1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg出版了《搜索、优化和机器学习中的遗传算法》一书，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时期的遗传算法从古典时期发展到了现代阶段，这本书则奠定了现代遗传算法的基础。

遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。其核心与精髓是自然选择法则——适者生存。在核心法则的作用下，遗传算法通过选择、交叉、变异等遗传操作的更替来完成问题的寻优。遗传从一组初始可行解出发，在不需要除目标函数之外的其他信息的条件下实现对可行域的全局高效搜索，并以概率1收敛到全局最优解。这种良好的特性使算法在组合优化领域获得了成功的应用，并成为计算智能领域研究的热点。随着科学技术的进步，问题的规模不断扩大，复杂度、难度增加，对GA求解质量和运行速度都提出了更高的要求，GA在处理这些问题时往往都显得“力不从心”。

遗传算法的主要任务是设法产生能够充分表现出解空间中的解的优良个体，从而提高算法效率并避免早熟收敛现象。但是，往往在遗传算法的实际应用中，容易出现早熟收敛和后期搜索速度慢以及局部搜索能力较差等缺点。对这些问题，自Holland提出标准的遗传算法后，众多学者在理论和工程各个领域对其进行了进一步研究和改进，使遗传算法得到了长足的发展。

国外，对于复制操作，1975年De Jong针对回放式随机采样复制具有较大的选择误差这一缺点，提出了无回放式随机采样复制以降低选择误差。1981年Brindle在De Jong的研究基础上，提出了一种无回放式余数随机采样复制使得选择误差更小、采样操作更简单。1992年Back针对搜索效率低这一缺陷，提出了与适配值大小无关的均匀排序策略和全局收敛的最优串复制策略，仿真结果表明不适于非线性较强的问题。对于交叉操作，1975年De Jong提出了单点交叉算子和多点交叉算子；1985年Smith提出了循环交叉算子；1989年Syswerda提出了双点交叉算子；1991年Starkweather等学者提出了增强边缘重组算子。此外，常用的交叉算子还有序号交叉、置换交叉、启发式交叉等。在变异操作方面，主要有自适应变异、多级变异等改进。此外，一些高级的基因操作也得到了发展和应用，譬如双倍体和显性遗传、倒位操作、优先策略、静态繁殖和没有重串的静态繁殖等。(www.xing528.com)

在函数优化方面，1975年De Jong提出“聚集”思想，根据群成员中的相似性替换群体中的部分个体，从而将某些个体聚集于各个群集中，然后在各个群集中分别求解问题的局部解。1989年Goldberg引入“分享”思想，首先将解空间分成若干个子空间，然后在子空间中产生子群体分别进行优化，以求得整个问题的解，避免算法仅收敛到局部最优解。然而，De Jong和Goldberg所提出的方法对于解是随机分布的情况就不易奏效，因而应用起来还有一定的局限。针对该问题，1995年孟庆春等学者提出门限变换思想，在选择个体进入下一代时，引入门限变换函数将某些优良个体周围的个体传到下一代，以达到增优除劣的目的，从而避免搜索的盲目性。

国内，陶卿等学者结合遗传算法的全局搜索和约束区域神经网络的局部搜索，提出基于约束区域神经网络的动态遗传算法。何新贵等学者，将适应值函数加入到函数在搜索点的函数值及其变化率中，使得按概率选择的染色体不但具有较小的函数值，而且具有较大的函数变化率值，大幅提高了算法的收敛速度。张良杰等学者通过引入i位改进子空间概念，采用模糊推理技术确定选取突变概率的一般性原则。Liu Li用模糊规则对选择概率和变异概率进行控制，在线改变其值。侯广坤等学者讨论了并行遗传算法的迁徙现象和群体规模估算模型，分析了迁徙的过程，揭示了迁徙的实质，并提出了基于理想条件的迁徙计算模型，且导出了粗粒度并行遗传算法进化质量估算模型。

此外，国内外学者还提出了基于遗传算法的混合算法。如：模拟退火遗传算法、免疫遗传算法、小生境遗传算法、模糊遗传算法、混沌遗传算法、量子遗传算法，还有将蚁群优化算法、粒子群优化算法与遗传算法结合的混合遗传算法。

总体来看，国内外关于遗传算法的研究兴趣可能已达到饱和，理论研究已经比较成熟。另外，就目前研究现状来看，很难在原有的基础上得出更多新的成果。