竞争和合作型协同进化算法

摘 要

本文基于大自然进化过程中种群之间、种群与环境之间的在进化过程中的协同作用，提出一种个体之间相互竞争和协助的协同进化算法CCEA（Coexistence co-evolutionary Algorithm）。基本思想为通过优势度和责任度概念，来控制各子种群繁殖的数量，在总的种群个体数量一定的前提下，使得优势种群拥有更多的繁殖机会，达到扩大搜索空间的目的，并迫使弱势种群更多的引入其他种群的优秀基因，达到增强自身优势度的目的。通过计算表明能有效的增强算法的搜索性能。

【关键词】协同进化 多目标算法 多目标优化

协同进化算法是基于协同进化理论出现的一类新的进化算法，其在传统进化算法强调个体与个体之间因环境原因所产生的竞争的基础之上，进一步考虑多个种群之间、种群与环境之间的在进化过程中的协同作用。目前通常使用的协同进化算法主要可以分为两类：以种群竞争的方式加速算法收敛和使用种群合作的方式保持种群多样性。但是这两种方式都只是强调了协同进化中的一部分，都存在其不足。在大自然生物们个体之间的协同进化过程中，竞争、合作这两种相互矛盾的关系往往都是同时存在的。只有强者才具优先的权利，以遗传下自身的基因，其他处于弱势的个体会团结起来与其对抗，达到留下自身基因的目的。刘静在她的博士论文《协同进化算法及其应用研究》中基于种群竞争和合作思想构建了MOCEA（Multi-objective Coevolutionary Algorithm），通过竞争特性算子――吞并算子来达到使得优秀的基因得到广泛的传播和保持种群基因的多样性，并得到很好的效果。但由于刘的思想仍然是主要依靠种群合作来达到加速收敛的目的，其所采用的竞争特性算子――吞并算子对其算法进化并没起到决定性作用。

1 算法设计

1.1 算子设定

1.3.1 测试函数一

该测试函数为一带约束条件两目标函数，其主要用于测试多目标优化算法在pareto前沿的收敛的能力。

从表3.1可以看出CCEA算法在Spreed这个指标上具有很大的优势，从图3-1也可以看出CCEA算法比NSGAII算法在这个测试函数的计算上具有更大的优势。

1.3.2 测试函数二

该函数为带约束的两目标测试函数，在其约束条件内含有两个可调变量a、b，本文选取a=0.1，b=16来对CCEA算法和NSGAII算法进行测试。该函数的PFtrue曲线为三段相互之间不连续的曲线，在对多目标优化算法测试时，通常对中间一段进行关注，其主要特点在于这个区段的部分点不易被搜索到，性能较差的算法在这部分通常表现为断开。该函数因此可以检测算法在pareto前沿的搜索能力。

由表3.2可以看出CCEA算法除了在GD这个指标上占优势以外，在其他两个指标上并不占优势，甚至在Spreed这个指标上略有不如。但从图3-2看出来在中间一段曲线上CCEA算法搜索出来的为一条连续曲线，而NSGAII算法在这部分是断开的，这可证明CCEA算法对pareto前沿解的搜索性能要强于NSGAII算法。

2 结论

本文基于本文利用大自然中种群竞争和合作的特性，基于大自然中种群首领在种群遇到外部危险时会对整个种群进行保护的特点，引入优势度和责任度的概念。提出一种个体之间相互竞争和协助的协同进化算法CCEA来控制各子种群繁殖的数量，在总的种群个体数量一定的前提下，使得优势种群拥有更多的繁殖机会，达到扩大搜索空间的目的，并迫使弱势种群更多的引入其他种群的优秀基因，达到增强自身优势度的目的。通过测试报表明该算法可以显著的提高其搜索性能，对于复杂的多目标优化问题具有较大的实用价值。

作者简介

郭晨阳（1987-），男，硕士研究生。