混合遗传算法综述

贵州大学电气工程学院 栗 盼

混合遗传算法综述

贵州大学电气工程学院 栗 盼

遗传算法是一种通过编码对可能问题解空间搜索求解，能够在目标函数的导数信息位置的情况下模拟自然界生物进化过程的自组织、自适应的过程。能够尽快确定最优值所处范围，而混合遗传算法在其基础上引入其他优化算法，以保证遗传算法全局性能的基础上大大减小计算量，提高收敛速度。普通的混合遗传将经典的优化算法和局部搜索能力融合，平衡深度搜索和广度搜索。通过对群体进行复制、杂交和变异，通过以自适应为原则的选择机制累积信息，遗传算法可以保持在解空间不同区域对多个点的搜索，通过交叉算子和变异算子来全面搜索解码空间，不容易陷入局部最优。

遗传算法；混合遗传算法；拉马克进化

引言

从简单到复杂,从低级到高级的生物进化过程本身是一个自然、并行发生的、稳健的优化过程,通过“优胜劣汰”及遗传变异,后代种群比前代更加适应环境,末代种群中得最优个体。

借鉴上述过程,形成的独特的随机搜索算法,即为遗传算法。初代种群(编码集合)产生后,按照优胜劣汰的原则,通过适应度选择个体,复制、交叉、变异等自然选择,产生出具有适应环境的优化的群体,循环往复,渐变式进化。

遗传算法受上述的生物进化学和生物遗传学的启发,使用自适应概率搜索技术,其选择、淘汰、优化等运算都是以一种概率的方式来进行的,这样增加了进化过程中自适应迭代过程的灵活性。由于遗传算法不依赖寻有问题情境的具体范围和梯度信息,为较为复杂的寻优问题提供了通用的基本框架。

1 遗传算法

1.1 遗传算法特点

作为人工智能系统的重要探究方向和人工生命探究的重要工具,GA是对进化系统进行的应用计算机中的模拟研究,常规的GA将问题的个体的染色体串编码,把所求解问题的可行解进行编码,根据进化和遗传原理,计算机会从某个初始点进行搜索,逐一梯次寻到最优解范围。

1.2 Lamarckian进化（拉马克进化）和Baldwin效应（班德文效应）

遗传算法在传统的方式基础上,利用局部搜索来提高种群适应性,最终的提高被遗传算法编码在字符串上,相当于有机体后天学习的获得性性状直接将编码反馈到基因型上,这相当于一种拉马克进化形式。还有一种形式,不会在基因上对其编码,而是通过对某种行为的学习能力遗传给下一代,这是一种改变适应度曲线的效应,这种机制就是班德文效应。

拉马克进化论点有:(1)生命是连续的、变化的、发展的,生物具有不断增加复杂性的趋势。(2)生物以“树状”进化,从低级到高级且向各个方向发展。(3)环境变化引起生活需要的改变,进而导致物种产生新的行为和养成新的习性。在拉马克的例证中有这么一个事例:以前的长颈鹿由于干旱,时常伸颈取食树上的叶子,使得脖子越来越长,这些后代获得的性状在自然选择中存活下来。时年累月,成为我们如今所熟知的长颈鹿。将这种进化过程用“用进废退”和“获得性遗传”原则进行了总结。

班德文效应观点为:在生物的群体遗传中,个体适应性对进化产生影响,即没有明确将特定的性能传给下一代,后代个体继承的是种学习能力。就长颈鹿的例子来讲,班德文认为,一方面是在长时间的进化过程中,学会到伸长脖子的个体得以存活,然后将这种认知能力传给后代,最终这些个体成为种群主要成员,另一方面个体学习到有益行为,会将其变成一种本能。

拉马克认识到了变异的普遍性,否认了其随机性,将新搜索到的个体放入群体中,易陷入局部最优,收敛速度慢;Baldwin只是修改个体的适应度,易获得全局最优解,但速度较慢。共同缺点是局部搜索能力较差和参数较难选择。

2 混合遗传算法的提出

尽管遗传算法对于各种问题能够尽快的找到最优解的范围,但就任何一个特殊领域而言,都只是寻到次优解,它们往往比不上专门处理该领域问题的算法。

2.1 遗传算法存在两个严重的问题

2.1.1 “早熟”问题

“早熟”问题作为遗传算法的缺陷之一,是一种由于群体丧失多样性而提前收敛到局部最优解的未成熟收敛的情况。主要表现为种群在进化过程中,生成的个体具有很高的适应度,通过选择,适应下来的个体大部分与其一致或相似,导致群体陷入同一极值而停止进化,从而不能得到全局最优解。

2.1.2 局部搜索能力低

从本质上讲,遗传算子主要是通过交叉算子和变异算子来实现的是随机搜索,不能保证产生改进的后代,其中交叉算子主导,而变异算子则是辅助。在算法的初期优秀的个体可以主导控制过程,竞争较为激烈;而在算法的晚期,群体中的个体趋于平均值,竞争趋于平缓,交叉操作的结果会出现很多类似性状的组合,呈现随机搜索行为。这直接影响了搜索效率以及寻到全局最优解的概率。

2.2 解决

由于以上问题的存在,随机搜索的收敛速度较慢,而且局部寻优能力差,往往只能得到全局的次优解,这时我们希望找的给定问题的解的同时随特定问题而变化,但如果将遗传算法和原有算法混合,融合原有算法中较为先进的优化技术和遗传算法,这样同时保持了两种算法的优势,使得在性能上优于这两种。一般采用传统优化算法的编码或者在编码解码过程中融合专业知识并且在GA步骤中添加局部搜索两种混合策略。

3 混合遗传算法基本原理

由于GA能够迅速的优化到最优值的大约92%,但是得到其近似最优解就很耗费时间,这表明其在全局的收敛性能优秀但是局部较差,但是一些经典的遗传算法具有局部收敛性能较高,精确度较高的优势,将二者融合,能够互相弥补,以迅速的得到最优解。

4 混合遗传算法实现

4.1 编码方式

编码的实质是在表型空间与基因型空间之间建立一个映射。传统的优化算法一般采用一种将实数空间离散化的二进制编码方式。在解决染色体可行性、合法性和唯一性的前提下,使用固定长度的二进制符号来表示群体中的个体,其等位基因是由二值符号集{0,1}组成的,初始个体基因值可用均匀分布的随机值生成。

4.2 交叉和选择操作

选择的基础是达尔文的适者生存理论。合适的选择压力很重要,初始阶段压力希望小,最终压力希望大,选择的作用使得群体最优解所在区域移动,遗传算法本质上是一种概率性的自适应迭代性的寻优算法,交叉算子反映随机信息的交换,产生新的基因组合即新个体,选择算子则是以适应度为选择原则的再生行为。

4.3 变异操作

根据基因变异原理,对自然选择出的个体的某些基因,按照变异的概率,执行异向转化,某个程度上可以看做对某位基因的取反。

4.4 适应度函数

适应度一般用来表示生物界的适者生存,适应度函数则是用来评判个体优劣的标准。一般通过适应度变换开维持个体之间的合理差距以及限制竞争、维持物种多样性。

4.5 局部搜索（常见的几种混合遗传算法）

小生境算法:生物界中,交叉并不是完全随机的,有很多因素的制约,从遗传算法的角度来看,显然缺乏对可能的交叉效果方面的考虑,会使优化效率降低,为了解决这种问题,将小生镜技术与双亲变异相结合,提出替换与本身性状类似的个体的预选择机制、用群体代间覆盖方式的排挤机制、利用共享函数选择的共享机制的小生境技术,来维护群体的多样性。

自适应算法:由于用不变的参数控制进化过程,容易影响交叉和变异概率,易导致早熟,所以用自适应调整遗传算法的控制参数的思想混合定量评价指数,以满足系统实时性以及全局收敛性。

免疫遗传算法:遗传算法的交叉和变异算子都是在一定概率下的迭代搜索,所以在个体进化的过程中不可避免的出现退化,故借鉴免疫系统的动态的自维持、多样性的遗传机理和对异物快速反应等机理,以达到抑制优化过程的退化现象,避免“早熟”情况的出现。

模拟退火算法则根据循环进化过程能够增强和保持生物种群的多样性,具有较强的局部搜索能力,在循环过程中能同时接受使目标函数变好的状态以及概率接受变差的状态点,则能通过摆脱局部最优解达到全局最优解。

其余的情况,可根据选择的遗传算法进行具体操作,例如梯度法等。

5 结语

遗传算法的收敛速度较慢以致影响全局收敛性,这是目前改善遗传算法性能的主要克服的问题。一些研究已经针对增强收敛性能提出了多种改进途径,并在多种实际领域中获得了良好的应用效果。本文综述了基于遗传算法的混合遗传算法的起因、原理以及算法的实现,可对混合遗传算法有了大概的了解,在此基础上有针对性的对混合遗传算法进行研究,可以解决现实生活中的很多难题。但是由于时间和经验等原因,混合遗传算法还有很大的改进和提升空间,有待我们以后深入研究。

［1］乔建忠,雷为民,李本忍,滕弘飞.混合遗传算法研究及其应用［J］.小型微型计算机系统,19(12).

［2］黄浩锋,陈少英.混合遗传算法概述［J］.科学技术,2008,04.

［3］张智霞.混合遗传算法及应用实例［J］.青海大学学报,2004,02.

［4］辛海涛.混合遗传算法及其应用［J］.软件导刊,2010,05.

［5］焦李成,公茂果.拉马克进化、班德文效应与自然计算［A］.第十一届中国人工智能学术年会.西安,2006.

栗盼（1992—），女，河北南宫人，硕士研究生，研究方向：嵌入式系统与自动化装置。