具有隨機分形自適應搜索策略的蟻獅優化算法*

趙克新，黃長強，王 淵

（空軍工程大學航空航天工程學院，西安 710038）

0 引言

蟻獅優化算法［1］（Ant Lion Optimizer，ALO）作為一種新的群智能優化算法，是澳大利亞學者Seyedali在2015年提出來的。相比于遺傳算法［2］、粒子群算法［3］、人工蜂群算法［4-5］（Artificial Beecolony Algorithm，ABC）、蟻群算法［6］，由于蟻獅優化算法包含螞蟻游走和蟻獅捕獵兩種行為，在求解復雜函數優化問題時表現出了更強的探索能力和開發能力［7］。同時該算法具有調節參數少，易于實現等優點，引起了很多學者的關注。在建立離散濾波器模型［8］、解決無線傳感網絡的數據收集［9］問題、可再生分布式產能的優化配置［10］、解決無人機航跡規劃［11-12］問題等方面表現出優越的性能。

ALO算法作為新的群智能優化算法，本身還有很多待優化的方面，螞蟻在精英蟻獅的周圍隨機游走，步長隨著算法迭代次數的增加而減小，算法在后期容易出現陷入局部最優［13］、收斂速度慢、搜索精度不高等問題，從而給算法的實際應用帶來了負面影響［14-15］。針對這一問題，本文提出了一種具有隨機分形自適應搜索策略的蟻獅優化算法（Ant Lion optimizer With Stochastic Fractal and Self-adaption Searching Strategy，SFSALO）。仿真結果表明，SFSALO算法很好地平衡了全局開發與局部探索能力，能夠有效解決復雜多維函數的優化問題。

1 標準ALO算法

蟻獅優化算法的靈感來源于蟻獅幼蟲捕食螞蟻的行為：螞蟻為了尋找食物在空間內隨機游走，蟻獅在沙丘內利用設計好的錐形陷阱獵捕螞蟻，當隨機游走的螞蟻落入陷阱，蟻獅便捕捉到了螞蟻并重新挖好陷阱等待另外的螞蟻。算法首先按照下式進行初始化：

螞蟻和蟻獅分別隨機生成SN個初始解，并計算每個蟻獅位置的優劣或者適應度值，同時進行排序，全局最優值。式（1）中，xn，i表示螞蟻或者蟻獅的位置，，ul和ub分別表示游走空間的下界和上界。螞蟻隨機游走數學表達式為：

式（2）中，cumsum表示計算數組累；m為螞蟻的數量；t為當前的迭代次數；r（t）是一個隨機函數，如下：

式（3）中，rand表示0到1之間的隨機數。

下列矩陣保存螞蟻的位置：

式中，d表示變量的維度，Ai，j表示第i只螞蟻在第j維上的位置。通過適應度函數評價螞蟻位置的優劣，螞蟻的適應度值保存在如下函數矩陣：

蟻獅的數量與螞蟻一致，其位置與適應度函數用下列矩陣表示：

式（4）中，d表示變量的維度，通過適應度函數MAP評價蟻獅的位置。螞蟻在第i維的位置更新公式：

式（8）中，ai和bi為第i只螞蟻隨機游走的最小步長和最大步長；cti和dti分別為螞蟻第t次迭代時的變量的最小值和最大值。cti和dti分別定義如下：

式中，ct表示蟻獅第t次迭代時變量的最小值和最大值。ct、dt的數學表達式如下：

式中，w為常值，t表示當前迭代次數，Tg表示最大迭代次數。

ALO算法將每次迭代的精英蟻獅個體EAntlion保存下來，螞蟻通過輪盤賭［20］的方式對蟻獅進行貪婪選擇并和螞蟻一樣在自身周圍隨機游走，表達式如下：

蟻獅在捉到螞蟻后的位置更新公式如下：

2 具有分形自適應搜索策略的蟻獅優化算法

群智能優化算法的探索與開發能力是決定算法效率的關鍵。開發能力指的是算法在特定區域內尋找并提取較優的解，探索能力是指在搜索空間內確定較優解的能力。ALO算法的螞蟻和蟻獅位置更新方程因選擇精英蟻獅進行游走而具有較強的開發能力。但同時可以看出，ALO算法的探索能力較弱，因而存在易陷入局部最優的問題。針對這一問題，提出了隨機分形自適應搜索策略，該策略主要是根據螞蟻的游走行為，提出了增強探索能力的隨機分形搜索方程；根據蟻獅重挖陷阱的行為，提出了增強開發能力的自適應搜索方程。下面對提出的策略進行詳細說明。

2.1 螞蟻隨機分形搜索方程

分形現象是自然界很常見的一種現象，例如植物的生長、山河的形成以及大腦皮層等，這種部分以某種方式與整體相似的形式稱為分形。隨機分形一般由不同的隨機原則反復迭代產生。常用的隨機原則有高斯游走（Gaussian Walk）、列維飛行（levy Flight）、自回避游走（Self-avoiding Walks）。列維飛行具有較強的全局搜索能力，將列維飛行與蟻獅優化算法中螞蟻的搜索行為相結合，提出了螞蟻隨機分形搜索方程：

式中，q表示種群數量，α表示比例因子，Xi表示最初的螞蟻位置。通過上述改進有效地提高了螞蟻對整個解空間的探索能力。

圖1 單個粒子隨機分形示意圖

2.2 蟻獅自適應搜索方程

標準ALO算法中蟻獅根據螞蟻進行陷阱位置的調整，蟻獅與螞蟻采用相同的搜索方程，經過對算法的原理分析得到：蟻獅的行為方式影響了算法對解的精細化搜索。所以受到文獻［15］的啟發，提出了蟻獅自適應搜索方程：

式中，r是0到1之間的隨機數，Elibest表示蟻獅全局最優位置，表示種群i中第t只蟻獅的位置，iter表示當前迭代的次數。隨著迭代次數的增加，蟻獅搜索范圍自適應減小，在全局最優位置附近進行精細開發。

2.3 改進算法的分析與步驟

在標準的ALO算法的基礎上引入隨機分形自適應搜索策略，首先針對螞蟻的行為引入隨機分形原則，對其游走方程進行了改進，該方程利用列維飛行能夠很好地對搜索空間進行探索。其次在蟻獅設置陷阱行為的基礎上引入自適應因子，隨著循環次數的增加，自適應地平衡算法的開發與探索能力。算法的具體步驟如下：

1）初始化算法的各個參數；

2）計算每個蟻獅對應位置的適應度值并記錄全局最優值；

3）while結束條件不滿足；

4）螞蟻根據式（16）進行隨機分形游走，并計算更新后的適應度值，與全局最優值進行比較，采用貪婪選擇機制進行更替；

5）位置最佳蟻獅根據式（18）進行自適應陷阱設置，應用貪婪機制更新蟻獅最優位置；

6）判斷當前迭代次數是否超過極限值，如果條件不滿足，轉至第4）步；否則進入第7）步；

7）結束循環，輸出最優解。

3 仿真實驗

3.1 實驗環境與參數設置

為了驗證本文提出的SFSALO算法的特性，選取了3個單峰，3個多峰基準函數作為被測函數，并與ABC算法、ALO算法的測試結果進行比較。實驗硬件條件為 Inter（R）Core（TM）i5-6500，CPU，3.20 GHz，4 GB，RAM，Win7操作系統，仿真軟件為MATLAB R2013a。3種算法種群規模SN設置為50和100，迭代次數macycle為300次，試驗次數100次。通過對比100次獨立實驗的最優值、平均值、最差值、方差等參數，評價各個算法的優化能力。

3.2 結果分析

下頁表1為6個基準函數的數學公式、理論最優值、搜索空間。為單峰測試函數，為多峰測試函數。圖2是在50維下6個標準測試函數的收斂過程，表2為測試結果（100維收斂過程省略）。

表1 測試函數

從圖2可以看出，改進后的SFSALO算法比標準的ALO算法具有明顯的優勢。分析圖2（a）、2（b）、2（c）可知，在對單峰測試函數進行尋優時，SFSALO算法的收斂速度明顯快于ALO算法，并總能夠找到理論最優值，而標準ALO算法卻很難達到理論最優值；分析圖 2（d）、2（e）、2（f）可知，在對多峰測試函數進行尋優時，SFSALO算法在對測試函數4和5尋優時，可以在較少的迭代次數內收斂到理論最優值，尋優的尋優精度強于標準ALO算法。在對函數6進行尋優，雖然SFSALO算法沒有收斂到理論最優值，但是收斂精度和速度明顯優于ALO算法。

通過下頁表2可以看出，改進后的算法無論是收斂精度還是穩定性，都優于標準的ALO算法，SFSALO算法對于單峰還是多峰函數都具有較好的適應性。在對復雜函數進行尋優時，螞蟻的隨機搜索具有很好的探索性，不容易陷入局部最優值；蟻獅的自適應搜索具有很好的開發性，能夠在適應度較高的位置附近進行精細搜索。改進后的算法很好地平衡了開發能力與探索能力。

圖2 不同基準函數的測試收斂過程

為了進一步說明SFSALO算法的優越性，對ABC算法，PSO算法，GWO算法進行了比較，維度設為50，最大迭代次數為300。圖3和圖4分別是4種算法對Sphere函數、Griewank函數的收斂過程對比。

圖3 Sphere函數收斂曲線

圖4 Griewank函數收斂曲線

表2 6個標準測試函數仿真結果比較（50維）

仿真結果分析表明SFSALO算法的收斂精度和收斂速度明顯比其他3種算法效果顯著。對Sphere高維單峰函數和Griewank多峰函數進行優化時，SFSALO算法在較少的迭代次數內都可以搜索到理論最優值。

4 結論

為了解決標準ALO算法易陷入局部最優值和收斂速度慢等缺點，更好地平衡算法的開發與探索能力，在隨機搜索思想的啟發下，結合自適應策略，提出了具有隨機搜索自適應蟻獅優化算法。改進后算法中的螞蟻通過隨機搜索方程提高了探索能力；蟻獅利用自適應搜索的方式對自身進一步精細開發，兩者協作共同提高了算法的全局搜索能力。通過對單峰、多峰函數進行測試，并且與其他常見的幾種算法進行比較，充分表明了SFSALO算法具有收斂速度快、尋優精度高、適用廣泛等優越的性能。