基于微分进化的改进杂草优化算法

陶 玲，高晓智

(1.上海海事大学 信息工程学院，上海 201306;2.芬兰阿尔托大学，赫尔辛基 00076)

入侵杂草优化算法［1］即Invasive Weed Optimization，在 2006 年由伊朗的 A.R.Mehrabian和 C.Lucas在Ecological Informatics杂志上发表的一篇论文中首次提出。它是一种模拟自然界杂草繁殖过程的随机搜索方法，包括杂草入侵的种子空间扩散、生长、繁殖和竞争等过程，具有很强的鲁棒性和自适应性，且算法简单，易于实现。到目前为止，该算法已成功应用于基因调控网络中的模糊神经模型的知识提取［2］、文本特征选择［3］、DNA计算编码序列的设计［4］等众多领域。

在标准的IWO算法中，随着迭代次数的增加，杂草个体产生种子，种子个体以父代杂草为均值，正态分布于杂草周围。正是由于这种扩散机制，使得个体之间不存在信息交换，导致迭代后期种群多样性差，局部搜索能力降低。同时，在标准IWO中存在以适应度为基准的繁殖机制。尽管这种机制给予了适应度差的个体生存和繁殖的机会，但适应度小的个体相应产生的种子也少，最终很有可能被直接剔除。这样随着繁殖的继续，就会丢失很多有用信息，使算法陷入局部最优。为此，2008年Zhang等［5］提出一种基于文化框架的IWO算法(CIWO)，引入信念空间提高算法的局部寻优能力，使算法的收敛速度加快;2009年，Hajimirsadeghi等［6］将IWO和 PSO两种算法进行融合，将PSO中粒子的速度和位移公式引入到杂草繁殖的种子个体中，使种子个体像PSO中的粒子一样拥有速度，然后再对种子进行正态分布扩散，避免了算法陷入局部最优;2010年，Zhang等［7］又提出了一种改进的 IWO算法(MIWO)，在杂草产生后代时引入交叉算子以改进算法性能;2012年，Chen等［8］提出了一种基于混沌序列的多种群杂草算法，引入混沌序列和多种群机制来避免算法早熟，提高算法收敛速度和寻优精度;2013年，Peng等［9］将遗传算法中的交叉和变异操作加入到IWO算法中，改善了算法的全局优化性能，获得了较好的效果。

本文提出的IWODE算法在父代杂草个体繁殖种子后，引入一个随机数对种子个体进行改进，以提高种子个体的质量，然后对繁殖一代后的种群引入差分进化算法中的变异、交叉和选择思想，增加种群多样性，提高算法性能。采用9个benchmark函数进行实验。实验结果表明:IWODE算法是有效的，其收敛精度和稳定性均有较大提高。

1 IWO算法

IWO算法基本流程［10］包括以下5个步骤:

1)初始化种群。杂草个体随机扩散在D维搜索空间，初始种群大小可根据实际问题具体确定。

2)生长繁殖。杂草个体根据其适应度产生种子，适应度大的产生种子多，适应度小的产生种子少。父代杂草个体产生种子数与其适应度成线性关系，如图1所示。

图1 杂草产生种子的示意图

3)空间扩散。子代个体以正态分布的方式扩散在D维空间中，以父代杂草为均值。每代扩散步长的计算如下:

其中，iter为当前迭代次数。

4)竞争排除。当繁殖数代后，种群规模超过环境的承受能力，则需要按照适应度进行淘汰，以达到种群上限要求。

5)重复步骤2)～4)，若达到最大迭代次数或最大种群规模，则结束循环，输出最优解。

算法流程如图2所示。

图2 IWO算法流程

2 IWODE算法模型

IWODE算法流程如图3所示。

图3 IWODE算法流程

2.1 对种子个体的改进

在解决连续性的工程问题时，种子个体采用正态分布的方式扩散在父代杂草周围，这是杂草优化算法与其他优化算法的最大区别。由于本文求解的都是标准测试函数的极小值，所以在产生子代个体时，引入一个0～1之间的随机数可以提高子代个体的质量，使得最终结果更加逼近最优解。种子个体正态分布计算见式(2)和(3)。

其中:delta_iter为标准差;X(i，:)为父代杂草个体。

2.2 对繁殖后的父子代种群的改进

在竞争排除前，对于繁殖了的种群，父代和子代个体一起，引入差分进化(DE)算法［11］中的变异操作，见式(4);随机选择待变异的个体，产生中间种群，然后对当代种群及其变异产生的中间种群进行个体间的交叉操作，见式(5);以一定的交叉概率判断是否将中间种群的个体保留到下一代，最后对交叉后的种群进行选择操作，见式(6);然后根据适应度值的大小判定要选择的进入下一代的个体。

DE算法中的变异操作:

其中:i≠r1≠r2≠r3;G为压缩因子;xi(g)表示第g代种群中第i个个体。

DE算法中的交叉操作:

其中，CR为交叉概率 jrand∈［1，2，…，dim］的随机整数。

DE算法中的选择操作:

其中，f为测试函数。

2.3 IWODE算法复杂度分析

IWODE算法描述如下:

步骤1 产生初始种群个体数为M0个;

步骤2 根据适应度函数计算每个个体的适应度值，找到最大和最小适应度值;

步骤3 当iter=1，while iter＜=itmax;

步骤3.1 根据适应度值计算每个父代个体产生的种子数;

步骤3.2 根据式(1)计算每代种群正态分布的标准差;

步骤3.3 根据式(2)和(3)将种子个体正态分布于父代个体周围;

步骤3.4 根据适应度函数计算每个种子个体的适应度值;

步骤3.5 将新的种子个体加入到父代种群中构成父子代种群;

步骤3.6 根据适应度函数计算父子代种群每个个体的适应度值;

步骤3.7 对于父子代种群中的每个个体:

当 it=1，while it＜ =100;

① 根据式(4)、(5)、(6)对个体引入DE中的3种操作;

② it=it+1，end while;

步骤3.8 对于新的种群:

if M＞Mmax;

①根据适应度值将新的种群个体排序;

②排除多余的个体直到M=Mmax;

步骤 3.9 iter=iter+1，end while;

步骤4 输出最优解。

在IWODE算法中，最坏情况下的复杂度估计如下:

1)在步骤1中，时间复杂度，初始化M0个个体;

2)在步骤2中，计算每个个体的适应度值;

3)在步骤3.1中，计算每个父代个体产生的种子数;

4)在步骤3.2中，计算每代种群正态分布的标准差;

5)在步骤3.3中，种子个体正态分布于父代个体周围;

6)在步骤3.4中，计算每个种子个体的适应度值;

7)在步骤3.6中，计算父子代种群每个个体的适应度值;

8)在步骤3.7中，引入DE操作，更新父子代种群。

以上是IWODE算法的复杂度估计，其他步骤中算法复杂度较低，可以忽略。

3 实验结果与分析

3.1 实验平台

所有仿真实验均在Windows 7操作系统，CPU为酷睿 i3－2375，主频为1.50 GHz，内存为2 GB的计算机上完成，采用Matlab编程。

3.2 IWODE和IWO算法参数设置

两种算法涉及到的所有参数设置见表1。分别对9个测试函数进行仿真，所有测试函数均独立运行50次，每个函数每次迭代50代。

表1 算法参数设置

3.2.1 实验结果

表2是本文采用的测试函数，其中:f1，f2，f3，f7，f8是单峰函数，f4，f5，f6，f9是多峰函数。

表3是IWODE与IWO独立运行50次的测试结果比较。图4～12是9个函数分别迭代1 000代的收敛曲线。

表2 benchmark函数

图4 函数f1的收敛曲线

图5 函数f2的收敛曲线

图6 函数f3的收敛曲线

图7 函数f4的收敛曲线

图8 函数f5的收敛曲线

图9 函数f6的收敛曲线

图10 函数f7的收敛曲线

图11 函数f8的收敛曲线

图12 函数f9的收敛曲线

3.2.2 结果分析

从表3可以看出:IWODE的各项测试结果几乎均优于 IWO。对于 f1，f2，f3，f5，f6，f7，f9，IWODE的最优值、最差值、平均值和标准差均远优于IWO。IWODE完全找到了相应测试函数的全局最优解，它的寻优精度和稳定性相比IWO要高很多。对于f4，IWODE的最优值、最差值、平均值和标准差相比IWO分别高15，8，10，9个数量级。对于f8，虽然IWODE的最优值次于IWO，但IWODE的最差值、平均值和标准差都比IWO好。以上结果表明:IWODE算法可行有效，且有较高的寻优精度和稳定性。

图4～12是9个函数分别迭代1 000代的测试函数收敛曲线。图4，5，6，10，11 分别是 f1，f2，f3，f7和 f8这 5 个单峰函数的收敛曲线，图7，8，9，12分别是f4，f5，f6，f9这4个多峰函数的收敛曲线。从图4～11可以看出:IWODE算法的收敛速度较IWO好，最后获得的最优解优于IWO算法。而在图12中，IWODE算法的收敛速度明显快于IWO算法，且求得的最优解也优于IWO。以上结果表明:IWODE算法适合高维函数寻优，无论函数是单峰的还是多峰的。

3.3 IWODE和GA、PSO的比较

为进一步表明本文算法的有效性，将IWODE和GA、PSO进行比较，选择函数f4进行测试。其中，函数独立运行次数为50，维数为30，IWODE其余参数设置与表1相同。表4为仿真结果，表中的成功率定义为:n/50(n表示50次运行结果中最优解＜0.005的次数)。

表4 仿真结果

从表4可以看出:IWODE的寻优精度优于GA和PSO，IWODE的平均值分别优于GA和PSO 13，12个数量级，并且IWODE算法相比GA和PSO在迭代次数较少的情况下获得了更好的结果。

4 结束语

本文针对基本IWO算法的不足，对产生的种子个体进行改进，以提高种子个体质量，从而提高算法的寻优精度，同时在父子代种群中引入差分进化算法中的各种思想，增加后期种群多样性，改善了算法的全局寻优能力和算法的稳定性。本文还将IWODE与PSO和GA进行比较。从仿真结果可以看出:IWODE算法取得了较好的结果。

［1］MEHRABIAN A R，LUCAS C A.novel numerical optimization algorithm inspired from weed colonization［J］.Ecological Informatics，2006，1(4):355－366.

［2］PRATYUSHA RAKSHIT，PAPIA DAS，AMIT KONAR，et al.A recurrent fuzzy neural model of a gene regulatory network for knowledge extraction using invasive weed and artificial bee colony optimization algorithm［C］//1st Int’1 Conf.on Recent Advances in Information Technology|RAIT－2012|.Piscataway:IEEE，2012.

［3］刘逵.基于野草算法的文本特征选择研究［D］.重庆:西南大学，2013.

［4］ZHANG XUNCAI，WANG YANFENG，CUI GUANGZHAO，et al.Application of a novel IWO to the design of encoding sequences for DNA computing［J］.Computers and Mathematics with Applications，2009，57(11/12):2001－2008.

［5］ZHANG XUNCAI，XU JIN，CUI GUANGZHAO，et al.Research on invasive weed optimization based on the cultural framework［C］//BICTA 2008:Proceedings of the 3rd International Conference on Bio-Inspired Computing:Theories and Applications.Piscataway:IEEE，2008:129－134.

［6］HAJIMIRSADEGHI H，LUCAS.A hybrid IWO/PSO algorithm for fast and global optimization［C］//IEEE EUROCON 2009.Piscataway:IEEE，2009:1964－1971.

［7］ZHANG XUNCAI，NIU YING，CUI GUANGZHAO，et al.A modified invasive weed optimization with crossover operation［C］//Proceedings of the 8th World Congress on Intelligent Control and Automation.Piscataway:IEEE，2010:11－14.

［8］陈欢，周永权，赵光伟.基于混沌序列的多种群入侵杂草算法［J］.计算机应用，2012，32(7):1958－1961.

［9］彭斌，胡常安，邵兵，等.求解TSP问题的混合杂草优化算法［J］.振动、测试与诊断，2013，33(z1):66－69.

［10］贾盼龙，田学民.基于自适应小生境的改进入侵性杂草优化算法［J］.上海电机学院学报，2012，15(4):225－230.

［11］杨启文，蔡亮，薛云灿.差分进化算法综述［J］.模式识别与人工智能，2008，21(4):506－513.