一、什么是蟻群算法
蟻群算法是一種啟發(fā)式算法，靈感來(lái)自于真實(shí)世界蟻群的覓食行為，它由Marco Dorigo于1992年在他的博士論文中提出。單只螞蟻智商有限，但整個(gè)蟻群確體現(xiàn)出一種高智能行為，為什么蟻群搬運(yùn)食物可以沿著比較短的路線，而不是繞遠(yuǎn)路。經(jīng)過(guò)研究，發(fā)現(xiàn)當(dāng)單只螞蟻覓食發(fā)現(xiàn)食物時(shí)，在途中會(huì)釋放信息素。其他螞蟻會(huì)根據(jù)信息素的濃度自覺(jué)向濃度高的地方行進(jìn)。當(dāng)走的次數(shù)多了，就會(huì)有一條標(biāo)識(shí)較近路線的高濃度信息素帶出現(xiàn)。信息素會(huì)隨時(shí)間消失，時(shí)間越久就越稀薄。
二、基本原理
我們拿最通俗的TSP問(wèn)題來(lái)演示蟻群算法。TSP (Traveling salesman problem)中文名稱叫做旅行商問(wèn)題。
下面演示基本原理。
有4個(gè)位置A、B、C、D。其中A是蟻穴所在，D是食物的位置。螞蟻1從A出發(fā)后經(jīng)過(guò)C、B、D找到食物，然后回到蟻穴，即A -> C -> B -> D -> A路徑長(zhǎng)度為18。這個(gè)過(guò)程中螞蟻選擇下一個(gè)節(jié)點(diǎn)的概率是隨機(jī)的。
類似的，螞蟻2從A出發(fā)后沿著路徑A-> D -> C -> B -> A，路徑長(zhǎng)度是15。
現(xiàn)實(shí)世界中螞蟻的信息素釋放是在行走過(guò)程中釋放的，算法中的人工螞蟻是在路徑結(jié)束后，計(jì)算需要釋放的信息素濃度。這一點(diǎn)是和現(xiàn)實(shí)生活不同的地方。
在第一輪中，螞蟻1、螞蟻2尋找下一個(gè)位置完全是隨機(jī)的。第一輪結(jié)束后，信息素濃度根據(jù)前一輪的路徑計(jì)算新的信息素濃度。第二輪中螞蟻們?cè)谶x擇路徑的時(shí)候就會(huì)參考信息素濃度，哪里濃度高就往哪里走。
下面是信息素的計(jì)算的簡(jiǎn)單公式：
需要增加的信息素濃度= 信息素常數(shù)（初始給定的值）/ 路徑長(zhǎng)度
取【信息素常數(shù)】為1，則：
螞蟻1路徑上需要增加的濃度=1/18
螞蟻2路徑上需要增加的濃度=1/15
更新后的信息素濃度表如下：
第二輪開(kāi)始。
螞蟻1從A位置開(kāi)始出發(fā)，面前有3中選擇，B、C、D。其中A -> B濃度是1/15，A -> C濃度是1/18， A-> D濃度是1/18+1/15。哪里濃度高就選擇走那條路，于是選擇了A-> D這條路。類似的，到了D位置后，D-> C濃度是1/15，D ->B濃度是1/18，自然選擇D-> C路徑。由于每個(gè)位置都需要走一遍，所以路徑結(jié)果已經(jīng)出來(lái)了A-> D -> C -> B -> A即是行走的路徑。
同理，螞蟻2在信息素影響下將會(huì)走相同的路徑。
等等。這里有個(gè)問(wèn)題，明顯最短路徑是A -> B -> D -> C -> A，或者A -> C -> D -> B -> A，長(zhǎng)度是13。如果路徑選擇僅僅是按照哪邊濃度最高就選擇哪邊，會(huì)陷入局部最優(yōu)解。這里我們引入一個(gè)選擇算法，輪盤賭法。
什么是輪盤賭法？舉個(gè)例子：中午不知道吃什么飯，面前有三個(gè)選擇，米飯、面、米線。這幾種你稍微更想吃米線、其次是面、然后是米飯。你可以給這三種設(shè)置個(gè)范圍[0,0.5]吃米線（概率50%）、(0.5,0.8]吃面（概率30%）、(0.8,1]吃米線（概率20%）。產(chǎn)生一個(gè)隨機(jī)數(shù)，取值范圍[0,1]，落到哪個(gè)區(qū)間就選擇哪個(gè)。
信息素在每一輪結(jié)束會(huì)揮發(fā)掉一部分。如果信息素只增加不減少，也容易產(chǎn)生局部最優(yōu)解。下面是每輪結(jié)束后的信息素濃度：
每輪結(jié)束后的信息素濃度=上一輪信息素濃度 - 揮發(fā)的信息素 + 增加的信息素濃度。
根據(jù)時(shí)間和計(jì)算量限制，可以指定這樣的計(jì)算進(jìn)行多少輪，在可接受的時(shí)間內(nèi)產(chǎn)生較短的路徑。
下一篇將從數(shù)學(xué)與代碼實(shí)現(xiàn)角度進(jìn)行說(shuō)明。
三、參考
- B站-數(shù)學(xué)建模愛(ài)好者-蟻群算法。鏈接貼了不給發(fā)。
