一种改进操作算子的加速收敛遗传算法

邓洋春　梁昔明

摘 要：针对基本遗传算法效率低和易早熟的缺陷，提出了一种改进操作算子的遗传算法。该算法在种群初始化、选择、交叉、变异等基本算子的基础上加以改进，使算法具有更好的适应性。对3组不同函数的测试表明，改进算法较传统的遗传算法具有在种群很小的情况下收敛速度快稳定性高的优点，同时能有效地避免早熟现象。

关键词：遗传算法；变异；收敛速度；种群数

中图分类号：TP391文献标识码：B

文章编号：1004 373X(2009)02 139 03

Accelerating Convergency Genetic Algorithm of Improved Operator

DENG Yangchun,LIANG Ximing

(College of Information Science and Engineering,Central South University,Changsha,410083,China)

Abstract：To overcome low performance and premature convergence of simple Genetic Algorithm(GA),an improved operator genetic algotithm is proposed.It improves the operators such as initialization,selection,crossover and mutation,which make the algorithm more adaptive.The 3 groups of experiments show that improved algorithm has a quick speed convergence and more stable than simple GA,and also can efficiently avoid premature convergence.

Keywords：genetic algorithm;mutation;convergence speed;population size

0 引 言

遗传算法(Genetic Algorithm,GA)是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程，从一个初始种群出发，不断重复执行选择，杂交和变异的过程，使种群进化越来越接近某一目标。它通过模拟达尔文“优胜劣汰，适者生存”的原理激励好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。经典遗传算法的求解步骤为：初始化种群；选择；交叉；变异；判断终止条件。由于它简单有效，具有很强的鲁棒性和通用性，所以被广泛应用于模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等多种领域［1］。

早熟和收敛时间过长是影响遗传算法效率的两个主要因素，而选择压力过大是导致早熟收敛的一个重要原因［2］，为此不少学者对遗传算法做了改进［3－5］，但仍存在一定局限性。在此对遗传算法个操作算子加以改进，通过对经典多极值测试函数的仿真研究表明，改进后的算法能够有效避免早熟且在种群规模较小的情况下具有较快的收敛速度。

1 改进操作算子的遗传算法

经典遗传算法的把变异作为一种辅助手段，认为变异只是一个背景机制，这一观点与生物学中的实际观察是相符的，但作为设计人工求解问题方法的思想，他正受到理论与实践两方面的挑战［6］。另外，从微观角度来讲，变异随时都有可能发生，如果突变向不好的方向进行，其“修复系统”立刻就能对其进行修复。基于以上两点，这里在选择与交叉算子中渗入不同的变异行为，且动态改进变异算子，使算法能快速达到全局最优。

1.1 初始化

为了改善初始群体的效能，提高模式的优良度，采取如下方法：先随机产生一个父染色体，对其进行一定次数(20次左右)的逐位精英选择高频变异，方法如下：例如染色体为01001，先把第一位变异为1，成为11001，若适应度提高，则此位以很大的概率p(如0.98)转换为1，否则以很小的概率(如0.01)转换为1，以此类推。接着产生具有一定规模的染色体种群，随机使其中每个染色体的某段基因与之前父染色体相应基因段保持一致。如：假设父染色体为00110，随机产生个体10101，若以第一和第二位基因与父染色体一致，则该个体变为：00101。该方法把较优秀的模式分散到各个染色体中，使它一开始就具有一定概率的优秀短模式，从而有效提高算法的寻优效率。

1.2 选择操作

经典遗传算法根据适者生存原则选择下一代个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

然而基于适应度的概率选择机制如轮盘赌选择法在种群中出现个别或极少数适应度相当高的个体时，就可能导致这些个体在群体中迅速繁殖，经过少数迭代后占满了种群的位置。这样，遗传算法的求解过程就结束了，也即收敛了。但这样很有可能使收敛到局部最优解，即出现早熟现象［1］。为了从根本上避免早熟现象且加快收敛速度，采用基于高频精英变异的锦标赛选择法。其操作如下：假设竞赛规模为2，首先选取种群中第1和第2个个体X和Y

如：X=100101，Y=011110

从第1位开始比较适应值的大小，即当个体X与Y的第1位分别是1和0时，假设fitness(X)＞ fitness(Y)，于是把Y的第1位由0高频变异为1，此时：

X=110101，Y=101110

此时，若fitness(X)＜ fitness(Y)，则把Y的第1位由1高频变异为0。如此下去，最终得到的为选择出的个体，其中较高位(如第1至L/3位，其中L为染色体长度)变异率为0.8，其他位变异率为0.95，理由是较高位的个体即使适应度低也有可能在附近变异成适应度更高的个体。

然后选取种群中第2和第3个个体应用上法选择出第2个个体，这个过程重复进行，完成剩余个体的选择。这种算子在选择个体上就可以有方向性且极大地加快算法的收敛速度。

1.3 交叉操作

交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作，从而在下一代产生新的个体。它的目的是开发问题解空间中新的区域，寻找父个体已有的但未能合理组合的基因，尽量保证具有优良模式的个体不被交叉操作所完全破坏，同时增大种群的离散程度，产生新的搜索空间。所有交叉操作的一个共同特征是，不破坏两个父个体之间的公共串模式，允许继续搜索空间时保留好的模式［2］。

对于选中用于繁殖下一代的个体，随机地选择2个个体的相同位置，按交叉概率P在选中的位置实行交换。在选中的位置实行交换［1］。这个过程反映了随机信息交换，目的在于产生新的基因组合，也即产生新的个体。在交叉时，可实行单点交叉或多点交叉。

一点交叉是经典的交叉方法，它是对于给定的两个父个体，随机地选取1个交叉位置，然后相互交换两个个体交叉位置右边部分基因，形成2个子代，一点交叉能够搜索到的空间十分有限。多点交叉的破坏性可以促进解空间的搜索，而不是促进过早地收敛，因此搜索更加健壮［1］。这里在采取多点交叉的同时考虑父个体间的多样度。

当两个父个体的汉明距离较低，可能导致交叉操作无效。另外，由于交叉点随机产生，可能会导致交叉后新个体无变化，例如，两父个体分别为01100101和01011010，如果交叉点取值为第2位，则交叉后的两个新个体与父个体相同，交叉操作无效。在此采取交叉概率与汉明距离成正比的策略：两父体相似度高时交叉概率减小以避免无效操作，一旦在这种情况下进行交叉，首先保持具有高适应度的父个体不变，然后对低适应度个体或者交叉点左右具有相同子串的个体采取变异操作以增大它们之间的汉明距离，从而提高交叉操作的有效性。

1.4 变异操作

根据生物遗传中基因变异的原理，以变异概率P璵对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。

单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

这里提出一种自适应快速收敛变异法：对每一个体采取从高位到低位逐位变异的策略。在寻优的早期主要是全局搜索，此时各变量二进制的高位应采用高变异率，低位采用低变异率。在寻优过程中不断调整各位的变异率，即高位变异率逐渐降低，低位变异率逐渐增加。到寻优后期，主要是局部优化，全局优化次之，此时各位变异率与早期相反，即低位变异率要比高位变异率大。在变异过程中采用概率精英保留策略，也就是每位变异后若适应值增加，则以高概率保留，否则放弃此位变异。实验证明，这种变异策略在种群规模较小的情况下能获得较满意的进化能力。

2 算法描述

算法描述为：

(1) 采用二进制编码，随机产生一个体，通过逐位高频精英变异，提高其适应度；

(2) 利用上述较优父染色体产生产生种群；

(3) 进行基于高频精英变异的锦标赛选择；

(4) 进行改进的交叉运算；

(5) 进行自适应变异运算；

(6) 是否到最大的遗传代数，如果达到，结束；否则转到步骤(3)。

3 仿真试验及结果分析

3.1 试验

为验证改进算法的效率，用经典遗传算法SGA和文中的加速收敛改进遗传算法相比较，其中SGA采用的遗传操作及相应参数为比例选择、单点交叉(交叉概率0.85)及基本位变异(变异概率0.05)，种群规模为100，进化代数为100。两者都采用保留个体精英的方法。选择如下3个算例进行仿真计算。

(1) Camel函数

f1(x,y)=(4-2.1x2+x4/3)x2+xy+(4y2-4)y2

此函数有6个极小点，其中有2个(-0.089 8,0.712 6)和(0.089 8,-0.712 6)为全局最小点，最小值为-1.031 628，自变量的取值范围为 -100＜x,y＜100。

(2) Shubert函数

f2(x,y)=∑5i=1icos［(i+1)x+1·

∑5i=1icos［(i+1)y+1+

0.5［(x+1.425 13)2+(y+0.800 32)2］

该函数有760个局部极小点，其中只有1个(-1.425 13,-0.800 32)为全局最小，最小值为186.730 9。自变量取值范围 -10＜x,y＜10。此函数极易陷入局部极小值186.34。

(3) Schaffer函数

f3(x,y) = 0.5-sin2x2+y2-0.52

该函数有无限个局部极大点，其中只有一个(0,0)为全局最大，最大值为1。自变量的取值范围为-100＜x,y＜100。该函数最大值峰周围有一个圈脊，它们的取值均为0.990 283，因此很容易停滞在局部极大值。

改进后算法的种群规模为20，进化代数为60。对两种算法进行100次随机仿真，试验结果如表1所示。

表1 试验结果

函数

SGA 最好解 最差解平均收敛代数 成功率%改进后遗传算法最好解最差解平均收敛代数成功率%

f1-1.031 628-1.031 6278177-1.031 628-1.031 62848100

f2186.730 9186.725 88773186.730 9186.730 75291

f311.000 02636871111100

3.2 结果分析

从以上结果可以看出，SGA容易早熟收敛，而改进后的算法能很好地摆脱早熟，并能以很高的成功概率快速搜索到最优值。从各参数也可以看出，改进后的遗传算法在种群规模很小的情况下也具有很高的寻优效率。因此，这里提出的改进算子GA从全局收敛概率和平均进

化代数来看，是成功的，它具有高效的全局以及局部搜索能力。

4 结 语

通过对算法各算子的改进，较好地解决了一般遗传算法收敛速度慢和全局寻优能力弱的缺点。实践表明，改进GA和标准GA相比，在花费更少的情况下具有更快的收敛速度和精度。

参考文献

［1］王小平,曹立明.遗传算法——理论,应用与软件实现.西安:西安交通大学出版社,2002.

［2］王忠,柴贺军,刘浩吾.关于遗传算法的几点改进［J］.电子科技大学学报,2002,31(1):76－80.

［3］熊范伦,邓超.退火遗传算法及其应用［J］.生物数学学报,2000,15(2):150－154.

［4］张毅,杨秀霞.一种基于能量熵的快速遗传算法研究［J］.系统工程理论与实践,2005(2):123－128.

［5］金朝红.一种基于自适应遗传算法的神经网络学习算法［J］.微计算机信息,2005,10(1):49－51.

［6］张文修,梁怡.遗传算法的数学基础［M］.西安:西安交通大学出版社,2003.

［7］Qi Xiaofeng.Theoretical Analysis of Evolutionary Algorithms With an Infinite Population Size in Continuous Space Part II:Analysis of the Diversification Role of Crossover［J］.IEEE Transactions on Neural Networks,1994,5(1):120－129.

［8］陶林波.一种解决早熟收敛的自适应遗传算法设计［J］.微计算机信息,2006,12(1):268－270.

［9］Introduction to Genetic Algorithms.http://www.rennard.org/alife/english/gavintrgb.html.

［10］Genetic Algorithm－Traveller in Space.http://arc.net.cn/wiki/pmwiki.php/R/GeneticAlgorithm.

［11］桂超,汪波.基于遗传算法的最短路径路由优化算法［J］.微计算机信息,2005,12(2):193－195.

作者简介

邓洋春 男，1983年出生，江西南昌人，硕士研究生。主要研究方向为智能算法，Java技术。

梁昔明 男，1967年出生，博士，教授，博士生导师。主要研究方向为过程控制与系统优化、进化计算与人工生命。