ＥＬＥＣＴＲＯＮＩＣＳ ＷＯＲＬＤ・技术交流 混合遗传算法综述 贵州１大学电气工程学院张先炼 中国水电顾问集团正安开发有限公司 王国杰 【摘要】遗传算法是在生物进化上面兴起的算法，它的应用范围广，但由于自身有不足之处，如早熟收敛等，则需对算法 的收敛速度及搜索能力等问题进行处理。本文对遗传算法的基本思想、操作步骤及主要特点，以及存在的问题进行了讨 论，介绍了几种混合遗传算法，对于其基本原理，特点及研究方向进行了概述。 【关键词】遗传算法；混合遗传算法；收敛；搜索 １．引言 遗传算法起源于达尔文“进化论”，借鉴生物界的 进化规律而来的全局搜索算法，对此，我们需要了解相 关知识，比如：种群、个体、基因、染色体、遗传与变 异等问题，在进化论中，繁殖过程，会发生基因交叉， 突变的基因，一些低适应度个体逐渐消失，然而高适应 度个体将会更多［１Ｉ引。对于遗传算法的应用，主要是在 一些图像处理、神经网络进化、组合优化等方面，但单 独的遗传算法存在很多缺点，比如局部搜索的能力弱和 未成熟收敛等等，最终导致很难快速找到最优解［。．４］。 对于遗传算法的诸多缺点，相关人士有了对应的方案去 解决，也就是把遗传算法和其他算法综合后为混合遗传 算法。本文所提到的模拟退火遗传算法、量子遗传算法 等等，用来弥补遗传算法某些不足之处。 ２遗传算法 ２．１遗传算法基本思想【 ．５】 遗传算法是一种随机搜索的算法，在遗传机理与 生物自然选择基础上发展而来的算法，能ｐ，Ｚ很好的解决最 优问题。其基本思想是：开始是初始种群的产生，然后 对于那些选中的染色体进行交叉、变异等操作后产生后 代，然后计算适应度值来选择符合条件的后代，对于不 符合条件的后代进行淘汰。经过若干代遗传后，该算法 会最终收敛于条件最好的染色体，也就能得到最优解。 ２．２遗传算法实现步骤 一般遗传算法实现步骤［１Ｉ ｓ］： 编码方式的选择一初始种群产生一计算适应度及 排序一若不满足（选择一交叉一变异一对适应度值计算） 等。如图１所示。 ・１２０・电子心界 图１遗传算法的流程圈 ３混合遗传算法 针对一般遗传算法的局部最优陷入、未成熟的收 敛、收敛速度慢等，只用简单的遗传算法是达不到的， 那么我们可对遗传算法作恰当的改进或者将与其它搜索 算法综合为混合遗传算法来解决这些问题。对于那些应 用广泛的混合遗传算法概述如下： ３．１模拟退火遗传算法【７－８】 基本思想：模拟退火算法主要运用在很大的可搜寻 的空间中找问题最优解。对于模拟退火，在这个大的搜 寻空间中，把它的每一个点都看成是空气中的分子；分 子的能量，就是它本身的动能；然而对于大的搜寻空间 中的每一个点，同样类似空气分子那样具有 “能量”， 该算法的开始是以这个大的搜索空间里的一个任意的 点，每次都要预先选择相应的“邻居”，之后看看在当 前位置到相应的“邻居”的概率问题。 研究方向：函数的最小值问题及ＴＳＰ问题；选择设 ＥＬＥＣＴＲＯＮＩＣＳ ＷＯＲＬＤ・技术交流 计合适退火温度来调整整个搜索的进程：对于相关应用问 题，选择获取适当的适应度函数；可以和一些优化算法综 合，比如模糊控制，在更大的范围内体现应用其优点等。 ３．２小生境遗传算法［５ｌ９】 基本思想：小生境遗传算法是把每一代的个体划分 成很多类，在此基础上，选出那些每类中适应度更大的 一些个体，最后将它们构成一个对应的群体，之后在特 定的种群中和一些不同种群中经过特殊的交叉、变异等 来得到新的一代。 研究方向：由于小生境遗传算法多样性的解，收敛 速度及全局寻优等优点，主要针对的是那些复杂多封峰 函数的优化问题的研究。 ３．３混沌遗传算 加・”】 基本思想：混沌遗传算法是在遗传算法总的变量群 体中添加混沌变量，添加混沌变量是因为它针对子一代 的群体所进行的轻微干扰以及跟着这个过程的进行慢慢 调节相应的幅度。再由基本遗传算法的 “适者生存”规 则，需要对应的选择、交叉、变异，之后对于混沌变量 再添加一个小小的混沌扰动，通过后面的不断进化，最 终在一个最优的环境下收敛从而得到相关问题的最优解 问题。 研究方向：可以通过其遍历性来进行初始种群的产 生和变异的操作，能对一般遗传算法进化的代数得以降 低，最优解就能很快寻找到，混沌遗传算法可以有效避免 一些早熟及局部收敛等问题。全局的寻优能力通过混沌遗 传算法得以很大的提高。最终表明，混沌遗传算法可以显 著提高计算效率，对于数据的冗余可以相应降低，种群 多样性也可以得到保持，具有较大的实用价值。 ３．４量子遗传算法［１ ２］ 基本思想：基于量子计算原理，利用量子叠加态、 量子比特的理论和概念，染色体是量子位编码表征， 对 于进化搜索的完成是通过量子门更新和量子门作用。量 子遗传算法通过量子门来实现染色体的演化，将量子的 态矢量引入染色体的编码。量子遗传算法有更好的收敛 速度和搜索能力，以及种群多样性等。 研究方向：对于重大挑战问题的算法设计、算法收 敛性分析、量子遗传算法的计算复杂性、建立量子遗传 算法机理分析的数学模型等研究。 ４结语 遗传算法是生物界的进化规律演化而得来，它不论 是在应用上，算法设计上，还是在基础理论上，均取得 了一定的发展，诸多领域都有一定应用价值，针对它还 存在的一些问题和不足，以后将出现更好的方法理论运 用其中。通过一些其他算法加上遗传算法综合的方式应 用，遗传算法将会走得更远。 参考文献 ［１】马永，贾俊芳．遗传算法研究综述卟山西大同大学学 报，２００７，２３（３）． ［２】吴玫，陆金桂．遗传算法的研究进展综述Ⅱ１＿机床与液 压，２００８，３６（３）． 【３】葛继科，邱玉辉．遗传算法研究综述Ⅱ】＿计算机应用研 究，２００８，２５（１０）． 【４］吉根林．遗传算法研究综述Ｕ］．计算机应用与软 件，２００４，２１（２）． 【５】杜永贵，石洪献．混合遗传算法的研究现状卟科技情 报开发与经济，２００６，１６（１０）． ［６］吴强．蚁群混合遗传算法的研究及应用【Ｄ】．包头：内 蒙古科技大学，２０１１：３—８． ［７】武兆慧，张桂娟，刘希玉．基于模拟退火遗传算法的 关联规则挖掘Ⅱ】．计算机应用，２００５，２５（５）． 【８】田东平，迟洪钦．混合遗传算法与模拟退火Ⅱ］．计算机 工程与应用．２００６．２２． ［９】黄聪明，陈湘秀．小生境遗传算法的改进Ⅱ］．北京理工 大学学报，２００４，２４（８）． ［１０】姚俊峰，梅炽澎小奇．混沌遗传算法（ｃＧＡ）的应用 研究及其优化效率评价Ⅱ】＿自动化学报，２００２，２８（６）． ［１１】王芳．混沌遗传算法研究及其在地震子波提取中 的应用［Ｄ】．北京：中国石油大学，２０１０：５—６． ［１２］周露芳，古乐野．基于量子遗传算法的二位最大熵 图像分割Ⅱ】．计算机应用，２００５，２５（８）． 作者简介： 张先炼（１９９３一），男，贵州遵义人，硕士研究 生，贵州大学电气工程学院检测技术与自动化装置专 业，主要研究方向：嵌入式系统与自动化装置。 王国杰（１９９２一），女，贵州遵义人，学士学位， 技术员，中国水电顾问集团正安开发有限公司。 电子ｔ■，●・１２１・
