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

摘  要  遗传算法作为一种功能强大的随机搜索算法被广泛地应用在许多领域，但是进化效率低下问题始终是困扰用户的一个主要问题，“进化停滞”即是它的表现之一。本文分析了“进化停滞”问题产生的机理，并给出了合理的解决方案。

关键词 遗传算法，进化停滞，适应函数

通过对遗传算法的基础理论研究，各种提高进化效率的方法得以广泛采用，但是针对具体的应用领域，还有许多细节问题影响着软件的具体运作，网络优化问题中出现的进化停滞问题就是其中一个例子。

遗传算法应用在网络优化中为网络设计者提供了第一手科学的理论依据，但是网络优化问题属于求解复杂问题的全局最优解，时间复杂性决定了遗传算法的执行效率，出现在进化过程中的“进化停滞”问题无疑又加剧了执行效率低下的缺陷，成为遗传算法应用在网络优化问题中的重要条件。

我们设计了一款染色体采用自然编码，以网络连接边为权值求解网络最小连接费用的软件，固定参数实验中发现如下问题（如表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]。由于初始种群随机产生，满足等式约束较麻烦，所以在算法一开始，就要采取措施使它们和相等数量的问题变量一起被消去，这样做就减少了一部分搜索空间，留下的线性不等式的约束就构成了搜寻解时必须进行搜索的凸集。搜索空间的凸性确保了解的线性组合无需检验约束就产生新的解，从而在全局角度减少了进化中搜索的范围，避免发散的搜索域带来的“进化停滞”问题。