遗传算法的收敛性及改进措施

遗传算法收敛性问题，即遗传算法能否达到全局最优解和达到全局最优解的速度问题，是遗传算法理论分析至今尚未解决的问题。目前普遍认为，标准遗传算法并不能保证全局最优收敛，但是在一定的约束条件下，遗传算法可以实现这一点。此外，关于早熟收敛问题，许多研究者从实际经验出发，给出了许多防范措施及改进对策。以下将着重介绍这两方面的论证结果，而略去繁杂的证明过程。

1.标准遗传算法的收敛性

定义9.3.9　对初始群体，以比例法进行选择操作（按个体适应度占群体适应度的比例进行复制），以概率pc∈［0，1］进行交换操作，以概率pm∈（0，1）进行变异操作的群体寻优算法，称为标准遗传算法。

定理9.3.2　标准遗传算法（参数如定义9.3.9）不能保证收敛至全局最优解（证明从略）。

上述定理无疑是一个令人沮丧的结论。然而，值得庆幸的是，只要对标准遗传算法作一些改进，就能保证其收敛性。

定理9.3.3　具有定义9.3.9所示参数，且在选择操作后保留当前最优值的遗传算法，最终能收敛到全局最优解（证明从略）。

定理9.3.4　具有定义9.3.9所示参数，且在选择操作前保留当前最优值的遗传算法，最终能收敛到全局最优解（证明从略）。

由上可知，标准的遗传算法在任意初始化、任意交换、任意变异操作（简单的或复杂的）和任意适应度函数下的比例选择操作，都不能保证收敛至全局最优解，而通过改进遗传算法，即在选择操作前或后保留当前最优解，则能保证收敛至全局最优解。这就是说，收敛至全局最优解，实际上是不断地保留当前最优解的结果。

值得注意的是，尽管证明了改进的遗传算法（保留当前最优解）最终能收敛至全局最优解，但收敛的时间可能是很长的。关于遗传算法的收敛速度问题，初始化对收敛性的影响以及其他非标准遗传算法的收敛问题至今仍未有深入研究。也许是由于这些研究需要涉及更深的数学理论，因此关于遗传算法收敛性的问题，已经成为当前数学研究的难题。

2.未成熟收敛及其对策

未成熟收敛是用遗传算法解决实际问题时常碰到的现象，它的表现是：

（1）群体中的个体很快陷于局部极值，进化停止；

（2）接近最优解的个体总是被淘汰，进化过程不收敛。

导致未成熟（早熟）收敛的因素，在遗传算法的每个环节上都可能发生，大致有以下几方面：

（1）在进化初始阶段，生成了具有很高适应度的个体X；

（2）在比例选择下，其他个体被淘汰，大部分个体与X一致；

（3）配对不好导致两个相同的个体进行交换操作，从而未能产生新个体；

（4）通过变异或逆转所生成的个体适应度高但数量少，所以被淘汰的概率很大；

（5）群体中的大部分个体处于与X一致的状态。

为了防止早熟，许多研究者做了大量的工作，把他们的经验加以总结，可以列出如下的对策。

1）尽量维持群体中个体的多样性

（1）适当考虑群体的初始规模。当然，也不能规模太大，否则会增加计算工作量。(www.xing528.com)

（2）采用可变群体规模。在进化计算过程中，在保证个体差异的前提下，群体的规模可增可减。

（3）使早熟现象局部化。把群体分割成若干子群体，每个群体独立进行选择操作，如果因出现不适当的个体而产生早熟时，早熟收敛也只发生在局部。

（4）淘汰掉相同的个体。但也要注意不能过分，因为适者生存是遗传算法的基本原则，优秀的个体总是在后代中有较多的繁衍。

（5）增大配对个体的距离，尽量避免近亲相配。可用海明距离来判断配对个体的相似度，选择距离较大的个体相配。

2）改进选择操作

（1）不采用比例法而采用保留当前最优解法。

（2）不采用赌轮法而采用期望值法。

（3）适当采用联赛选择法和排挤法来选择操作。

（4）对选择概率进行加权处理，例如用乘幂法来加大相近概率的距离。

3）改进交换操作

（1）适当设定交换点，保证交换操作能继承前一代优秀个体的基因。这里的困难是事先难以确定最佳基因座的位置。可以用试验法来调整。

（2）采用一致交换法，适当设定屏蔽字。其目的是产生能继承上一代优良特性的新个体。

（3）把交换操作与编码设计结合起来考虑，实行编码-交换设计。

（4）选择距离较大的配对亲体进行交换操作。

4）改进变异操作

（1）在进化初始阶段提高变异概率，以加强遗传算法的随机搜索能力。

（2）采用编号的逆转操作，在保持适应度的前提下对基因座进行重新排列。

（3）把逆转操作与交换操作相结合，形成独特的交换操作（PMX、OX、CX），参见9.6节。

5）对适应度恰当定标

参见9.3.5节。