一種自適應尋優的社會蜘蛛優化算法（SA-SSA）

施怡樂，喬之勇,2，白克強，陳 果，劉知貴*

（1.西南科技大學 信息工程學院，綿陽 621000；2.綿陽職業技術學院，綿陽 621000）

0 引言

社會蜘蛛智能優化算法（SSA）于2015年香港大學James等人提出[1]。作為一種新型全局智能優化算法，其思想源于蜘蛛發現食物以后，振動蛛網向同伴發出信息并吸引其他蜘蛛前來覓食的自然現象。社會蜘蛛智能優化算法（SSA）中，蛛網表示待求解問題的解空間，每個蜘蛛表示解空間中的一個可行性解，食物表示解空間中解的適應度。當某一個蜘蛛發現食物以后，將產生與該食物適應度所匹配的振動，并吸引其他蜘蛛前來覓食。該算法具有結構簡單、自身參數少的優點，在多元函數問題求解時比傳統遺傳算法和粒子群算法速度更快、精度更高[2]。目前社會蜘蛛智能優化算法（SSA）被廣泛應用于電力調度優化[3]、網絡服務器分布[4]、神經網絡訓練[4]、防洪調度[6]、水紋頻率參數優化[7]中。作為一種新型全局智能優化算法，社會蜘蛛智能優化算法（SSA）已成為多個領域中的研究熱點[8]。

為進一步提高社會蜘蛛智能優化算法（SSA）尋優能力，有學者提出引入隨機交叉策略用于個體蜘蛛的更新，通過快速的個體更新策略提高SSA的搜索速率[9]；采用自適應尋優和偏好隨機游動機制，以迭代次數為變量來提高SSA在多峰測試函數中的全局搜索能力和尋優精度[10]；引入分層協作思想將蜘蛛群體劃分為兩個分工種類，并結合貪婪策略定性移除部分蜘蛛，提高處理高維優化問題的全局搜索能力和尋優精度[11]；在分層協作思想基礎上引入差分進化算子，通過優化群體中不同種類蜘蛛的進化方式來提高SSA的全局搜索能力和尋優精度[12]。目前已有一些關于SSA改進算法被提出，但大多改進都沒有考慮到振動強度對算法全局搜索能力的影響。

針對上述問題，本文提出了一種自適應策略的社會蜘蛛智能優化算法（self adaption social spider optimization algorithm，SA-SSA）。該算法在蜘蛛振動過程中利用自適應權重，動態調整算法不同迭代時段的收斂速度，并通過最優領域擾動策略來抑制算法早熟。為驗證SA-SSA的尋優性能，在6個測試函數中進行了仿真實驗，結果表明該算法具有更高的尋優精度和更快的尋優速度。

1 社會蜘蛛優化算法（SSA）

在社會蜘蛛智能優化算法（SSA）中，將優化問題的搜索空間擬化為蛛網，蛛網的每一個位置均代表了優化空間中的一個可行性解，且蛛網還作為信息交流的媒介用于傳播振動。在SSA初始化階段隨機生成每一個蜘蛛的位置，并對應產生相應的適應度，依據該適應度產生對應的振動并傳播。單個蜘蛛判斷自身振動與接收其他蜘蛛振動的大小，產生游走概率，進行隨機游走。社會蜘蛛智能優化算法（SSA）主要包括：蜘蛛信息、振動產生以及游走尋優三個環節。

1.1 蜘蛛信息

社會蜘蛛智能優化算法（SSA）中，每個蜘蛛在蛛網上的位置均代表了優化問題中的一個可行性解，其中每一個蜘蛛均攜帶著如下信息：

圖1 社會蜘蛛示意圖

1）蜘蛛S所在的位置計為Ps；

2）蜘蛛S所在位置的適應度計為f(Ps)；

4）自上一次改變目標振動后的迭代次數Cs；

5）上次迭代的移動方向w；

6）上次迭代中用于游走的掩碼m。其中前兩個信息為蜘蛛自身的個體信息，其他的則是引導蜘蛛前往適應度更高位置的信息。

1.2 振動產生

振動產生是SSA的核心環節，也是與其他算法區別開的一個主要特性。在SSA中從蜘蛛個體振動強度和感知群體中其他蜘蛛振動強度兩個方面來定義了振動的概念。當蜘蛛S到達某個位置Ps以后將對對應產生在該位置的振動，其強度表示為I(Ps,Ps,t)；除此以外該振動強度也會在振動衰減的基礎上被群體中其他蜘蛛感知，同樣也能感受到來自其他蜘蛛的振動，其強度表示為I(Ps,Ps,t)（其中i的范圍[1，pop-1]，pop表示種群數量）?；谶@種種群信息共享的方式，SSA的全局尋優能力得到了增強。

其中，蜘蛛S自身振動強度I(Ps,Ps,t)是指蜘蛛S在t時刻所產生的振動強度，具體的計算表示如下。

式(1)中，f(Ps)為蜘蛛S所在位置的適應度，C為極小常數用于保證f(Ps)+C＞0。

蜘蛛S感知種群其他蜘蛛的震動強度I(Ps,Ps,t)的具體計算表示如下，在計算I(Ps,Ps,t)之前首先需要分別計算蜘蛛S與其他蜘蛛的距離。這里我們選擇采用曼哈頓距離計算方法，定義蜘蛛S與蜘蛛A的距離為D(Ps,PA)。

此時，可表示蜘蛛S感知蜘蛛A產生振動強度為I(Ps,PA,t)。

式(3)中，為蜘蛛種群每個維度的標準差，Ra為振動衰減率。

1.3 游走尋優

社會蜘蛛智能優化算法（SSA）游走尋優方式，不存在全局最優標準來指導種群進化的行為，而是蜘蛛個體依靠自身攜帶信息和種群共享信息，隨迭代采用逐步逼近的方式向全局最優解靠近。

游走尋優的本質是基于概率的一種游走形式，在SSA中規定了每一個蜘蛛均攜帶一個固定分配的二進制編碼表M（該表為pop×dim的矩陣，pop表示種群數量，dim表示待優化問題的維度），在算法初始階段矩陣中各個元素均為零，在每輪迭代的過程中蜘蛛S具有的概率改變矩陣（其中Cs表示自上一次改變目標振動后的迭代次數）。當M矩陣被判定為改變以后，M中的每個元素均有Pm的概率被改變為1。在隨機編碼M確定以后，根據M生成蜘蛛S新的目標位置，該目標位置的第i維數值記為具體表示如式(4)所示。

其中a的取值范圍為[1，pop]。

式(5)中r和R均為服從[0，1]分布的隨機數，o為矩陣中點對點乘運算。

在隨機游走環節中為防止蜘蛛超出解空間，得到不可行解，需要對SSA進行約束處理，在SSA中采用reflecting算法進行邊界約束，具體表達如下。

式(6)中為搜索空間第i維的上界，為搜索空間第i維的下界。

2 改進型社會蜘蛛優化算法

通過分析發現，傳統的社會蜘蛛優化算法（SSA）在全局尋優精度和全局收斂速度方面仍存在一定缺陷。目前SSA的算法改進幾乎沒有考慮到振動強度對算法尋優的影響，以及算法在全局搜索能力的不足。因此根據標準的蜘蛛種群位置（適應度）更新，引入振動自適應調整函數和最優鄰域擾動構成自適應尋優社會蜘蛛優化算法（SA-SSA）。

2.1 振動自適應函數

傳統的SSA在振動強度和傳遞距離確定的情況下，振動傳遞的衰減由蜘蛛種群每個維度的標準差σ和振動衰減率Ra影響。又因蜘蛛種群每個維度的標準差σ主要由初始化隨機決定，因此振動衰減率Ra為主要SSA的主要控制參數。然而通過實驗發現，在SSA中以10000倍的跨度調節振動衰減率Ra對傳統社會蜘蛛優化算法（SSA）的全局優化能力并無太大改善。通過分析發現，該現象出現的主要原因是由于標準差σ值過于極端且隨機性強，變相使得振動衰減率Ra的控制效力不足，造成振動環節隨機性較強，SSA的全局優化能力提升受限。

基于上述實驗驗證和分析，為提升社會蜘蛛優化算法（SSA）的全局優化能力，本文在粒子群優化算法的權重因子思想上，結合迭代規律，引入振動自適應函數。

式(7)中Ra為算法初始化設定的振動衰減率，iter為當前迭代次數，max_iter為初始化設定的最大迭代次數。該函數使得算法在迭代前期增加群體對個體的影響能力，進而增加全局搜索的能力；在迭代后期該影響逐漸減小，以獲得更高的尋優精度。綜上所述，改進的W-SSA振動傳遞式如式(8)所示。

2.2 最優鄰域擾動

個體蜘蛛經過迭代進行位置更新時，一般以當前迭代的最強振動為方向進行有目的的隨機游走。但目標函數以及群體蜘蛛的位置均為未知，且個體振動與個體接收振動的量化均存人為經驗的判斷，因此在算法尋優時不可避免的會出現算法早熟，陷入局部最優的問題。為規避該問題，本文提出在SSA中引入最優領域擾動，在當前最優位置產生隨機擾動，增加個體蜘蛛對附近空間的搜索能力，最優領域擾動如下。

式(9)中rand1、rand2為[0，1]之間的均勻產生的隨機數；為上一次迭代所處最佳位置的蜘蛛S，經過最優領域擾動以后新位置。對于蜘蛛S新生成的領域位置采用貪婪機制判斷是否保留。

2.3 SA-SSA算法流程

SA-SSA綜合考慮了算法的收斂速度、全局和局部搜索能力。引入振動自適應函數用于提升算法收斂速度和全局搜索能力，引入最優領域擾動并結合貪婪機制增加最優個體的局部搜索能力，具體算法流程如表1所示。

表1 SA-SSA算法流程表

2.4 算法復雜度分析

對于算法復雜度的分析，主要從時間復雜度和空間復雜度兩個方面展開。

在社會蜘蛛優化算法（SSA）中，設算法中鯨魚的規模為N，最大迭代次數為I，問題維度為D，于是可以得到社會蜘蛛優化算法（SSA）的時間復雜度為O（N×I×D）。而SA-SSA是在原SSA基礎上引入了兩種改進策略，從算法流程可以看出，在加入振動自適應函數以后并未增加算法的循環次數，而加入最優鄰域擾動也僅僅是只給算法外圍增加了一次遍歷種群的循環，增加了O（N×I）的運算量。對于整個算法的時間復雜度而言，增加O（N×I）的運算量并不會對整個算法造成太大的計算負擔，總體來說SA-SSA相較SSA在時間復雜度方面幾乎持平。

空間復雜度則是用來評判一個算法對內存空間的需求。本文所述的空間復雜度主要由蜘蛛種群的規模決定，而SA-SSA和SSA均采用相同的種群規模，因此兩種算法具有相同的空間復雜度O（N×D）。

3 仿真與分析

3.1 測試函數及性能指標

為測試SA-SSA算法的尋優能力，選擇了6個標準測試函數，其函數特性如表所示。算法尋優精度為實際尋得最優解與理論最優解之間的誤差絕對值，本文采用兩個評價指標：尋優精度的平均值（Ave）和標準差（Std），其計算式分別如式(11)、式(12)所示。

3.2 優化算法性能分析

將W-SSA算法在6個標準測試函數上進行性能測試，并將其與蝙蝠優化算法（BA）、人工魚群算法（AFA）以及傳統社會蜘蛛算法（SSA）進行對比。算法參數設置相同：種群規模為30、最大迭代次數500。算法均分為10和30兩組優化問題維度分別測試20次，得到優化結果的平均精度及其標準差如表3、表4所示，其中黑色粗體為較優結果。

算法主要參數設置如表3所示，算法收斂精度對比如表4所示。

表3 算法參數設置表

表4 算法收斂精度對比表

由表2可以看出改進以后的SA-SSA在f1～f6的6個測試函數中其尋優精度均優于傳其他三種全局優化算法。特別是在f1、f2、f3以及f6四個測試函數中，SA-SSA的尋優精度具有極佳的表現。

表2 標準測試函數表

為進一步驗證SA-SSA算法在尋優速度方面的表現，對收斂精度較好的SSA和SA-SSA在上述6個標準測試函數下的求解收斂曲線進行了對比，如圖2所示。

圖2 算法收斂速度對比圖

從圖中可以看出，SA-SSA算法在上述6個標準測試函數的收斂速度均明顯高于標準SSA。綜上所述，改進后的SA-SSA算法在求解復雜函數最優解時，比標準的SSA以及其他群智能優化算法具有更高的尋優精度，在收斂速度方面也相較于標準SSA更快。

4 結語

社會蜘蛛優化算法（SSA）是一種具有仿生尋優的智能優化算法，已被廣泛的應用于多個領域中，但該算法在全局尋優精度和收斂速度方面仍存在一定的缺陷。本文分析了標準SSA算法的尋優過程。根據標準的蜘蛛種群位置（適應度）更新，引入振動自適應調整函數和最優鄰域擾動構成自適應尋優社會蜘蛛優化算法（SA-SSA），提升整個算法的全局搜索能力。通過標準測試函數測試，SASSA算法相較于BA、AFA以及SSA在尋優精度和收斂速度兩方面均更優。證明了本文所提出的兩種改進策略對于SSA算法的有效性。