改進(jìn)的基于差分進(jìn)化的群集蜘蛛優(yōu)化算法*

向 蕾，魯海燕,2，胡士娟，沈莞薔,2

(1.江南大學(xué) 理學(xué)院,江蘇 無(wú)錫 214122;2.無(wú)錫市生物計(jì)算工程技術(shù)研究中心,江蘇 無(wú)錫 214122)

0 引 言

近些年，新型群智能體算法在函數(shù)優(yōu)化、工程應(yīng)用等方面得到了快速發(fā)展，基于生物自然特性的群智能算法不斷被提出，例如蟻群[1](artificial bee colony，ABC)算法、粒子群優(yōu)化[2](particle swarm optimization，PSO)算法、蝙蝠算法[3](bat algorithm，BA)、螢火蟲(chóng)優(yōu)化[4](glowworm swarm optimization，GSO)算法等。2013年Cuevas E提出了一種模擬自然界蜘蛛互相協(xié)作行為的新型群體智能優(yōu)化算法—群集蜘蛛優(yōu)化(social spider optimization，SSO)算法[5]，其研究表明，與PSO和ABC算法相比，SSO算法具有更快的收斂速度和更高的求解精度。目前，國(guó)內(nèi)外許多學(xué)者已把SSO算法應(yīng)用于約束優(yōu)化[6]、經(jīng)濟(jì)負(fù)荷調(diào)度[7]、路徑規(guī)劃[8]問(wèn)題中。雖然SSO算法在一些實(shí)際問(wèn)題中已經(jīng)得到了成功的應(yīng)用，但與一些先進(jìn)算法相比，仍存在求解精度低、收斂速度慢、易陷入局部極值等缺陷。因此，一些學(xué)者提出了多種改進(jìn)的算法。王艷嬌等人[9]提出一種基于動(dòng)態(tài)學(xué)習(xí)策略的群集蜘蛛優(yōu)化算法，該算法利用云模型對(duì)蜘蛛位置更新公式中的隨機(jī)部分進(jìn)行改進(jìn)，同時(shí)加入動(dòng)態(tài)學(xué)習(xí)策略，提高了算法的收斂速度；趙汝鑫等人[10]采用反向?qū)W習(xí)和精英選擇機(jī)制進(jìn)行種群初始化，使算法的全局搜索能力得到了提高；朱林波等人[11]將群集蜘蛛算法和差分進(jìn)化算法相結(jié)合，提出了基于差分進(jìn)化變異策略的群集蜘蛛算法，該算法對(duì)交配后的新一代蜘蛛進(jìn)行變異，有效地提高了種群多樣性。

本文提出了帶有差分變異算子和粒子群慣性權(quán)重及學(xué)習(xí)因子的改進(jìn)SSO算法。利用差分進(jìn)化(differential evolution,DE)算法的變異操作，更新部分雌蜘蛛的位置，并引入一組非線性的慣性權(quán)重及反余弦非對(duì)稱的學(xué)習(xí)因子，使得算法前期具有較快的收斂速度，后期具有較強(qiáng)的開(kāi)發(fā)能力。

1 SSO算法

在SSO算法中，整個(gè)搜索空間被視作蜘蛛運(yùn)動(dòng)的蜘蛛網(wǎng)，而每只蜘蛛的位置則被作為目標(biāo)優(yōu)化函數(shù)的候選解，且每只蜘蛛的權(quán)重大小由蜘蛛的適應(yīng)值大小決定。蜘蛛個(gè)體之間通過(guò)分工合作、信息交流和繁衍后代等行為實(shí)現(xiàn)對(duì)問(wèn)題最優(yōu)解進(jìn)行搜索。

1.1 種群初始化

設(shè)種群數(shù)目設(shè)為N，雌性蜘蛛數(shù)目為Nf=[(0.9-0.25·rand)·N]，雄性蜘蛛數(shù)目為Nm=N-Nf，雌性蜘蛛種群為F={f1,f2,…,fNf}，雄性蜘蛛種群為M={m1,m2,…,mNm}。

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

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

j∈{1,2,…,D}

(1)

式中 [·]為向下取整函數(shù)，rand為[0,1]之間隨機(jī)數(shù)，fij和mij分別為第i個(gè)雌性和雄性個(gè)體的第j維變量，fjmax和fjmin為雌性蜘蛛個(gè)體第j維變量的上限和下限，mjmax和mjmin為雄性蜘蛛個(gè)體第j維變量的上限和下限。

1.2 雌性蜘蛛位置更新

雌性蜘蛛根據(jù)自身振動(dòng)的大小吸引或排斥其他蜘蛛，其位置更新模式如下

(2)

式中Sc為距離個(gè)體蜘蛛fi最近且體重比它重的蜘蛛fc的體重，Sb為蜘蛛群體中體重最重的蜘蛛fb的體重，Vibci為個(gè)體蜘蛛fi和個(gè)體蜘蛛fc之間的振動(dòng)信息，PF為概率因子，α，β，δ，rand均為[0,1]之間的隨機(jī)數(shù)。

雌性蜘蛛振動(dòng)信息公式如下

(3)

(4)

式中J(Si)為第i個(gè)個(gè)體的目標(biāo)適應(yīng)值，dij為個(gè)體fi與fj的歐氏距離。

1.3 雄性蜘蛛位置更新

以中間個(gè)體(中間個(gè)體指的是按權(quán)重大小對(duì)蜘蛛排序處于中間位置的個(gè)體)的權(quán)重ωNf+n為準(zhǔn)線，SSO算法把雄性蜘蛛分成兩類，其中個(gè)體權(quán)重大于ωNf+n的雄性蜘蛛為支配雄蜘蛛，否則為非支配雄蜘蛛。支配雄蜘蛛吸引與之靠近的雌蜘蛛，而非支配雄蜘蛛向著雄蜘蛛群的中間個(gè)體靠近。雄蜘蛛位置更新模式如下

(5)

1.4 交配行為

在雄性蜘蛛中，支配雄蜘蛛會(huì)與其交配半徑r內(nèi)的雌蜘蛛進(jìn)行交配，交配半徑定義如下

(6)

交配過(guò)程中，交配蜘蛛越重對(duì)新的子代蜘蛛個(gè)體影響越大,每只蜘蛛的影響可能性為Psk，根據(jù)輪盤賭的方法確定，公式如下

(7)

雌性和雄性蜘蛛交配完成后，若新的子代優(yōu)于上一代中體重最輕的個(gè)體，則由新的蜘蛛代替上一代中體重最輕的個(gè)體；否則，保持原蜘蛛種群不變。

2 改進(jìn)的群集蜘蛛算法

2.1 差分變異策略

DE算法是一種基于種群個(gè)體之間合作與競(jìng)爭(zhēng)行為的群體進(jìn)化算法，主要包括變異、交叉和選擇三種操作。首先，DE算法對(duì)父代種群進(jìn)行變異和交叉操作，產(chǎn)生子代種群，然后利用選擇操作，選取適應(yīng)值較優(yōu)的個(gè)體作為新一代種群。變異操作中的變異個(gè)體由下式產(chǎn)生，vi=xr1+F·(xr2-xr3)，i∈{1,2,…,Np},r1≠r2≠r3≠i。其中，xr2-xr3為偏差變量；F為變異算子，控制偏差變量的放大作用。由上式可知，DE算法中的變異個(gè)體由基向量以及父代種群中的兩個(gè)個(gè)體的偏差變量組成。因?yàn)樵诟复N群中隨機(jī)選取兩個(gè)個(gè)體的組合繁多，所以算法在迭代過(guò)程中能維持良好的多樣性。變異算子的大小決定算法向偏差向量學(xué)習(xí)的能力大小，因而合理設(shè)置變異算子能夠使得算法具有良好的勘探能力。

本文借鑒DE算法中的變異操作，對(duì)原群集蜘蛛算法中的部分雌蜘蛛進(jìn)行變異操作，具體如下：

設(shè)置閾值m，隨機(jī)產(chǎn)生一個(gè)數(shù)Z∈(0,1)，當(dāng)Z≤m時(shí)，雌蜘蛛變異公式如下

(8)

式中fp，fq由雌性蜘蛛種群F={f1,f2,…,fNf}中隨機(jī)產(chǎn)生，且p≠q；T為變異算子，這里令T=g/G,g為當(dāng)前迭代次數(shù)，G為總迭代次數(shù)?？梢钥闯?，變異算子T隨著迭代次數(shù)增加動(dòng)態(tài)變大，在迭代初期，T值比較小，偏差變量對(duì)變異影響小，蜘蛛的變異較大程度受群體最優(yōu)的蜘蛛影響，蜘蛛會(huì)較快地往群體最優(yōu)個(gè)體靠近；在算法運(yùn)行后期，蜘蛛聚集在最優(yōu)的蜘蛛周圍，T值比較大，此時(shí)偏差變量對(duì)變異的影響較大，使得種群在最優(yōu)蜘蛛周圍進(jìn)行局部的精細(xì)搜索，提高算法搜索精度。

2.2 非線性慣性權(quán)重策略與反余弦非對(duì)稱學(xué)習(xí)因子策略

本文借鑒文獻(xiàn)[12]中粒子群算法的反余弦非對(duì)稱的學(xué)習(xí)因子的搜索機(jī)制,為蜘蛛位置更新設(shè)計(jì)了一組新的慣性權(quán)重k及學(xué)習(xí)因子c，其公式如下

(9)

本文設(shè)置kmax=1.1,kmin=0.4使得慣性權(quán)重k在0.2～0.9之間非線性增大，這時(shí)種群向自身學(xué)習(xí)力度最好；c1,c2的選取與文獻(xiàn)[12]一致，c1max=2.75,c1min=1.25,c2max=2.25，c2min=0.5；i為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。

本文所提出的慣性權(quán)重k及學(xué)習(xí)因子c隨迭代次數(shù)增加的變化曲線如圖1所示。

圖1 慣性權(quán)重k及加速因子c1和c2的迭代曲線

當(dāng)設(shè)置kmax=1.1，kmin=0.4時(shí)，如圖1(a)所示，慣性權(quán)重k在0.2～0.9之間隨著迭代次數(shù)的增加非線性增大，這里將非線性增大的慣性權(quán)重加入基本群集蜘蛛算法的位置更新中。由圖1(b)可以看出，c1和c2呈現(xiàn)非對(duì)稱的增大與減小，使得種群在算法初期更多的獲得全局最優(yōu)個(gè)體的信息，從而以較快的速度進(jìn)入局部搜索，在算法后期，種群更多的獲得局部最優(yōu)個(gè)體的信息并保持一定的搜索速度，從而進(jìn)行局部的精細(xì)搜索。根據(jù)上述策略，以下給出雌雄蜘蛛的位置更新公式。

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

(10)

(11)

式中k,c1,c2為式(9)給出的非線性慣性權(quán)重及反余弦非對(duì)稱學(xué)習(xí)因子。

2.3 本文算法步驟

1) 初始化參數(shù)：初始化種群數(shù)目N;初始解的維度D；權(quán)重系數(shù)的最大值kmax和最小值kmin;學(xué)習(xí)因子的最大值cmax和最小值cmin。2) 隨機(jī)產(chǎn)生一組個(gè)數(shù)為N的初始解，分配雌性蜘蛛和雄性蜘蛛種群。3) 計(jì)算每一只蜘蛛相應(yīng)的適應(yīng)值。4) 隨機(jī)產(chǎn)生一個(gè)Z(Z∈(0,1))，若Z≤0.5，按式(8)更新雌性蜘蛛個(gè)體位置；否則，按式(10)更新雌性蜘蛛個(gè)體位置，并保留新老雌性蜘蛛個(gè)體中較為優(yōu)秀的個(gè)體作為下一代的蜘蛛個(gè)體。5) 按式(11)更新雄性蜘蛛個(gè)體的位置，并保留新老雄性蜘蛛個(gè)體中較為優(yōu)秀的50%作為進(jìn)入下一代的蜘蛛個(gè)體。6) 雌性蜘蛛進(jìn)行交配，選取適應(yīng)值優(yōu)的新個(gè)體保留。7) 判斷是否滿足結(jié)束條件，若滿足，直接輸出結(jié)果；否則返回步驟(3)。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 基本測(cè)試函數(shù)

本文選取了8個(gè)測(cè)試函數(shù)對(duì)本文算法的性能進(jìn)行對(duì)比測(cè)試。測(cè)試函數(shù)f1～f8依次為Sphere,Schwefel’s P2.22,Schwefel’s P1.2,Bentcigar ,Alpine,Griewank,Rastrigin,Ackley。其中，f1～f4為單峰函數(shù)和f5～f8為多峰函數(shù)，理論上的最優(yōu)值均為0。

3.2 仿真實(shí)驗(yàn)結(jié)果分析

3.2.1 與相關(guān)改進(jìn)算法的比較

將本文算法與一種基于差分進(jìn)化變異策略的改進(jìn)群集蜘蛛優(yōu)化(SSO-DE)算法[13]進(jìn)行對(duì)比。文獻(xiàn)[13]中所提出的SSO-DE算法和本文所提出的算法都利用了差分變異策略對(duì)雌性蜘蛛進(jìn)行了變異操作，不同點(diǎn)在于SSO-DE是利用兩個(gè)偏差變量誘導(dǎo)差分變異，本文算法則是利用一個(gè)偏差變量誘導(dǎo)差分變異。為了方便比較，本文將兩個(gè)算法的參數(shù)設(shè)置與文獻(xiàn)[13]保持一致，由于文獻(xiàn)[13]僅提供5個(gè)測(cè)試函數(shù)的數(shù)值，下面將兩種算法在文獻(xiàn)[13]中所涉及的5個(gè)經(jīng)典函數(shù)上進(jìn)行尋優(yōu)，比較最優(yōu)解的平均值(mean)和標(biāo)準(zhǔn)方差(Std)來(lái)體現(xiàn)算法的優(yōu)越性。具體實(shí)驗(yàn)結(jié)果分別由表1給出。

由表1所示SSO-DE和本文算法的實(shí)驗(yàn)結(jié)果可以看出，本文算法在單峰函數(shù)Sphere,Schwefel’s P2.2和Quartic上的求解精度和穩(wěn)定性高于SSO-DE算法。兩個(gè)算法在多峰函數(shù)Rastrigin上都尋找到了最優(yōu)解，在多峰函數(shù)Ackley上的求解精度幾乎相同。由上可知，本文算法的求解性能優(yōu)于SSO-DE算法。

表1 SSO-DE和本文算法實(shí)驗(yàn)結(jié)果

3.2.2 與其他幾種群智能算法的比較

將DESSOcw算法與PSO、BA、SSO、隨機(jī)慣性權(quán)重的粒子群算法RandPSO(random weighting particle swarm optimization algorithm)算法進(jìn)行對(duì)比實(shí)驗(yàn)，PSO算法參數(shù)設(shè)置參照文獻(xiàn)[2]，BA算法參數(shù)設(shè)置參照文獻(xiàn)[3]，RandPSO算法的參數(shù)參照文獻(xiàn)[14]，SSO算法參數(shù)設(shè)置參照文獻(xiàn)[5]，本文算法參數(shù)設(shè)置參照本文2.1,2.2節(jié)。實(shí)驗(yàn)分成3組，維數(shù)分別設(shè)置為10維、30維和50維,所有算法的種群群體規(guī)模為NP=50，最大迭代次數(shù)為1 000。這里記錄5種算法在8個(gè)經(jīng)典測(cè)試函數(shù)上分別獨(dú)立運(yùn)行30次的最優(yōu)解的平均值(Mean)和標(biāo)準(zhǔn)方差(Std)(見(jiàn)表2)，同時(shí)列出以上5種算法求解問(wèn)題為30維時(shí)的收斂圖(見(jiàn)圖2)。

表2 5種算法的測(cè)試結(jié)果

圖2 5種算法在不同測(cè)試函數(shù)上的收斂曲線

由表2的數(shù)據(jù)對(duì)比可以得出，與PSO,BA,SSO,Rand-PSO算法相比，無(wú)論在10維、30維還是50維的函數(shù)上，本文算法的求解精度和穩(wěn)定性都有了很大提高。針對(duì)4個(gè)單峰函數(shù)，本文算法的求解精度十分接近理論最優(yōu)值，隨著維度的提高，本文算法的求解精度并沒(méi)有明顯下降。對(duì)于4個(gè)多峰函數(shù)，本文算法在f6和f7兩個(gè)函數(shù)上可以求解到理論最優(yōu)值0，說(shuō)明本文提出的算法在求解函數(shù)f6和f7時(shí)顯示出良好的求解性能。同時(shí)，在三種維度下，本文算法在8個(gè)測(cè)試函數(shù)上的標(biāo)準(zhǔn)方差最小，尤其在f1,f4,f6～f8函數(shù)上的標(biāo)準(zhǔn)方差都為0，說(shuō)明算法具有更強(qiáng)的穩(wěn)定性?？傮w來(lái)說(shuō)，本文提出的本文算法的求解精度和穩(wěn)定性均優(yōu)于其他4種算法，顯示了極高的求解性能。

算法的收斂曲線可以直觀地對(duì)比各算法的收斂性能。由圖2(a)～(d)可知，在求解這4個(gè)單峰函數(shù)時(shí)，PSO算法、RandPSO算法、BA算法、SSO算法的收斂曲線平緩，說(shuō)明這4種算法在收斂過(guò)程中多樣性差，易陷入局部最優(yōu)解，而本文算法的收斂曲線較為陡峭，尋找到的最優(yōu)解均優(yōu)于其他4個(gè)算法。由圖2(f)和圖2(g)可知，在求解Griewank和Rastrigin這兩個(gè)多峰函數(shù)時(shí)，本文算法收斂速度和求解精度均優(yōu)于其他4種算法，不僅收斂到最優(yōu)解0，而且收斂速度極快。綜上所述，本文算法的收斂速度均優(yōu)于其他4種算法。

為了便于觀察解集的分布情況，給出5個(gè)算法在4個(gè)經(jīng)典函數(shù)上獨(dú)立運(yùn)行30次的最優(yōu)解集箱須圖(見(jiàn)圖3)。從圖3(a)～(h)中可以看出，對(duì)于4個(gè)單峰函數(shù)和4個(gè)多峰函數(shù)，本文算法得到的數(shù)據(jù)整體都比其他4種算法更接近橫坐標(biāo)軸，說(shuō)明本文算法得到的解均優(yōu)于其他算法。另外，本文算法所得的數(shù)據(jù)范圍均小于其他4種算法，且未出現(xiàn)異常解，說(shuō)明本文算法不僅收斂精度高，而且具有極高的穩(wěn)定性。

圖3 5種算法在不同測(cè)試函數(shù)上最優(yōu)解的方差分析

4 結(jié) 論

本文算法利用差分進(jìn)化算法的變異策略，對(duì)部分雌蜘蛛進(jìn)行變異，從而增加了種群的多樣性；同時(shí)，在個(gè)體更新過(guò)程中加入一組非線性的慣性權(quán)重及學(xué)習(xí)因子，以更好地平衡算法局部搜索和全局搜索能力。仿真實(shí)驗(yàn)表明，與相關(guān)算法相比，本文給出的改進(jìn)算法具有更高的求解精度和更好的穩(wěn)定性，有一定實(shí)際應(yīng)用的潛力。