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算法的进化个体采用实向量进行编码,采用均匀分布的随机数产生初始个体。令
代表第g代的第i个个体,
,则
(1)
式中,
、
分别为个体的上、下限,NP为种群大小,
为最大进化代数。
DE算法就是由这NP个个体构成的种群在搜索空间不断进化来进行寻优的。DE算法候选解产生模式有很多种策略 [1] ,其中DE/rand/1/bin策略应用较为广泛,且具有全局搜索能力较好,收敛速度较慢的特性,因此,本文选择该进化模式为研究对象。以求解最小值问题为例说明差分进化算法的进化过程如下。
1) 初始化种群
在n维实数空间按式(2)随机产生NP个个体
(2)
式中,
是
上服从均匀分布的随机数。
2) 变异算子
首先随机从种群中选择3个不同个体
,且
则变异算子为
(3)
式中,F为缩放因子。
3) 交叉算子
交叉算子可以增加种群的多样性,其操作过程如式(4)所示。
(4)
式中,CR为交叉率,
,
是
上的随机整数,这种交叉模式确保
中至少有一位来自
。
4) 选择算子
DE算法的选择策略采用“贪婪”策略,由评价函数对向量
和向量
比较,保留较优个体,即
(5)
反复执行式(3)到(5),直到达到算法预设的终止条件。
2.2. IWOMDE算法
DE算法的变异策略有多种,其中DE/rand/1/bin变异策略具有全局搜索能力强、收敛速度慢的特性。由式(3)可知,DE/rand/1/bin变异过程中,其候选解的产生是采用的是种群中随机选择的3个不同个体,通过线性运算产生的。该变异过程并没有考虑所选择个体的适应度信息,随机性强,有利于保持种群的多样性,但同时也使算法的收敛速度较慢。
DE算法的随机搜索过程,使得算法的局部搜索能力较差,收敛速度慢,这主要是由于进化过程中,尤其是在候选解的产生过程中未考虑个体的适应度引起的,因此,借鉴IWO算法的进化思想,将适应度的信息融入候选解的生成过程,使较优的个体能够产生较多的候选解,较差的个体产生较少的候选解或者保持停滞状态。这样不但能够使最优个体引导群体快速收敛,而且由于有个体随机停滞现象,能够很好地保持群体的多样性。
1) 优秀个体的选取
群体适应度均值
(6)
式中,
为第i个个体的适应度。
选取
个体为最优个体,其余个体为较差个体。
2) 修正的变异算子
基于以上个体定义,针对差分进化算法的变异算子,对不同类型的个体进行不同的变异算子设计。对于优秀个体,使其以较大概率进化,若进化成功,则继续执行进化过程以加快算法的收敛速度。对于较差个体,以较小概率进化或者停滞,使其能够保证群体的多样性。
优秀个体进化过程如下:
Step1:变异算子
if
(7)
else
Step2:执行式(4)的交叉算子
Step3:执行式(5)的选择算子
Step4:if
,转Step1继续进化。
较差个体的进化过程如下:
if
执行式(4)的交叉算子与式(5)的选择算子。
else
停滞。
式中
为优秀个体进化概率,
为服从均值为0,方差为1的正态分布随机数。
设置
为较大值(如0.9)则优秀个体会以该概率执行局部搜索,能够增强算法的局部探索能力;而较差个体进化概率为
,这些个体起到维持种群多样性的作用。若
为0,则优秀个体的变异算子中的式(7)不会被执行,变异算子退化为DE算法的变异过程,只是在优秀个体更新完后,若竞争成功,则继续进化;而此时,对于较差个体,会按照DE算法的进化过程正常进化,不会出现停滞现象。若
设置为1,则对于优秀个体的变异算子完全由式(7)决定,而对于较差个体则处于完全停滞状态,即整个算法只有优秀个体进化,其余个体处于停滞状态。IWOMDE算法正是基于以上思想进行设计的,其实现步骤如下。
Step1:设置种群规模NP、交叉概率CR、缩放因子F,计算精度
及优秀个体进化概率
,在参数空间随机初始化每一个个体,设置最大进化代数为T,令
。
Step2:计算当前种群的最优适应度bestfitness及最优个体
。
Step3:若最优适应度bestfitness达到精度要求或者迭代次数达到最大,则输出当前最优适应度值,退出;否则,转Step4。
Step4:依据式(6)计算当前群体的平均适应度;
Step5:对群体中的所有个体执行
若
按优秀个体进行进化;否则,按较差个体进化。
Step6
,转Step2。
3. 仿真结果及分析
3.1. 仿真测试设置
由于IWOMDE算法在DE算法的基础上改进的,并且引入了优秀个体进化概率
,因此,首先对该引入参数对算法的影响进行仿真分析,然后对IWOMDE算法与其它算法进行比较分析。
采用5个典型的测试函数,与DE算法(DE/rand/1/bin模式)进行比较。
为Schaffer函数,该函数在全局极大点范围内有无限多的局部极大点,很难全局最优化。
为Ackley函数,该函数带有指数项,存在大量局部最优解。
为Rosenbrock函数,该函数是一个非凸病态函数,很难实现全局最优化。
为Rastrigin函数,该函数是一个多峰函数,在定义域内大约存在10n个局部极小点。
为Griewank函数,该函数是一个多峰函数,存在大量局部极小点。
![](//html.hanspub.org/file/10-1541285x62_hanspub.png)
为了使算法的比较更公平,采用函数评价次数为终止条件。算法的其它参数设置如表1所示。
![](Images/Table_Tmp.jpg)
Table 1. Experimental parameter setting of algorithm
表1. 算法实验参数设置
3.2. 测试结果及分析
为避免仿真结果的随机性,IWOMDE算法对每个函数均独立运行30次。图1~图3为IWOMDE算法在取不同优秀个体进化概率
时,求解3个Benchmarks函数时30次运行的平均适应度及最优适应度的比较。其中横坐标为
的取值,纵坐标为适应度值。从图中可以看出,优化结果随着
值的增大,平均最优适应度越来越优,而最优适应度存在随机性,这主要原因是群体的进化过程由式(5)决定的成分越来越多,能够进化的个体越来越少,较差个体在群体中的作用逐渐被忽略,从而改变了群体原有的进化进程,尽管在
取值为1时,获得的平均适应度最优,但其最优适应度不全是最优,因此,在实验中建议设置
为较接近1.0的值,本文后面的实验中取该参数为0.9。
表2给出了IWOMDE算法与SMDE算法 [9] 的优化结果比较,从表中数据可以看出,IWOMDE算法除Ronsenbrock函数的优化结果要差于SMDE获得的结果之外,其余结果都要优于SMDE的优化结果。SMDE算法采用的是固定进化代数为终止条件,函数评价次数是未知的,而IWOMDE算法采用固定的
![](//html.hanspub.org/file/10-1541285x68_hanspub.png)
Figure 1. Comparison of mean fitness and optimal fitness of 30 runs at different P1 of f1(x)
图1. 不同P1值时f1(x) 30次平均适应度及最优适应度比较
![](//html.hanspub.org/file/10-1541285x69_hanspub.png)
Figure 2. Comparison of mean fitness and optimal fitness of 30 runs at different P1 of f2(x)
图2. 不同P1值时f2(x) 30次平均适应度及最优适应度比较
![](//html.hanspub.org/file/10-1541285x70_hanspub.png)
Figure 3. Comparison of mean fitness and optimal fitness of 30 runs at different P1 of f3(x)
图3. 不同P1值时f3(x) 30次平均适应度及最优适应度比较
函数评价次数为终止条件,因此,IWOMDE算法在相同函数评价次数下,性能应优于SMDE算法的性能。
![](Images/Table_Tmp.jpg)
Table 2. Comparison of the optimization results of functions by IWOMDE and SMDE
表2. IWOMDE与SMDE函数优化结果比较
表3给出了IWOMDE算法与ADE算法 [7] 的优化结果比较,其中IWOMDE算法的最大函数评价次数对于f4和f5为2e4,而对于f3设置为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 算法。
![](Images/Table_Tmp.jpg)
Table 3. Comparison of the optimization results of functions by IWOMDE and ADE
表3. IWOMDE与ADE函数优化结果比较
表4给出了IWOMDE算法与ONDE算法 [12] 的优化结果比较,四个测试函数的维数设置为100维,函数评价次数设置为6e4。从表中数据可以看出,IWOMDE算法与ONDE算法的结果各有优劣,IWOMDE算法在f2与f5上的优化结果要优于ONDE算法,在f4的最优值上也要优于ONDE算法,但在f3上优化结果要比ONDE算法差很多。
![](Images/Table_Tmp.jpg)
Table 4. Comparison of the optimization results of functions by IWOMDE and ONDE
表4. IWOMDE与ONDE函数优化结果比较
综合以上分析可以发现,IWOMDE算法在多峰函数上的优化结果要优于比较算法,但对于单峰病态函数Rosenbrock函数,优化结果较差。这主要原因是对于多峰函数,由于群体进化过程中,优秀个体使群体能够快速收敛到较优点,而较差个体的停滞进化,使群体维持了较好的多样性,从而为优秀个体跳出局部最优点提供了较好的帮助。
4. 结语
DE算法的DE/rand/1/bin进化模式具有全局搜索能力的特性,被广泛应用于实际问题求解中,但其收敛速度较慢,局部搜索能较差。为使DE算法能够实现快速收敛,且具有很强的搜索精度,本文提出了一种简单易实现的IWOMDE算法,该算法受入侵杂草算法(IWO)启发,将进化群体依据群体适应度均值进行划分为优秀个体与较差个体,对两种不同个体采用不同的变异算子。多个Benchmarks函数的优化结果表明,IWOMDE具有收敛速度快,对于多峰函数有较强的优化效率,但对于单峰病态函数优化效率不高的特点,可广泛应用于各种实际工程优化问题中。