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

趙克新，黃長強，王 淵

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

0 引言

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

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

1 標準ALO算法

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

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

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

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

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

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

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

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

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

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

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

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

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

2 具有分形自適應搜索策略的蟻獅優(yōu)化算法

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

2.1 螞蟻隨機分形搜索方程

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

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

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

2.2 蟻獅自適應搜索方程

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

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

2.3 改進算法的分析與步驟

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

1）初始化算法的各個參數(shù)；

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

3）while結束條件不滿足；

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

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

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

7）結束循環(huán)，輸出最優(yōu)解。

3 仿真實驗

3.1 實驗環(huán)境與參數(shù)設置

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

3.2 結果分析

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

表1 測試函數(shù)

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

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

圖2 不同基準函數(shù)的測試收斂過程

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

圖3 Sphere函數(shù)收斂曲線

圖4 Griewank函數(shù)收斂曲線

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

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

4 結論

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