遗传算法中进化停滞问题的思考(2)

2、最优保存策略的选择

最优保存策略是对适应函数控制的有力补充，就是第 n 代种群通过遗传算子的操作过后，如果得到的新的种群中的最优个体（最符合适应函数的个体）没有前 n 代种群中的最优个体优秀的话，就把第 n+1 代种群的最差个体用上代最优个体替代^[1]。最优保存策略的实施可保证迄今为止的最优个体不会被交叉、变异运算所破坏，否则在运算过程中总的最优个体之后的一切运算都成了没有必要的浪费，陷于“进化停滞”问题。

3、   合理采用交叉概率和变异概率

针对已定的适应函数，进化中积累的局部优化会在交叉或变异时带入下一代，导致适应函数值的改变非常困难。为了提高效率和快速获得最优解,我们可以根据个体的适应度值,自适应地调节交叉概率和变异概率,当群体有陷入局部最优解的趋势时,就相应地提高交叉概率和变异概率,当群体在解空间发散时,就降低交叉概率和变异概率^[3]。对于适应值较高的个体,选择较低的交叉概率和变异概率,使该个体得以保护进入下一代,对于适应值较低的个体,选择较高的交叉概率和变异概率,使该个体被淘汰掉。这样既保持了群体的多样性,又保证了遗传算法的收敛性,有效地提高了遗传算法的优化能力，从而避免了“进化停滞”问题的产生。

4、无效染色体的处理

遗传算法是一种随机搜索算法，这就不可避免的导致进化过程中无效染色体的产生。直接丢弃显然不是一个好的选择，这会大大增加循环的次数，陷于进化停滞问题，解决办法是设计一个合理的惩罚算子对无效染色体实施惩罚^[2]，使之能够被重新应用到进化过程中，避免无效循环产生的“进化停滞”问题。

5、动态域值限制的引入

对于交叉或变异染色体适应度函数值差异过小导致的进化停滞问题，采取的解决办法则在于根据实际情况确定一个动态参数阈值，作为判断相邻两代或几代染色体进化方向的依据，若相邻两代或几代染色体适应度函数值的差小于此阈值，则视为进化方向有误，应重新选择父染色体进行交叉或变异引导进化方向。当然，对于进化要求不高的情况，也可以据此直接结束进化。

实验中，用动态阈值作为适应函数参考阈值，即每代均求前n代适应函数值的均值（或者群体中所有个体适应度的方差小于某一个极小的阈值）^[2]，交叉或变异时若新一代染色体的适应函数值小于此阈值，则重新进行交叉或变异，50次阈值判断仍未能满足要求则结束进化。事实充分证明了上述看法，解决了“进化停滞”问题，使程序效率得以大幅度提高。

遗传算法是一种不受结构模型、约束条件、参数初值等因素限制的新型优化算法^[4]，在许多领域得以实现，但是它的进化效率低下问题始终是困扰用户的主要问题，解决“进化停滞”问题只是解决了进化效率低下问题的一个方面，问题的最终解决还需要更为深入的研究与探讨。

1 陈国良.遗传算法及应用［M］,北京：人民邮电出版社，1996

2 杨新敏 孙静怡 钱育渝.城市交通流配流问题的遗传算法求解[J],城市交通，2002年第二期

3 南海鹏，王 涛，余向阳.基于改进遗传算法的水轮机调速器参数优化[M],北京：中国水利水电出版社，2002

4 孙艳丰　戴春荣.几种随机搜索算法的比较研究[J],北京：系统工程与电子技术第二期，1998年