第四章 蜘蛛猴優化算法

群居生物的覓食行為一直是優化算法研究的熱點問題。蜘蛛猴優化(SpiderMonkey Optimization，SMO)是一種全局優化算法，靈感來自於蜘蛛猴在覓食過程中的裂變融合社會(Fission-Fusionsocial，FFS)結構。SMO巧妙地描述了群體智能的兩個基本概念：自組織和分工。SMO作為一種基於群體智能的算法，近年來得到了廣泛的應用，並被應用於許多工程優化問題中。這一部分詳細介紹了蜘蛛猴優化算法。為了更好地理解SMO過程的工作原理，給出了一個SMO過程的數例。

4.1 蜘蛛猴優化

蜘蛛猴優化(SMO)算法是近年來出現的一種基於群體智能的優化算法[1, 2]，更新方程是基於可能解之間的歐氏距離該算法已廣泛應用於求解複雜的優化問題。在[3]中，Dhar和Arora應用蜘蛛猴優化算法(SMO)設計和優化了一個模糊規則庫；Sharma等人[4]將SMO應用於IEEE-14、30和33測試總線系統中，在適當分配3和5個電容器的情況下，解決最優電容器配置和尺寸問題；Wu等人[5]將SMO用於稀疏線性陣列的合成。利用SMO算法對擴展稀疏子陣中所有元素的幅值和位置進行優化，從而在一組實際約束條件下降低整個陣列的旁瓣電平；Cheruku等人設計了用於糖尿病數據規則挖掘任務的SM-RuleMiner[6]。SMO還被用於合成線性天線陣的陣列因子，並為無線應用優化設計了一種E形貼片天線[7]。

4.1.1 動機4.1.1.1裂變融合社會結構的出現

裂變融合社會的概念是生物學家「漢斯·庫默」在解釋最複雜的哺乳動物阿拉伯狒狒的社會組織時提出的。由於季節變化導致食物短缺時，母系群體成員之間的食物競爭導致分裂成許多群體，然後融合成一個單一的群體。當食物供應充足時，群體是最大的，而在最小的群體中，食物短缺處於頂峰。裂變部分表現了蜘蛛猴的覓食行為，融合是將較小的群體組合成較大的群體。

4.1.1.2蜘蛛猴的覓食行為蜘蛛猴生活在中美洲和南美洲的熱帶雨林中，北至墨西哥[8]。蜘蛛猴是世界最聰明的猴子之一。它們被稱為蜘蛛猴，因為當它們通過尾巴掛起來的時候看起來像蜘蛛[9]。蜘蛛猴總是喜歡生活在一個稱為父群的單元組中。根據食物的稀缺性或充足性，它們會自動拆分或合併。它們之間通過手勢、姿勢和叫聲進行交流。群體組成（Groupcomposition）是這個結構中的一個動態屬性。4.1.1.3社會組織與行為1.蜘蛛猴生活在一個大約40-50隻個體的群體中；2.這個群落裡的所有個體在白天時都以小組的形式朝不同的方向覓食，晚上每個個體都在自己的棲息地分享覓食的經驗。4.如果領頭沒有找到足夠的食物，她就把小組分成更小的小組，這些小組分別覓食；5.社會中的個體可能不會因為彼此之間的相互寬容而在一個地方被注意到。當他們接觸時，他們的手勢反映出他們實際上是一個大群體的一部分。4.1.1.4交流蜘蛛猴通過位置和姿勢分享它們的意圖和觀察結果。在很遠的距離，它們通過特定的聲音相互交流，如大叫或鳴叫。每隻猴子都有自己可辨別的聲音，其他小組成員可以通過這些聲音辨別出那隻猴子。

圖1 蜘蛛猴的覓食行為

4.1.1 蜘蛛猴優化過程SMO是一種元啟發式技術，靈感來自於蜘蛛猴的智能覓食行為。蜘蛛猴的覓食行為是基於分裂融合的社會結構。該算法的特點依賴於一個群體的社會組織，在這個群體中，女性領導者決定是分裂還是合併。整個團隊的領導者在這裡被命名為全局領導者，而小組織的領導者被稱為為局部領導者。參考SMO算法，食物短缺現象被定義為解不再改善。由於SMO是一種基於群體智能的算法，所以每個小群體都應該有一個最小數量的猴子。因此，在任何時候，如果進一步的裂變產生了至少一組少於最小數量的猴子，我們將其定義為融合時間。在SMO算法中，蜘蛛猴(SMO)表示一個可選解。SMO由六個階段組成：局部領導者階段、全局領導者階段、局部領導者學習階段、全局領導者學習階段、局部領導者決策階段和全局領導者決策階段。接下來將解釋SMO的所有這些階段：

在初始化階段，SMO生成一個包含N個蜘蛛猴的均勻分布初始群體，  SMi代表群體中的第i個蜘蛛猴，每個SMi按下式初始化：

（1）

其中SMminj和SMmaxj是搜索空間中第維的下界和上界，U（0,1）是（0,1）內均勻分布的隨機數。

局部領導者階段（LLP）：

這是SMO算法的一個重要階段。在這裡，所有的蜘蛛猴都有機會更新自己。蜘蛛猴基於其局部領導者和小組成員的經驗更新其位置。在新的位置計算每個蜘蛛猴的適應度值，如果適應度高於其舊的位置，則更新，否則不更新。這裡，位置更新方程為

（2）

其中，SMij是第i個蜘蛛猴的第j維，LLkj代表第k組局部領導者的第j維，SMrj是從第k組中隨機選擇的蜘蛛猴的第j維，且r≠i，U(-1,1)是（-1,1）範圍內均勻分布的隨機數。

從公式（2）中可以清楚地看出，待位置更新的蜘蛛猴在保持自己的自信或堅持時，會被局部領導者吸引，最後一部分有助於在搜索過程中引入擾動，維持算法的隨機性，從而避免過早停滯。這個階段的完整位置更新過程見算法1，該算法中pr表示當前解的擾動率，其值一般位於[0.1,0.8]。

for 每一個屬於第k組的成員SMi  do  for 每一個維度j∈{1,2，…，D}  do    if U(0,1)≥pr then      使用式（2）更新位置；    else      不更新位置，即SMnewij=SMij ；    end if  end forend for
全局領導者階段（GLP）：
完成局部領導者階段後，算法進入全局領導者階段，這裡基於某一選擇概率進行解的更新，而選擇概率是適應度的函數。從目標函數fi可以根據下式計算處適應度fiti：
（3）
選擇概率probi由輪盤賭選擇確定，如果fiti是第i個蜘蛛猴的適應度，可以通過以下任一公式計算其在全局領導者階段被選中的概率：
蜘蛛猴利用全局領導者的知識、臨近SM的經驗和自身的堅持來更新自己的位置。該階段位置更新方程為
（4）
其中GLj是全局領導者在第j維上的位置，該位置更新等式包含三部分：第一部分展示了父（當前）蜘蛛猴的持久性，第二部分將父蜘蛛猴朝全局領導者方向吸引，最後一項用於維持算法的隨機性。在這個等式中，第二項用於加強對已確定的搜索空間的利用，第三項用於避免搜索過程早熟收斂，降低陷入局部最優的機會。該階段的整個搜素過程見算法2。
count=0；while count<種群大小 do  for 群內的每一個成員 do    if U(0,1)<probi then      count=count+1;      隨機選擇維度j∈{1,2，…，D}；      隨機選擇蜘蛛猴SMr且r≠i；      使用式（4）進行位置更新；    end if  end forend while
顯然，算法2中更新解的機會取決於probi,因此高適應度的解相較於低適應度的解，有更多的機會更新其位置。此外，對已更新解應用貪婪選擇方法，即對於已更新和原有的蜘蛛猴，只考慮適應度更優的解。
全局領導者學習階段：
在此階段，算法找出整個群體的最優解，被識別的蜘蛛猴被認為是群體的全局領導者。此外，檢查全局領導者的位置，如果不更新它，那麼與全局領導者關聯的計數器(稱為全局限制計數(globalLimit Count, GLC))將增加1，否則將設置為0。檢查全局領導者的全局限制計數，並與全局領導者限制比較。
局部領導者學習階段：
在算法的這一階段中，通過對組內成員進行貪婪選擇來更新局部領導者的位置。如果局部領導者沒有更新其位置，那麼與局部領導者關聯的計數器localLimit Count (LLC)將增加1;否則計數器被設置為0。此過程應用於每個組，以找到其各自的局部領導者。局部限制計數是一個計數器，它會遞增，直到達到一個固定的閾值，稱為局部領導者限制LocalLeader Limit (LLL)。
局部領導者決策階段：
在此階段之前，已經確定了局部領導者和全局領導者。如果有任何局部領導者沒有被重新組織到一個特定的邊緣，也就是所謂的局部領導者限制，然後，該組所有成員通過隨機初始化或通過公式(5)使用全局領導者的經驗來更新他們的位置。按照一個被稱為擾動率的概率 pr應用公式(5)。
(5)
從這個方程可以看出，當現有的局部領導者被耗盡(迭代LLL次沒有更新)時，該組的解被排斥，而解被吸引向全局領導者，以改變現有的搜索方向和位置。基於pr,隨機初始化解的某些維數，在解的現有位置引入擾動。這裡局部領導者限制是檢查局部領導者是否陷入局部極小值的參數，通常計算為DxN，其中D為維度，N為SM的總數。如果LLC大於LLL，則將LLC設置為零，並按照上面描述的方式初始化SM，以改進搜索空間的探索。
算法3局部領導者決策階段（LLD）
if 局部限制計數>局部領導者限制 then  局部限制計數=0；  for 每一個維度 do    if U(0,1)≥pr then       使用公式（1）初始化；    else       使用公式（5）更新；    end if  end forend if
全局領導者決策階段：
類似於局部領導者決策階段，如果全局領導者沒有被重新組織到一個特定的邊緣，即全局領導者限制，那麼全局領導者會將群體劃分成更小的組或將組融合為一個單元組。這裡全局領導者限制GLL是檢查是否存在早熟的參數，一般取值範圍為[n/2,2N]。如果全局領導者計數超過全局領導者限制，那麼設置計數為0，同時比較組數與最大組數。如果現有的組數少於預定義的最大組數，那麼全局領導者會進一步分組，否則通過組合形成單個父組。算法4中描述了分裂-融合過程。
if 全局限制計數>全局領導者限制  全局限制計數=0；  if 組數<MG then    分裂群體成組；  else    組合所有的組為一個組；  end if  更新局部領導者位置；end if
Step1. 初始化種群、局部領導者限制、全局領導者限制和擾動率pr；Step2. 評估種群；Step3. 識別全局和局部領導者；Step4. 局部領導者階段位置更新（算法1）；Step5. 全局領導者階段位置更新（算法2）；Step6. 通過全局領導者學習階段進行學習；Step7. 通過局部領導者學習階段進行學習；Step8. 局部領導者決策階段位置更新（算法3）；Step9. 全局領導者決策階段決定分裂或融合（算法4）；Step10. 如果滿足終止條件則停止，並將全局領導者位置聲明為最優解，否則跳轉至Step4。
4.2 SMO分析在尋找最優解的同時，SMO更好地平衡了利用和探索。局部領導者階段用於探索搜索區域，在這個階段，所有的組成員都會更新他們的位置，並且在維數上有很高的擾動。而全局領導者階段促進了利用，在這個階段，更好的候選人有更多的機會更新他們的位置。該特性使SMO在基於搜索的優化算法中成為較好的候選對象。SMO還擁有一種內置的停滯檢查機制。局部領導者學習階段和全局領導者學習階段，用於檢查搜索過程是否停滯不前。在停滯的情況下(在局部或全局層面)，局部領導者和全局領導者的決策階段將工作。局部領導者決策階段創建了一個額外的探索，而在全局領導者決策階段，則做出關於裂變或聚變的決策。因此，在保持收斂速度的同時，SMO可以更好地平衡探索和利用。4.3 SMO參數SMO主要有四個控制參數：局部領導者限制（LLL）、全局領導者限制（GLL）、最大組數（MG）和擾動率pr。下面給出了參數的建議設置：4.4 SMO性能分析在[2]將SMO的性能與三種著名的元啟發式算法，即人工蜂群算法(ABC)、差分進化算法(DE)和粒子群優化算法(PSO)進行了對比分析。通過對25個基準問題的測試和各種統計測試，得出的結論是SMO是一種具有競爭力的元啟發式優化算法，在單峰、多峰、可分性和不可分性優化問題中具有良好的性能。對於連續優化問題，SMO比PSO、ABC或DE具有更好的可靠性。4.5 求解案例這一節描述了一個使用SMO的數值案例，逐步求解簡單的優化問題。
GLL∈[N/2，2N]=[10,40]，取GLL=30。
初始化：
在[-5,5]範圍內隨機初始化20個食物源的位置（蜘蛛猴）。

這裡由於最大的適應度為0.885，對應的是第10個蜘蛛猴，因此第10個蜘蛛猴就為全局領導者，在此階段只有單一一個組，所以該蜘蛛猴也是局部領導者。
位置更新階段：
在此階段，所有的蜘蛛猴都有機會更新其位置，更新公式見（2）。對於第一個維度j=1，生成一個隨機數U(0,1)，設U(0,1)=0.3。由於U(0,1)≥pr(=0.7)為false，因此SMnew11=SM11。對於j=2，設U(0,1)=0.8，由於pr≤0.8，SM12將進行更新。如果隨機選擇鄰域解索引r=6，且U(-1,1)=-0.7，則SMnew12=1.2+0.8(0.2-1.2)+(-0.7)(3.2-1.2)=-1計算其函數值和適應度值，f1(SMnew1)=2.96，fit(SMnew1)=0.252。基於適應度值對SMnew1和SM1進行貪婪選擇，由於0.252>0.227，所以新解SMnew1更優，所以SM1=(1.4,-1)。
對於全局領導者階段，需要根據適應度向量計算概率函數，即probi=0.9xfiti/max_fit+0.1，這裡max_fi=0.9041，對應著第11個解。下表列出了適應度概率。
在此階段，蜘蛛猴將基於上面計算的概率probi按照式（4）進行更新，更新數量取決於種群大小。這裡只展示第8和第17隻蜘蛛猴的更新過程。需要注意的是，每個被選擇的解只需要更新其一個維度。
更新第8個蜘蛛猴（i=8）
prob8=0.929521，設U（0,1）=0.6<prob8，因此需要更新該蜘蛛猴。對SM8進行全局領導者階段位置更新，得到SMnew8=（0.4，-0.75），計算得到函數值和適應度值分別為f8(x)=0.7225和fit8=0.5805。由於0.5805<0.8333，所以不對SM8進行更新。
更新第17個蜘蛛猴（i=17）
prob17=0.6692，設U（0,1）=0.52<prob17，因此需要更新該蜘蛛猴。對SM17進行全局領導者階段位置更新，得到SMnew17=（-0.264，-0.33），計算得到函數值和適應度值分別為f17(x)=0.1785和fit17=0.8484。由於0.8484>0.5718，所以對SM17進行更新，得到SM17=（-0.264，-0.33）。第一輪過後（所有解都有機會更新其位置），蜘蛛猴的新位置如下：
在全局領導者階段的第一輪，一共有12個解得到了更新，根據本階段的終止條件，更新次數應該等於種群中蜘蛛猴的個數，因此開始下一輪更新蜘蛛猴。第二輪過後，蜘蛛猴更新後的位置如下：
目前在此階段，蜘蛛猴的總更新次數為20，所以該階段停止。很顯然，具有更高適應度的解將有更多的機會更新其位置，從而提高算法的利用能力。
全局領導者學習階段
全局領導者學習階段決定了群體的全局領導者。所有解的適應度將相互比較，如果全局領導者獲得更好的位置，則將全局限制計數設置為0，否則將其增加1。由於第9個蜘蛛猴的適應度在更新後的群體中是最好的，所以它成為了全局領導者。此外，全局限制計數將被設置為0，因為全局領導者已經更新。
局部領導者學習階段
局部領導者學習階段決定了小組的局部領導者。與全局領導者學習階段類似，所有解的適應度都將相互比較。如果局部領導者獲得更好的位置，則將局部限制計數設置為0，否則將計數增加1。這裡我們只有一個組，所以第9個蜘蛛猴既是全局領導者，也是局部領導者。局部限制計數被設置為0，因為已更新了局部領導者。
局部領導者決策階段
根據我們的參數設置，局部領導者限制是40。因為局部限制計數=0<40，所以此階段不執行。
全局領導者決策階段
在此階段，將監視全局領導者的位置，如果達到全局領導者限制(本例中為30)次沒有更新，則將種群劃分為更小的組。如果子組的數量達到其最大計數(本例中為=2)，則將所有子組組合成一個組。在做出決定後，將全局限制計數設置為0，並更新局部領導者的位置。
為了解釋全局領導者決策階段的作用，考慮這樣一個情況：對於某個迭代，全局限制計數為31，然後將該組劃分為兩個子組。解SM1-SM10屬於第一組，而SM11-SM20屬於第二組。假設群體由下表表示：
由於第9個蜘蛛猴的適應度在第一組的所有蜘蛛猴中最高，因此它被指定為第一組的局部領導者，即LL1=(-0.4,0.1)。其次，第二組中第19蜘蛛猴的適應度最高，被認為是第二組的局部領導者，即LL2=(-0.4,0.3)。對於兩個局部領導者，局部限制計數都被設置為0。
也可以看出，第9個蜘蛛猴的適應度在群體的所有成員中是最好的，因此第9個蜘蛛猴被認為是群體的全局領導者，即GL=(-0.4,0.1)。由於執行了全局領導者決策，全局限制計數變為0。
經過全局領導者決策階段後，再由局部領導者階段和其他階段以類似的方式對群體進行更新。此過程將迭代地繼續，直到達到終止條件。
4.6 結論
本部分中，討論了一種基於群體智能的算法-蜘蛛猴優化算法，該算法從蜘蛛猴的社會行為中得到啟發。在SMO中，局部領導者階段和全局領導者階段有助於利用搜索空間，而探索則通過局部領導者決策階段和全局領導者決策階段完成。SMO性能分析表明，SMO在可靠性、有效性和精度方面超過了ABC、DE和PSO。然而，SMO中存在大量依賴於用戶的參數，是需要進一步研究的問題。自適應參數調整有助於提高算法的魯棒性和可靠性。僅僅在4年內，就有大量關於SMO的開發和應用的出版物，這表明SMO具有成為高效優化器的巨大潛力。
備註：SMO代碼（C++,Python和Matlab）可在http://smo.scrs.in/下載（可直接點擊閱讀原文）。
參考文獻
1.     Bonabeau, E., M. Dorigo, and G. Theraulaz, Swarm intelligence: from natural toartificial systems. 1999: Oxford University Press, Inc. 307.2.     Bansal, J., et al., Spider Monkey Optimization algorithm for numerical optimization.Memetic Computing, 2014. 6.3.     Dhar, J. and S. Arora, Designing Fuzzy Rule Base using Spider Monkey Optimization Algorithm inCooperative Framework. Future Computing and Informatics Journal, 2017. 2.4.     Sharma, A., et al., Optimal placement and sizing of capacitor using Limaçon inspired spidermonkey optimization algorithm. Memetic Computing, 2016. 9(4): p. 311-331.5.     Wu, H., et al., Pattern Synthesis of Sparse Linear Arrays Using Spider MonkeyOptimization. IEICE Transactions on Communications, 2017. E100.B(3): p. 426-432.6.     Cheruku, R., D.R. Edla, and V. Kuppili, SM-RuleMiner: Spider monkey based rule minerusing novel fitness function for diabetes classification. Comput Biol Med,2017. 81: p. 79-92.7.     Al-Azza, A.A., A.A. Al-Jodah, and F.J.Harackiewicz, Spider Monkey Optimization:A Novel Technique for Antenna Optimization. IEEE Antennas and WirelessPropagation Letters, 2016. 15: p.1016-1019.8.     SpiderMonkeys. Available from: https://www.nationalgeographic.com/animals/mammals/group/spider-monkeys/.9.     ANIMALCORNER. Available from: https://animalcorner.co.uk/animals/spider-monkey/.