求解最優化問題的改進蜘蛛猴算法

姜 爽

(承德石油高等專科學校 數理部，河北 承德 067000)

蜘蛛猴算法(SMO)是2014年由Jagdish Chand Bansal等[1]學者提出的，是一種建立在對蜘蛛猴群覓食行為建模基礎上產生的新型解決優化問題的數值優化方法.根據原始SMO算法多種改進算法[2-4]被研發用來解決優化問題.本文設計了S-SMO算法并挑選了優化問題的測試函數進行了實驗，表明改進算法的多重評價性能均優于原算法和WSMO算法。

1 基本蜘蛛猴算法

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

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

最后算法會經歷全局領導人決策階段，此時若全局領導人的位置更新次數未達到已知的GlobalLeaderLimit的值，則猴群會將群體分成更多的組來覓食，重復這樣的操作到最大組數后，算法將所有小組合并成為一個組.這樣7個階段的操作被重復后算法會得到其尋優能力范圍內的最優解。

2 慣性權重正弦調整的蜘蛛猴算法

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

2.1 本地領導人進程中的權重改進

原算法中本進程中新位置的產生依靠的是本地領導人和群體成員的反饋.根據慣性權重公式的特點，在算法剛開始時，ω的值接近于本文設定的慣性權重的最小值，猴群在其自身附近進行局部尋優從而更能最大化地利用小組成員信息.隨著權重增大對解空間進行全局搜索，迭代后期進行局部開發和尋優，調整方式見(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代表慣性權重的最大值，ωmin為最小值，iter表示當前迭代次數，maxcycle是運行次數最大值.

2.2 本地領導人決策進程中的權重改進

當擾動率較大時算法會利用全局領導人和本地領導人的綜合反饋對每個個體的位置進行確定，此時我們為該階段個體位置增加同樣的慣性權重：

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

(3)

3 數值實驗

3.1 實驗設置

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

3.2 改進算法有效性測試

為了檢測S-SMO算法對最優化問題求解的效果，分別將SMO算法和S-SMO算法用于求解表1中的待優化函數其理論最優解均為“0”。先后對處于低維和高維的函數求解30次，實驗數據見表2和表3。

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

當被優化問題處于高維度時，SMO算法對函數的優化能力下降，但是S-SMO算法仍然保持著優異的求解性能和穩定性。求解f1-f3單峰函數時，在最優值、最差值

表1 本文選擇的測試函數

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

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

和均值3個指標上其精度均提高了1個數量單位，在穩定性角度標準差降低了1個單位.對于處于高維度的f4-f6函數，S-SMO算法的30次求解仍能得到最優值，且求解性能穩定.S-SMO算法對f5函數的優化雖然沒有達到理論最優解“0”，但得出的平均值精度提高了 15 個單位，且標準差為“0”具有很好的穩定性。

3.3 算法效率測試

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

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

5 結束語

蜘蛛猴算法作為一種新開發的群體智能算法在處理優化問題時表現著非常優異的性能，本文設計的S-SMO算法在探索原始SMO算法的原理上對其運行機制方面做出了改進，并在選取的標準函數上進行檢測結果顯示有效性，效率都高于原算法。