蟻獅算法的參數(shù)效能統(tǒng)計分析

趙轉(zhuǎn)哲，張 宇，劉永明，張 振

(安徽工程大學(xué)機(jī)械與汽車工程學(xué)院，安徽 蕪湖 241000；)

1 引言

在自然界，蟻獅是一種專門捕食螞蟻的昆蟲，Seyedali Mirjalili等學(xué)者通過觀察并模仿蟻獅在幼蟲時期按某種特定規(guī)律進(jìn)行捕食的行為，提出了一種新型群智能仿生算法——蟻獅算法[1](Ant Lion Optimizer，ALO)，由于該算法具有參數(shù)設(shè)置少，尋優(yōu)精度高等特點，被國內(nèi)外學(xué)者廣泛應(yīng)用于求解各種優(yōu)化問題，如函數(shù)優(yōu)化[2]、電機(jī)控制中PID參數(shù)調(diào)優(yōu)[3]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練[4]、預(yù)測模型優(yōu)化[5]、路徑規(guī)劃[6]、調(diào)度優(yōu)化[7]等領(lǐng)域，并取得了不錯的成效。

與其它經(jīng)典算法如遺傳算法[8]、粒子群算法[9]、混合蛙跳算法[10]等相比，關(guān)于ALO理論基礎(chǔ)的研究成果較少，尤其是在算法參數(shù)設(shè)置方面，缺乏有效的理論依據(jù)和實驗驗證，具有一定的盲目性。因此本文以統(tǒng)計學(xué)中的方差分析為基礎(chǔ)，將ALO算法中3個關(guān)鍵參數(shù) (種群規(guī)模P、步長浮動因子γ、陷阱浮動因子β) 分別進(jìn)行統(tǒng)計分析，探尋這些參數(shù)對ALO算法性能影響的一般規(guī)律。

2 ALO算法的數(shù)學(xué)模型

蟻獅的獵捕過程，可以分為5個步驟，即螞蟻的隨機(jī)游走、蟻獅的陷阱挖掘、螞蟻落入陷阱、蟻獅捕食螞蟻、陷阱重建。圖1 (a) 展示了蟻獅在土地上挖出大小不一的陷阱。由于蟻獅了解螞蟻的行蹤軌跡，蟻獅在構(gòu)筑陷阱時會確保螞蟻在陷阱附近進(jìn)行隨機(jī)游走。蟻獅幼蟲在挖好陷阱后，便蹲守在陷阱底部等待附近游走的螞蟻落入陷阱，此過程如圖1 (b)。

圖1 蟻獅陷阱的挖掘與獵捕過程示意圖

1) 螞蟻在(解)空間內(nèi)隨機(jī)游走，其步長公式可描述為

(1)

(2)

式中，rw(1) 表示螞蟻游走步長初值；T表示最大迭代次數(shù)，t表示當(dāng)前迭代次數(shù)；γ表示步長浮動因子，默認(rèn)設(shè)為1；rw(t+1) 表示螞蟻在第t+1代距離起點的游走步長；rand取0～1間的隨機(jī)數(shù)；

2) 蟻獅以自身為中心挖掘陷阱，利用式 (3) 和(4) 可以把算法初始邊界范圍轉(zhuǎn)化為以該蟻獅為中心的陷阱包圍圈

cr(t)=als(t)+c(t)

(3)

dr(t)=als(t)+d(t)

(4)

式中，c(t)與d(t)分別表示第t代陷阱的上、下界；als(t)表示算法選中的蟻獅個體；cr(t)與dr(t)分別表示第t代陷阱相對als(t)所在位置的上、下界。

3) 為防止螞蟻隨機(jī)游走越界，通過式 (5)進(jìn)行游走范圍標(biāo)準(zhǔn)化處理

(5)

式中，Rsd(t) 表示第t代標(biāo)準(zhǔn)化的隨機(jī)游走步長；a(T)、b(T)分別表示螞蟻T次游走后游走步長的最大與最小值。

4) 各螞蟻的隨機(jī)游走可表示為

(6)

式中，ant(t+1) 表示更新得到第t+1代的螞蟻個體，根據(jù)輪盤賭與精英優(yōu)選策略，Rsd(t) 可分別記為Rrs(t)與Re(t)。

5) 螞蟻被蟻獅拖入沙中捕食，此過程在螞蟻適應(yīng)度值優(yōu)于蟻獅的條件下發(fā)生，且蟻獅將取代螞蟻所在位置

6) 當(dāng)糧食儲備耗盡后，蟻獅會修補(bǔ)好陷阱以待下一次獵捕的到來，如式 (8) 和 (9)

(8)

(9)

式中，I(t)=10wt/T，其中w在算法不同的迭代時間段內(nèi)被賦予不同的常數(shù)值

(10)

式中，β表示陷阱浮動因子，其控制著w定義域的動態(tài)變化，默認(rèn)設(shè)為1。

3 參數(shù)特性的統(tǒng)計分析

3.1 方差分析

方差分析又稱“F檢驗”，通過統(tǒng)計分析不同來源的差異對實驗總差異的貢獻(xiàn)量，從而確定實驗中參數(shù)不同等級對統(tǒng)計結(jié)果影響的大小。方差分析實驗中影響指標(biāo)的參數(shù)稱為因素，各個因素?fù)碛胁煌燃壏Q為水平[11，12]。

表1 方差分析表

在實際的方差分析實驗中，首先對各參數(shù)因素設(shè)置m個水平，各個水平下進(jìn)行k次重復(fù)實驗，各次實驗完成后記錄實驗結(jié)果記作aij，表示第i個水平下第j個實驗值。利用統(tǒng)計學(xué)中顯著性檢驗的方法對得出的結(jié)果進(jìn)行分析與評判，方差分析表具體形式見表1，表中名詞表示方法如式(11)～(16)

(11)

(12)

(13)

(14)

(15)

(16)

根據(jù)F值的大小，就可以對參數(shù)因素的不同水平進(jìn)行顯著性檢驗，即按不同的顯著性水平a0和a1，與自由度vA和ve在F分布表里找出對應(yīng)的上下邊界值Fa0(vA，ve)，F(xiàn)a1(vA，ve)，且有以下規(guī)則：若FFa1，則認(rèn)為Q的不同水平對該方差分析實驗影響顯著[13]，由文獻(xiàn)[14]可知a0=0.05，a1=0.01。

3.2 關(guān)鍵參數(shù)的范圍設(shè)置

在標(biāo)準(zhǔn)的ALO算法中，除了針對實際要求設(shè)置算法維數(shù)、最大迭代次數(shù)、陷阱初始邊界等這些來自求解問題本身的參數(shù)之外，還有部分參數(shù)源于算法本身，如種群規(guī)模P、陷阱浮動因子β、步長浮動因子γ等。

對種群規(guī)模P，種群規(guī)模設(shè)置過低會使初始解生成量過少，種群無法正常進(jìn)化，導(dǎo)致算法極易陷入局部最優(yōu)，甚至失去其固有的尋優(yōu)性能，綜合文獻(xiàn)[15-17]的推薦值，將P的下界設(shè)為20；為了更加全面的表現(xiàn)出ALO算法的實際性能，應(yīng)該對參數(shù)設(shè)置范圍合理的放大，綜合文獻(xiàn)[18，19]設(shè)定P的上界為800，即得到

20≤P≤800

(17)

對步長浮動因子γ，原算法默認(rèn)為1。由于各代螞蟻游走步長的相對大小對解空間中粒子分布的密集程度有顯著影響，在求解收斂精度要求較高的問題時，需要將步長適當(dāng)?shù)目s減，發(fā)揮出算法的局部尋優(yōu)潛能，故γ的值可以取到1以下；為了多角度的觀察ALO算法的優(yōu)化性能，由文獻(xiàn)[19]對步長的推薦值，本文對γ的實驗范圍進(jìn)行合理的放大

0<γ≤10

(18)

對陷阱浮動因子β，根據(jù)式 (10)，在算法迭代的末期滿足式 (19)

0.95β·T≤t

(19)

由于迭代次數(shù)t的最大值取T，β范圍取整得

0<β≤1

(20)

3.3 實驗設(shè)計方法

本節(jié)將ALO算法的3個關(guān)鍵參數(shù)分別對應(yīng)于方差實驗中的3個因素，參數(shù)范圍被劃分為不同的參數(shù)水平，對每個參數(shù)設(shè)置10種不同的參數(shù)水平，且在每個水平下獨立測試10次，設(shè)置參數(shù)水平如表2。另外，參數(shù)基本值設(shè)為P=340；γ=1；β=0.5。

表2 實驗參數(shù)水平設(shè)置

本實驗選用2種常用的測試函數(shù)，Sphere函數(shù) (F1) 與Levy函數(shù) (F2)，Sphere函數(shù)屬于典型的非線性對稱函數(shù)，模型相對簡單，主要用來測試算法的求解精度與速度；Levy函數(shù)屬于復(fù)雜多模函數(shù)，算法尋優(yōu)過程極易早熟，其主要用來測試算法跳出局部最優(yōu)的能力。函數(shù)表達(dá)式見式 (21) 與 (22)，另外，在測試過程中，設(shè)維數(shù)D為15。

Sphere函數(shù)

(21)

Levy函數(shù)

(πyi+1)]+(yD-1)2[1+sin2(2πyD)]

(22)

本實驗中，算法的收斂速度和收斂精度為評判依據(jù)，具體如下

1) 收斂速度：當(dāng)算法的求解值精度達(dá)到1.00E-08時停止迭代，并以迭代步數(shù)作為收斂速度的判別標(biāo)準(zhǔn)。設(shè)置最大迭代次數(shù)T=1000，若迭代次數(shù)達(dá)到T時，精度仍未達(dá)到要求，則認(rèn)為此次尋優(yōu)失敗。

2) 收斂精度：對兩測試函數(shù)分別迭代1000次，記錄最優(yōu)解，以此作為算法收斂精度的判別標(biāo)準(zhǔn)。

4 統(tǒng)計結(jié)果分析

ALO算法在不同水平下迭代曲線結(jié)果如圖2～4所示，其中橫坐標(biāo)表示因素設(shè)置水平，(a) 表示收斂速度曲線，數(shù)據(jù)來源于不同水平下算法迭代步數(shù)的均值；(b) 表示收斂精度曲線，為了顯著的觀察曲線變化趨勢，縱坐標(biāo)使用對數(shù)坐標(biāo)，數(shù)據(jù)來源于不同水平下算法1000代適應(yīng)度值以10為底的對數(shù)均值。表3～8表示ALO中關(guān)于3個基本參數(shù)的方差分析表。

圖2 P的水平對算法收斂速度及求解精度的影響

由圖2，從整體上看，隨著種群規(guī)模P水平的增大，算法在兩個測試函數(shù)中收斂速度以及求解精度都有顯著的上升；而關(guān)于F1的兩條迭代曲線遞減趨勢相對較慢，這表明種群規(guī)模P的不同水平對單模函數(shù)尋優(yōu)影響較小；當(dāng)橫坐標(biāo)水平因素超過4時，F(xiàn)2收斂速度幾乎不再改變，P在該函數(shù)求解中的性能表現(xiàn)接近飽和；F2的收斂精度曲線在P設(shè)為水平4附近出現(xiàn)波動，但波動范圍小于一個數(shù)量級，且不影響曲線在水平8之前的整體走勢，在曲線達(dá)到水平8之后，推測算法種群個體數(shù)基本飽和，并幾乎不再對算法性能起到主導(dǎo)作用。

表3 方差分析表(關(guān)于P對收斂速度的影響)

表4 方差分析表(關(guān)于P對收斂精度的影響)

查F分布表可得，F(xiàn)0.05(9，90)=1.99、F0.01(9，90)=2.61。鑒于表3～4中的F比值皆大于F0.05(9，90)與F0.01(9，90)，故因素P對ALO算法收斂速度與求解精度影響都是顯著的。

圖3 γ的水平對算法收斂速度及求解精度的影響

由圖3可知，隨著γ水平的逐步提高，在求解單模函數(shù)F1函數(shù)時，算法的收斂速度與收斂精度變化皆不顯著，其曲線波動范圍十分有限，斜率幾乎接近0；而在求解多模函數(shù)F2時，收斂速度曲線達(dá)到水平6附近有極小值，此時算法收斂速度最快，但各水平之間步數(shù)差距并不明顯，大約在10步以內(nèi)；而求解F2時，算法的收斂精度隨著γ因素水平的提升顯著變差，推測該現(xiàn)象是由于γ水平的提高會導(dǎo)致隨機(jī)游走步長過大，導(dǎo)致算法難以進(jìn)行局部精密尋優(yōu)。

表5 方差分析表(關(guān)于γ對收斂速度的影響)

表6 方差分析表(關(guān)于γ對收斂精度的影響)

由表5與表6數(shù)據(jù)可知，對于F1函數(shù)，其收斂速度與收斂精度的F比值皆小F0.05(9，90)，故步長浮動因子γ的大小設(shè)置對F1函數(shù)的收斂速度與收斂精度影響不明顯；對于F2函數(shù)，其收斂速度的F比值小于F0.05(9，90)，而收斂精度的F比值大于F0.01(9，90)，故γ的大小對F2函數(shù)的收斂速度影響不明顯，對收斂精度有顯著影響。

圖4 β的水平對算法收斂速度及求解精度的影響

由圖4可知，隨著β水平的遞增，ALO在F1、F2中的收斂速度均明顯變慢，曲線的變化率表現(xiàn)較為穩(wěn)定；而F1的收斂精度變化在所給區(qū)間內(nèi)僅有小幅度的波動，這說明β水平的設(shè)置對單模函數(shù)尋優(yōu)精度影響不顯著；在參數(shù)β水平超出水平4后，算法對F2的尋優(yōu)精度表現(xiàn)明顯變差，這是因為β設(shè)置過大，犧牲了ALO算法過多的局部搜索時間，導(dǎo)致算法無法尋找到全局最優(yōu)，從而使曲線居高不下。

表7 方差分析表(關(guān)于β對收斂速度的影響)

表8 方差分析表(關(guān)于β對收斂精度的影響)

由表7和表8可知，對于F1函數(shù)，其收斂速度對應(yīng)的F比值遠(yuǎn)大于F0.01(9，90)，而收斂精度對應(yīng)的F比值小于F0.05(9，90)，故β的大小設(shè)置對算法求解F1函數(shù)的收斂速度影響較為顯著，而對其收斂精度影響不明顯；對于F2函數(shù)，其收斂速度與收斂精度的F比值皆大于F0.01(9，90)，故因素β的大小對算法求解F2時的收斂速度與求解精度影響都是顯著的。

5 結(jié)論

在ALO算法的實際應(yīng)用中，算法尋優(yōu)潛力的釋放往往取決于其關(guān)鍵參數(shù)合理的設(shè)置，本文基于統(tǒng)計學(xué)中的方差分析法分別對ALO中種群規(guī)模P、步長浮動因子γ、陷阱浮動因子β設(shè)置不同的參數(shù)水平分別進(jìn)行了統(tǒng)計分析，最終得出了參數(shù)水平對ALO算法性能影響的一般規(guī)律：

綜合本文實驗結(jié)果可知，在參數(shù)測試范圍內(nèi)，對于種群規(guī)模P，推薦參數(shù)值設(shè)置在水平7附近 (P=500)，ALO求解精度與收斂速度會得到顯著提升；對于步長浮動因子γ，由于在求解單模問題時其范圍對算法求解性能影響不明顯，可以設(shè)為默認(rèn)值1，而在求解多模問題時，需要適當(dāng)?shù)目s小以提高ALO的求解精度；對于陷阱浮動因子β，在求解單模問題時，推薦設(shè)置偏小有利于ALO收斂速度的提升，求解多模問題時，本文推薦β值在水平2 (β=0.2) 附近取值，ALO的收斂性能會得到顯著提升。