1. 蟻獅算法簡(jiǎn)介
（以下描述但狭，均不是學(xué)術(shù)用語(yǔ)窥岩，僅供大家快樂的閱讀）
蟻獅是一種昆蟲甲献，城里長(zhǎng)大的我沒有見過這玩意兒，請(qǐng)教了農(nóng)村長(zhǎng)大小的伙伴颂翼，依然沒見過晃洒，這玩意兒可能在我們生活的地方分布較少。
（圖片及介紹來自百度百科）
蟻獅算法(Ant Lion Optimization)是根據(jù)蟻獅挖制漏斗狀陷阱進(jìn)行捕食螞蟻的過程提出的優(yōu)化算法朦乏。算法提出于2015年（2014年末）球及，也是一個(gè)比較新的算法，不過好像相關(guān)的論文也比較多了呻疹。算法的過程和操作步驟比較簡(jiǎn)單吃引，算法的效果卻出乎意料的好，不過算法的實(shí)現(xiàn)與蟻獅的行為不是很匹配刽锤，但這也不會(huì)影響我們的理解镊尺。
蟻獅算法中，每個(gè)蟻獅以及螞蟻的位置表示解空間中的一個(gè)可行解并思。螞蟻在選擇一個(gè)蟻獅庐氮，在其陷阱范圍內(nèi)進(jìn)行隨機(jī)游走（random walk）。蟻獅會(huì)吃掉陷阱范圍內(nèi)位置最優(yōu)的個(gè)體（取代其位置）宋彼。
可以看出算法的主要步驟很簡(jiǎn)單旭愧，不過其具體實(shí)現(xiàn)與捕食過程還是有些許不同，當(dāng)然螞蟻也不可能會(huì)自愿的圍繞蟻獅的陷阱為中心進(jìn)行隨機(jī)游走宙暇。具體的算法將在下一節(jié)中詳細(xì)描述输枯。
2. 算法流程
蟻獅算法中有兩種角色，蟻獅和螞蟻占贫，其數(shù)量均為N, 其位置為 桃熄，其適應(yīng)度值為F(x) 。為了方便描述，下面使用X_AL表示蟻獅的位置瞳收，X_A表示螞蟻的位置碉京。
初始化時(shí)，會(huì)在解空間內(nèi)隨機(jī)初始化N個(gè)蟻獅以及N個(gè)螞蟻螟深，下面是其迭代步驟谐宙。
整個(gè)算法的流程大致可以分為四步：
1. 螞蟻選擇目標(biāo)蟻獅陷阱。（自投羅網(wǎng)界弧，說吧凡蜻，你是選擇清蒸還是紅燒）
2. 計(jì)算陷阱的放縮比例。
3. 螞蟻隨機(jī)游走垢箕。
4. 蟻獅移動(dòng)到指定螞蟻的位置划栓。
2.1螞蟻選擇目標(biāo)蟻獅
每一只螞蟻都要選擇一個(gè)目標(biāo)蟻獅來進(jìn)行后續(xù)的隨機(jī)游走，選擇過程可以隨機(jī)選擇也可以使用輪盤賭的方式進(jìn)行選擇条获，具體的實(shí)現(xiàn)比較簡(jiǎn)單忠荞，不在贅述。（輪盤賭參見遺傳算法）帅掘。
2.2計(jì)算陷阱的比例
該步驟計(jì)算陷阱（相對(duì)搜索空間）的大小委煤，用于下一步中確定螞蟻隨機(jī)游走后的位置。
論文中修档，陷阱的大小與個(gè)體無關(guān)碧绞，只與當(dāng)前迭代次數(shù)有關(guān)，其計(jì)算公式如下：
其中t為當(dāng)前迭代次數(shù)萍悴，T為最大迭代次數(shù)≡⒚猓可以看出這是一個(gè)分段函數(shù)癣诱，我們看看它的圖像。
從圖像可以看出袜香，在迭代的末期撕予，比例會(huì)變得很大，但是該值是用作分母蜈首，所以隨著迭代次數(shù)增加实抡，陷阱范圍越來越小。
2.3螞蟻隨機(jī)游走
螞蟻的隨機(jī)游走是蟻獅算法的核心欢策，在介紹之前先看看random walk的定義及圖像吆寨。
2.3.1隨機(jī)游走
定義函數(shù)rw如下：
其中r為0-1內(nèi)的均勻隨機(jī)數(shù)。
隨機(jī)游走函數(shù)RW定義如下：
即t個(gè)rw隨機(jī)數(shù)之和踩寇。明顯可知-t<=RW(t)<=t啄清。
看看RW(100)的圖像，
從圖像可以看出俺孙，雖然函數(shù)的期望為0辣卒，但其曲線還是比較曲折的掷贾，有偏向正數(shù)的曲線，有偏向負(fù)數(shù)的曲線荣茫，也有在0值上下波動(dòng)的曲線想帅。總而言之啡莉，隨機(jī)游走的曲線的隨機(jī)性還是比較大的港准，這也為算法提供了隨機(jī)搜索能力。
2.3.2計(jì)算螞蟻隨機(jī)游走相對(duì)值
下面要將隨機(jī)游走轉(zhuǎn)換為螞蟻的隨機(jī)游走票罐。
第i個(gè)螞蟻的在第t代時(shí)隨機(jī)游走的值為RW_i(t),則RW_i(t+1)=RW_i(t)+rw叉趣。
第t代群體中隨機(jī)游走的最大值為Max(RW(t)),最小值為Min(RW(T))。
定義ARW_i(t)為第i個(gè)螞蟻在第t代隨機(jī)游走過程的相對(duì)位置该押，其計(jì)算公式如下：
可以看出ARW是一個(gè)取值范圍為0-1的數(shù)疗杉，即將這N個(gè)螞蟻的隨機(jī)游走值歸一化到0-1范圍內(nèi)，再做進(jìn)一步計(jì)算蚕礼。
2.3.3計(jì)算蟻獅陷阱范圍
該螞蟻選定第k個(gè)蟻獅作為自己的目標(biāo)蟻獅烟具，由上一步計(jì)算出的比例ratio可以計(jì)算出該蟻獅所在陷阱的范圍trap。
其中
2.3.4計(jì)算螞蟻的位置
螞蟻會(huì)圍繞自己所選擇的蟻獅做隨機(jī)游走宵距，最終腊尚，螞蟻會(huì)停留在該蟻獅的陷阱范圍內(nèi)。螞蟻位置的計(jì)算公式如下：
可以看出第i個(gè)螞蟻位置在它所選擇的蟻獅的陷阱內(nèi)满哪，具體的位置由它隨機(jī)游走結(jié)果在群體中的相對(duì)位置決定婿斥。
除此之外，該螞蟻還會(huì)向著全局最優(yōu)的蟻獅個(gè)體進(jìn)行隨機(jī)游走哨鸭，最后會(huì)停留在這兩個(gè)位置的中點(diǎn)處民宿。
以上，蟻獅算法中隨機(jī)游走部分就結(jié)束了像鸡】备撸看上去很復(fù)雜，但是理解之后還是很簡(jiǎn)單的，大致分為兩步：
1. 螞蟻選擇蟻獅华望，通過陷阱確定自己的大致位置蕊蝗。
2. 螞蟻根據(jù)隨機(jī)游走在種群中的相對(duì)位置，確定自己在陷阱中的精確位置赖舟。
2.4蟻獅移動(dòng)到指定螞蟻的位置
該步驟也是較為簡(jiǎn)單的步驟蓬戚，其實(shí)現(xiàn)與描述相差較大。具體實(shí)現(xiàn)為在這N個(gè)蟻獅以及N個(gè)螞蟻一共2N個(gè)個(gè)體中宾抓，選擇較好的N個(gè)個(gè)體作為蟻獅子漩。注意，只是選擇了N個(gè)蟻獅石洗，原蟻獅若未被選中則不復(fù)存在幢泼，但原螞蟻依然存在，只是新蟻獅和原螞蟻位置重疊了讲衫。該實(shí)現(xiàn)方式是原文代碼的實(shí)現(xiàn)缕棵，其實(shí)大家想怎么實(shí)現(xiàn)都可以，算法的魯棒性很強(qiáng)涉兽，不會(huì)因?yàn)檫@些細(xì)微的改動(dòng)而變差招驴。
2.5算法步驟
可以看出蟻獅算法的整體流程還是比較簡(jiǎn)單的，雖然隨機(jī)游走部分公式較多枷畏，但是只要知道其含義還是比較容易理解的别厘。
3.實(shí)驗(yàn)
適應(yīng)度函數(shù)。
實(shí)驗(yàn)一：
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100拥诡，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 選擇蟻獅方式 | 輪盤賭 |
| 值 | |
|---|---|
| 最優(yōu)值 | 3.8900618299208255E-10 |
| 最差值 | 3.105985890779366E-7 |
| 平均值 | 6.142564495109296E-8 |
從結(jié)果可以看出触趴，蟻獅算法的效果非常好。從圖像可以看出渴肉，算法的收斂速度也是非常之快冗懦，在3-4代之后群體就收斂到了一個(gè)相對(duì)集中的位置。不過我們可以看到算法的ratio的實(shí)現(xiàn)宾娜，應(yīng)該是在最后的10%代才進(jìn)行小范圍搜索批狐，而圖像可以看出3-4代就收斂了扇售，可能與輪盤賭選擇有關(guān)前塔。雖然結(jié)果很，收斂過快容易陷入局部最優(yōu)承冰，但這也可能是該適應(yīng)度函數(shù)太簡(jiǎn)單的緣故华弓。
實(shí)驗(yàn)二：
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 選擇蟻獅方式 | 隨機(jī)選擇 |
| 值 | |
|---|---|
| 最優(yōu)值 | 5.652087288375292E-10 |
| 最差值 | 5.641551352947513E-7 |
| 平均值 | 7.520606013312168E-8 |
圖像和結(jié)果與實(shí)驗(yàn)一并沒有太大的差別困乒，收斂的依然很快寂屏。螞蟻選擇蟻獅方式對(duì)結(jié)果的影響不太大。看來應(yīng)該是蟻獅選擇螞蟻的方式對(duì)種群造成的影響迁霎，步驟2.4中可以看出吱抚，算法沒有使用貪心算法，而是選擇在2N個(gè)個(gè)體中選擇前N個(gè)個(gè)體考廉。這種方式向著最優(yōu)個(gè)體收斂的速度應(yīng)該快于普通的貪心算法秘豹。（普通的貪心算法，如果螞蟻隨機(jī)游走到的位置由于蟻獅昌粤，則蟻獅移動(dòng)到該位置）既绕。
實(shí)驗(yàn)三： 使用貪心算法移動(dòng)蟻獅
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 最大迭代次數(shù) | 50 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 選擇蟻獅方式 | 隨機(jī)選擇 |
| 值 | |
|---|---|
| 最優(yōu)值 | 3.1748247992028467E-9 |
| 最差值 | 5.054159478342528E-7 |
| 平均值 | 6.544495515254065E-8 |
從圖像看可知涮坐，種群的收斂速度沒有之前那么快了凄贩，結(jié)果也與實(shí)驗(yàn)一和實(shí)驗(yàn)二相差不大。故可知袱讹，算法的快速收斂主要由其蟻獅移動(dòng)的方式?jīng)Q定疲扎。改為貪心算法后，收斂速度慢了一點(diǎn)廓译，總體而言差別不大评肆。
4.總結(jié)
蟻獅算法是根據(jù)蟻獅使用陷阱捕食隨機(jī)游走的螞蟻而提出的算法。不過其核心確實(shí)螞蟻的隨機(jī)游走非区。原文的描述時(shí)將所有的流程融合為了一個(gè)公式瓜挽，理解不易，本文中將其分步分解后可以明顯的看出其公式的含義征绸。算法的性能不錯(cuò)久橙，魯棒性也較強(qiáng)，對(duì)其操作步驟的簡(jiǎn)單修改對(duì)其效果的影響不太大管怠。
算法中隨機(jī)游走過程為算法提供了不錯(cuò)的搜索能力淆衷，而陷阱的比例則決定了其搜索范圍，是局部搜索還是全局搜索渤弛，蟻獅的移動(dòng)方式?jīng)Q定了種群的收斂速度祝拯。總體來看她肯，對(duì)于平滑的局部最優(yōu)較少的函數(shù)佳头，算法能得到非常好的效果，在其他問題上也有不錯(cuò)的結(jié)果晴氨。
參考文獻(xiàn)
[Mirjalili, Seyedali. The Ant Lion Optimizer[J]. Advances in Engineering Software, 2015, 83:80-98.]
以下指標(biāo)純屬個(gè)人yy,僅供參考
| 指標(biāo) | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★★★☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★★★★★☆ |
| 全局搜索 | ★★★★★★★☆☆☆ |
| 局部搜索 | ★★★★★★☆☆☆ |
| 優(yōu)化性能 | ★★★★★★☆☆☆☆ |
| 跳出局部最優(yōu) | ★☆☆☆☆☆☆☆☆☆ |
| 改進(jìn)點(diǎn) | ★★★★☆☆☆☆☆☆ |
