求解最優(yōu)化問(wèn)題的改進(jìn)蜘蛛猴算法

姜 爽

(承德石油高等?？茖W(xué)校 數(shù)理部，河北 承德 067000)

蜘蛛猴算法(SMO)是2014年由Jagdish Chand Bansal等[1]學(xué)者提出的，是一種建立在對(duì)蜘蛛猴群覓食行為建?；A(chǔ)上產(chǎn)生的新型解決優(yōu)化問(wèn)題的數(shù)值優(yōu)化方法.根據(jù)原始SMO算法多種改進(jìn)算法[2-4]被研發(fā)用來(lái)解決優(yōu)化問(wèn)題.本文設(shè)計(jì)了S-SMO算法并挑選了優(yōu)化問(wèn)題的測(cè)試函數(shù)進(jìn)行了實(shí)驗(yàn)，表明改進(jìn)算法的多重評(píng)價(jià)性能均優(yōu)于原算法和WSMO算法。

1 基本蜘蛛猴算法

首先程序會(huì)產(chǎn)生一個(gè)規(guī)模為N的蜘蛛猴群.SMOi代表群體中第i個(gè)猴子,同時(shí)也為D維被優(yōu)化函數(shù)潛在的解。按：SMOij=SMOminj+rand(0,1)×(SMOmaxj-SMOminj)確定其自身位置.我們稱第2階段為本地領(lǐng)導(dǎo)人階段，在本進(jìn)程中新位置的產(chǎn)生依靠的是本地領(lǐng)導(dǎo)人和群體成員的反饋所決定即SMOnewij=SMOij+rand(0,1)×(LLkj-SMOij)+rand(-1,1)×(SMOrj-SMOij)，LLk是第k組本地領(lǐng)導(dǎo)人位置向量.當(dāng)實(shí)現(xiàn)了本地領(lǐng)導(dǎo)人階段，隨即開(kāi)始進(jìn)行全局領(lǐng)導(dǎo)人進(jìn)程：SMOnewij=SMOij+rand(0,1)×(GLj-SMOij)+rand(-1,1)×(SMOrj-SMOij)，GLj代表全局領(lǐng)導(dǎo)人位置向量，此時(shí)位置的改變依靠的是全局領(lǐng)導(dǎo)人和小組成員的反饋。

接下來(lái)展開(kāi)全局領(lǐng)導(dǎo)人學(xué)習(xí)進(jìn)程，判斷全局領(lǐng)導(dǎo)人的位置是否得到了改變，如未得到改變則GlobalLimitCount增加1。隨后算法開(kāi)展本地領(lǐng)導(dǎo)人學(xué)習(xí)階段，同樣地，判斷本地領(lǐng)導(dǎo)人位置是否更新，否則LocalLimitCount增加1。在以上兩階段本地領(lǐng)導(dǎo)人位置和全局領(lǐng)導(dǎo)人位置由距離“食物源”最近的個(gè)體位置確定。第6階段為本地領(lǐng)導(dǎo)人決策階段，若本地領(lǐng)導(dǎo)人位置更新次數(shù)未達(dá)到已知的LocalLeaderLimit的值，那么該小組的所有成員啟動(dòng)新的公式：SMOnewij=SMOij+rand(0,1)×(GLj-SMOij)+rand(0,1)×(SMOij-LLkj)來(lái)改變位置。

最后算法會(huì)經(jīng)歷全局領(lǐng)導(dǎo)人決策階段，此時(shí)若全局領(lǐng)導(dǎo)人的位置更新次數(shù)未達(dá)到已知的GlobalLeaderLimit的值，則猴群會(huì)將群體分成更多的組來(lái)覓食，重復(fù)這樣的操作到最大組數(shù)后，算法將所有小組合并成為一個(gè)組.這樣7個(gè)階段的操作被重復(fù)后算法會(huì)得到其尋優(yōu)能力范圍內(nèi)的最優(yōu)解。

2 慣性權(quán)重正弦調(diào)整的蜘蛛猴算法

增強(qiáng)探索和開(kāi)發(fā)最優(yōu)解的能力是提高群體智能算法尋優(yōu)、求解能力的兩個(gè)重要指標(biāo)，蜘蛛猴算法作為一種新型算法創(chuàng)造性地平衡了其兩種尋優(yōu)方式.本文在其原始程序運(yùn)行的基礎(chǔ)上在本地領(lǐng)導(dǎo)人階段及其決策階段調(diào)節(jié)蜘蛛猴個(gè)體位置變化的頻率和周期性即增加了正弦調(diào)整[6]的慣性權(quán)重，ω=ωmin*(1-sin(t))+rand*ωmax*sin(t)，t=π*iter/maxCycle。該權(quán)重調(diào)節(jié)中，在迭代早期慣性權(quán)重ω的值很小，使得每個(gè)蜘蛛猴個(gè)體在其周圍進(jìn)行局部尋優(yōu)，可以規(guī)避在初期陷入局部最優(yōu)解從而發(fā)展為停滯狀態(tài)。隨著算法的推進(jìn)，迭代次數(shù)在不斷地上升則ω的值不斷增大，導(dǎo)致猴群個(gè)體之間協(xié)作程度增大，猴群更側(cè)重全局尋優(yōu)。后期猴群對(duì)最優(yōu)解進(jìn)行局部的開(kāi)發(fā)和搜索。這樣的設(shè)計(jì)即對(duì)蜘蛛猴群搜索的初期及末期都進(jìn)行了正弦調(diào)整。公式中h的變動(dòng)規(guī)律增加了ω變化的周期性且rand函數(shù)的引入為ω的變化增添了隨機(jī)性.

2.1 本地領(lǐng)導(dǎo)人進(jìn)程中的權(quán)重改進(jìn)

原算法中本進(jìn)程中新位置的產(chǎn)生依靠的是本地領(lǐng)導(dǎo)人和群體成員的反饋.根據(jù)慣性權(quán)重公式的特點(diǎn)，在算法剛開(kāi)始時(shí)，ω的值接近于本文設(shè)定的慣性權(quán)重的最小值，猴群在其自身附近進(jìn)行局部尋優(yōu)從而更能最大化地利用小組成員信息.隨著權(quán)重增大對(duì)解空間進(jìn)行全局搜索，迭代后期進(jìn)行局部開(kāi)發(fā)和尋優(yōu)，調(diào)整方式見(jiàn)(1)和(2):

ω=ωmin*(1-sin(t))+rand*ωmax*sin(t)

(1)

SMOnewij=ω×SMOij+rand(0,1)×(LLkj-SMOij)+rand(-1,1)×(SMOrj-SMOij)

(2)

該式中，t=π*iter/maxcycle。其中ωmax代表慣性權(quán)重的最大值，ωmin為最小值，iter表示當(dāng)前迭代次數(shù)，maxcycle是運(yùn)行次數(shù)最大值.

2.2 本地領(lǐng)導(dǎo)人決策進(jìn)程中的權(quán)重改進(jìn)

當(dāng)擾動(dòng)率較大時(shí)算法會(huì)利用全局領(lǐng)導(dǎo)人和本地領(lǐng)導(dǎo)人的綜合反饋對(duì)每個(gè)個(gè)體的位置進(jìn)行確定，此時(shí)我們?yōu)樵撾A段個(gè)體位置增加同樣的慣性權(quán)重：

SMOnewij=ω×SMOij+rand(0,1)×(GLj-SMOij)+rand(0,1)×(SMOij-LLkj)

(3)

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

猴群群體規(guī)模N設(shè)定為50，最大迭代次數(shù)M為2 000次,猴群可以被劃分的最大組數(shù)：DP=N/10。ωmax=0.8,ωmin=0.4,GlobalLeaderLimit=N,LocalLeaderLimit=N×D。擾動(dòng)率：Hiter+1=Hiter+0.4/maxCycle,H1=0.1。

3.2 改進(jìn)算法有效性測(cè)試

為了檢測(cè)S-SMO算法對(duì)最優(yōu)化問(wèn)題求解的效果，分別將SMO算法和S-SMO算法用于求解表1中的待優(yōu)化函數(shù)其理論最優(yōu)解均為“0”。先后對(duì)處于低維和高維的函數(shù)求解30次，實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表2和表3。

當(dāng)被優(yōu)化問(wèn)題處于低維度時(shí)，我們可以觀察到此兩種算法都能取得比較好的效果，其中f1-f3為單峰待優(yōu)化函數(shù)，S-SMO算法對(duì)其優(yōu)化的能力高于SMO算法，尋優(yōu)均值的精度均提升了1個(gè)數(shù)量單位，標(biāo)準(zhǔn)差降低了1個(gè)單位。原算法對(duì)f4函數(shù)平均值的精度與S-SMO算法相比低了8個(gè)數(shù)量單位，對(duì)f6函數(shù)優(yōu)化性能更不理想。S-SMO算法對(duì)表中f4-f6多峰函數(shù)的求解都能達(dá)到最優(yōu)解“0”，且穩(wěn)定性指標(biāo)即標(biāo)準(zhǔn)差為“0”。而對(duì)f5函數(shù)的求解雖未達(dá)到理論最小值“0”，但是平均值精度較SMO算法提升了12個(gè)數(shù)量單位，標(biāo)準(zhǔn)差為“0”，表現(xiàn)了優(yōu)異的穩(wěn)定性。

當(dāng)被優(yōu)化問(wèn)題處于高維度時(shí)，SMO算法對(duì)函數(shù)的優(yōu)化能力下降，但是S-SMO算法仍然保持著優(yōu)異的求解性能和穩(wěn)定性。求解f1-f3單峰函數(shù)時(shí)，在最優(yōu)值、最差值

表1 本文選擇的測(cè)試函數(shù)

表2 兩種算法有效性對(duì)比(D=30)

表3 兩種算法有效性對(duì)比(D=100)

和均值3個(gè)指標(biāo)上其精度均提高了1個(gè)數(shù)量單位，在穩(wěn)定性角度標(biāo)準(zhǔn)差降低了1個(gè)單位.對(duì)于處于高維度的f4-f6函數(shù)，S-SMO算法的30次求解仍能得到最優(yōu)值，且求解性能穩(wěn)定.S-SMO算法對(duì)f5函數(shù)的優(yōu)化雖然沒(méi)有達(dá)到理論最優(yōu)解“0”，但得出的平均值精度提高了 15 個(gè)單位，且標(biāo)準(zhǔn)差為“0”具有很好的穩(wěn)定性。

3.3 算法效率測(cè)試

為了更加形象地展示SMO、S-SMO和WSMO算法對(duì)各個(gè)函數(shù)不同的求解效果，比較算法在收斂速率、最少迭代數(shù)量等效率上的差異.當(dāng)函數(shù)處于30維時(shí)，利用軟件仿真出3個(gè)算法在各個(gè)函數(shù)上的收斂圖像。

如圖1～圖6所示，S-SMO算法最有能力尋找到最優(yōu)解，在6個(gè)問(wèn)題上的求解均優(yōu)于其他兩種算法，且達(dá)到目標(biāo)精度的迭代次數(shù)大大少于SMO算法和WSMO算法，搜索速度最快.通過(guò)觀察圖像可以發(fā)現(xiàn)WSMO算法改善了原始SMO算法極易陷入局部最優(yōu)的情況，但是仍存在被短暫地困在局部最優(yōu)附近的情形，例如WSMO算法在f1函數(shù)的200-400代，f2函數(shù)的200代周圍，f4函數(shù)的500～600代均暫時(shí)性地停留在局部最優(yōu)解，S-SMO算法對(duì)停留于局部最優(yōu)情況的改善更加明顯,與此同時(shí)可以迅速地捕捉到最優(yōu)解。S-SMO算法僅需要少量的迭代就可以符合規(guī)定精度的要求.在時(shí)耗角度由于迭代的減少?gòu)亩鴷?huì)壓縮處理問(wèn)題的運(yùn)行時(shí)間，收斂速度即效率得到了提高。

5 結(jié)束語(yǔ)

蜘蛛猴算法作為一種新開(kāi)發(fā)的群體智能算法在處理優(yōu)化問(wèn)題時(shí)表現(xiàn)著非常優(yōu)異的性能，本文設(shè)計(jì)的S-SMO算法在探索原始SMO算法的原理上對(duì)其運(yùn)行機(jī)制方面做出了改進(jìn)，并在選取的標(biāo)準(zhǔn)函數(shù)上進(jìn)行檢測(cè)結(jié)果顯示有效性，效率都高于原算法。