遗传算法中的变异算子的述评

沈 畅 乐 天

（浙江海洋学院数理与信息学院 浙江 舟山 316000）

0 引言

遗传算法于1969年由美国Michigan大学的Holland教授提出后，在保持其基本框架的基础上，许多学者提出了不同的改进方法，如自适应遗传算法、混沌遗传算法、量子遗传算法、混合遗传算法等。但算法的改进和问题本身相关，并且遗传算法的基础理论仍未根本解决，在进行算法改进时缺少理论的指导，所以改进的算法没有普遍的适用性。虽然遗传算法有自身的不足，但因其具有较强的鲁棒性，在如金融，自动控制，模式识别，组合优化，故障诊断等领域都有成功的应用。

在遗传算法中，变异算子通过模拟生物遗传和进化过程中的变异环节对个体进行变异，虽然发生变异的可能性比较的小，但也是产生新物种的一个不可忽视的原因[1]。通过变异不断在交叉算子产生的新个体的基础上进行微调、增加种群的多样性、使遗传算法在交叉算子决定的全局搜索能力的基础上还具有一定的局部搜索能力。变异算子被认为是必不可少的产生新个体的辅助方法，文献[2]认为变异算子能够成为一个重要的遗传算子，特别体现在维持种群的多样性问题上。正是变异算子在遗传算法中的不可或缺性，本文在总结相关文献资料的基础上，从不同角度对变异算子的改进进行讨论，并展望其发展方向，为遗传算法中变异算子的进一步发展提供参考。

1 变异算子的发展

简单遗传以初始种群为基点，经过选择、交叉、变异操作生成新的种群，如此更新种群直到满足终止条件。遗传算法中变异算子的具体操作是以变异概率Pm用新的基因值替代原有的基因值，产生新的个体。变异算子对个体编码串的基因做了局部的改变，维持种群的多样性，这样有利于防止出现早熟现象。

1.1 传统的变异算子

用遗传算法求解问题时，对于变异算子的选择首先会考虑已有的成熟的变异算子。几种常用的变异算子主要有基本位变异、均匀变异和高斯变异等。

1.1.1 基本位变异是指对个体的每一个基因座，依变异概率Pm指定其为变异点，对变异点的基因值进行反转或用其他等位基因值来代替。

1.1.2 均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率替换个体编码串中各个基因座上的原有基因值。

1.1.3 高斯变异操作是指进行变异操作时，用符合均值为μ、方差为σ的正态分布的一个随机数来替换原有基因值。

还有如边界变异、非均匀变异等等，这里不赘述了。可以看出变异算子的设计会涉及变异点位置的确定和基因值的替换两个方面。这两个问题的解决与编码及所解决的问题是密切联系的。上述的变异算子对多值编码都适用，但考虑问题的特殊性，变异算子又不能一概简单进行操作。如对TSP问题，若用数字代表城市，如用52134编码串表示5个城市的一种旅行路线。因问题本身要求城市不能重复出现，这使得变异时不能通过对基因座上的基因值进行替换来实现。出现了如倒位变异和交换变异等变异算子。倒位变异是指将随机选取的两个基因座之间的基因进行逆序排序。变换变异是指对于随机选取的基因座之间的基因值进行交换。

1.2 改进的变异算子

在成熟的传统变异算子的基础上不少学者做了大量的研究和探索，从理论，克服早熟现象和应用等方面提出了许多改进方法，有效提高遗传算法的性能。

1.2.1 变异算子在理论方面的研究

变异算子在理论方面的深入研究不多，文献[3]给出了基于模式定理的变异概率上限确定公式，由公式可知，可以通过选择适当的变异概率，使得某模式所含个体数目经过选择、交叉和单点变异等操作后得到增长。 文献[4]提出了基于位变异的模式遗传算法。直接把模式作为个体，使用的编码策略本质上比SGA的编码策略更加直接。并对其收敛性进行了分析。

1.2.2 变异算子在克服早熟现象上的改进

对变异算子的改进主要是针对遗传算法的局部搜索能力较弱及存在早熟现象，许多研究者提出了许多改进的方法，下面对此做个总结。

文献[5]提出基于细分变异算子的遗传算法。将变异算子细分为最优调教算子和大步前进算子两种算子的形式。文献[6]提出了一种新的改进遗传算法双变异算子遗传算法。通过将所有产生的子代个体与父代个体混合作为下一代种群，在种群选择前对适应度值较低的个体进行一次变异，然后通过选择、交叉，再一次变异产生新种群，再利用自适应算法改变交叉和变异率及最优保存策略保护历代最优个体，双变异算子的遗传算法能够最大限度使种群多样性，这样最有可能得到最优解，也易突破局部收敛的局限而达到全局最优。文献[7]提出了一种双变异率的改进遗传算法。在进化过程中，引入广义海明距离这个概念，当由广义海明距离控制的交叉操作产生个体数不足种群规模时，对原种群进行局部小变异，这样在避免近亲繁殖的同时又可扩大搜索空间，增加种群多样性，有效地抑制了早熟收敛；随后进行的全局大变异保证整个过程全局收敛。文献[8]提出了一种基于位变异的防止遗传算法过早收敛的算法。该算法通过种群熵来判断过早收敛的发生。当发生过早收敛时，在单调系数的指导下进行有针对性的位变异，从局部最优解的范围内摆脱出来，算法重新具有进化能力。文献[9]提出一种采用新的解码方案的动态变异遗传算法。文献[10]根据个体适应度不同对变异概率进行自适应调整，使群体中的优良模式不易被破坏，同时又保证了种群个体的多样性，从而提高了算法的搜索效率。算法中改变了交叉与变异的操作顺序，避免了个体适应度的重复计算，提高运行速度。文献[11]提出了一种将强制变异、最佳解保留和自适应交叉变异参数调整相结合的改进遗传算法。这种方法将进化过程中群体的平均适应度与最大适应度进行比较，以确定是否需要对群体实施强制变异或采用自适应交叉、变异概率调整。这种方法可有效地克服早熟现象，提高全局优化能力。

1.2.3 变异算子在TSP的改进

组合优化问题是遗传算法通常解决的应用问题，TSP是典型的组合优化问题，属于NP难问题。其变异算子的设计有其特殊性，有学者在这方面也做了相应的研究。

文献[12]通过分析TSP问题的特征，结合以减少周游路线中交叉边为启发式信息，引入了一个遗传算法中新的变异策略用于TSP求解。该变异策略能够引导算法通过有指导性的变异更快地收敛到更好的解。文献[13]也在遗传算法解决tsp问题中进行了改进。提出多步强化变异，其是在单步强化变异策略的基础上进行了改进，通过向前考察几步个体进化效果，将该信息向回传递，影响个体变异策略。

2 遗传算法中变异算子的未来研究方向展望

通过与遗传算法中变异算子相关的文献的整理，我们知道变异算子的改进有助于遗传算法性能的提高，在总结已有研究的基础上，提出以下几点未来研究方向：

2.1 加强遗传算法基础理论的研究

几乎对遗传算法中变异算子的改变都是从处理的实际问题出发的，这种改进对于处理其他问题的遗传算法是否有效值得商榷。这种改进还是受到遗传算法基础理论的薄弱的限制。从遗传算法的收敛性，早熟机理等方面从数学角度进行分析，剖析变异算子的作用机理，更好地改进变异算子。

2.2 变异算子与其他技术的结合

从上述的研究看，变异算子的改进还是集中在对算子本身的直接改进，可以借鉴其他算法特别是优化算法，与变异算子进行结合，提高变异算子对算法搜索性能的作用。

2.3 相关应用问题的拓宽

遗传算法应用领域比较广泛，对变异算子的改进主要应用于函数优化问题，今后可以探讨变异算子在不同问题中的改进方法。

3 结束语

遗传算法提供解决问题的基本框架，确实带来一定优势，但基本遗传算法的性能有待提高。可以从不同的角度进行遗传算法的改进，其改进的切入点不仅和所解决的问题相关，也和所使用的编码，遗传算子及相关的参数相关。本文从变异算子的角度介绍了对遗传算法的改进方法，加强了变异算子对传统遗传算法的作用，改善了算法的搜索效率，克服过早收敛的缺点，为今后的遗传算法的发展提供借鉴。

［1］周明，孙树栋，等.遗传算法原理及应用[M].北京：国防工业出版社，1999.

［2］Muehlenbein H.How genetic algorithms really work：mutation and hill climbing [C].In Proc，and Workshop Parallel Problem Solving from Nature，1992：15-25.

［3］巩敦卫，等.基于模式定理的遗传算法交叉和变异概率上限[J].控制与决策，2004，19(5)：554-556.

［4］张爱华.基于位变异的模式遗传算法[J].五邑大学学报，2009，23 (3)：32-36.

［5］王乾龙，等.基于细分变异算子策略的遗传算法[J].济南大学学报，2012，26(1)：15-19.

［6］鲁群，等.双变异算子遗传算法的应用 [J].计算机技术与发展，2008，18(7)：42-44.

［7］王杰，等.一种双变异率的改进遗传算法及其仿真研究[J].计算机工程与应用，2008，44(3)：57-59.

［8］万定生，等.基于位变异防止遗传算法过早收敛的算法[J].微电子学与计算机，2005，22(8)：117-120.

［9］郑磊，等.基于动态变异遗传算法的组播路由算法[J].计算机工程与应用，2005，31：141-143.

［10］刘德朋.基于变异概率自适应调整的逆序遗传算法研究[J].杭州电子工业学院学报，2004，24(1)：8-11.

［11］孔祥蕾，等.一种引入强制变异的改进遗传算法[J].中国科学院研究生院学报，2003，20(3)：317-320.

［12］张晓玲，等.用一种含启发式变异策略的遗传算法求解TSP[J].计算机应用与软件，2010，27(3)：237-240.

［13］刘菲，等.基于多步强化变异算子的混合遗传算法[J].计算机工程与应用，2011，47(29)：46-48.