遗传算法的研究进展

1.理论研究

Holland教授提出的模式定理为遗传算法奠定了数学理论基础，也是研究较深入、影响较大的遗传算法理论。模式定理将遗传算法的运行过程理解为模式操作过程，并从模式运算的角度解释遗传算法的运行特性。李军等建立了基于自然数编码的模式定理[108]。李茂军等对单亲遗传算法的模式定理进行了全面的分析，给出了单亲遗传算法模式定理的表达式，并对各种遗传算子破坏模式的概率做了估算[109]。孙艳丰等对模式定理进行了详细分析，给出了具有选择、变异两种算子的模式定理的精确表达式[110]。遗传算法通过模式对搜索空间进行划分，模式的阶越高搜索空间划分越细致。模式定理从模式操作的角度分析了标准遗传算法（Simple genetic algorithms，简称SGA）的运算过程（见图5-1），论证了在选择、杂交、变异算子作用下群体中某一模式所含代表串的数目变化。

图5-1　遗传算法运行过程[111]

遗传算法的另一理论问题是欺骗问题（Deceptive problem）。所谓欺骗问题就是指那些引导遗传算法出错的函数与编码组合[28]。已有的研究结果表明，遗传算法欺骗问题往往包含孤立的最优点，即最好的点往往被差点所包围。文献[27]提出了积木块假设：在遗传算法运行中短的、低阶的、高于群体平均适应度的模式（积木块，Building blocks）逐步组合形成高阶高于平均的模式，直至产生最优解。根据模式定理，如果一个问题的编码满足积木块假设，用遗传算法求解效率较高，否则效率较低。低阶积木块错误地引导搜索过程，不能发现高阶高于平均的模式，最终使算法发散，找不到最优解，这种现象就是欺骗问题。研究欺骗问题是为了预测给定问题用遗传算法求解的难易程度。Goldberg设计了一个最小欺骗问题，旨在尽可能使问题的编码违背积木块假设，使高阶积木块最优解不能生成。实验结果表明，用遗传算法求解包含欺骗问题的优化问题时得到最优解与得不到最优解的情况均可能发生，这说明欺骗问题不是衡量用遗传算法解决问题难易程度的唯一标准[112]。

遗传算法的收敛性问题受到普遍关注，也是遗传算法一直没能解决的难点问题。虽然近年来有关遗传算法的渐近行为受到越来越广泛的注意，但到目前为止，还没有一套完整的理论可以准确、全面地阐述一般遗传算法的收敛性，也无法对遗传算法在大量应用中所表现出的全局优化能力做出理论解释。目前也还没有找到一个恰当度量和论证方法来精确刻画遗传算法在不同条件下的收敛速度，进而也无法对遗传算法的各种改进做出统一、公正的评判。遗传算法收敛性研究结果大致可分为四类：

（1）Vose-Liepins模型。Vose-Liepins模型是基于Vose和Liepins的研究，其核心思想是用两个矩阵算子分别刻画比例选择与组合（即杂交算子与变异算子的复合），通过研究这两个算子不动点的存在性与稳定性来刻画遗传算法的渐近行为[113]。

（2）Markov（马尔柯夫）链模型。由于遗传算法下一代种群的状态通常完全依赖当前种群信息，而不依赖于以往状态，故可自然地用Markov链来描述，即Markov链模型。Markov链模型也一直被用于研究不同形式遗传算法的渐近行为。Horn就长度为1的二进制串分析了不同壁盒算子（Niching operators）对遗传算法的随机影响，Mahfoud[114]详细讨论了当有限Markov链用于描述Boltzmann锦标选择遗传算法时，其转移概率的确定过程[55]。Suzuki通过估计转移矩阵的特征值，分析了修正杰出者选择遗传算法的收敛性与收敛速度[115]。

（3）公理化模型。最近徐宗本等人通过公理化描述遗传算法的选择算子与重组算子，并利用所引进的参量分析遗传算法的收敛性。

（4）连续（积分算子）模型。为了有效求解高维连续问题和解决遗传算法实现中的效率与稳健性问题，Peck和Dhawan及Qi和Palmieri发展了对于连续变量收敛性的分析方法[116-118]，但分析框架与方法均不完善。目前还没有一个好的方法可用于准确描述连续遗传算法的动态行为，并在不强加任何严格的或人为的条件下给出相关的收敛性结果。

与收敛性分析紧密相关的另一基本理论问题则是遗传算法能以多快的速度收敛，即收敛速度问题。收敛速度的研究不仅可从另一侧面来阐明遗传算法的收敛性，而且对于建立合适的停机准则及恰当的度量标准以全面、客观地评判遗传算法的各种执行策略有重要意义。然而，关于遗传算法收敛速度与复杂性研究方面仅有少量特殊的结果，该方面的工作可归纳为收敛速度估计、迭代次数估计和时间复杂性估计等三类估计。到目前为止，有关遗传算法收敛速度与复杂性的结果几乎全部限于对二进制情形、特殊适应函数或仅使用某一两个遗传算子操作情形的遗传算法，由于所使用的度量准则各不相同，均存在相当的局限性。

编码是遗传算法实现的关键。目前遗传算法的编码方式主要有二进制编码、Delta编码、格雷码编码、实数编码、顺序编码、广义图编码、树编码等[119]。标准遗传算法采用二进制编码，而当变量个数较多或其取值范围较广时，其收敛速度将大大降低。为此，Whitley等提出了“Delta编码”，对多变量优化问题，可以将各变量的二进制码串联在一起形成码链，也称为串（String）或人工染色体，这种方法称为串联编码法（Series encoding）[120]。对于实变量情况，精度要求与计算量之间的矛盾较为突出，对此Michalewicz等采用实数编码对标准遗传算法予以改进[121]。岑文辉等采用两阶编码，先用二进制编码求近似解，以缩小解空间，再在缩小的解空间上用实数编码求精确解以提高遗传算法的效率[122]。Schraudolph等还提出了动态编码方法[123]。

另外，遗传算法在算法停止执行准则方面，各使用者根据实际情况的不同，可选取不同形式的终止条件，可以按照最优解的精度、进化代数的次数、适应度函数值不再改善和染色体与上代群体相同的数量等来终止遗传算法的运行[124]。

2.与其他方法的结合(www.xing528.com)

遗传算法与人工神经网络结合的研究近年来日趋活跃，主要体现在两个方面：

（1）用遗传算法优化人工神经网络的结构和参数。

（2）利用BP算法对遗传算法进行精细搜索。杨晓红用遗传算法对连接权为离散值的神经网络进行优化训练，提出了结构矩阵基因码表示法，并对异或问题进行了成功的计算[125]。岑文辉等用遗传算法来改善BP算法的局部收敛性[122]。王宏伦等利用遗传算法的全局最优性在大范围内搜索可能的极值，用BP算法的误差梯度下降特性在极值点附近快速搜索，提出了遗传算法与BP混合学习算法[126]。

遗传算法和模拟退火算法都是模拟自然法则的优化算法，它们的结合对提高遗传算法的效率是有意义的。目前的研究大都是基于在遗传算法中引入模拟退火算法以保持群体的多样性，以避免遗传算法的早熟收敛。Fogel提出了遗传算法与模拟退火算法相结合的一种退火演化算法，该算法克服了模拟退火算法单点迭代的缺点，充分利用了遗传算法的并行性特点，减少了算法陷入局部极小的概率，提高了算法的速度和全局收敛性[55]。

从生物进化或自然界的各种现象中所获得的新启示提出新的遗传算法，或利用以往的优化方法对现有的遗传算法进行改进，以及从理论和实际计算效果两方面进一步比较遗传算法与其他优化方法的计算效果，并探索如何把遗传算法推广到非优化类问题中去，也是目前遗传算法研究的重要内容。赵明旺在遗传算法中嵌入最速下降算子，并定义适当的适应度函数和子代个体的选择算子，将遗传算法和最速下降法两者有效地进行结合，减少了最速下降法陷入局部极小的概率，提高了遗传算法的速度和效率[127]。张春慨等利用混沌特定的内在随机性、遍历性和变化的进化速率，较好地模拟了生物进化过程，提高了算法的爬山能力，并针对不同的阶段，适应地采取不同的算子操作次序，在一定程度上保护了已得到的有效个体，提出了基于进化混沌突变算子的实数编码遗传算法[124]。

3.应用研究

由于遗传算法具有全局优化性、并行性和智能性等特点，遗传算法得到了越来越广泛的应用。首先，遗传算法是一种全局性优化方法，即使在目标函数是不连续的、非线性的、非规则的或带有噪声的情况下，遗传算法也能以很大概率找到全局最优解；其次，遗传算法是一种并行性优化方法，非常适合于并行计算；第三，遗传算法是一种智能性优化方法，容易渗透到已有模型中，具有充分的可扩展性，使得遗传算法易于同别的方法、技术融合。因此，目前遗传算法在遗传计算、遗传编程、分类器系统学习、投影寻踪、模糊规划、多目标决策、分形分维和进化神经网络等方面得到了大量应用。

张毅等建立了求解多变量非线性整数规划问题的实际模型—串联电抗率优化计算模型的遗传算法[128]。曾三友等用遗传算法求解了一类混合整数非线性规则问题，结果表明此法求解速度理想，易达最优解，也可以处理纯整型或纯实型变量的非线性函数优化问题[129]。金菊良等利用实数编码加速遗传算法解决了水质规划问题[130]。Vignaux以运输问题为例探讨了新的处理约束的方法，生成的初始群体全部是可行解，经进化迭代后仍是可行解[131]。王黎等提出用遗传算法的罚函数法把约束组合到适应度函数表达式中处理了水电站优化调度问题和水电厂经济运行问题，并得到了满意的结果[132，133]。樊重俊用特定的杂交、变异算子在一定程度上解决了线性等式约束问题[134]。1987年Goldberg和Richardson用共享和限制交配机制结合在一起的方法成功地实现了多峰的搜索。林焰等也利用小生境技术，成功地实现了多峰的搜索[135]。刘洪杰等在传统遗传算法的基础上，引入梯度算子、聚类算子和单亲繁殖，并将梯度平方和倒数作为评价函数，用来搜索多极值点，该算法对等高等距、不等高等距和不等高不等距情况都有很好的结果[136]。遗传算法也被用于求解多目标决策优化问题[137]。

遗传算法已有许多其他的实际应用。20世纪80年代，Goldberg用遗传算法学控制天然气输气管道系统。美国通用电器公司和Rensselaer综合技术学院的研究人员成功地将遗传算法用到高涵道比的喷气发动机的涡轮设计中。1992年在巴塞罗那奥运会之后举行的伤残运动会由于10%的运动员被重新确定伤残等级，赛程表需要实时地重新安排，AIS人工智能公司采用遗传算法成功地解决了这一难题，而在1988年汉城奥运会职员用传统人工智能方法需要通宵达旦才能重新安排赛程。美国西方通信公司采用遗传算法进行光缆布线优化设计，节省费用1亿美元[138]。

遗传算法创建于20世纪60年代，到了20世纪70年代遗传算法潜在的求解复杂问题的能力开始引起了学者们的关注，但那个时代由于计算机计算速度慢、价格昂贵，所以计算量较大的遗传算法没有引起人们的广泛关注和应用。从20世纪80年代开始，随着计算机技术的发展和对遗传算法的深入研究，遗传算法被广泛地应用于许多不同的领域，取得了良好的效果，并由此掀起了遗传算法研究热潮。

值得注意的是，虽然遗传算法模拟了生物的进化过程，但目前遗传算法的运行规模还远远小于生物的进化规模。随着大规模并行计算机和分布式计算机系统性能的不断提高以及对生物的进化系统的进一步的认识，人们将有可能模拟更接近于自然的进化系统，这样遗传算法的并行性将得到充分的发挥，从而为人类进一步揭示生命和智能的奥秘写下新的篇章[30]。