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

(1.江南大學 理學院,江蘇 無錫 214122;2.無錫市生物計算工程技術研究中心,江蘇 無錫 214122)

0 引 言

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

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

1 SSO算法

在SSO算法中，整個搜索空間被視作蜘蛛運動的蜘蛛網，而每只蜘蛛的位置則被作為目標優(yōu)化函數的候選解，且每只蜘蛛的權重大小由蜘蛛的適應值大小決定。蜘蛛個體之間通過分工合作、信息交流和繁衍后代等行為實現對問題最優(yōu)解進行搜索。

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)

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

2 改進的群集蜘蛛算法

2.1 差分變異策略

DE算法是一種基于種群個體之間合作與競爭行為的群體進化算法，主要包括變異、交叉和選擇三種操作。首先，DE算法對父代種群進行變異和交叉操作，產生子代種群，然后利用選擇操作，選取適應值較優(yōu)的個體作為新一代種群。變異操作中的變異個體由下式產生，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ài)變大，在迭代初期，T值比較小，偏差變量對變異影響小，蜘蛛的變異較大程度受群體最優(yōu)的蜘蛛影響，蜘蛛會較快地往群體最優(yōu)個體靠近；在算法運行后期，蜘蛛聚集在最優(yōu)的蜘蛛周圍，T值比較大，此時偏差變量對變異的影響較大，使得種群在最優(yōu)蜘蛛周圍進行局部的精細搜索，提高算法搜索精度。

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呈現非對稱的增大與減小，使得種群在算法初期更多的獲得全局最優(yōu)個體的信息，從而以較快的速度進入局部搜索，在算法后期，種群更多的獲得局部最優(yōu)個體的信息并保持一定的搜索速度，從而進行局部的精細搜索。根據上述策略，以下給出雌雄蜘蛛的位置更新公式。

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

(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)更新雌性蜘蛛個體位置，并保留新老雌性蜘蛛個體中較為優(yōu)秀的個體作為下一代的蜘蛛個體。5) 按式(11)更新雄性蜘蛛個體的位置，并保留新老雄性蜘蛛個體中較為優(yōu)秀的50%作為進入下一代的蜘蛛個體。6) 雌性蜘蛛進行交配，選取適應值優(yōu)的新個體保留。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為多峰函數，理論上的最優(yōu)值均為0。

3.2 仿真實驗結果分析

3.2.1 與相關改進算法的比較

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

由表1所示SSO-DE和本文算法的實驗結果可以看出，本文算法在單峰函數Sphere,Schwefel’s P2.2和Quartic上的求解精度和穩(wěn)定性高于SSO-DE算法。兩個算法在多峰函數Rastrigin上都尋找到了最優(yōu)解，在多峰函數Ackley上的求解精度幾乎相同。由上可知，本文算法的求解性能優(yōu)于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節(jié)。實驗分成3組，維數分別設置為10維、30維和50維,所有算法的種群群體規(guī)模為NP=50，最大迭代次數為1 000。這里記錄5種算法在8個經典測試函數上分別獨立運行30次的最優(yōu)解的平均值(Mean)和標準方差(Std)(見表2)，同時列出以上5種算法求解問題為30維時的收斂圖(見圖2)。

表2 5種算法的測試結果

圖2 5種算法在不同測試函數上的收斂曲線

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

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

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

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

4 結 論

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