改进的基于差分进化的群集蜘蛛优化算法*

向 蕾，鲁海燕,2，胡士娟，沈莞蔷,2

(1.江南大学 理学院,江苏 无锡 214122;2.无锡市生物计算工程技术研究中心,江苏 无锡 214122)

0 引 言

近些年，新型群智能体算法在函数优化、工程应用等方面得到了快速发展，基于生物自然特性的群智能算法不断被提出，例如蚁群[1](artificial bee colony，ABC)算法、粒子群优化[2](particle swarm optimization，PSO)算法、蝙蝠算法[3](bat algorithm，BA)、萤火虫优化[4](glowworm swarm optimization，GSO)算法等。2013年Cuevas E提出了一种模拟自然界蜘蛛互相协作行为的新型群体智能优化算法—群集蜘蛛优化(social spider optimization，SSO)算法[5]，其研究表明，与PSO和ABC算法相比，SSO算法具有更快的收敛速度和更高的求解精度。目前，国内外许多学者已把SSO算法应用于约束优化[6]、经济负荷调度[7]、路径规划[8]问题中。虽然SSO算法在一些实际问题中已经得到了成功的应用，但与一些先进算法相比，仍存在求解精度低、收敛速度慢、易陷入局部极值等缺陷。因此，一些学者提出了多种改进的算法。王艳娇等人[9]提出一种基于动态学习策略的群集蜘蛛优化算法，该算法利用云模型对蜘蛛位置更新公式中的随机部分进行改进，同时加入动态学习策略，提高了算法的收敛速度；赵汝鑫等人[10]采用反向学习和精英选择机制进行种群初始化，使算法的全局搜索能力得到了提高；朱林波等人[11]将群集蜘蛛算法和差分进化算法相结合，提出了基于差分进化变异策略的群集蜘蛛算法，该算法对交配后的新一代蜘蛛进行变异，有效地提高了种群多样性。

本文提出了带有差分变异算子和粒子群惯性权重及学习因子的改进SSO算法。利用差分进化(differential evolution,DE)算法的变异操作，更新部分雌蜘蛛的位置，并引入一组非线性的惯性权重及反余弦非对称的学习因子，使得算法前期具有较快的收敛速度，后期具有较强的开发能力。

1 SSO算法

在SSO算法中，整个搜索空间被视作蜘蛛运动的蜘蛛网，而每只蜘蛛的位置则被作为目标优化函数的候选解，且每只蜘蛛的权重大小由蜘蛛的适应值大小决定。蜘蛛个体之间通过分工合作、信息交流和繁衍后代等行为实现对问题最优解进行搜索。

1.1 种群初始化

设种群数目设为N，雌性蜘蛛数目为Nf=[(0.9-0.25·rand)·N]，雄性蜘蛛数目为Nm=N-Nf，雌性蜘蛛种群为F={f1,f2,…,fNf}，雄性蜘蛛种群为M={m1,m2,…,mNm}。

雌性和雄性蜘蛛初始化种群公式如下

i∈{1,2,…,Nf},h∈(1,2，…，Nm},

j∈{1,2,…,D}

(1)

式中 [·]为向下取整函数，rand为[0,1]之间随机数，fij和mij分别为第i个雌性和雄性个体的第j维变量，fjmax和fjmin为雌性蜘蛛个体第j维变量的上限和下限，mjmax和mjmin为雄性蜘蛛个体第j维变量的上限和下限。

1.2 雌性蜘蛛位置更新

雌性蜘蛛根据自身振动的大小吸引或排斥其他蜘蛛，其位置更新模式如下

(2)

式中Sc为距离个体蜘蛛fi最近且体重比它重的蜘蛛fc的体重，Sb为蜘蛛群体中体重最重的蜘蛛fb的体重，Vibci为个体蜘蛛fi和个体蜘蛛fc之间的振动信息，PF为概率因子，α，β，δ，rand均为[0,1]之间的随机数。

雌性蜘蛛振动信息公式如下

(3)

(4)

式中J(Si)为第i个个体的目标适应值，dij为个体fi与fj的欧氏距离。

1.3 雄性蜘蛛位置更新

以中间个体(中间个体指的是按权重大小对蜘蛛排序处于中间位置的个体)的权重ωNf+n为准线，SSO算法把雄性蜘蛛分成两类，其中个体权重大于ωNf+n的雄性蜘蛛为支配雄蜘蛛，否则为非支配雄蜘蛛。支配雄蜘蛛吸引与之靠近的雌蜘蛛，而非支配雄蜘蛛向着雄蜘蛛群的中间个体靠近。雄蜘蛛位置更新模式如下

(5)

1.4 交配行为

在雄性蜘蛛中，支配雄蜘蛛会与其交配半径r内的雌蜘蛛进行交配，交配半径定义如下

(6)

交配过程中，交配蜘蛛越重对新的子代蜘蛛个体影响越大,每只蜘蛛的影响可能性为Psk，根据轮盘赌的方法确定，公式如下

(7)

雌性和雄性蜘蛛交配完成后，若新的子代优于上一代中体重最轻的个体，则由新的蜘蛛代替上一代中体重最轻的个体；否则，保持原蜘蛛种群不变。

2 改进的群集蜘蛛算法

2.1 差分变异策略

DE算法是一种基于种群个体之间合作与竞争行为的群体进化算法，主要包括变异、交叉和选择三种操作。首先，DE算法对父代种群进行变异和交叉操作，产生子代种群，然后利用选择操作，选取适应值较优的个体作为新一代种群。变异操作中的变异个体由下式产生，vi=xr1+F·(xr2-xr3)，i∈{1,2,…,Np},r1≠r2≠r3≠i。其中，xr2-xr3为偏差变量；F为变异算子，控制偏差变量的放大作用。由上式可知，DE算法中的变异个体由基向量以及父代种群中的两个个体的偏差变量组成。因为在父代种群中随机选取两个个体的组合繁多，所以算法在迭代过程中能维持良好的多样性。变异算子的大小决定算法向偏差向量学习的能力大小，因而合理设置变异算子能够使得算法具有良好的勘探能力。

本文借鉴DE算法中的变异操作，对原群集蜘蛛算法中的部分雌蜘蛛进行变异操作，具体如下：

设置阈值m，随机产生一个数Z∈(0,1)，当Z≤m时，雌蜘蛛变异公式如下

(8)

式中fp，fq由雌性蜘蛛种群F={f1,f2,…,fNf}中随机产生，且p≠q；T为变异算子，这里令T=g/G,g为当前迭代次数，G为总迭代次数。可以看出，变异算子T随着迭代次数增加动态变大，在迭代初期，T值比较小，偏差变量对变异影响小，蜘蛛的变异较大程度受群体最优的蜘蛛影响，蜘蛛会较快地往群体最优个体靠近；在算法运行后期，蜘蛛聚集在最优的蜘蛛周围，T值比较大，此时偏差变量对变异的影响较大，使得种群在最优蜘蛛周围进行局部的精细搜索，提高算法搜索精度。

2.2 非线性惯性权重策略与反余弦非对称学习因子策略

本文借鉴文献[12]中粒子群算法的反余弦非对称的学习因子的搜索机制,为蜘蛛位置更新设计了一组新的惯性权重k及学习因子c，其公式如下

(9)

本文设置kmax=1.1,kmin=0.4使得惯性权重k在0.2～0.9之间非线性增大，这时种群向自身学习力度最好；c1,c2的选取与文献[12]一致，c1max=2.75,c1min=1.25,c2max=2.25，c2min=0.5；i为当前迭代次数，T为最大迭代次数。

本文所提出的惯性权重k及学习因子c随迭代次数增加的变化曲线如图1所示。

图1 惯性权重k及加速因子c1和c2的迭代曲线

当设置kmax=1.1，kmin=0.4时，如图1(a)所示，惯性权重k在0.2～0.9之间随着迭代次数的增加非线性增大，这里将非线性增大的惯性权重加入基本群集蜘蛛算法的位置更新中。由图1(b)可以看出，c1和c2呈现非对称的增大与减小，使得种群在算法初期更多的获得全局最优个体的信息，从而以较快的速度进入局部搜索，在算法后期，种群更多的获得局部最优个体的信息并保持一定的搜索速度，从而进行局部的精细搜索。根据上述策略，以下给出雌雄蜘蛛的位置更新公式。

雌蜘蛛和雄性蜘蛛位置更新公式如下

(10)

(11)

式中k,c1,c2为式(9)给出的非线性惯性权重及反余弦非对称学习因子。

2.3 本文算法步骤

1) 初始化参数：初始化种群数目N;初始解的维度D；权重系数的最大值kmax和最小值kmin;学习因子的最大值cmax和最小值cmin。2) 随机产生一组个数为N的初始解，分配雌性蜘蛛和雄性蜘蛛种群。3) 计算每一只蜘蛛相应的适应值。4) 随机产生一个Z(Z∈(0,1))，若Z≤0.5，按式(8)更新雌性蜘蛛个体位置；否则，按式(10)更新雌性蜘蛛个体位置，并保留新老雌性蜘蛛个体中较为优秀的个体作为下一代的蜘蛛个体。5) 按式(11)更新雄性蜘蛛个体的位置，并保留新老雄性蜘蛛个体中较为优秀的50%作为进入下一代的蜘蛛个体。6) 雌性蜘蛛进行交配，选取适应值优的新个体保留。7) 判断是否满足结束条件，若满足，直接输出结果；否则返回步骤(3)。

3 实验结果与分析

3.1 基本测试函数

本文选取了8个测试函数对本文算法的性能进行对比测试。测试函数f1～f8依次为Sphere,Schwefel’s P2.22,Schwefel’s P1.2,Bentcigar ,Alpine,Griewank,Rastrigin,Ackley。其中，f1～f4为单峰函数和f5～f8为多峰函数，理论上的最优值均为0。

3.2 仿真实验结果分析

3.2.1 与相关改进算法的比较

将本文算法与一种基于差分进化变异策略的改进群集蜘蛛优化(SSO-DE)算法[13]进行对比。文献[13]中所提出的SSO-DE算法和本文所提出的算法都利用了差分变异策略对雌性蜘蛛进行了变异操作，不同点在于SSO-DE是利用两个偏差变量诱导差分变异，本文算法则是利用一个偏差变量诱导差分变异。为了方便比较，本文将两个算法的参数设置与文献[13]保持一致，由于文献[13]仅提供5个测试函数的数值，下面将两种算法在文献[13]中所涉及的5个经典函数上进行寻优，比较最优解的平均值(mean)和标准方差(Std)来体现算法的优越性。具体实验结果分别由表1给出。

由表1所示SSO-DE和本文算法的实验结果可以看出，本文算法在单峰函数Sphere,Schwefel’s P2.2和Quartic上的求解精度和稳定性高于SSO-DE算法。两个算法在多峰函数Rastrigin上都寻找到了最优解，在多峰函数Ackley上的求解精度几乎相同。由上可知，本文算法的求解性能优于SSO-DE算法。

表1 SSO-DE和本文算法实验结果

3.2.2 与其他几种群智能算法的比较

将DESSOcw算法与PSO、BA、SSO、随机惯性权重的粒子群算法RandPSO(random weighting particle swarm optimization algorithm)算法进行对比实验，PSO算法参数设置参照文献[2]，BA算法参数设置参照文献[3]，RandPSO算法的参数参照文献[14]，SSO算法参数设置参照文献[5]，本文算法参数设置参照本文2.1,2.2节。实验分成3组，维数分别设置为10维、30维和50维,所有算法的种群群体规模为NP=50，最大迭代次数为1 000。这里记录5种算法在8个经典测试函数上分别独立运行30次的最优解的平均值(Mean)和标准方差(Std)(见表2)，同时列出以上5种算法求解问题为30维时的收敛图(见图2)。

表2 5种算法的测试结果

图2 5种算法在不同测试函数上的收敛曲线

由表2的数据对比可以得出，与PSO,BA,SSO,Rand-PSO算法相比，无论在10维、30维还是50维的函数上，本文算法的求解精度和稳定性都有了很大提高。针对4个单峰函数，本文算法的求解精度十分接近理论最优值，随着维度的提高，本文算法的求解精度并没有明显下降。对于4个多峰函数，本文算法在f6和f7两个函数上可以求解到理论最优值0，说明本文提出的算法在求解函数f6和f7时显示出良好的求解性能。同时，在三种维度下，本文算法在8个测试函数上的标准方差最小，尤其在f1,f4,f6～f8函数上的标准方差都为0，说明算法具有更强的稳定性。总体来说，本文提出的本文算法的求解精度和稳定性均优于其他4种算法，显示了极高的求解性能。

算法的收敛曲线可以直观地对比各算法的收敛性能。由图2(a)～(d)可知，在求解这4个单峰函数时，PSO算法、RandPSO算法、BA算法、SSO算法的收敛曲线平缓，说明这4种算法在收敛过程中多样性差，易陷入局部最优解，而本文算法的收敛曲线较为陡峭，寻找到的最优解均优于其他4个算法。由图2(f)和图2(g)可知，在求解Griewank和Rastrigin这两个多峰函数时，本文算法收敛速度和求解精度均优于其他4种算法，不仅收敛到最优解0，而且收敛速度极快。综上所述，本文算法的收敛速度均优于其他4种算法。

为了便于观察解集的分布情况，给出5个算法在4个经典函数上独立运行30次的最优解集箱须图(见图3)。从图3(a)～(h)中可以看出，对于4个单峰函数和4个多峰函数，本文算法得到的数据整体都比其他4种算法更接近横坐标轴，说明本文算法得到的解均优于其他算法。另外，本文算法所得的数据范围均小于其他4种算法，且未出现异常解，说明本文算法不仅收敛精度高，而且具有极高的稳定性。

图3 5种算法在不同测试函数上最优解的方差分析

4 结 论

本文算法利用差分进化算法的变异策略，对部分雌蜘蛛进行变异，从而增加了种群的多样性；同时，在个体更新过程中加入一组非线性的惯性权重及学习因子，以更好地平衡算法局部搜索和全局搜索能力。仿真实验表明，与相关算法相比，本文给出的改进算法具有更高的求解精度和更好的稳定性，有一定实际应用的潜力。