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

摘  要  遗传算法作为一种功能强大的随机搜索算法被广泛地应用在许多领域，但是进化效率低下问题始终是困扰用户的一个主要问题，“进化停滞”即是它的表现之一。本文分析了“进化停滞”问题产生的机理，并给出了合理的解决方案。关键词 遗传算法，进化停滞，适应函数一  引言通过对遗传算法的基础理论研究，各种提高进化效率的方法得以广泛采用，但是针对具体的应用领域，还有许多细节问题影响着软件的具体运作，优化问题中出现的进化停滞问题就是其中一个例子。遗传算法应用在网络优化中为网络设计者提供了第一手的理论依据，但是网络优化问题属于求解复杂问题的全局最优解，时间复杂性决定了遗传算法的执行效率，出现在进化过程中的“进化停滞”问题无疑又加剧了执行效率低下的缺陷，成为遗传算法应用在网络优化问题中的重要条件。二  遗传算法中“进化停滞”问题的分析我们设计了一款染色体采用编码，以网络连接边为权值求解网络最小连接费用的软件，固定参数实验中发现如下问题（如表1所示）：表1 进化结果对比表

进化代数	最小费用
0	939.88645cm
50	548.94277cm
100	460.02706cm
200	342.16332cm
300	322.83430cm
500	322.66646cm

某一次500代程序优化运行结果所示，前300代进化基本理想，但300­­——500代进化却陷于停滞。分析其原因，以适应函数阈值限制交叉或变异的染色体进化，对于优化未进行到一定程度的代数影响不大，因为此时局部优化同样具有很大的空间，适应函数的改变是可观的，但是对于进化达到一定程度后，积累的局部优化会在交叉或变异时带入下一代，导致适应函数值的改变非常困难，此时就会产生 “进化停滞”问题。看来“进化停滞”问题的出现在于适应函数对进化过程控制的不合理性，所以我们有必要重新认识适应函数。三  适应函数分析我们知道，适应度是遗传算法得以进行下去的关键^[1]。由于有了适应度，个体之间才存在竞争，竞争的结果就是：生存下来的个体越来越优秀，适应度最高的个体则是最符合求解目标的个体（最优解）。适应度是这么重要，对个体适应度的评价方法和具体操作在遗传算法中就有相当重要的地位。把优化的目标函数解释为生物种群对环境的适应性，要实现的目标就是个体的适应度评判标准，越符合目标的个体，其适应度就越大，反之就小，这就是适应函数。适应函数的选取直接关系到进化结果的收敛和成熟，对进化效率起着至关重要要的作用。四  遗传算法中解决进化停滞问题的可行方案“进化停滞”问题的出现导致进化方向的盲目性和无效染色体的产生，科学选择适应函数、科学处理必然存在的无效染色体就成为解决问题的关键。因此，我们可以从以下几个围绕适应函数控制的方面着手处理“进化停滞”问题：1、   做好约束的处理优化目标函数的约束一般可分为值域约束、等式约束、不等式约束^[2]。由于初始种群随机产生，满足等式约束较麻烦，所以在算法一开始，就要采取措施使它们和相等数量的问题变量一起被消去，这样做就减少了一部分搜索空间，留下的线性不等式的约束就构成了搜寻解时必须进行搜索的凸集。搜索空间的凸性确保了解的线性组合无需检验约束就产生新的解，从而在全局角度减少了进化中搜索的范围，避免发散的搜索域带来的“进化停滞”问题。

 

2、最优保存策略的选择最优保存策略是对适应函数控制的有力补充，就是第 n 代种群通过遗传算子的操作过后，如果得到的新的种群中的最优个体（最符合适应函数的个体）没有前 n 代种群中的最优个体优秀的话，就把第 n+1 代种群的最差个体用上代最优个体替代^[1]。最优保存策略的实施可保证迄今为止的最优个体不会被交叉、变异运算所破坏，否则在运算过程中总的最优个体之后的一切运算都成了没有必要的浪费，陷于“进化停滞”问题。3、   合理采用交叉概率和变异概率针对已定的适应函数，进化中积累的局部优化会在交叉或变异时带入下一代，导致适应函数值的改变非常困难。为了提高效率和快速获得最优解,我们可以根据个体的适应度值,自适应地调节交叉概率和变异概率,当群体有陷入局部最优解的趋势时,就相应地提高交叉概率和变异概率,当群体在解空间发散时,就降低交叉概率和变异概率^[3]。对于适应值较高的个体,选择较低的交叉概率和变异概率,使该个体得以保护进入下一代,对于适应值较低的个体,选择较高的交叉概率和变异概率,使该个体被淘汰掉。这样既保持了群体的多样性,又保证了遗传算法的收敛性,有效地提高了遗传算法的优化能力，从而避免了“进化停滞”问题的产生。4、无效染色体的处理遗传算法是一种随机搜索算法，这就不可避免的导致进化过程中无效染色体的产生。直接丢弃显然不是一个好的选择，这会大大增加循环的次数，陷于进化停滞问题，解决办法是设计一个合理的惩罚算子对无效染色体实施惩罚^[2]，使之能够被重新应用到进化过程中，避免无效循环产生的“进化停滞”问题。5、动态域值限制的引入对于交叉或变异染色体适应度函数值差异过小导致的进化停滞问题，采取的解决办法则在于根据实际情况确定一个动态参数阈值，作为判断相邻两代或几代染色体进化方向的依据，若相邻两代或几代染色体适应度函数值的差小于此阈值，则视为进化方向有误，应重新选择父染色体进行交叉或变异引导进化方向。当然，对于进化要求不高的情况，也可以据此直接结束进化。实验中，用动态阈值作为适应函数阈值，即每代均求前n代适应函数值的均值（或者群体中所有个体适应度的方差小于某一个极小的阈值）^[2]，交叉或变异时若新一代染色体的适应函数值小于此阈值，则重新进行交叉或变异，50次阈值判断仍未能满足要求则结束进化。事实充分证明了上述看法，解决了“进化停滞”问题，使程序效率得以大幅度提高。五  结论遗传算法是一种不受结构模型、约束条件、参数初值等因素限制的新型优化算法^[4]，在许多领域得以实现，但是它的进化效率低下问题始终是困扰用户的主要问题，解决“进化停滞”问题只是解决了进化效率低下问题的一个方面，问题的最终解决还需要更为深入的研究与探讨。参考1 陈国良.遗传算法及应用［M］,北京：人民邮电出版社，19962 杨新敏 孙静怡 钱育渝.城市流配流问题的遗传算法求解[J],城市交通，2002年第二期3 南海鹏，王 涛，余向阳.基于改进遗传算法的水轮机调速器参数优化[M],北京：水利水电出版社，20024 孙艳丰　戴春荣.几种随机搜索算法的比较研究[J],北京：系统工程与技术第二期，1998年