协同进化多生境遗传算法

郭方炜+许峰

摘要：为了提高多生境遗传算法的优化效率，提出了一种基于协同进化的多生境遗传算法，其基本思想是：将种群分割为若干子种群，每个子种群采用合作型协同进化方法独立进化；个体评价采用多生境方法，具体作法为：在对个体的适应值进行共享调整的同时，在选择中采用确定性排挤方法，在替换中采用最相似个体适应度最差个体被替换策略，以维持种群的多样性。数值实验表明，上述算法在维持多生境遗传算法较强全局搜索能力的同时，可适当提高算法运行效率。

关键词：遗传算法；协同进化；多生境；多峰函数；算法效率DOI：10.11907/rjdk.162706中图分类号：TP312

文献标识码：A

文章编号：16727800（2017）004005104

0引言 在多模态函数优化问题中，需要搜索多模函数空间的多个极值点。遗传算法已被证明是求解多模态函数优化问题的有效算法[1]，其中基于适应值共享的多生境遗传算法（MultiNiche Fitness Sharing Crowding Genetic Algorithm，MNSCGA）[2]综合了适应值共享与确定性排挤两种遗传算法在维持种群多样性方面的优点，具有较强的多模态搜索能力。不过，也正是由于基于适应值共享的多生境遗传算法在选择、替换中采用了较为复杂的策略，从而使得该算法具有较高的算法复杂度，算法运行效率较低。〖JP〗协同进化在生物学中是指生物与环境、生物与生物之间在进化过程中的某种依存关系。Ehrlich和Raven[3]最早提出进化算法中的协同进化概念，Hillis[4]首先将协同进化思想引入遗传算法。此后，陆续出现了多种协同进化遗传算法[58]。由于协同进化遗传算法采用多个子种群同时进化，且考虑了子种群间的协同进化，有类似于并行计算的特点，通常可加快种群的进化进程，提高算法的运行效率。本文将协同进化思想与多生境排挤策略相结合，提出了一种基于协同进化的多生境排挤遗传算法，并根据数值实验对该算法进行了性能分析。

1多生境排挤遗传算法 基本遗传算法采用轮盘赌选择方式，选择压力偏大，不利于维持种群的多样性。MNSCGA在适应值共享的基础上，将排挤机制应用到选择和替换过程，减缓了选择压力。此外，在交叉过程中，算法还允许不同生境之间的竞争，从而使得各小生境内均保持有一定量的小群体，即多生境排挤。这些方法有效地维持了种群的多样性，提高了算法的多模态搜索能力。

1.1排挤选择 MNSCGA采用排挤选择方法，具体可分为两个步骤：从群体中随机地选择一个个体Ii；从一个含有Cs个个体的排挤组中选择与Ii配对的个体Ij，排挤组中的Cs个个体是从整个种群中随机产生的。Ij的选择规则为：在所有排挤组个体中，选择与Ii最相似的个体作为Ij。

1.2间隔交叉与变异 Mahfoud[9]的研究证实，在小生境遗传算法中，若采用单点交叉，则子代往往与父代分属不同的生境。MNSCGA采用的是间隔交叉[2]，即每一对父代个体交叉后只产生一个子代个体。由于根据排挤规则，交叉的一对个体的搜索区间相邻，所以由间隔交叉所产生的子代个体以很大的概率与其父代个体属于同一生境。这样，大大降低了搜索的盲目性。 MNSCGA采用的变异算子与基本遗传算法大致相同，唯一的区别是变异操作仅对由间隔交叉产生的那一个子代个体进行。

1.3最相似个体适应值最小替换 MNSCGA采用最相似个体中适应值最小个体替换（Worst Among Most Similar， WAMS）的方法，其操作步骤如下：①对父代和子代群体进行适应值共享调整；②从父代个体中随机选择Cf个排挤组，每组有s个个体；③在每个排挤组中，寻找一个与子代个体最为相似的个体；④比较Cf个个体的适应值大小，挑选出适应值最小的个体将其替换；⑤重复步骤②～⑤，直至完成群体间一次替换。 WAMS方法的示意如图1所示。

2协同进化遗传算法

2.1协同进化基本思想 遗传算法是建立在进化论基础上的，强调优胜劣汰，其核心是种群内个体的竞争，而忽略了生物其它方面的各种联系，如合作、利他和寄生等，因此具有一定的片面性。其实，在自然界中，生物进化主要包括相互制约和相互受益两类机制，优胜劣汰仅仅是制约机制中的一种。基本遗传算法由于没有考虑进化中的受益机制，而在對复杂优化问题时，往往无能为力。 协同进化概念最早由Ehrlich和Raven在讨论蝴蝶之间进化影响时提出的[3]。Hillis[4]首先将协同进化引入遗传算法，提出了协同进化遗传算法（Coevolutionary Genetic Algorithm，CGA），其基本思想是[11]：将整个种群分成多个子种群，每个子种群同时进化，进化时不仅考虑同一子种群中个体之间的关系，而且还要考虑不同子种群中个体之间的关系。对个体进行评价时，个体适应度不仅由目标函数决定，还由其他个体决定。也就是说，子种群之间通过相互作用而共同进化，这样就弥补了传统遗传算法只考虑竞争机制的不足。协同进化遗传算法流程如图2所示。

2.2合作型协同进化遗传算法 协同进化遗传算法主要有竞争型协同进化遗传算法和合作型协同进化遗传算法两种。由于合作型协同进化遗传算法（Cooperative Coevolutionary Genetic Algorithm， CCGA）的进化效率较高，且计算复杂度较小，所以逐渐成为协同进化遗传算法的主流。CCGA首先将决策变量的空间分割为若干子空间，每个子空间经编码后即构成一个子种群，各子种群独立进行进化。在个体适应度评价时，要将待评价个体与其它子种群中选择的个体相结合，构成了一个完整解，通过计算此完整解的目标函数值得到个体适应度。

3协同进化多生境遗传算法

3.1算法基本思想 多生境遗传算法能较好地维持种群的多样性，具有良好的多峰搜索能力。但由于多生境遗传算法在适应值共享的基础上添加了排挤机制，且采用了较为复杂的最相似个体中适应值最小个体替换策略，这就使得此算法的计算复杂度较高，运行效率欠佳。 考虑到协同进化具有类似于“并行进化”的特点，本文提出一种基于合作型协同进化思想的多生境遗传算法（Cooperative Coevolutionary Multiniche Genetic Algorithm， CCMNGA），其基本思想是：将种群分割为若干子种群，每个子种群采用合作型协同进化方法独立进化；个体评价采用多生境方法，具体作法为：在对个体的适应值进行共享调整的同时，〖HJ*3〗在选择中采用确定性排挤方法，在替换中采用最相似个体适应度最差个体被替换策略，以维持种群的多样性。

3.2算法步骤 ①将整个种群分成若干个子种群；②对每个子种群采用合作型协同进化方法进化；③对子种群中的个体进行适应度共享调整；④对每一个个体i，根据排挤选择机制寻找与之匹配的个体j；⑤对个体i和j，以概率Pc进行间隔交叉，以概率Pm进行变异；⑥根据WAMS方法进行替换，完成种群间的一次迭代；⑦将各种群中的个体合并，计算适应值，进行个体评价；⑧若满足结束条件，则算法结束，否则转②。

4数值实验

从图3、图4和表2可以看出，CCMNGA不仅搜索到了全部的全局最优解，而且精度较高，这充分显示了CCMNGA较佳的全局搜索能力和局部寻优能力。表3和表4分别给出了CCMNGA和MNSCGA对函数f1（x，y）和f2（x，y）进行10次优化的成功率、平均进化代数和平均运行时间。搜索到全部峰，且满足表1中的收敛判据视为成功。

从表3和表4中可以很清楚地看出，无论对相对较简单的多峰函数f1（x，y）还是比较复杂的多峰函数f2（x，y），CCMNGA和MNSCGA两种算法搜索多峰的能力基本相当，均保持较高的成功率。但CCMNGA的平均进化代数和平均运行时间明显低于MNSCGA，特别对于复杂多峰函数f2（x，y），优势更加明显。这在一定程度上表明，引入了协同进化机制，确实可以提升多生境遗传算法的运行效率。

5结语 本文针对多生境遗传算法运行效率较低的缺陷，提出了一种基于合作型协同进化思想的多生境遗传算法。数值实验结果表明，改进后的算法不仅保持了多生境遗传算法多峰搜索能力高的优点，而且在一定程度上提高了算法的运行效率。 需要指出的是，由于小生境遗传算法特别是协同进化遗传算法的理论基础还很薄弱，譬如整个种群如何合理分组、子种群的规模能否自适应变化、如何确定搜索区域、如何选择代表个体等问题尚没有明确的结论[1213]。另外，本文对改进算法的性能研究只是根据对测试问题的对比实验，这无疑在一定程度上影响了结论的普适性。

参考文献：[1]MILLER B L，SHAW M J.Genetic algorithms with dynamic niche sharing for multimodal function optimization[C].In： IEEE International Conference on Evolutionary Computation， Piscataway， NJ： IEEE Press，1996：786791.

[2]谭艳艳，许峰.基于适应值共享的多生境排挤遗传算法[J].计算机工程与应用，2009，45（5）：4649.

[3]EHRLICH P R，RAVEN P H.Butterflies and plants：a study in coevolution[J].Evolution，1965（18）：586608.

[4]HILLIS W D.Coevolution parasites improve simulated evolution as an optimization procedure[C].Proceeding of 2nd Artificial Life Conference，New York： AddisonWesley，1991：25369.

[5]PENAREYES C A，SIPPER M.Fuzzy CoCo：a cooperative coevolutionary approach to fuzzy modeling[J].Fuzzy System，2001，9（5）：727737.

[6]IORIO A W，LI X D.Parameter control within a cooperative coevolutionary genetic algorithm[C].Proceedings of Parallel Problem Soling from Nature，Berlin：SpringerVerlag，2002：247256.

[7]IORIO A W，LI X D.A cooperative coevolutionary multiobjective algorithm using nondominated sorting[C].Proceedings of 2003 Genetic and Evolutionary Computation Conference，San Mateo：Morgan Kaufmann，2004：537548.

[8]SIM K B，LEE D W，KIM J Y.Game theorybased coevolutionary algorithm，a new computational coevolutionary approach[J].International Journal of Control， Automation， and Systems，2004，2（4）：463474.[9]MAHFOUD S W.Simple analytical models of genetic algorithms for multimodal function optimization[R].IlliGAL Report No. 93001，Dept. of Computer Science， University of Illinois，UrbanaChampaign，1993.〖ZK）〗[10]〖ZK（#〗于歆杰，王贊基.自适应调整峰半径的适应值共享遗传算法[J].自动化学报，2002，28（5）：816820.

[11]祝勤友，许峰.自适应邻居结构元胞遗传算法[J].软件导刊，2015，14（11）： 3942.

[12]巩敦卫，孙曉燕.协同进化遗传算法理论及应用[M].北京：科学出版社，2009.

[13]焦李成，刘静.协同进化计算与多智能体系统[M].北京：科学出版社，2006.

（责任编辑：孙娟）

Abstract：In order to improve the optimization efficiency of multiniche genetic algorithm， a multiniche genetic algorithm based on coevolution is proposed. The basic idea is that the population is divided into several subpopulations， and each subpopulation evolves independently using cooperative coevolutionary method. Multiniche method is used to individual evaluation， and the specific methods is that individual adaptive value is share adjustment at the same time， the deterministic crowding method is used to choice， and WAMS is used to replace， so that maintain the diversity of population. Numerical experiments show that the algorithm can improve the operation efficiency of the algorithm， while maintaining the strong global searching ability of the multi niche genetic algorithm.

Key Words： Genetic Algorithm； Coevolution； MultiNiche； Multipeak Function； Algorithm Efficiency