自适应Memetic算法

摘要：在处理多峰函数的优化问题时， 遗传算法局部搜索能力差，并且容易早熟。针对这种问题，将遗传算法与多种局部搜索算法相结合，形成多种Memetic算法。通过进行数值优化实验，发现算法的优化效率有所提高，但是局部搜索算法的不同对优化性能影响很大。为解决这种问题，在传统Memetic算法的基础上提出了一种使每代个体根据局部搜索算法的搜索效率自适应选取局部搜索算法的Memetic算法，即基于离散度的自适应Memetic算法。通过测试函数测试，这种算法具有更高的效率和更强的通用性。

关键词：多峰函数优化；遗传算法； 局部搜索算法；离散度；自适应Memetic算法

中图分类号：TP312 文献标识码：A 文章编号：16727800（2013）009005803

作者简介：王振华（1986-），男，上海飞机设计研究院民用飞机模拟飞行国家重点实验室工程师，研究方向为飞行仿真。

0引言

遗传算法是一种全局优化算法，是模拟生物在自然界中的进化过程而形成的，已在机器学习、组合优化、图像处理和自适应控制等领域中广泛应用。然而大量研究与实践显示，遗传算法全局搜索能力很强而局部搜索能力不是很强，且容易过早地收敛，相反，局部搜索算法搜索目的性很强，能够很快收敛到局部最优解，因此将局部搜索算法与遗传算法相结合，可以提高遗传算法的优化性能。我们称这种混合算法为遗传局部搜索算法，也可称作Memetic算法。

Memetic算法是一种局部搜索侧略与全局搜索策略相结合的算法[1]。相比传统的遗传算法，这种结合机制使其在某些问题优化中的搜索效率快很多。Memetic算法提出的是一个概念，一种框架，不只是混合遗传算法或拉马克进化算法。在这种框架下，不同搜索策略的选取可以形成不同的Memetic算法，比如局部搜索算法可以选取模拟退火、爬山搜索、禁忌搜索、贪婪算法等，全局搜索算法可以选取进化规划、进化策略、遗传算法等。

全局搜索策略与局部搜索策略耦合的过程中有以下6个方面[2]需要注意：①局部搜索的频率；②个体进行局部搜索的概率 ；③种群中可进行局部搜索的范围 ；④局部搜索的强度；⑤局部搜索方法的选择；⑥如何减小通过引入局部搜索算子而增加的计算时间 。

局部搜索算法有很多，不同的局部搜索算法对特定优化问题的优化效率差别很大。自适应Memetic算法，即可以根据优化问题的不同自适应的选取局部搜索算子的Memetic算法，成为优化算法领域新的研究方向。Krasnogor在文献[3]中提出了对多种局部搜索算法进行整合，并依据局部搜索邻域的选择函数与当前算子的搜索情况来选取局部搜索算法的策略。文献[4]中用“hyperheuristic”一词来描述将多个局部搜索算法整合，不同个体采取不同局部搜索算法的策略。Smithz提出了Coevolving Memetic 算法，采用某种策略选择局部搜索算法[5]。这种策略，Ong and Keane描述为“metaLamarckian learning”[6]。文献[7]总结了自适应Memetic算法的研究现状。

局部搜索个体的选择策略同样是Memetic算法的研究重点。文献[8]中提到了基于离散度的策略来确定局部搜索点。文献[9]中提到了基于适应值、空间分布及精英保留等策略来确定局部搜索点。

本文选取基于离散度的策略来确定局部搜索点，并且将多种局部搜索算法与遗传算法结合，形成多种Memetic算法。将这些算法应用于基准函数优化中，通过对每种算法的优化特性进行观察，进一步提出了基于离散度的自适应Memetic算法（DAMA，即Diversitybased Adaptive Memetic Algorithm ）。通过将该种算法与传统Memetic算法作对比，表明该算法具有更强的通用性，更高的效率和更好的鲁棒性。

1基于离散度的自适应Memetic算法

1.1耦合策略及参数设置

（1）局部搜索算法的选取策略：局部搜索算法的效率。局部搜索算法的选取策略在自适应Memetic算法中有很多。相比排序法、随机法、经验法，本文通过局部搜索算法的搜索效率来选择局部搜索算法。单纯形搜索法、方向加速法、拉格朗日搜索法与模式搜索法组成了局部搜索算法库。对前面的局部搜索点随机选择局部搜索算法，组建局部搜索算法的优化效率库，然后，后面的局部搜索点根据前面局部搜索算法在周围已搜索点的优化效率选择局部搜索算法。

（2）局部搜索点集的选取策略：离散度原则。为求得最优解，种群中的个体最好每个都进行局部搜索，然而为了提高优化效率，在实际问题优化中，不能对每个个体都进行搜索。在局部搜索点的选取上有很多算法，比如适应值法、随机法、离散度法等[56]。本文在局部搜索点的选择上选取基于离散度的策略，具体策略如下：① 将种群中的最优点确定为局部搜索点；②单位化其他搜索点到最优点的距离；③去掉种群中距离最优点相对距离较小的点；④当局部搜索点的个数满足要求时，停止搜索，否则转步骤①，继续搜索。

（3）局部搜索点选取搜索邻域的策略。不同的搜索邻域对算法的优化效率具有很大的影响。搜索邻域的选取取决于个体的不同类型：对种群中的最优个体选取小的搜索领域，进行精确搜索；为使其他局部搜索点共享最优个体的搜索信息，其它局部搜索点的搜索邻域半径定为搜索点到最优个体的距离（见图1）。

（4）局部搜索点选取搜索强度策略。需要进行深度搜索的点，如每代种群中的最优点，搜索强度高，搜索次数可设置相对较多，如8倍变量个数，其他局部搜索点不需要进行深度搜索，搜索次数可设置相对低一些，如4倍变量个数。

1.2算法流程

算法流程见图2。

2数值实验

Ackey 、Sphere、Rastrigin和Griewank[10]等测试函数组成数值试验的测试函数集，具体函数特性见表1。为体现DAMA算法的优越性， GA及传统Memetic算法（MAPOWE，MASIMP，MAHOJE，MALAGRH）共同参与数值实验，进行对比。各算法的参数设置如表2。对所有函数在20维的情况下进行测试，中止条件为运算5 000次，各实验均独立运行20次，选函数最优点的平均值及方差来确定算法的效率和鲁棒性，结果见图1、表3。

3结语

针对遗传算法局部搜索能力差且易过早收敛的缺点，本文提出了一种基于离散度的自适应Memetic算法（DAMA），该算法通过离散度来确定局部搜索点，然后根据局部搜索算法的效率自动选择局部搜索算法。数值试验表明，DAMA比遗传算法（GA）及4种传统Memetic算法（MAPOWE，MASIMP，MAHOJE，MALAGRH）更具通用性，效率也更高。

参考文献：

[1]P MOSCATO.On evolution，search，optimization，genetic algorithms and martial arts：towards memetic algorithms，publication report 790[J].Caltech Concurrent Computation Program，1989.

[2]YEWSOON ONG，MENG HIOT LIM，XIANSHUN CHEN.Research frontier：memetic computationpast[Z].Present & Future.

[3]N KRASNOGOR，B BLACKBURNE，J D HIRST，et al.Multimeme algorithms for the structure prediction and structure comparison of proteins，in parallel problem solving from nature[J].Lecture Notes in Computer Science，2002.

[4]P COWLING，G KENDALL，E SOUBEIGA.A hyperheuristic approach to scheduling a sales summit[C]//PATAT 2000，Springer Lecture Notes in Computer Science.Konstanz，Germany，Aug.2000：176190.

[5]J E SMITH ET AL.Coevolution of memetic algorithms： initial investigations，in parallel problem solving from nature—PPSN VII，G.Guervos et al.，Eds.Berlin，Germany[J].Springer，Lecture Notes in Computer Science，2002：537548.

[6]Y S ONG，A J Keane.MetaLamarckian in memetic algorithm[J].IEEE put，vol.8，pp.99110，Apr.2004.

[7]ONG YS，LIM MH，ZHU N，et al.Classification of adaptive memetic algorithms： a comparative study[J].IEEE Trans Syst Man Cybern Part B.

[8]M W S LAND.Evolutionary algorithms with local search for combinatorial optimization.Ph.D.Thesis[J].University of California，San Diego，1998.

[9]W E HART.Adaptive global optimization with local search[D].PhD thesis：University of California，1997.

[10]MINH NGHIA LE，YEWSOON ONG ，YAOCHU JIN .Lamarckian memetic algorithms： local optimum and connectivity structure analysis[J].Memetic Comp，2009（1）：175190.