ABSTRACT

DE/rand/1/bin model of DE Algorithm has good global performance, but its convergence speed is slow. A modified differential evolution optimization algorithm named IWOMDE was presented in this paper based on Invasive Weed Optimization algorithm. The IWOMDE algorithm incorporated IWO’s design philosophy into Differential Evolution (DE) algorithm. The IWOMDE algorithm divided the evolution population into elite individuals and poor individuals based on the average fitness of population. The elite individuals can be evolutionary many times, but the poor individuals are less evolved or “stagnate” in order to maintain the diversity of population. The simulation results showed the hybrid optimization algorithm has the advantage of searching effectively and being fairly robust to initial conditions.

Keywords:Differential Evolution (DE) Algorithm, Invasive Weed Optimization (IWO), Elite Individual, Function Optimization

一种基于入侵杂草算法改进的差分进化算法

卢青波，崔巍，闫生辉，李廷锋

郑州职业技术学院机械工程系，河南 郑州

收稿日期：2019年1月16日；录用日期：2019年1月28日；发布日期：2019年2月12日

摘 要

差分进化算法(Differential Evolution, DE)的DE/rand/1/bin模式具有良好的全局性能，但其收敛速度慢，针对此，应用入侵杂草算法(Invasive Weed Optimization, IWO)的设计思想，研究提出一种改进的差分进化算法(Modified Differential Evolution Algorithm based on Invasive Weed Optimization, IWOMDE)。该算法依据IWO算法思想，以群体平均适应度为划分依据，将群体中的个体划分为优秀个体与较差个体，对优秀个体使其能够多进化，而较差个体少进化或者“停滞”以维持种群的多样性。仿真实验结果表明，IWOMDE算法对多峰多模态函数具有优化效率高、优化精度高的特性。

关键词 :差分进化算法，入侵杂草算法，精英个体，函数优化

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

进化算法是模仿生物进化过程设计的现代优化方法，作为一种有效的随机优化方法，被广泛应用于求解复杂优化问题。DE算法 [1] 使用浮点矢量进行个体编码，通过简单的变异、交叉及竞争算子实现在连续空间中的随机搜索。DE算法原理简单，易于理解和实现，在许多复杂优化问题中得到了应用 [2] [3] [4] [5] [6] 。DE算法同其它进化算法类似，需要平衡算法的全局搜索能力与其收敛速度。这种平衡可以通过调节算法的控制参数来实现，但往往控制参数的调节效果有限 [7] [8] ，对于DE算法，交叉率大则收敛速度快，但其全局搜索能力下降，易陷入局部最优，从而使算法的收敛精度下降。因此，许多学者从不同类型算法的优势出发，结合DE算法的全局性能和一些局部优化算法的局部搜索能力，研究提出了不同的混合优化算法 [9] [10] 。这些对DE算法的改进从不同的侧面使算法的性能得到了提升，但都未对DE算法的候选解产生过程有较大的改变。DE算法候选解的产生采用的从种群中随机选择不同个体，通过线性运算产生，该变异过程并没有考虑所选择个体的适应度信息，随机性强，有利于保持种群的多样性，但同时也使算法的收敛速度较慢。

入侵杂草算法(Invasive Weed Optimization, IWO) [11] 于2006年提出，是模拟杂草在自然界中生长过程的一种新的优化算法，该算法的种群是由杂草组成，通过杂草在空间的扩散、生长、繁殖和竞争进行寻优，算法具有鲁棒性强、易于实现等特点。IWO算法在进化过程中，杂草会依据适应度值进行繁殖，适应度较优的个体会产生较多的种子，且所产生的种子是以正态分布在该种子的周围。这种思想使得较优个体占有较强的优势，且兼顾了局部搜索。本文将基于该思想研究提出一种改进的差分进化算法(A Modified Differential Evolution Algorithm based on Invasive Weed Optimization, IWOMDE)。

2. IWOMDE算法

2.1. 差分进化算法

DE算法的进化个体采用实向量进行编码，采用均匀分布的随机数产生初始个体。令 $x_i\left(g\right)$ 代表第g代的第i个个体， $x_i^L\le x_i\left(g\right)\le x_i^U$ ，则

$x_i\left(g\right)=\left(x_{i1}\left(g\right),x_{i2}\left(g\right),\cdots ,x_{in}\left(g\right)\right),i=1,2,\cdots ,\text{NP};g=1,2,\cdots ,T_{\max }$ (1)

式中， $x_i^U$ 、 $x_i^L$ 分别为个体的上、下限，NP为种群大小， $T_{\max }$ 为最大进化代数。

DE算法就是由这NP个个体构成的种群在搜索空间不断进化来进行寻优的。DE算法候选解产生模式有很多种策略 [1] ，其中DE/rand/1/bin策略应用较为广泛，且具有全局搜索能力较好，收敛速度较慢的特性，因此，本文选择该进化模式为研究对象。以求解最小值问题为例说明差分进化算法的进化过程如下。

1) 初始化种群

在n维实数空间按式(2)随机产生NP个个体

$x_{ij}\left(0\right)=x_{ij}^L+rand\left(0,1\right)\left(x_{ij}^U-x_{ij}^L\right)$ (2)

式中， $rand\left(0,1\right)$ 是 $\left[0,1\right]$ 上服从均匀分布的随机数。

2) 变异算子

首先随机从种群中选择3个不同个体 $x_{p1},x_{p2},x_{p3}$ ，且 $p1\ne p2\ne p3\ne i$ 则变异算子为

$h_{ij}\left(g\right)=x_{p1j}+F\left(x_{p2j}-x_{p3j}\right)$ (3)

式中，F为缩放因子。

3) 交叉算子

交叉算子可以增加种群的多样性，其操作过程如式(4)所示。

$v_{ij}\left(g+1\right)=\{\begin{array}{l}{h}_i{}_j\left(g\right),rand\left(0,1\right)\le \text{CR}或j=j_{rand}\\ x_{ij}\left(g\right),rand\left(0,1\right)>\text{CR}或j\ne j_{rand}\end{array}$ (4)

式中，CR为交叉率， $\text{CR}\in \left[0,1\right]$ ， $j_{rand}$ 是 $\left[1,n\right]$ 上的随机整数，这种交叉模式确保 $v_{ij}\left(g+1\right)$ 中至少有一位来自 $h_{ij}\left(g\right)$ 。

4) 选择算子

DE算法的选择策略采用“贪婪”策略，由评价函数对向量 $v_i\left(g+1\right)$ 和向量 $x_i\left(g\right)$ 比较，保留较优个体，即

$x_i\left(g+1\right)=\{\begin{array}{l}{v}_i\left(g+1\right),f\left(v_i\left(g+1\right)\right)<f\left(x_i\left(g\right)\right)\\ x_i\left(g\right),f\left(v_i\left(g+1\right)\right)\ge f\left(x_i\left(g\right)\right)\end{array}$ (5)

反复执行式(3)到(5)，直到达到算法预设的终止条件。

2.2. IWOMDE算法

DE算法的变异策略有多种，其中DE/rand/1/bin变异策略具有全局搜索能力强、收敛速度慢的特性。由式(3)可知，DE/rand/1/bin变异过程中，其候选解的产生是采用的是种群中随机选择的3个不同个体，通过线性运算产生的。该变异过程并没有考虑所选择个体的适应度信息，随机性强，有利于保持种群的多样性，但同时也使算法的收敛速度较慢。

DE算法的随机搜索过程，使得算法的局部搜索能力较差，收敛速度慢，这主要是由于进化过程中，尤其是在候选解的产生过程中未考虑个体的适应度引起的，因此，借鉴IWO算法的进化思想，将适应度的信息融入候选解的生成过程，使较优的个体能够产生较多的候选解，较差的个体产生较少的候选解或者保持停滞状态。这样不但能够使最优个体引导群体快速收敛，而且由于有个体随机停滞现象，能够很好地保持群体的多样性。

1) 优秀个体的选取

群体适应度均值

$f_{avg}=\frac{1}{\text{NP}}{\displaystyle \underset{i=1}{\overset{\text{NP}}{\sum }}{f}_i}$ (6)

式中， $f_i$ 为第i个个体的适应度。

选取 $f_i<f_{avg}$ 个体为最优个体，其余个体为较差个体。

2) 修正的变异算子

基于以上个体定义，针对差分进化算法的变异算子，对不同类型的个体进行不同的变异算子设计。对于优秀个体，使其以较大概率进化，若进化成功，则继续执行进化过程以加快算法的收敛速度。对于较差个体，以较小概率进化或者停滞，使其能够保证群体的多样性。

优秀个体进化过程如下：

Step1：变异算子

if $\left(rand\left(0,1\right)<P_1\right)$

$h_{ij}\left(g\right)=\left[1+\sigma \left(0,1\right)\right]x_{ij}+F\left(x_{gbestj}-x_{ij}\right)$ (7)

else

$h_{ij}\left(g\right)=x_{p1j}+F\left(x_{p2j}-x_{p3j}\right)$

Step2：执行式(4)的交叉算子

Step3：执行式(5)的选择算子

Step4：if $\left[f\left(x_i\left(g+1\right)\right)<f\left(x_i\left(g\right)\right)\right]$ ，转Step1继续进化。

较差个体的进化过程如下：

if $\left(rand\left(0,1\right)<1-P_1\right)$

$h_{ij}\left(g\right)=x_{p1j}+F\left(x_{p2j}-x_{p3j}\right)$

执行式(4)的交叉算子与式(5)的选择算子。

else

停滞。

式中 $P_1$ 为优秀个体进化概率， $\sigma \left(0,1\right)$ 为服从均值为0，方差为1的正态分布随机数。

设置 $P_1$ 为较大值(如0.9)则优秀个体会以该概率执行局部搜索，能够增强算法的局部探索能力；而较差个体进化概率为 $1-P_1$ ，这些个体起到维持种群多样性的作用。若 $P_1$ 为0，则优秀个体的变异算子中的式(7)不会被执行，变异算子退化为DE算法的变异过程，只是在优秀个体更新完后，若竞争成功，则继续进化；而此时，对于较差个体，会按照DE算法的进化过程正常进化，不会出现停滞现象。若 $P_1$ 设置为1，则对于优秀个体的变异算子完全由式(7)决定，而对于较差个体则处于完全停滞状态，即整个算法只有优秀个体进化，其余个体处于停滞状态。IWOMDE算法正是基于以上思想进行设计的，其实现步骤如下。

Step1：设置种群规模NP、交叉概率CR、缩放因子F，计算精度 $\epsilon$ 及优秀个体进化概率 $P_1$ ，在参数空间随机初始化每一个个体，设置最大进化代数为T，令 $t=1$ 。

Step2：计算当前种群的最优适应度bestfitness及最优个体 $x_{gbest}$ 。

Step3：若最优适应度bestfitness达到精度要求或者迭代次数达到最大，则输出当前最优适应度值，退出；否则，转Step4。

Step4：依据式(6)计算当前群体的平均适应度；

Step5：对群体中的所有个体执行

若 $f_i<f_{avg}$ 按优秀个体进行进化；否则，按较差个体进化。

Step6 $t=t+1$ ，转Step2。

3. 仿真结果及分析

3.1. 仿真测试设置

由于IWOMDE算法在DE算法的基础上改进的，并且引入了优秀个体进化概率 $P_1$ ，因此，首先对该引入参数对算法的影响进行仿真分析，然后对IWOMDE算法与其它算法进行比较分析。

采用5个典型的测试函数，与DE算法(DE/rand/1/bin模式)进行比较。 $f_1$ 为Schaffer函数，该函数在全局极大点范围内有无限多的局部极大点，很难全局最优化。 $f_2$ 为Ackley函数，该函数带有指数项，存在大量局部最优解。 $f_3$ 为Rosenbrock函数，该函数是一个非凸病态函数，很难实现全局最优化。 $$ 为Rastrigin函数，该函数是一个多峰函数，在定义域内大约存在10n个局部极小点。 $f_5$ 为Griewank函数，该函数是一个多峰函数，存在大量局部极小点。

$f_1=0.5-\frac{\left({\sin }^2\sqrt{x_1^2+x_2^2}-0.5\right)}{{\left(1+0.001\left(x_1^2+x_2^2\right)\right)}^2}-100\le x_1,x_2\le 100,$

$-32.768\le x_i\le 32.768$

$f_3={\displaystyle \underset{i=1}{\overset{29}{\sum }}\left(100{\left(x_i^2-x_{i+1}^2\right)}^2+{\left(x_i-1\right)}^2\right)}-2.048\le x_i\le 2.048,$

$f_4={\displaystyle \underset{i=1}{\overset{30}{\sum }}\left(x_i-10\cos \left(2\text{π}{x}_i\right)+10\right)}-5.12\le x_i\le 5.12,$

为了使算法的比较更公平，采用函数评价次数为终止条件。算法的其它参数设置如表1所示。

表1. 算法实验参数设置

3.2. 测试结果及分析

为避免仿真结果的随机性，IWOMDE算法对每个函数均独立运行30次。图1~图3为IWOMDE算法在取不同优秀个体进化概率 $P_1$ 时，求解3个Benchmarks函数时30次运行的平均适应度及最优适应度的比较。其中横坐标为 $P_1$ 的取值，纵坐标为适应度值。从图中可以看出，优化结果随着 $P_1$ 值的增大，平均最优适应度越来越优，而最优适应度存在随机性，这主要原因是群体的进化过程由式(5)决定的成分越来越多，能够进化的个体越来越少，较差个体在群体中的作用逐渐被忽略，从而改变了群体原有的进化进程，尽管在 $P_1$ 取值为1时，获得的平均适应度最优，但其最优适应度不全是最优，因此，在实验中建议设置 $P_1$ 为较接近1.0的值，本文后面的实验中取该参数为0.9。

表2给出了IWOMDE算法与SMDE算法 [9] 的优化结果比较，从表中数据可以看出，IWOMDE算法除Ronsenbrock函数的优化结果要差于SMDE获得的结果之外，其余结果都要优于SMDE的优化结果。SMDE算法采用的是固定进化代数为终止条件，函数评价次数是未知的，而IWOMDE算法采用固定的

图1. 不同P₁值时f₁(x) 30次平均适应度及最优适应度比较

图2. 不同P₁值时f₂(x) 30次平均适应度及最优适应度比较

图3. 不同P₁值时f₃(x) 30次平均适应度及最优适应度比较

函数评价次数为终止条件，因此，IWOMDE算法在相同函数评价次数下，性能应优于SMDE算法的性能。

表2. IWOMDE与SMDE函数优化结果比较

表3给出了IWOMDE算法与ADE算法 [7] 的优化结果比较，其中IWOMDE算法的最大函数评价次数对于f₄和f₅为2e4，而对于f₃设置为2e5。由于ADE算法F的范围为[0.5, 1.0]，CR的范围为[0.5, 1.0]，因此IWOMDE设置F为0.5，CR设置为[0.5, 1.0]上的均匀分布的随机数。三个测试函数的维数均为20维。表3给出了IWOMDE与ADE算法的优化结果比较，从表中数据可以看出，对于Rosenbrock函数，ADE的优化结果要优于IWOMDE算法，但对于Rastrigin函数与Griewank函数，IWOMDE算法表现出了更好的优化性能，不仅获得了较好的函数优化结果，而且只用了ADE函数评价次数的1/10，表明收敛速度要远远优于ADE 算法。

表3. IWOMDE与ADE函数优化结果比较

表4给出了IWOMDE算法与ONDE算法 [12] 的优化结果比较，四个测试函数的维数设置为100维，函数评价次数设置为6e4。从表中数据可以看出，IWOMDE算法与ONDE算法的结果各有优劣，IWOMDE算法在f₂与f₅上的优化结果要优于ONDE算法，在f₄的最优值上也要优于ONDE算法，但在f₃上优化结果要比ONDE算法差很多。

表4. IWOMDE与ONDE函数优化结果比较

综合以上分析可以发现，IWOMDE算法在多峰函数上的优化结果要优于比较算法，但对于单峰病态函数Rosenbrock函数，优化结果较差。这主要原因是对于多峰函数，由于群体进化过程中，优秀个体使群体能够快速收敛到较优点，而较差个体的停滞进化，使群体维持了较好的多样性，从而为优秀个体跳出局部最优点提供了较好的帮助。

4. 结语

DE算法的DE/rand/1/bin进化模式具有全局搜索能力的特性，被广泛应用于实际问题求解中，但其收敛速度较慢，局部搜索能较差。为使DE算法能够实现快速收敛，且具有很强的搜索精度，本文提出了一种简单易实现的IWOMDE算法，该算法受入侵杂草算法(IWO)启发，将进化群体依据群体适应度均值进行划分为优秀个体与较差个体，对两种不同个体采用不同的变异算子。多个Benchmarks函数的优化结果表明，IWOMDE具有收敛速度快，对于多峰函数有较强的优化效率，但对于单峰病态函数优化效率不高的特点，可广泛应用于各种实际工程优化问题中。

文章引用

卢青波,崔 巍,闫生辉,李廷锋. 一种基于入侵杂草算法改进的差分进化算法
A Modified Differential Evolution Algorithm Based on Invasive Weed Optimization[J]. 计算机科学与应用, 2019, 09(02): 266-274. https://doi.org/10.12677/CSA.2019.92031

参考文献