遗传算法的收敛性研究

汪民乐

摘 要：遗传算法的收敛性分析是遗传算法研究中的重要问题，直接关系到遗传算法的实际应用价值。给出遗传算法全局收敛性的定义，描述当前遗传算法收敛性分析的主要模型，对自适应遗传算法、并行遗传算法、小生境遗传算法等典型遗传算法的收敛性进行分析，给出相关的研究结果，并指出遗传算法收敛性研究的未来发展方向。研究结果对提高遗传算法收敛性具有参考价值。

关键词：遗传算法；全局收敛性；自适应遗传算法；并行遗传算法；小生境遗传算法

中图分类号：TP18 文献标识码：A

Abstract：The convergence analysis is an important problem in research on Genetic Algorithm. In this paper， the new definition of Genetic Algorithms convergence was given，the main models for Genetic Algorithms convergence were described， and the typical Genetic Algorithms convergence were analyzed， the conclusions were given. Finally，the future efforts were put forward. The results can offer support for improving Genetic Algorithms convergence .

Key words：genetic algorithm；convergence；adaptive genetic algorithm；parallel genetic algorithm；niche genetic algorithm

1 引 言

作为一种普遍适用的随机大范围搜索策略，遗传算法（Genetic Algorithm—GA）的收敛性研究[1-10]，是遗传算法随机搜索机理研究的核心内容。建立公理化的收敛性理论体系，不但可以提高现有遗传算法的收敛速度，克服陷于局部极值和出现过早收敛，同时可以探讨判定当前解是否达到最优解的合理准则，从而给出合理的停机准则。因此，通过遗传算法收敛性的研究，可为遗传算法的发展提供坚实可靠的理论依据及正确的方向。目前，关于遗传算法的收敛性研究主要有两种方法：一种是将种群数目推广到无穷，研究其概率密度[11]；一种是以马氏链理论作为工具研究有限种群收敛性[12]。由于GA实际应用中，均只能构造有限种群，故在此主要研究有限种群GA的全局收敛性。

2 遗传算法收敛性研究的主要方法

遗传算法的收敛性通常是指遗传算法所生成的迭代种群收敛到某一稳定状态，或其适应值函数的最大或平均值随迭代趋于优化问题的最优值。依据不同的研究方法及所用的数学工具，已有的遗传算法收敛性研究方法可大致分为四类[13]：VoseLiepins模型、Markov模型、公理化模型和连续（积分算子）模型。

2.1 VoseLiepins 模型

这类模型大致可以分为两种情形， 即针对无限种群和有限种群的模型。 首先由Vose 和Liepins在1991 年提出了针对无限种群的模型， 其核心思想是： 用两个矩阵算子分别刻画比例选择与组合算子（即杂交算子与变异算子的复合）， 通过研究这两个算子不动点的存在性与稳定性来刻画GA 的渐近行为。VoseLiepins 模型在种群规模无限的假设下可精确刻画GA ， 但在有限规模情形下却只能描述GA 的平均性态。 为了克服这一缺陷， Nix 和Vose 在1992 年结合VoseLiepins 模型与Markov 链描述， 发展了GA 的一个精确Markov 链模型， 称为NixVose 模型， 它针对的是有限种群的情形， 该模型恰好描述了GA 的实际演化过程， 但是由于NixVose 的有限种群模型概率转移矩阵的复杂性， 故直接基于该模型分析GA 收敛性是困难的， 而VoseLiepins 的无限种群模型虽然只能描述实际GA 演化的平均性态， 但它却精确预报了GA收敛性态随种群规模的变化。

2.2 Markov 链模型

由于遗传算法下一代种群的状态通常完全依赖当前种群信息， 而不依赖于以往状态， 故可自然地用Markov链描述，这也是遗传算法收敛性研究中最常采用的工具。这种方法一直被用于研究不同形式GA 的渐近行为， 并得出一些典型的结果， 如：用Markov 链描述其动态行为；从更一般的等价类层次表述种群等。当然， 还有很多其它的分析结果充分体现了使用Markov 链模型描述遗传算法具有直接、精确的优点， 但由于所采用有限状态Markov链理论本身的限制， 该模型只能用于描述通常的二进制编码或特殊的非二进制编码GA。

2.3 公理化模型

这种模型既可用于分析时齐GA，又可用于分析非时齐GA。其核心思想是： 通过公理化描述GA的选择算子与演化算子， 并利用所引进的参量分析GA的收敛性。 对于常见的选择算子与演化算子， 所引进的参量能方便地确定， 因而这一模型具有重要的理论意义与应用价值。该模型通过详细估计常见选择算子与演化算子的选择压力、选择强度、保存率、 迁入率、迁出率等参数， 导出了一系列具有重要应用价值的GA 收敛性结果。此外， 该模型也可用于非遗传算法类的其它模拟演化算法的收敛性分析。

2.4 连续（积分算子）模型

大量数值试验表明：为了有效解决高维连续问题和GA 实现中的效率与稳健性问题， 直接使用原问题的浮点表示而不进行编码转换具有许多优点，由此形成的遗传算法称为连续变量遗传算法或浮点数编码遗传算法。对于这类连续变量遗传算法收敛性的分析方法，已有一些研究成果，如： 浮点数编码模式定理，用以描述进化过程中模式的变化规律，特别是优良模式的产生及变化（保持或被破坏）规律，从而有助于分析连续变量遗传算法的收敛性；通过研究大样本行为， 分别导出了连续变量GA 在使用比例选择、均匀杂交和变异以及三个遗传算子联合作用等情形下， 当种群规模趋于无穷时， 种群的概率分布所对应的密度函数应满足的递归公式，但该结果只是在种群规模趋于无穷的条件下得到的种群迭代序列分布的估计， 故只能看作是对GA 渐近行为的大样本近似，并不能直接应用于改进一般GA 的实际执行策略。

3 典型遗传算法的收敛性

3.1 标准遗传算法（Canonical Genetic Algorithm—CGA）的全局收敛性

实数编码遗传算法的产生是遗传算法研究的一大进步，相关的理论与应用成果不断出现。实数编码遗传算法除了具有二进制编码遗传算法的所有特点，如：简单、通用、鲁棒性强、适于并行分布处理等之外，在算法的收敛性方面还有以下优势[16]：

1）直接使用实数作为染色体参与遗传操作，无需特定的编码与解码过程，因此降低了算法实现的复杂度，提高了算法的执行效率，尤其是当处理大规模复杂问题、高维数值优化问题或子目标个数较多的多目标优化问题时，实数编码遗传算法的效率更能得到体现。

2）用实数编码可以消除二进制编码存在的海明悬崖（Hamming cliffs）问题。

3）实数编码遗传算法中可以利用连续变量函数的渐变性（Graduality）。这里的“渐变性”是指变量值的微小变化所引起的对应函数值的变化也是微小的，由于这一特点，使实数编码遗传算法具有较强的局部调节功能，例如实数编码遗传算法的非一致变异算子（Non uniform mutation）相比二进制编码遗传算法的变异算子，能更好地实现种群的局部调节，从而更有利于逼近最优解。

4）在染色体长度一定的条件下，实数编码遗传算法具有比二进制编码遗传算法更大的搜索空间，甚至是无穷搜索空间，而不会影响其搜索精度，但在二进制编码遗传算法中，由于其本质是将一切寻优问题均转化为组合优化问题进行离散寻优，且由于染色体长度的限制，二进制染色体所能表达的个体数是有限的（等价于在问题的解空间所能遍历的点是有限个），如果扩大搜索空间，个体间的距离将被拉大，导致种群空间里个体分布的稀疏性，从而降低搜索精度，不利于获取全局最优解，尤其对于欺骗问题（Deceptive problem）更是如此。因此，实数编码遗传算法比二进制编码遗传算法具有更好的全局收敛性。

5）对于具有非平凡约束条件的问题，实数编码遗传算法更易吸取问题域知识，指导种群朝正确的搜索方向进化。

6）实数编码遗传算法繁殖新个体的方式更加灵活。对于二进制编码遗传算法，由于编码的限制，可供使用的交叉和变异算子的种类十分有限，而实数编码遗传算法可使用的交叉和变异算子则相对丰富，因而实数编码遗传算法在寻优时能够在解空间中进行更好的探索和开发。

3.4 并行遗传算法（Parallel Genetic Algorithm—PGA）的全局收敛性

在求解大规模甚至超大规模问题时，采用并行遗传算法（PGA）是一种行之有效的策略，能获得较高的计算效率。并行遗传算法主要分为三种类型[26]，其收敛性各有特点，详细分析如下：

1）主从式并行模型

这种并行模型由一个主处理器和若干个从处理器构成，主处理器的工作是监控整个染色体种群，并基于全局统计执行操作；各个从处理器接受来自主处理器的个体然后进行重组、交叉、变异，产生新一代个体，并计算适应度，再把计算结果回传给主处理器。由于存在主处理机忙而从处理机空闲的情况，而且从处理机计算完成后要向主处理机发送结果，造成瓶颈和通信延迟，从而导致效率的低下，在很大程度上限制了此类模型的应用。如果个体适应度评价很费时，并且在时间上远远超过通信时间，主从式并行遗传算法将能够获得很高的效率。

2）粗粒度并行模型

粗粒度并行遗传算法模型将种群划分为多个子种群，并分配给不同的处理器，每个处理器相互独立并发运行一个进化过程。为了减少通信量，进化若干代后通信一次，互相传递最佳个体或以一定比例交换个体。虽然最佳个体的多次迁移会造成一定的通信开销，但正是由于粗粒度并行遗传算法允许子种群之间根据预定的通讯拓扑关系按一定比例交换个体，通过新个体的加入，增加了个体的差异，维持了种群的多样性，并且每个子种群同时搜索种群空间的不同区域，提高了全局搜索能力，从而有利于避免早熟收敛现象。粗粒度并行遗传算法模型是目前应用最为广泛的一种并行遗传算法，一方面是由于它容易实现，只需要在串行遗传算法中增加个体迁移子例程，在并行计算机的节点上各自运行一个算法的副本，定期交换最佳个体即可；另一方面是它容易模拟，即使在没有并行计算机的情况下，也可在串行机网络或者单台串行机上执行粗粒度并行遗传算法，有较高的加速比。虽然在串行计算机上实现的粗粒度并行遗传算法不具有并行计算的速度优势，但仍具有避免早熟收敛的特性。因此，粗粒度并行遗传算法作为遗传算法的一种特殊变形，能有效克服遗传算法在全局搜索能力方面的固有不足。

3）细粒度并行模型

细粒度并行模型又称为邻域模型，是将遗传算法与细胞自动机结合起来的模型。细粒度模型可以看作是一种细胞状的自动机网络，群体划分为多个小的子群体，分配到给定空间环境（一般是排列成环形阵列的二维网格的形状，以防止边界效应的问题发生）中的处理机中（在理想情况下每个处理机单独处理一个个体，称为细胞）。网格中的邻域关系限定了个体空间上的关系，遗传操作被看作随机的局部更新规则，这样模型是完全分布而无需任何全局控制结构的。对每个细胞而言，选择仅仅是在赋给该细胞的个体及其邻域的个体上进行，交叉也仅交配邻近的个体。通过比较细粒度模型与标准遗传算法，可以发现细粒度模型能提供对搜索空间更彻底的搜索，因为它的局部选择机制减轻了选择压力。对困难的问题，细粒度遗传算法比标准算法的求解效果好，也更不容易陷人局部最优。考虑到参数的设置，细粒度遗传算法的鲁棒性较好，但是细粒度并行模型要求有尽可能多的处理机，所以此类模型的应用范围不广，一般只运行于大规模系统。细粒度模型和粗粒度模型的根本区别就是算法框架中的结构的控制次数的不同，前者是群体中个体的个数，而后者则是子群体规模，即处理器的个数。

3.5 小生境遗传算法（Niche Genetic Algorithm—NGA）的全局收敛性

在生物学中 ，小生境 （Niche）是指特定的生存环境。生物在其进化过程中 ，一般总是与自己相同的物种生活在一起，这就是一种小生境的自然现象。在遗传算法中引进小生境的概念 ，让种群中的个体在不同特定的生存环境中进化 ，而不是全部聚集在一种环境中，这样可以使算法在整个解空间中搜索 ，以找到更多的最优个体，避免了在进化后期适应度高的个体大量繁殖 ，充斥整个解空间 ，导致算法停止在局部最优解上。

遗传算法中模拟小生境的方法主要有以下几种[27]：

1）基于预选择的小生境实现方法 其基本思想是：仅当新产生子代个体的适应度超过其父代个体时 ，所产生出的子代个体才能替代其父代个体而遗传到下一代群体中，否则父代个体仍保留在下一代群体中。由于子代和父代个体之间的编码结构有相似性 ，所以该方法替代掉的只是一些编码结构相似的个体 ，故它能有效地维持种群多样性 ，并造就小生境的生存环境，从而有利于全局收敛。

2）基于排挤的小生境实现方法 其基本思想是：设置一个排挤因子CF，由群体中随机选择的 1/CF个个体组成排挤成员，排挤掉一些与其相类似的个体。这里个体之间的相似性可用个体编码串之间的海明距离来度量。随着排挤过程的进行 ，群体中的个体逐渐被分类 ，从而形成各个小的生存环境即小生境 ，并维持了群体的多样性。

3）基于共享（Sharing）函数的小生境实现方法 其基本思想是：通过反映个体之间相似程度的共享函数来调整群体中各个个体的适应度，从而在以后的进化过程中 ，能够依据调整后的新适应度来进行选择运算。这种调整适应度的方法能够限制群体内个别个体的大量增加 ，以维护群体的多样性 ，并形成了一种小生境的进化环境。

4）基于淘汰相似结构机制的小生境实现方法 该方法是在标准遗传算法的基础上增加小生境淘汰运算 ，通过引入罚函数的方法来调整个体的适应度 ，淘汰结构相似的个体 ，使得各个个体之间保持一定的距离 ，从而造就了一种小生境的进化环境 ，维护了群体的多样性 ，提高了全局搜索能力。

小生境遗传算法具有更强的全局搜索能力和更高的收敛速度 ，能够高效地寻找到多个全局最优值 ，是一种寻优能力、搜索效率和全局收敛概率更高的优化算法 ，其综合性能比标准遗传算法有显著提高。

4 遗传算法收敛性研究的主要发展方向

遗传算法收敛性研究的主要发展方向包括以下几个方面：

1）遗传算法的收敛性与遗传算子的内在关系研究。主要包括遗传算子的操作方式对遗传算法收敛性的影响机制研究、影响结果的定量刻画与描述，如：对遗传算法收敛速度的影响、对遗传算法收敛到全局最优解的影响等。

2）平衡遗传算法的收敛性与时间复杂性的研究。收敛性与时间复杂性平衡是指在保证遗传算法收敛的同时预防过度进化，防止出现“漫游”（Roam）现象。在遗传算法的实际运行中，为提高遗传算法的收敛性（收敛到全局最优解的概率），往往以增加进化时间为代价，而这在求解大规模问题时是难以接受的。

3）遗传算法最终收敛到全局最优解的时间复杂度研究。主要是遗传算法收敛速度的定量估计和提高收敛速度的方法研究。除有关标准遗传算法时间复杂度的研究外，还包括各种改进遗传算法时间复杂度的研究。

4）在提高遗传算法收敛性的同时预防早熟收敛的研究。为提高遗传算法的收敛速度，降低其时间复杂性，在遗传算法的实际运行中，往往采用控制参数选择（如：提高遗传算法的交叉概率）和改进遗传操作的方法，但这容易导致“早熟”（Premature）现象的发生，从而降低遗传算法收敛到全局最优解的概率，这一矛盾至今依然存在。

5）混合遗传算法的收敛性研究。许多研究表明，采用混合模型可有效提高遗传算法的局部搜索能力，从而进一步改善其收敛速度和解的品质。通过对混合遗传算法收敛性的研究，不仅可以增强现有遗传算法的实用性与可靠性，而且可为正在蓬勃发展的混合遗传算法提供一定的理论支撑。而关于混合遗传算法的收敛性分析，却更加困难。

6）构造高效且全局收敛遗传算法的方法研究。对遗传算法的收敛性进行研究的最终目的是构造高效、收敛的遗传算法，这直接关系到遗传算法的实际应用价值。要构造高效、收敛的遗传算法，必须充分运用已有的收敛性分析的研究成果，从算法结构、控制参数选择、遗传算子的操作方式等方面进行综合设计，其中还存在许多尚未解决的问题，如：如何利用遗传算法的收敛性构造合理的停机准则。

参考文献

[1] GOLDBERG D E. Genetic algorithm in Search， optimization and machine learning[M]. Reading， AddisonWesley，1989.

[2] MICHALEWICZ Z. Genetic Algorithms+Data Structure=Evolution Program[M]. 3rd edition. Berlin：Springer—Verlag，1996.

[3] BACK T，FORGEL D，Michalewicz Zeds. Handbooks of Evolutionary computation[M]. New York：Oxford university Press，1997.

[4] SANKAR K.Pal，Fellew and C.A.Murthy. GA for generation of class boundaries[J]. IEEE Trans on SMC-Part B：cybemetics，1998，28（6）：816-828.

[5] POTTS JC，et al. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial Selection[J]. IEEE Trans on SMC，1994，24（1）：73-86.

[6] 潘正君. 演化计算[M]. 北京：清华大学出版社，1998.

[7] 王岚. 基于自适应交叉和变异概率的遗传算法收敛性研究[J]. 云南师范大学学报，2010，30（3）：32-37.

[8] 明亮，王宇平. 关于一类遗传算法收敛速度的研究[J]. 计算数学，2007，29（1）：15-26.

[9] 应伟勤，李元香. 热力学遗传算法计算效率的改进[J]. 软件学报，2008，19（7）：1613-1622

[10]喻寿益，邝溯琼. 保留精英遗传算法收敛性和收敛速度的鞅方法分析[J]. 控制理论与应用，2010，27（7）：843-848.

[11]Xiao Fang Qi，FRARCESCO P. Theoretical Analysis of Evolutionary Algorithms with on Infinite Population Size in Continuous Space， Part I and PartII： Basic Properties of Selection and Mutation[J]. IEEE Trans on neural network， 1994，5 （1）：102-129.

[12]明亮. 遗传算法的模式理论及收敛理论[D]. 西安：西安电子科技大学博士学位论文，2006.

[13]曹建文. 遗传算法收敛性问题研究[J].中南林业科技大学学报，2008，28（3）：163-167.

[14]RUDOLPH G. Convergence Analysis of Canonical GA[J]. IEEE Trans on Neural Networks，1994，5（1）：96-101.

[15]陈国良. 遗传算法及其应用[M]. 北京：人民邮电出版社，1996.

[16]田小梅，龚静. 实数编码遗传算法的评述[J]. 湖南环境生物职业技术学院学报，2006，11（1）：25-31.

[17]YAO X. A Review of Evolutionary Artificial Neural Networks[J]. Int.J.Intelligent Systems， 1993，8（6）：539-567.

[18]CHIPPERFIELD A J. Multiobjective turbine engine controller design using GA[J]. IEEE trans. Int Electron，1996，4（3）：583-589.

[19]CARLOS M. Multiobjective optimization and multiple constraint handling with evolutionary algorithm[J]. IEEE Trans on SMC，1998，28（1）：26-34.

[20]GLOVFER F. GA and tabu search： hybrids for optimization[J]. Computer Ops. Res.1995，22（1）：111-134.

[21]肖宏峰，谭冠政. 基于单纯形的小生境混合遗传算法[J]. 小型微型计算机系统，2008，29（9）：1719-1725.

[22]KRISTISSON K，DUMENT G A. System identification and control using Genetic Algorithms[J]. IEEE Trans on SMC.1992，22（5）：1033-1046.

[23]FOGEL D.B. A comparison of evolutionary Programming and genetic algorithms on selected constrained Optimization Problems[J]. Simulation，1995， 64 （6）：397-406.

[24]HOMAIFER A，et al. Constrained Optimization Via Genetic Algorithms[J]. Simulation， 1994，62（4）：242-254.

[25]SRINIVAS M，PATNAIK LM. Adaptive Probabilities of Crossover and Mutation in GA[J]. IEEE Trans on SMC，1994，24（4）：656-667.

[26]张旭风，王纪川，牟莉. 并行遗传算法收敛性分析及优化[J]. 西安工程科技学院学报，2007，21（5）：657-660.

[27]朱筱蓉，张兴华. 基于小生境遗传算法的多峰函数全局优化研究[J]. 南京工业大学学报，2006，28（3）：39-43.