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

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

0 引言

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

為進(jìn)一步提高社會蜘蛛智能優(yōu)化算法（SSA）尋優(yōu)能力，有學(xué)者提出引入隨機(jī)交叉策略用于個體蜘蛛的更新，通過快速的個體更新策略提高SSA的搜索速率[9]；采用自適應(yīng)尋優(yōu)和偏好隨機(jī)游動機(jī)制，以迭代次數(shù)為變量來提高SSA在多峰測試函數(shù)中的全局搜索能力和尋優(yōu)精度[10]；引入分層協(xié)作思想將蜘蛛群體劃分為兩個分工種類，并結(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)都沒有考慮到振動強(qiáng)度對算法全局搜索能力的影響。

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

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

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

1.1 蜘蛛信息

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

圖1 社會蜘蛛示意圖

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

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

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

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

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

1.2 振動產(chǎn)生

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

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

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

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

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

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

1.3 游走尋優(yōu)

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

游走尋優(yōu)的本質(zhì)是基于概率的一種游走形式，在SSA中規(guī)定了每一個蜘蛛均攜帶一個固定分配的二進(jìn)制編碼表M（該表為pop×dim的矩陣，pop表示種群數(shù)量，dim表示待優(yōu)化問題的維度），在算法初始階段矩陣中各個元素均為零，在每輪迭代的過程中蜘蛛S具有的概率改變矩陣（其中Cs表示自上一次改變目標(biāo)振動后的迭代次數(shù)）。當(dāng)M矩陣被判定為改變以后，M中的每個元素均有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)對點(diǎn)乘運(yùn)算。

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

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

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

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

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

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

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

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

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

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

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

2.3 SA-SSA算法流程

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

表1 SA-SSA算法流程表

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

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

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

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

3 仿真與分析

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

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

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

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

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

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

表4 算法收斂精度對比表

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

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

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

圖2 算法收斂速度對比圖

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

4 結(jié)語

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