蟻群算法是一種用來(lái)尋找優(yōu)化路徑的概率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。

這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法。

蟻群系統(tǒng)（Ant System或Ant Colony System）是由意大利學(xué)者Dorigo、Maniezzo等人于20世紀(jì)90年代首先提出來(lái)的。他們?cè)谘芯课浵佉捠车倪^(guò)程中，發(fā)現(xiàn)單個(gè)螞蟻的行為比較簡(jiǎn)單，但是蟻群整體卻可以體現(xiàn)一些智能的行為。例如蟻群可以在不同的環(huán)境下，尋找最短到達(dá)食物源的路徑。這是因?yàn)橄伻簝?nèi)的螞蟻可以通過(guò)某種信息機(jī)制實(shí)現(xiàn)信息的傳遞。后又經(jīng)進(jìn)一步研究發(fā)現(xiàn)，螞蟻會(huì)在其經(jīng)過(guò)的路徑上釋放一種可以稱之為“信息素”的物質(zhì)，蟻群內(nèi)的螞蟻對(duì)“信息素”具有感知能力，它們會(huì)沿著“信息素”濃度較高路徑行走，而每只路過(guò)的螞蟻都會(huì)在路上留下“信息素”，這就形成一種類似正反饋的機(jī)制，這樣經(jīng)過(guò)一段時(shí)間后，整個(gè)蟻群就會(huì)沿著最短路徑到達(dá)食物源了。

將蟻群算法應(yīng)用于解決優(yōu)化問(wèn)題的基本思路為：用螞蟻的行走路徑表示待優(yōu)化問(wèn)題的可行解，整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問(wèn)題的解空間。路徑較短的螞蟻釋放的信息素量較多，隨著時(shí)間的推進(jìn)，較短的路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個(gè)數(shù)也愈來(lái)愈多。最終，整個(gè)螞蟻會(huì)在正反饋的作用下集中到最佳的路徑上，此時(shí)對(duì)應(yīng)的便是待優(yōu)化問(wèn)題的最優(yōu)解。

規(guī)則

（1）感知范圍

螞蟻觀察到的范圍是一個(gè)方格世界，相關(guān)參數(shù)為速度半徑，一般為3，可觀察和移動(dòng)的范圍為3x3方格。

（2）環(huán)境信息

螞蟻所在環(huán)境中有障礙物、其他螞蟻、信息素，其中信息素包括食物信息素（找到食物的螞蟻留下的）、窩信息素（找到窩的螞蟻留下的），信息素以一定速率消失。

（3）覓食規(guī)則

螞蟻在感知范圍內(nèi)尋找食物，如果感知到就會(huì)過(guò)去；否則朝信息素多的地方走，每只螞蟻會(huì)以小概率犯錯(cuò)誤，并非都往信息素最多的方向移動(dòng)。螞蟻找窩的規(guī)則類似，僅對(duì)窩信息素有反應(yīng)。

（4）移動(dòng)規(guī)則

螞蟻朝信息素最多的方向移動(dòng)，當(dāng)周圍沒(méi)有信息素指引時(shí)，會(huì)按照原來(lái)運(yùn)動(dòng)方向慣性移動(dòng)。而且會(huì)記住最近走過(guò)的點(diǎn)，防止原地轉(zhuǎn)圈。

（5）避障規(guī)則

當(dāng)螞蟻待移動(dòng)方向有障礙物時(shí)，將隨機(jī)選擇其他方向；當(dāng)有信息素指引時(shí)，將按照覓食規(guī)則移動(dòng)。

（6）散發(fā)信息素規(guī)則

在剛找到食物或者窩時(shí)，螞蟻散發(fā)的信息素最多；當(dāng)隨著走遠(yuǎn)時(shí)，散發(fā)的信息素將逐漸減少。

特點(diǎn)

與其他優(yōu)化算法相比，蟻群算法具有以下幾個(gè)特點(diǎn)：

（1）采用正反饋機(jī)制，使得搜索過(guò)程不斷收斂，最終逼近最優(yōu)解。

（2）每個(gè)個(gè)體可以通過(guò)釋放信息素來(lái)改變周圍的環(huán)境，且每個(gè)個(gè)體能夠感知周圍環(huán)境的實(shí)時(shí)變化，個(gè)體間通過(guò)環(huán)境進(jìn)行間接地通訊。

（3）搜索過(guò)程采用分布式計(jì)算方式，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，大大提高了算法的計(jì)算能力和運(yùn)行效率。

（4）啟發(fā)式的概率搜索方式不容易陷入局部最優(yōu)，易于尋找到全局最優(yōu)解。