引入进化梯度的改进小生境遗传算法

第２６卷第１　１期　２００６年１　１月　文章编号：１００１—９０８１（２００６）１１—２６５１—０３　计算机应用　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．２６　Ｎｏ．１　１　ＮＯＶ．２ｏ０６　引入进化梯度的改进小生境遗传算法　康钦建，李荣，周激流　（四川大学电子信息学院，四川成都６１００６４）　（ｋａｑｉｊｉ＠１６３．ＣＯ１ＴＩ）　摘　要：针对基本遗传算法易于早熟及局部寻优能力较差等不足，提出了一种引入进化梯度的改　进小生境混合遗传算法（ＧＮＧＡ）。利用进化梯度信息调整个体向更优解进化，并根据进化代数自适　应调整实数编码个体的交叉量和变异量，增强了局部寻优能力和解的精度。基于排挤的小生境算法　的引入，保持了种群的个体多样性以克服早熟。在Ｓｈｕｂｅｒｔ函数上的仿真结果表明，与小生境遗传算　法相比该算法能有效提高解的精度及收敛速度，找到更多最优解。　关键词：遗传算法；进化梯度；交叉量；变异量；小生境　中图分类号：ＴＰ１８　文献标识码：Ａ　Ａｎ　ａｄａｐｔｉｖｅ　ｎｉｃｈｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｂｙ　ｅｖｏｌｕｔｉｏｎ　ｇｒａｄｓ　ＫＡＮＧ　Ｑｉｎｇ—ｊｉａｎ，ＬＩ　Ｒｏｎｇ，ＺＨＯＵ　ｊｉ—ｌｉｕ　（Ｓｃｈｏｏｌ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，Ｓｉｃｈｕａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ　Ｓｉｃｈｕａｎ　６１００６４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎｄ　ｌｏｃａｌ　ｍｉｎｉｍａ　ｉｎ　ｓｉｍｐｌｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ（ＳＧＡ），ａｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｇｒａｄ－ｉｎｃｌｕｄｅｄ　ｎｉｃｈｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｉｒｔｈｍ（ＧＮＧＡ）Ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｉｎ　ｔｈｅ　ＧＮＧＡ，ｅｖｏｌｕｔｉｏｎａｒｙ　ｇｒａｄ　ｗａｓ　ｕｓｅｄ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ａｂｉｌｉｔｙ　ｏｆ　ｆｉｎｄｉｎｇ　ｔｈｅ　ｌｏｃａｌ　ｂｅｓｔ；ｔｈｅ　ｃｒｏｓｓｏｖｅｒ　ｖａｌｕｅ　ａｎｄ　ｍｕｔａｔｉｏｎ　ｖａｌｕｅ　ｗｅｒｅ　ａｄａｐｔｅｄ　ｄｙｎａｍｉｃａｌｌｙ　ｗｉｔｈ　ｔｈｅ　ｇｅｎｅｒａｔｉｏｎ　ｓｏ　ｔｈａｔ　ｔｈｅ　ｐｒｅｃｉｓｉｏｎ　ｗａｓ　ｉｍｐｒｏｖｅｄ；ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ　ｄｉｖｅｒｓｉｔｙ　ｗａｓ　ｇｕａｒａｎｔｅｅｄ　ｂｙ　ｔｈｅ　ｕｓｅ　ｏｆ　ｔｈｅ　ｎｉｃｈｅ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｃｒｏｗｄｉｎｇ　ｍｅｃｈａｎｉｓｍ．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｈａｓ　ｉｔｓ　ｓｕｐｅｒｉｏｒｉｔｙ　ｉｎ　ｐｒｅｃｉｓｉｏｎ　ａｎｄ　ｃｏｎｖｅｒｇｅｎｃｅ　ｒａｔｅ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ＳＧＡ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｍ；ｅｖｏｌｕｔｉｈｏｎ　ｇｒａｄ；ｃｒｏｓｓｏｖｅｒ　ｖａｌｕｅ；ｍｕｔａｔｉｏｎ　ｖａｌｕｅ；ｎｉｃｈｅ　遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＧＡ）是１９７５年由Ｈｏｌｌｎｄ提　ａ出的基于Ｄａｒｗｉｎ自然进化论和群体进化学说的一种启发式　全局随机搜索算法　。自提出以来，ＧＡ作为一种通用性好、　鲁棒性强的随机搜索优化算法，广泛应用于自动控制、图像处　理、组合优化、人工智能等领域。但在实际应用中，遗传算法　也暴露了一些自身固有的缺点：１）容易过早收敛到局部最　度量，　。和　是ｎ维向量。　显然ｄ４越小，Ｘ　与　，相似程度越大；反之亦然。若ｄ　＜　Ｌ（Ｌ为设定的一较小的正数），即它们属于同－ｄ，生境，则对　适应度较小者施加较强的惩罚函数Ｆ　＝Ｐｅｎａｌｔｙ。将小生境　算子溶人遗传算法中能克服在基本遗传算法后期，适应度高　的个体大量繁殖而充满整个群体，造成早熟的不足，保证了种　群的多样性及对整个解空间的搜索。　１．２编码及进化梯度　优；２）局部寻优能力差，求解精度不高。近年来，许多文献针　对遗传算法的缺陷提出了各种改进方法，如引入爬山法、模拟　退火法　Ｊ、自适应遗传算法、小生境遗传算法　Ｊ、实数编码遗　传算法　Ｊ，并获得了性能上的一定改善。　因为实数编码具有复杂度低，执行效率高等优点，本文采　与其他优化的遗传算法不同，本文提出的引入进化梯度　的小生境改进遗传算法能同时提高局部搜索能力和克服早　熟。利用小生境算法很强的把握整个搜索空间的能力与遗传　算法的优势互补来克服早熟。进化梯度为每个个体标记进化　方向，按标记的进化方向继续局部寻优，会进一步提高解的精　度，加快收敛速度。　用实数编码。个体编码串中包含决策变量和进化梯度向量，个　体的编码方案为：　Ｇ　ｒ——　——．、广——　——．、　ｌ，　２，…，　＾・ｇｌ，ｇ２，…，　其中　［Ｍｋ，　］为目标函数的第　个决策变量；Ｇ＝　［ｇ。，ｇ　，…，ｇ　］是进化梯度向量。在遗传操作中ｇ。是不参与　交叉和变异的。　传统的基于微分的寻优方法依赖于目标函数的梯度信　１　ＧＮＧＡ算法策略　１．１小生境算子　息，通过按梯度所指方向移动寻找最优解。该方法中目标函数　，（　）的ｎ维梯度向量由下式给出：　本文使用的基于排挤的小生境算法＿６　的基本思想是：依　据个体之间的相似性将种群分为若干个小生境，并排挤掉同　ｄ＇生境中的较差个体，这样各小生境中的最优个体便可以　－ｖＡｘ）＝（、　　ｌＯｘ，　　Ｏｘ，…，，　　Ｏｘ），　就能得到　）的极小值。即：　Ｘ　＝Ｘ一８・ｖｆ（　）　（１）　（２）　认为是局部最优解邻域内的一点。个体之间的相似性用编码　，＿　————————一　该向量始终指向最快增长方向。因此，朝相反方向移动　串之间的海明距离ｄ　＝ｌ　ｌＸ。一　ｌｌ＝√∑（　一　）　来　收稿日期：２００６—０５—２７；修订日期：２００６—０７—１７　作者简介：康钦建（１９７６一），男，四川安岳人，硕士研究生，主要研究方向：人工智能、图像处理；李荣（１７６一），９男，四川广元人，硕士研究生，主要　研究方向：＾工智能、信号处理；周激流（１９６３一），男。四川威远人，教授，博士生导师，主要研究方向：图像图形处理、模式识别、＾工智能．　维普资讯 http://www.cqvip.com

２６５２　６是一足够小的正实数。　计算机应用　ｐｌ擀“　２００６皇　受传统梯度概念的启发，在遗传算法中引入进化梯度的　概念。它指目标函数最快增长时个体进化的方向。因此，若知　一　道个体的进化梯度向量Ｇ，则有目标函数　Ｘ一６・Ｇ）＜　—　＋一　＋　．巡　一　一艿　Ｐ　＝Ｆ（Ｘ　）／∑Ｆ（　）　＝（８）　０　本文提出的算法流程如图１所示。　ｌ开始．选择算法运行参数ｌ　ｔ　艿厂（　），对于求最小值的优化问题，有适应度函数：　ｌ随机产生＾价初始个体，ｔ＝０　Ｉ　（３）　●　Ｆ（Ｘ一６・Ｇ）＞Ｆ（Ｘ）　但是在实际应用中，目标函数的梯度信息往往不能用解　一一　一　析式表达。因此，为了数值计算简便，目标函数的一阶偏微分　一　ｌ计算、评价各个体并记录前Ⅳ个个体ｌ　ｌ　ｔ　可由下式近似计算：　～　＋０（　）　（４）　Ｐ　是第ｉ个值为１，其余值为０的ｎ维向量。所以得到第ｉ　个基因的梯度值以及梯度向量：　：　，Ｇ：ｖＡｘ）　（５）　ＯＸｉ　对群体中每个小生境的最优个体进行基于进化梯度的局　部寻优，就能使这一局部最优邻域的点向局部最优进化。其　具体过程如下：　ｗｈｉｌｅ　Ｆ（Ｘ　）＞Ｆ（Ｘ）　Ｘ＝Ｘ　；　Ｘ　＝Ｘ一６‘Ｇ＝　１—６。ｇ１，…，　一６・ｇ　２　改进的遗传算子　２．１　交叉算子　交叉操作的作用是组合出新的个体，在变量空间进行有　效的搜索。启发式交叉算子　能保证交叉后，一点落于进行　交叉的两父代之间，另一点落于靠近较好父代的一侧，使解向　较好的方向发展。而自适应交叉系数　使交叉量随进化代数　的增大而减小。把二者结合起来提出了改进的自适应非均匀　算术交叉算子。在该算子中，首先比较个体　与置的适应度　值，在此不妨设Ｆ（　）＞Ｆ（　，），交叉后的结果为：　（６）　＝ｘ　＋　其中，　：ｆＬ～　・（　‘（Ⅳ＾一　　），一　　ｉ），　ｆｘ≤　ａ＞　，△　：，。。　　．　（　一　），　＝ｅｘｐ（一　∥　），％为一预定系数，ｔ为当前进　化代数，　为最大进化代数。当Ｆ（Ｘｉ）＜Ｆ（　）时，有类似的　交叉结果。可见绝对交叉量Ｉ　Ｉ和Ｉ　Ｉ随进化代数ｔ的增　加而减小。　２．２　变异算子　本文采用固定变异概率Ｐ　，自适应变异量的非一致变异　算子　。决策变量　的变异结果由下式决定：　，　＝｛：　Ｌ　　△（‘，Ⅳ＾一　），　“ｄ。ｍ（０，　）＝０（７）ｌ，）　　一△（ｔ，　一Ｍｋ），ｉｆ　ｒａｎｄｏｍ（０，１）＝１　式中，△（ｔ，Ｙ）＝Ｙ・ｆ　１一ｒ　１，ｒ为［０，１］上均匀分　布的随机数。可见遗传算法在初始阶段进行近似均匀随机搜　索，在后期，随进化代数ｔ的增加变异量△（ｔ，Ｙ）减小，算法将　重点搜索原个体附近的微小区域。　２．３　选择算子　由于在小生境算子里对个体的适应度进行了调整，利用　轮盘赌的选择算子能达到择优且较优个体又不会充斥群体的　目的。每个个体的选择概率为：　＜　》　圃　Ｎ●　ｌ　ｔ＋＋，执行ＧＡ的选择、交叉、变异操作ｌ　●　Ｊ将种群　和记录的Ⅳ个个体合并为　＋｜＾，个个体　●　ｌ小生境运算，并得到各小生境最优个体的进化梯度　●　ｌ各个体按梯度局部寻优Ｉ　●　Ｉ计算、评价　＋Ⅳ个个体，按适应度降Ｉ　Ｉ序排列，并分别记录前Ｍ和前Ⅳ个个体ｌ　图１　ＧＨＧＡ算法流程　３实验及结果　本文利用Ｖｃ＋＋语言在Ｐｃ上仿真，将ＧＮＧＡ算法应用　于著名的Ｓｈｕｂｅ￣函数，并将它与小生境遗传算法（Ｎｉｃｈｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＮＧＡ）的结果作比较，验证了ＧＮＧＡ算法在　保持个体多样性、克服早熟和局部寻优上有较优的能力。　Ｓｈｕｂｅａ函数数学表述为：　ｆＩ　ｍｉｎ　ｚ：）＝｛∑ｉ．ｃ０ｓ［（ｉ＋１）　＋ｆ］｝×　１【　｛∑ｉ．ｃ０ｓ［（ｉ＋１）　：＋　］｝　ｓ．Ｉ．＿１０　≤１　ｆ－１，２）　该函数有７６０个局部最优点，其中１８个是全局最优点。全　局最优点处函数值是Ｌ（　，　：）＝一１８６．７３０９０８８３。其三维　图如图２所示。　３ｏｏ　２ｏｏ　ｌｏｏ　０　一ｌｏｏ　－２ｏｏ　１０　１０　图２　Ｓｈｕｂｅ￣函数的三维图　本实验中所使用的运行参数如下：种群规模Ｍ＝１２０，记录　优秀个体数Ｎ＝４５，最大进化代数Ｔ＝５００，交叉概率Ｐ　＝Ｑ　８，变　异概率Ｐ　＝Ｑ　１，海明距离下限￡＝０．４，罚函数Ｐｅｎａｌｔｙ＝１０　，　自适应交叉参数　＝４０．０，进化梯度占＝１０　。　先使用上述参数进行ＮＧＡ运算，运行到７０代左右可以　收敛到１８个最优点附近，此时１８个最优点的平均值在　一１８６．７；Ｅ右，到９０代时，其平均值在一１８６．７３０９左右，可以　认为已经收敛。ＮＧＡ算法找到所有１８个全局最优解。　保持上述参数不变，使用本文的ＧＮＧＡ算法来进行仿　真，收敛得比ＮＧＡ更快。运行到第３ｏ代左右就可以收敛到　１８个最优点附近。到４０代时，其平均值在一１８６．７３０９左右，　可以认为已经收敛。图３、图４绘出了两种算法在最优个体　和全局收敛性能随进化代数ｔ变化的直观比较图。从图３可　维普资讯 http://www.cqvip.com

第１１期　康钦建等：引入进化梯度的改进小生境遗传算法　２６５３　以看出，ＧＮＧＡ只要１０代左右就能找到至少一个全局最优　皿　用本文的ＧＮＧＡ算法找到的１８个全局最优如表１所示。　点，而ＮＧＡ则需要６０代左右。从图４可以看出，ＧＮＧＡ种群　收敛速度比ＧＮＡ更快。　表１　１８个全局最优解　遥　斗　●●Ｏ　ＯＯ　Ｏ●ＯＯ　Ｏ　Ｏ●Ｏ　Ｏ　Ｏ　ＯＯ　Ｏ　Ｏ　ＯＯ　Ｏ　Ｏ　ＯＯ　Ｏ●ＯＯ　Ｏ　Ｏ●进化代数ｔ　图４种群平均值收敛曲线　４　结语　遗传算法具有搜索空间整体把握能力强的优点；小生境　能保持群体的多样性，寻找到更多的最优解；进化梯度能在决　策变量的一定领域内使个体更优，具有很强的局部搜索能力。　本文提出的标记进化梯度的改进小生境遗传算法融合了三种　Ｏ　Ｏ●Ｏ　Ｏ　Ｏ　ＯＯＯ　Ｏ　Ｏ●策略，充分利用它们的优点，克服了遗传算法种群早熟和局部　搜索能力差的缺点。通过典型多峰值函数的仿真实验，证明　了该算法有效地维持了种群的多样性，局部搜索能力及解的　精度得到提高，且参数的选择不必过分严格，是一种有效可靠　的多峰值优化算法。　参考文献：　【１】ＨＯＬＬＡＮＤ　ＪＨ．Ａｄａｐｔａｔｉｏｎ　ｉｎ　Ｎａｔｕｒａｌ　ａｎｄ　Ａｒｔｉｉｆｃｉａｌ　Ｓｙｓｔｅｍｓ【Ｍ】．　Ａｎｎ　Ａｒｂｏｒ：Ｔｈｅ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｍｉｃｈｉｇａｎ　Ｐｒｅｓｓ，１９７５．　Ｏ　Ｏ　Ｏ　ＯＯ　Ｏ　Ｏ　ＯＯ　Ｏ　Ｏ　ＯＯ　Ｏ　１　１Ｏ　Ｏ　Ｏ　Ｏ【２】　冯毅，李利，高艳明，等．一种基于小生境的混合遗传退火算　法【Ｊ】．机械科学与技术，２００４，２３（１２）：１４９４—１４９８．　【３】　黄聪明，陈湘秀．小生境遗传算法的改进【Ｊ】．北京理工大学学　报，２００４，２４（８）：６７５－６７８．　进化代数ｔ　【４】　田小梅，龚静．实数编码遗传算法的评述【Ｊ】．湖南环境生物职　业技术学院学报，２００５，１１（１）：２５—３１．　【５】　董颖，刘欢杰．一种基于实数编码的改进遗传算法【Ｊ】．东北大　学学报，２００５，２６（４）：１１９－２２１．　【６】　周丽，孙树栋．遗传算法原理及应用【Ｍ】．北京：国防工业出版　社，２００１．　Ｏ　Ｏ　Ｏ　ＯＯ　Ｏ　Ｏ　ＯＯ　Ｏ　１　１Ｏ　Ｏ　Ｏ　Ｏ图３种群最优个体收敛曲线　Ｏ　Ｏ　Ｏ　Ｏ（上接第２６４４页）　０　０－１　０１　０－１　０　０　ｌ　０　０　１　０　０　Ａ＝　ＬＡ：　０　１　Ｉ　０　０　１　０　０　１　　ｌ０　ｌ　０　１　０　０　０　ｌ　０　１　０　０　ｌ　ＬＡ：　ｌ　Ｉ　１　０　１　Ｊ　ｌ　０　１　０　０　ＬＡ：　ｌ　１　０　１　００　１Ｊ　完工时间Ｍａｋｅｓｐａｎ＝３９．７５＜４２。　ｉｎｇ　Ｕｎｒｅｌａｔｅｄ　Ｍａｃｈｉｎｅｓ　ｂｙ　【２】　ＳＣＨＵＬＺ　ＡＳ，ＳＫＵＴＥＬＬＡ　Ｍ．Ｓｃｈｅｄｕｌ５　结语　通过以上实例说明，采用极大利用机器加工能力和均衡　Ｒａｎｄｏｍｉｚｅｄ　Ｒｏｕｎｄｉｎｇ［Ｊ】．Ｓｏｃｉｅｔｙ　ｆｏｒ　Ｉｎｄｕｓｔｒｉａｌ　ａｎｄ　Ａｐｐｌｉｅｄ　Ｍａｔｈｅ—　ｍａｔｉｃｓ，２００２，１５（４）：４５０—４６９．　【３】　唐国春，张峰，罗守成，等．现代排序论【Ｍ】．上海：上海科学普及　机器负荷的混合策略对机器进行调度，具有一定的有效性和　优化效果。但对于很多复杂情况，尚不能给出完善的结果。　参考文献：　【１】ＡＤＡＭＳ　Ｊ＇ＢＡＬＡＳ　Ｅ，ＺＡＷＡＣＫ　Ｄ．　Ｓｈｉｆｔｉｎｇ　Ｂｏｔｔｌｅｎｅｃｋ　Ｐｒ∞ｅｃｈ　ｆｏｒ　Ｊｏｂ－Ｓｈ￣Ｓ￣ｔｕｌｉｇＩＪ］．ｈ１ｎ日ｍ８ｅＩＩｌｅｒ吐Ｓｄｅｎｃｅｓ，Ｎ６８，３４（３）：３９１—４ｏ１．　出版社，２００３．　【４】　刘志雄，王少梅基于混合进化策略算法的并行多机调度问题研究　【Ｊ】＿武汉理工大学学报（交通科学与工程版），２Ｏ０５，２９（４）：５７１—５７４．　【５】　王磊，黄文奇．求解工件车间调度问题的一种新的邻域搜索算法　【Ｊ】．计算机学报，２００５，２８（５）：８０９—８１６．