基于种间竞争的协同差分进化算法

徐萍+王友才+王凯

0 引言

差分进化算法（Differential Evolution， DE）作为一种新兴的进化计算技术[1]具有算法操作简单、适应性强、鲁棒性强、精确度高、收敛速度快等优点。但由于在DE算法是通过父代个体差异和“贪婪”的选择方式生成子代个体，个体之间仅存着竞争关系，通过个体之间的竞争而淘汰差的个体，保留优秀个体，从而使解群体不断向最优解逼近，而没有考虑其进化的环境和个体之间的复杂合作关系。使其存在着收敛速度和搜索鲁棒性相冲突，算法随着进化代数的增加和群体多样性降低，后期收敛速度变慢，容易陷入局部最优解等问题。

在生态学中认为，生存在一定自然环境资源制约中的种群，通过相互之间的竞争协同，能够使双方相互驱动提高性能和复杂性，从而实现种群之间的协同进化，已有的证据表明协同进化能大大加快生物进化的历程[2]。而协同进化算法正是源于竞争协同的思想而发展起来的一种算法。在协同进化算法中，个体之间不仅存在竞争关系，同时也存在相互合作、相互促进的关系，各个子群体之间通过适应度的关联而共同进化。与传统进化算法的区别在于协同算法在进化算法的基础上，考虑了种群与环境之间、种群与种群之间在进化过程中的协调。由于协同进化算法的诸多优越性，越来越多的学者对此进行了研究[3～6]，成为當前进化计算的一个热点问题。

1 种间竞争的协同进化

由生态学研究可知，进化的基本单位是个体或种群，种群是指在特定时间内，由分布到同一区域的许多同种生物个体自然组成的生物系统。种群具有共同的基因库，因此种群是种族生存的前提，是系统发展的结果。协同进化动力学系统是以种群为基础的。

在一定生态环境中的种群，其进化不仅受到自身适应度的影响，同时还受到环境和其他种群相互竞争的影响。如果不考虑种群间的相互作用，可以用下面的Logistic方程来描述种群增长与环境间的动力学特征：

式1中，K表示环境负荷量，r表示种群的个体增长率，N是种群的大小。这是一个单一种群的增长情况，它只考虑了种内竞争，即种群内部每增加一个个体，对种群本省增长的抑制作用为1/K。

以Logistic方程为基础，进一步考虑种群间竞争的协同进化关系。假设有两个相互竞争的种群P1和P2，均利用同一资源，则Logistic方程可以改成以下方程组来表示每个种群的增长：

式2中，K1和K2表示在没有竞争的情况下种群P1和P2的环境负荷量；r1和r2表示种群P1和P2个体的最大瞬时增长率；N1和N2分别是种群P1和P2的大小；α12和α21是竞争系数，αij表示种群Pi的每个个体对种群Pj的竞争抑制作用。

由竞争方程组可知，种间竞争的结果主要取决于双方的竞争抑制（α12和α21的大小）及其K值的相对大小。对于一个由n个不同种群组成的群落，上述竞争方程可改写成式3。

2 基于种间竞争的协同差分进化算法

将协同进化理论应用到差分进化算法可以处理约束优化问题[7～8] 和合作式协同差异演化问题[9～10]。而在生态学理论中，生物个体在自身进化过程中受个体适应度、所处生态环境以及其他个体之间的相互竞争等因素的影响。在一定生态环境中的种群，其种群进化不仅受到自身适应度的影响，同时还受到环境和其他种群相互之间的竞争协同的影响。因此，可以将结合了竞争与合作因素的种群间协同进化机制引入到差分进化算法中，对其性能进行改善。其中环境和种群间的协同竞争因素可以通过种群密度来体现。衡量种群竞争协同的一个主要因素是种群密度，如果种群密度大，则该种群的竞争能力强，反过来又增强了种群密度。

从式1可以看出，Logistic系数对种群密度的变化起着一种制动作用，使种群密度总是趋向于环境负荷量。当 时，Logistic系数是正值，种群密度上升；当 时，Logistic系数为0，此时种群密度不变；当 时， Logistic系数是负值，种群密度下降。利用式1所表示的Logistic方程，提出基于竞争机制的协同差分进化算法（CDE）。

CDE算法的主要思想是以标准差分进化算法框架为基础，将完整种群分为若干子种群，再进一步考虑子种群间基于种群密度的协同进化。算法在每次迭代中都依次进行进化过程和协同过程，其中进化过程采用标准差分进化算法的操作，协同过程通过种群竞争方程计算种群密度，并根据计算出的种群密度调整各个子种群的规模，即

由上可知，如果某子种群的密度增大，算法随机产生个体加入该群体，有利于提高该群体的多样性，从而在一定程度上提高了个体的全局分布。如果密度减少，则删除适应度小的个体。这种处理既体现了进化过程中的种间协同竞争，也体现出群体内部个体之间的相互竞争过程。CDE算法的步骤如下：

（1）确定算法参数值，包括种群规模、变异因子、交叉因子、最大迭代次数、子种群数目、环境负荷量、增长率、竞争系数和精度要求等。

（2）种群初始化。

（3）计算每个个体适应值，求出最优适应度和最优个体。判断最优适应度是否达到精度要求或是否达到最大迭代次数，若是则退出。

（4）计算子种群 的增长值，根据增长值调整种群规模。

（5）各子种群按照标准差分进化算法流程进行进化，生成下一代种群。

（6）迭代次数加1，返回至（3）。

3 算法测试与性能分析

为验证CDE算法的有效性，通过对五个典型的无约束测试函数进行测试，分别是Sphere函数（f1）、Rosenbrock函数（f2）、Rastrigin函数（f3）、Griewank函数（f4）、Schaffer函数（f5）[11]，并且与标准DE算法中的DE7 [12]（rand/ 1/bin）算法进行比较。

实验参数设置如下：种群规模60，最大进化代数10000，变异因子 ，交叉因子CR=0.5，子种群数目3，子种群初始规模30，环境负荷量为50，竞争系数取为子种群平均适应度的比值。所有算法利用Matlab编程实现，为评价算法的收敛性能，以运行一次所得函数全局极小值点和收敛时间作为算法的衡量指标，计算结果如表1所示。

从表1可以看出，CDE算法能够以更短的收敛时间，搜索到质量优于DE7算法的解。图1、2和3分别是某次搜索f1、f3和f4函数时CDE和DE7算法最优适应值的变化曲线。

4 结语

根据现有进化算法只考虑种群之间的竞争，而没有考虑到种群之间的协同进化的问题，本文提出了基于竞争机制的协同差分进化算法。该算法除了采用标准差分进化算法个体适应度控制进化的方式外，还考虑了种群与环境之间的相互作用以及种群间的协调，即基于种群密度的进化方式，这种方式增强了算法的全局搜索能力。通过对5个典型测试函数的仿真结果表明，CDE算法性能优于标准差分进化算法，其能够有效改善早熟收敛和提高收敛速度。

参考文献

[1] Rainer Storn and Kenneth Price. Differential Evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces [R]. Technical Report， TR-95-012， ICSI， March 1995.

[2] 焦李成，劉静，钟伟才著。协同进化计算与多智能体系统，科学出版社，2006年。

[3] 曹先彬，罗文坚等。基于生态种群竞争模型的协同进化[J]，软件学报，2001年，12（4）：556-562。

[4] 李敏强，寇纪淞。多模态函数优化的协同多群体遗传算法[J]，自动化学报，2002，28（4）：497-504。

[5] 高鹰，姚振坚，谢胜利。基于种群密度的粒子群优化算法[J]，系统工程与电子技术，2006，28（6）：922-924，932。

[6] 吴斯，曹炬。带记忆信息的协同进化算法[J]，计算机工程与科学，2008，30（3）：78-81。

[7] Bo Liu， Hannan Ma， Xuejun Zhang. A Co-evolutionary differential evolution algorithm for constrained optimization[C]. ICNC2007

[8] Fu-zhuo Huang， Ling Wang， Qie He. An effective co-evolutionary differential evolution for constrained optimization [J]. Applied mathematics and computation， 2007， 186：340-356.

[9] Yan-jun Shi， Hong-fei Teng， Zi-qiang Li. Cooperative co-evolutionary differential evolution for function optimization[C]. ICNC2005， 1080-1088.

[10] 张萍.协同差异演化方法在函数优化中的应用[D].中国地质大学硕士学位论文，2008年5月.

[11] 王凌.智能优化算法及其应用[ M].北京：清华大学出版社，2001.1-6.

[12] 赵光权，彭喜元等. 基于混合优化策略的微分进化改进算法[J].电子学报， 2006， 34（12A） ： 2402-2405.