拓守恒

（陕西理工学院 计算机系，陕西 汉中723000）

0 引 言

差分进化算法（differential evolution，DE）具有全局探索和局部开发的能力，容易和其他优化搜索混合等特性［1］，在大规模复杂应用研究中取得了较好的效果［2］，但也存在求解精度低等缺点，研究者们为了提高DE算法的性能，做了大量研究和改进。文献［3］按照个体适应度的差异将个体分成不同的子种群，并针对不同的个体适应度值采用不同的变异算子，以保证在加快算法收敛速度的同时有效地跳出局部极值点。文献［4］提出一种基于多进化模式协作的差分进化算法，在每次迭代时，总是依次从3种模式中选取一种用于不同个体的进化，从而提高算法的通用性。文献［5］提出一种带有随机变异的动态差分进化算法，在这个算法中，两种不同的变异策略DE/rand/1和DE/best/1通过线性递减加权组合策略产生新的变异策略，以便动态利用DE/rand/1和DE/best/1的优点。文献［6］提出了中心变异差分进化算法，算法在每代变异时，选择种群的一个中心个体作为基向量，根据参加变异的3个随机个体向量间的函数适应值的大小关系，确定差向量的方向。上述几种算法都是针对差分进化算法的某一方面的缺点进行了改进，或者针对某一具体问题的应用性改进，但是往往通用性较差，难以在各种复杂变化的问题中得到好的优化效果。

为了提高DE算法的通用能力，受蚁群算法的启发，本文提出一种基于蚁群算法的自适应差分进化算法。算法将目前已经取得较好效果的变异算子综合应用于优化问题中，采用一种改进的多模式并行差分变异策略，不同于文献［4］，本文采用蚁群算法对差分变异算子的选择概率进行动态调整，从而提高算法的优化速度、稳定性和通用性。

1 差分进化算法

差分进化（differential evolution，DE）［7］是由Storn和Price于1996年为求解切比雪夫多项式而提出的一种演化算法。DE算法用浮点矢量编码在连续空间中进行随机搜索。DE主要采用2种进化算子：差分变异算子和交叉算法进化种群。由于DE算法采用实属编码，算法简单易用，所以在连续域优化问题种得到了广泛应用［8］。

1.1 差分变异算法性能特征分析

DE算法的关键是差分变异算子（differential operator，DO），目前有多种变异进化模式，其一般表示形式为DE/x/u/y/z［4，9］，其中，x表示在差分变异算法中与差异向量进行重组的基准个体，基准个体可以是：当前个体Xi、随机选取的个体Xrand或者是当前群体的最优个体Xbest；u表示差异向量的生成方式（rand－to－rand，rand－to－best），y表示参与重组的差异向量个数；z表示重组所采用的方式，主要有指数重组方式和二项式重组方式。本文选取下面4个取得较好优化效果的变异进化模式，并对其进行改进：

其中，λ，c1，c2是变异因子，在（0，1）上取值，r是（0，1）上的随机数。

模式（1）是标准的差分变异进化算法，从种群中随机选择个体Xr1、Xr2和Xr3。让基准个体Xr1和差向量Xr2－Xr3进行重组生成新个体Vi。该算法全局搜索能力强、不容易陷入局部搜索，但收敛速度慢，求解精度低。

模式（3）以当前种群中最优个体Xgbest作为基准个体，从准确中随机选择4个个体生成差向量：Xr1－Xr2和Xr3－Xr4，特点是收敛速度快、求解精度高，但对于多模态优化问题，容易陷入局部最优。

模式（2）以随机个体Xr1作为基准个体，用Xgbest（当前种群中最优个体）和Xpbest（随机选择的3个体中最优个体）分别和随着个体Xr2，Xr3作差，生成差向量：Xgbest－Xr1和Xpbest－Xr2。模式（4）借鉴粒子群优化算法思想，以局部最优个体Xpbest和种群最优个体Xgbest作为基准个体，随机选择2个体作差向量。模式（2）、模式（4）结合模式（1）和模式（3）的优缺点，在全局收敛性、局部收敛性和收敛速度等方面做了均衡，增强了算法的通用性，但算法的鲁棒性和求解精度任然较低。

上述变异进化模式（2）～模式（4）各自虽然针对差分进化算法的某一方面的缺点进行了改进，但对一些具体问题进行优化时性能表现各异，其一种算法并不能对所有问题通用有效，甚至同一问题在维度不同时（比如100维和200维），同一算法的有效性也有很多差异。为了使差分进化算法具有更强的通用性和鲁棒性，文献［4］随机从3种变异进化模式中随机选取一种用于不同个体的进化，虽然使得算法具有更强的通用性，但随机选取变异模式使得收敛速度明显降低。文献［5］中，两种不同的变异策略DE/rand/1和DE/best/1通过线性递减加权组合策略产生新的变异策略，算法也仅仅是在全局收敛和局部收敛做了一点平衡。

本文提出一种利用蚁群算法动态选择差分变异进化模式，算法根据个体进化中各模式对优化问题的有效性对权值进行动态调整，从而提高算法的收敛速度、稳定性和通用性。

2 算法描述

2.1 蚁群算法

蚁群算法（ant colony optimization algorithm，ACO）［10－11］也是新型仿生智能优化算法。ACO算法通过模仿蚂蚁寻食过程，利用蚂蚁群在寻找食物过程中留下的信息素，探索一条到食物源的最佳路径［12－13］。

2.2 基于蚁群算法的多模式差分变异

本文提出一种基于蚁群算法的多模式差分变异算法，使群体在进化过程中根据各变异进化算法的有效性动态调整其选择权值，个体在每代进化中根据变异进化模式（DO1，DO2，DO3，DO4）上的信息素（τ1，τ2，τ3，τ4）的大小采用轮盘赌选择算法选择变异算子，如图1所示。

（1）信息素的更新

设置初始信息素τ1（t0）＝τ2（t0）＝τ3（t0）＝τ4（t0）＝0.25，这样在进化开始时，各变异算子（DO1，DO2，DO3，DO4）被选中的概率相同。

为了提高进化效率，在个体的进化过程中根据各变异算子对进化所做的贡献更新信息素。更新规则如下

图1 基于蚊君算法的多模式差分进化过程

式中：M——种群中个体的数量（蚂蚁的数量），i＝1，2，…，M，ρ——信息素的蒸发率。max f、min f——当前种群中个体的最大、最小适应值。

（2）改进的自适应差分变异

本文提出一种自适应的并行变异策略，改进后变异算子可表示为：

其中，λ＝rand（1，D），rnd＝rand（1，D），rand（1，D）表示在（0，1）上产生一个D维的随机向量。

br＝｛s1s2，…，sD｝＝round（rand（1，D）＊ex），，（u∈［0.8，1.5］，σ∈［0.7，2］），t是当前进化代数。maxT是最大进化次数。D是维数，round（a）表示对a进行4舍5入取整。“.×”表示向量对应位的乘积，比如：（0.5，0.4，0.7，0.2）.×（1，0，1，0）＝（0.5，0，0.7，0）。

2.3 基于蚁群算法的自适应差分进化算法

算法步骤如下：

（1）参数初始化：设置种群大小 M，交叉概率p，信息素的蒸发率ρ＝0.2，变异参数（u，σ），最大迭代次数maxT，维数D，种群拥挤裁剪最小距离minL，进化终止条件等参数。

（2）在可行解空间内随机初始化种群。

（3）计算个体的适应度。

（4）利用本文提出的基于蚁群算法的差分变异算法对种群进行一次变异进化。

（5）利用交叉算子和选择算子对种群进行交叉和选择。

（6）混沌搜索：选择种群中最优个体Xgbest进行混沌迭代［14］，最大迭代次数设置为20。

（7）为了避免种群陷入局部搜索，采用种群拥挤距离裁剪策略［15］将种群中拥挤距离＜minL的部分个体剔除。

（8）产生新个体补充到种群，使得种群大小为保持为M。

（9）终止条件判断。如果迭代次数达到规定最大值或获得到理想的结果，则结束并输出结果，否则转到第（4）步继续下一代进化。

3 算法仿真分析

为了验证本文算法的性能，所使用的硬件环境为：方正Pentium 4CPU1.8GHz处理器，512MB内存，算法编码在MATLAB 2009（a）进行编程实现。测试选取了5个标准benchmark高维多模态测试函数（f1－f5）作为测试用例，将算法测试结果与 MEDE［4］进行比较。在所有测试函数中，设置参数u＝1.0，σ＝1.2。分别测试在维数D＝100和D＝200是的运行结果，让每个测试各自独立运行20次，并记录下平均进化次数（Gens），20次结果的最优值（Best），20次测试的平均值（Mean）及标准方差（Std），见表1。

表1 本文算法与MEDE算法在函数f1－f5上的测试结果比较

在测试中，实验同时记录了不同阶段4种变异进化模式上的信息素的变化过程，如图2、图3所示。通过图2和图3可以看出，对100维的函数f1，进化初期，DO3获得很高的信息素，DO1一直保持低水平的信息素，DO4在进化后期效果明显，信息素增加较快。而对函数f3和f1相比，变异进化模式DO1和DO3出现了相反的变化过程。这说明对于不同的问题往往解决方式有差异，本文通过基于蚁群算法的自适应多模式差分变异策略，使得算法面对具体问题时，能够根据进化的需要自适应的选择变异模式，从而提高收敛速度和解的精度。

图2 函数f1（100维）在进化过程中信息素变化曲线

从表1中可以看出，除了测试函数f3之外，其余函数在100和200维都能够在3000次以内获得高精度全局近似最优解。观察20次独立运行的结果发现，Best、Mean和Std在测试函数f1和f2上与MEDE算法比较接近，而测试函数f3－f5结果具有明显优势，并且进化代数和函数的评价次数也远低于MEDE。图4是函数f3在200维时的进化收敛曲线，由图可以明显看出，本文算法不论是收敛速度还是解的精度都明显优于MEDE算法。

4 结束语

传统差分进化算法存在收敛速度慢、鲁棒性低和通用性差等特点，并且同一变异算子对不同问题时，性能存在较大差异，甚至对同一函数在维度不同时也存在差异。为了提高算法的通用性，本文在传统的差分进化算法基础上提出了一种基于蚁群算法的自适应多模式差分进化算法，算法根据各变异算子对当前种群的进化效果进行动态调整各变异模式上的信息素，使得各变异算子发挥其最大性能。

［1］CHI Yuan－cheng，FANG Jie，CAI Guo－biao.Hybrid optimization algorithm based on differential evolution and particle swarm optimization［J］.Computer Engineering and Design，2009，30（12）：2963－2965（in Chinese）.［池元成，方杰，蔡国飙.基于差分进化和粒子群优化算法的混合优化算法［J］.计算机工程与设计，2009，30（12）：2963－2965.］

［2］TUO Shou－heng，WANG Wen－yong.Self－adaptive differential evolution algorithm based on orthogonal and niche elite for highdimensional multi－modal optimization［J］，Journal of Computer Applications，2011，31（4）：1094－1098（in Chinese）.［拓守恒，汪文勇.求解高维多模优化问题的正交小生境自适应差分演化算法［J］.计算机应用，2011，31（4）：1094－1098.］

［3］LU Feng，GAO Li－qun.Adaptive differential evolution algorithm based on multiple subpopulation with parallel policy［J］.Journal of Northeastern University（Natural Science），2010，31（11）：1538－1541（in Chinese）.［卢峰，高立群.基于多种群的自适应差分进化算法［J］.东北大学学报（自然科学版），2010，31（11）：1538－1541.］

［4］HE Yi－chao，WANG Xi－zhao.Convergent analysis and algorithmic improvement of differential evolution［J］.Journal of Software，2010，21（5）：875－885（in Chinese）.［贺毅朝，王熙照.差分进化的收敛性分析与算法改进［J］.软件学报，2010，21（5）：875－885.］

［5］GAO Yue－lin，LIU Jun－mei.Dynamic differential evolution algorithm with random mutation［J］.Journal of Computer Applications，2009，29（10）：2719－2722（in Chinese）.［高岳林，刘俊梅.一种带有随机变异的动态差分进化算法［J］.计算机应用，2009，29（10）：2719－2722.］

［6］CHI Yuan－cheng，FANG Jie，CAI Guo－biao.Center mutation based differential evolution［J］.Systems Engineering and Electronics，2010，32（5）：1105－1108（in Chinese）.［池元成，方杰，蔡国飙.中心变异差分进化算法［J］.系统工程与电子技术，2010，32（5）：1105－1108.］

［7］Storn R，Price K.Differential evolution－a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11（4）：341－359.

［8］YANG Qi－wen，CAI Liang，XUE Yuancan.A survey of differential evolution algorithms［J］.Pattern Recognition and Artificial Intelligence，2008，21（4）：506－513（in Chinese）.［杨启文，蔡亮，薛云灿.差分进化算法综述［J］.模式识别与人工智能，2008，21（4）：506－513.］

［9］Noman N，Iba H.Enhancing differential evolution performance with local search for high dimensional function optimization［C］.Beyer HG，et al.Proc of the Conf on Genetic and Evolutionary Computation.New York：ACM Press，2005：967－974.

［10］Zhang Jun，Hu Xiaomin，Tan X.Implementation of an ant colony optimization technique for job shop scheduling problem［J］.Transactions of the Institute of Measurement and Control，2006，28（1）：93－108.

［11］Cai Zhaoquan，Huang Han.Ant colony optimization algorithm based on adaptive weight and volatility parameters［C］.Shanghai：IEEE Press，2008：75－79.

［12］Li Yancang，Li Wanqing.Adaptive ant colony optimization algorithm based on Information entropy［J］.Foundation and Application，Fundamental Informaticae，2007，77（3）：229－242.

［13］XIAO Jing，LI Liang－ping.Adaptive ant colony algorithm based on information entropy［J］.Computer Engineering and Design，2010，31（22）：4873－4876（in Chinese）.［肖菁，李亮平.基于信息熵调整的自适应蚁群算法［J］.计算机工程与设计，2010，31（22）：4873－4876.］

［14］DENG Ze－xi，LIU Xiao－Ji.Chaotic mutation differential evolution algorithm combined with niche［J］.Computer Engineering and Applications，2010，46（25）：31－33（in Chinese）.［邓泽喜，刘晓冀.基于小生境的混沌变异差分进化算法［J］.计算机工程与应用，2010，46（25）：31－33.］

［15］Tseng Lin－Yu，Chen Chun.Multiple trajectory search for large scale global optimization［C］.IEEE Congress on Evolutionary Computation，2008：3052－3059.