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

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

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

1 引言

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

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

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

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

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

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

(1)

(2)

式中，rw(1) 表示螞蟻游走步長(zhǎng)初值；T表示最大迭代次數(shù)，t表示當(dāng)前迭代次數(shù)；γ表示步長(zhǎng)浮動(dòng)因子，默認(rèn)設(shè)為1；rw(t+1) 表示螞蟻在第t+1代距離起點(diǎn)的游走步長(zhǎng)；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)表示算法選中的蟻獅個(gè)體；cr(t)與dr(t)分別表示第t代陷阱相對(duì)als(t)所在位置的上、下界。

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

(5)

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

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

(6)

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

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

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

(8)

(9)

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

(10)

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

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

3.1 方差分析

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

表1 方差分析表

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

(11)

(12)

(13)

(14)

(15)

(16)

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

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

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

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

20≤P≤800

(17)

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

0<γ≤10

(18)

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

0.95β·T≤t

(19)

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

0<β≤1

(20)

3.3 實(shí)驗(yàn)設(shè)計(jì)方法

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

表2 實(shí)驗(yàn)參數(shù)水平設(shè)置

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

Sphere函數(shù)

(21)

Levy函數(shù)

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

(22)

本實(shí)驗(yàn)中，算法的收斂速度和收斂精度為評(píng)判依據(jù)，具體如下

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

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

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

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

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

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

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

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

查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對(duì)ALO算法收斂速度與求解精度影響都是顯著的。

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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