混合遗传算法综述

贵州大学电气工程学院 张先炼

中国水电顾问集团正安开发有限公司 王国杰

混合遗传算法综述

贵州大学电气工程学院 张先炼

中国水电顾问集团正安开发有限公司 王国杰

遗传算法是在生物进化上面兴起的算法,它的应用范围广，但由于自身有不足之处，如早熟收敛等,则需对算法的收敛速度及搜索能力等问题进行处理。本文对遗传算法的基本思想、操作步骤及主要特点,以及存在的问题进行了讨论,介绍了几种混合遗传算法,对于其基本原理,特点及研究方向进行了概述。

遗传算法；混合遗传算法；收敛；搜索

1.引言

遗传算法起源于达尔文“进化论”,借鉴生物界的进化规律而来的全局搜索算法,对此,我们需要了解相关知识,比如：种群、个体、基因、染色体、遗传与变异等问题,在进化论中,繁殖过程,会发生基因交叉,突变的基因,一些低适应度个体逐渐消失,然而高适应度个体将会更多［1,2］。对于遗传算法的应用,主要是在一些图像处理、神经网络进化、组合优化等方面,但单独的遗传算法存在很多缺点,比如局部搜索的能力弱和未成熟收敛等等,最终导致很难快速找到最优解［3,4］。对于遗传算法的诸多缺点,相关人士有了对应的方案去解决,也就是把遗传算法和其他算法综合后为混合遗传算法。本文所提到的模拟退火遗传算法、量子遗传算法等等,用来弥补遗传算法某些不足之处。

2 遗传算法

2.1 遗传算法基本思想[4，5]

遗传算法是一种随机搜索的算法,在遗传机理与生物自然选择基础上发展而来的算法,能很好的解决最优问题。其基本思想是：开始是初始种群的产生,然后对于那些选中的染色体进行交叉、变异等操作后产生后代,然后计算适应度值来选择符合条件的后代,对于不符合条件的后代进行淘汰。经过若干代遗传后,该算法会最终收敛于条件最好的染色体,也就能得到最优解。

2.2 遗传算法实现步骤

一般遗传算法实现步骤［1,5］：

编码方式的选择→初始种群产生→计算适应度及排序→若不满足{选择→交叉→变异→对适应度值计算}等。如图1所示。

图1 遗传算法的流程图

3 混合遗传算法

针对一般遗传算法的局部最优陷入、未成熟的收敛、收敛速度慢等,只用简单的遗传算法是达不到的,那么我们可对遗传算法作恰当的改进或者将与其它搜索算法综合为混合遗传算法来解决这些问题。对于那些应用广泛的混合遗传算法概述如下：

3.1 模拟退火遗传算法[7，8]

基本思想：模拟退火算法主要运用在很大的可搜寻的空间中找问题最优解。对于模拟退火,在这个大的搜寻空间中,把它的每一个点都看成是空气中的分子;分子的能量,就是它本身的动能;然而对于大的搜寻空间中的每一个点,同样类似空气分子那样具有 “能量”,该算法的开始是以这个大的搜索空间里的一个任意的点,每次都要预先选择相应的“邻居”,之后看看在当前位置到相应的 “邻居”的概率问题。

研究方向：函数的最小值问题及TSP问题;选择设计合适退火温度来调整整个搜索的进程;对于相关应用问题,选择获取适当的适应度函数;可以和一些优化算法综合,比如模糊控制,在更大的范围内体现应用其优点等。

3.2 小生境遗传算法[5，9]

基本思想：小生境遗传算法是把每一代的个体划分成很多类,在此基础上,选出那些每类中适应度更大的一些个体,最后将它们构成一个对应的群体,之后在特定的种群中和一些不同种群中经过特殊的交叉、变异等来得到新的一代。

研究方向：由于小生境遗传算法多样性的解,收敛速度及全局寻优等优点,主要针对的是那些复杂多封峰函数的优化问题的研究。

3.3 混沌遗传算法[10，11]

基本思想：混沌遗传算法是在遗传算法总的变量群体中添加混沌变量,添加混沌变量是因为它针对子一代的群体所进行的轻微干扰以及跟着这个过程的进行慢慢调节相应的幅度。再由基本遗传算法的 “适者生存”规则,需要对应的选择、交叉、变异,之后对于混沌变量再添加一个小小的混沌扰动,通过后面的不断进化,最终在一个最优的环境下收敛从而得到相关问题的最优解问题。

研究方向：可以通过其遍历性来进行初始种群的产生和变异的操作,能对一般遗传算法进化的代数得以降低,最优解就能很快寻找到,混沌遗传算法可以有效避免一些早熟及局部收敛等问题。全局的寻优能力通过混沌遗传算法得以很大的提高。最终表明,混沌遗传算法可以显著提高计算效率,对于数据的冗余可以相应降低,种群多样性也可以得到保持,具有较大的实用价值。

3.4 量子遗传算法[12]

基本思想：基于量子计算原理,利用量子叠加态、量子比特的理论和概念,染色体是量子位编码表征, 对于进化搜索的完成是通过量子门更新和量子门作用。量子遗传算法通过量子门来实现染色体的演化,将量子的态矢量引入染色体的编码。量子遗传算法有更好的收敛速度和搜索能力,以及种群多样性等。

研究方向：对于重大挑战问题的算法设计、算法收敛性分析、量子遗传算法的计算复杂性、建立量子遗传算法机理分析的数学模型等研究。

4 结语

遗传算法是生物界的进化规律演化而得来,它不论是在应用上,算法设计上,还是在基础理论上,均取得了一定的发展,诸多领域都有一定应用价值,针对它还存在的一些问题和不足,以后将出现更好的方法理论运用其中。通过一些其他算法加上遗传算法综合的方式应用,遗传算法将会走得更远。

[1]马永,贾俊芳．遗传算法研究综述[J]．山西大同大学学报,2007,23(3)．

[2]吴玫,陆金桂．遗传算法的研究进展综述[J]．机床与液压,2008,36(3)．

[3]葛继科,邱玉辉．遗传算法研究综述[J]．计算机应用研究,2008,25(10)．

[4]吉根林．遗传算法研究综述[J]．计算机应用与软件,2004,21(2)．

[5]杜永贵,石洪献．混合遗传算法的研究现状[J]．科技情报开发与经济,2006,16(10)．

[6]吴强．蚁群混合遗传算法的研究及应用[D]．包头:内蒙古科技大学,2011:3-8．

[7]武兆慧,张桂娟,刘希玉．基于模拟退火遗传算法的关联规则挖掘[J]．计算机应用,2005,25(5)．

[8]田东平,迟洪钦．混合遗传算法与模拟退火[J]．计算机工程与应用,2006．22．

[9]黄聪明,陈湘秀．小生境遗传算法的改进[J]．北京理工大学学报,2004,24(8)．

[10]姚俊峰,梅炽,彭小奇．混沌遗传算法(CGA)的应用研究及其优化效率评价[J]．自动化学报,2002,28(6)．

[11]王芳．混沌遗传算法研究及其在地震子波提取中的应用[D]．北京:中国石油大学,2010:5-6．

[12]周露芳,古乐野．基于量子遗传算法的二位最大熵图像分割[J]．计算机应用,2005,25(8)．

张先炼（1993—），男，贵州遵义人，硕士研究生，贵州大学电气工程学院检测技术与自动化装置专业，主要研究方向：嵌入式系统与自动化装置。

王国杰（1992—），女，贵州遵义人，学士学位，技术员，中国水电顾问集团正安开发有限公司。