一種自適應(yīng)尋優(yōu)的社會(huì)蜘蛛優(yōu)化算法（SA-SSA）

施怡樂，喬之勇,2，白克強(qiáng)，陳 果，劉知貴*

（1.西南科技大學(xué) 信息工程學(xué)院，綿陽 621000；2.綿陽職業(yè)技術(shù)學(xué)院，綿陽 621000）

0 引言

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

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

針對(duì)上述問題，本文提出了一種自適應(yīng)策略的社會(huì)蜘蛛智能優(yōu)化算法（self adaption social spider optimization algorithm，SA-SSA）。該算法在蜘蛛振動(dòng)過程中利用自適應(yīng)權(quán)重，動(dòng)態(tài)調(diào)整算法不同迭代時(shí)段的收斂速度，并通過最優(yōu)領(lǐng)域擾動(dòng)策略來抑制算法早熟。為驗(yàn)證SA-SSA的尋優(yōu)性能，在6個(gè)測(cè)試函數(shù)中進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明該算法具有更高的尋優(yōu)精度和更快的尋優(yōu)速度。

1 社會(huì)蜘蛛優(yōu)化算法（SSA）

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

1.1 蜘蛛信息

社會(huì)蜘蛛智能優(yōu)化算法（SSA）中，每個(gè)蜘蛛在蛛網(wǎng)上的位置均代表了優(yōu)化問題中的一個(gè)可行性解，其中每一個(gè)蜘蛛均攜帶著如下信息：

圖1 社會(huì)蜘蛛示意圖

1）蜘蛛S所在的位置計(jì)為Ps；

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

4）自上一次改變目標(biāo)振動(dòng)后的迭代次數(shù)Cs；

5）上次迭代的移動(dòng)方向w；

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

1.2 振動(dòng)產(chǎn)生

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

其中，蜘蛛S自身振動(dòng)強(qiáng)度I(Ps,Ps,t)是指蜘蛛S在t時(shí)刻所產(chǎn)生的振動(dòng)強(qiáng)度，具體的計(jì)算表示如下。

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

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

此時(shí)，可表示蜘蛛S感知蜘蛛A產(chǎn)生振動(dòng)強(qiáng)度為I(Ps,PA,t)。

式(3)中，為蜘蛛種群每個(gè)維度的標(biāo)準(zhǔn)差，Ra為振動(dòng)衰減率。

1.3 游走尋優(yōu)

社會(huì)蜘蛛智能優(yōu)化算法（SSA）游走尋優(yōu)方式，不存在全局最優(yōu)標(biāo)準(zhǔn)來指導(dǎo)種群進(jìn)化的行為，而是蜘蛛個(gè)體依靠自身攜帶信息和種群共享信息，隨迭代采用逐步逼近的方式向全局最優(yōu)解靠近。

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

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

式(5)中r和R均為服從[0，1]分布的隨機(jī)數(shù)，o為矩陣中點(diǎn)對(duì)點(diǎn)乘運(yùn)算。

在隨機(jī)游走環(huán)節(jié)中為防止蜘蛛超出解空間，得到不可行解，需要對(duì)SSA進(jìn)行約束處理，在SSA中采用reflecting算法進(jìn)行邊界約束，具體表達(dá)如下。

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

2 改進(jìn)型社會(huì)蜘蛛優(yōu)化算法

通過分析發(fā)現(xiàn)，傳統(tǒng)的社會(huì)蜘蛛優(yōu)化算法（SSA）在全局尋優(yōu)精度和全局收斂速度方面仍存在一定缺陷。目前SSA的算法改進(jìn)幾乎沒有考慮到振動(dòng)強(qiáng)度對(duì)算法尋優(yōu)的影響，以及算法在全局搜索能力的不足。因此根據(jù)標(biāo)準(zhǔn)的蜘蛛種群位置（適應(yīng)度）更新，引入振動(dòng)自適應(yīng)調(diào)整函數(shù)和最優(yōu)鄰域擾動(dòng)構(gòu)成自適應(yīng)尋優(yōu)社會(huì)蜘蛛優(yōu)化算法（SA-SSA）。

2.1 振動(dòng)自適應(yīng)函數(shù)

傳統(tǒng)的SSA在振動(dòng)強(qiáng)度和傳遞距離確定的情況下，振動(dòng)傳遞的衰減由蜘蛛種群每個(gè)維度的標(biāo)準(zhǔn)差σ和振動(dòng)衰減率Ra影響。又因蜘蛛種群每個(gè)維度的標(biāo)準(zhǔn)差σ主要由初始化隨機(jī)決定，因此振動(dòng)衰減率Ra為主要SSA的主要控制參數(shù)。然而通過實(shí)驗(yàn)發(fā)現(xiàn)，在SSA中以10000倍的跨度調(diào)節(jié)振動(dòng)衰減率Ra對(duì)傳統(tǒng)社會(huì)蜘蛛優(yōu)化算法（SSA）的全局優(yōu)化能力并無太大改善。通過分析發(fā)現(xiàn)，該現(xiàn)象出現(xiàn)的主要原因是由于標(biāo)準(zhǔn)差σ值過于極端且隨機(jī)性強(qiáng)，變相使得振動(dòng)衰減率Ra的控制效力不足，造成振動(dòng)環(huán)節(jié)隨機(jī)性較強(qiáng)，SSA的全局優(yōu)化能力提升受限。

基于上述實(shí)驗(yàn)驗(yàn)證和分析，為提升社會(huì)蜘蛛優(yōu)化算法（SSA）的全局優(yōu)化能力，本文在粒子群優(yōu)化算法的權(quán)重因子思想上，結(jié)合迭代規(guī)律，引入振動(dòng)自適應(yīng)函數(shù)。

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

2.2 最優(yōu)鄰域擾動(dòng)

個(gè)體蜘蛛經(jīng)過迭代進(jìn)行位置更新時(shí)，一般以當(dāng)前迭代的最強(qiáng)振動(dòng)為方向進(jìn)行有目的的隨機(jī)游走。但目標(biāo)函數(shù)以及群體蜘蛛的位置均為未知，且個(gè)體振動(dòng)與個(gè)體接收振動(dòng)的量化均存人為經(jīng)驗(yàn)的判斷，因此在算法尋優(yōu)時(shí)不可避免的會(huì)出現(xiàn)算法早熟，陷入局部最優(yōu)的問題。為規(guī)避該問題，本文提出在SSA中引入最優(yōu)領(lǐng)域擾動(dòng)，在當(dāng)前最優(yōu)位置產(chǎn)生隨機(jī)擾動(dòng)，增加個(gè)體蜘蛛對(duì)附近空間的搜索能力，最優(yōu)領(lǐng)域擾動(dòng)如下。

式(9)中rand1、rand2為[0，1]之間的均勻產(chǎn)生的隨機(jī)數(shù)；為上一次迭代所處最佳位置的蜘蛛S，經(jīng)過最優(yōu)領(lǐng)域擾動(dòng)以后新位置。對(duì)于蜘蛛S新生成的領(lǐng)域位置采用貪婪機(jī)制判斷是否保留。

2.3 SA-SSA算法流程

SA-SSA綜合考慮了算法的收斂速度、全局和局部搜索能力。引入振動(dòng)自適應(yīng)函數(shù)用于提升算法收斂速度和全局搜索能力，引入最優(yōu)領(lǐng)域擾動(dòng)并結(jié)合貪婪機(jī)制增加最優(yōu)個(gè)體的局部搜索能力，具體算法流程如表1所示。

表1 SA-SSA算法流程表

2.4 算法復(fù)雜度分析

對(duì)于算法復(fù)雜度的分析，主要從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面展開。

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

空間復(fù)雜度則是用來評(píng)判一個(gè)算法對(duì)內(nèi)存空間的需求。本文所述的空間復(fù)雜度主要由蜘蛛種群的規(guī)模決定，而SA-SSA和SSA均采用相同的種群規(guī)模，因此兩種算法具有相同的空間復(fù)雜度O（N×D）。

3 仿真與分析

3.1 測(cè)試函數(shù)及性能指標(biāo)

為測(cè)試SA-SSA算法的尋優(yōu)能力，選擇了6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，其函數(shù)特性如表所示。算法尋優(yōu)精度為實(shí)際尋得最優(yōu)解與理論最優(yōu)解之間的誤差絕對(duì)值，本文采用兩個(gè)評(píng)價(jià)指標(biāo)：尋優(yōu)精度的平均值（Ave）和標(biāo)準(zhǔn)差（Std），其計(jì)算式分別如式(11)、式(12)所示。

3.2 優(yōu)化算法性能分析

將W-SSA算法在6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上進(jìn)行性能測(cè)試，并將其與蝙蝠優(yōu)化算法（BA）、人工魚群算法（AFA）以及傳統(tǒng)社會(huì)蜘蛛算法（SSA）進(jìn)行對(duì)比。算法參數(shù)設(shè)置相同：種群規(guī)模為30、最大迭代次數(shù)500。算法均分為10和30兩組優(yōu)化問題維度分別測(cè)試20次，得到優(yōu)化結(jié)果的平均精度及其標(biāo)準(zhǔn)差如表3、表4所示，其中黑色粗體為較優(yōu)結(jié)果。

算法主要參數(shù)設(shè)置如表3所示，算法收斂精度對(duì)比如表4所示。

表3 算法參數(shù)設(shè)置表

表4 算法收斂精度對(duì)比表

由表2可以看出改進(jìn)以后的SA-SSA在f1～f6的6個(gè)測(cè)試函數(shù)中其尋優(yōu)精度均優(yōu)于傳其他三種全局優(yōu)化算法。特別是在f1、f2、f3以及f6四個(gè)測(cè)試函數(shù)中，SA-SSA的尋優(yōu)精度具有極佳的表現(xiàn)。

表2 標(biāo)準(zhǔn)測(cè)試函數(shù)表

為進(jìn)一步驗(yàn)證SA-SSA算法在尋優(yōu)速度方面的表現(xiàn)，對(duì)收斂精度較好的SSA和SA-SSA在上述6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)下的求解收斂曲線進(jìn)行了對(duì)比，如圖2所示。

圖2 算法收斂速度對(duì)比圖

從圖中可以看出，SA-SSA算法在上述6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的收斂速度均明顯高于標(biāo)準(zhǔn)SSA。綜上所述，改進(jìn)后的SA-SSA算法在求解復(fù)雜函數(shù)最優(yōu)解時(shí)，比標(biāo)準(zhǔn)的SSA以及其他群智能優(yōu)化算法具有更高的尋優(yōu)精度，在收斂速度方面也相較于標(biāo)準(zhǔn)SSA更快。

4 結(jié)語

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