蟻群算法詳解
沒(méi)有中心化的組織，蟻群何以進(jìn)行高效地搜尋呢？一個(gè)快遞小哥有5個(gè)包裹要送，如何確定一條最短的行進(jìn)路線？
本文我們一起學(xué)下常用于路徑優(yōu)化的蟻群算法，主要內(nèi)容如下：
蟻群算法簡(jiǎn)介 蟻群算法原理 蟻群算法實(shí)例
1.蟻群算法簡(jiǎn)介
如何尋找一條合適的路徑，幾乎是一個(gè)永恒的話題。每個(gè)人、每天都會(huì)遇到。大到全國(guó)列車的運(yùn)行規(guī)劃，小到每個(gè)人的手機(jī)導(dǎo)航。其中一部分是關(guān)于“如何尋找兩個(gè)位置間的最短距離”的，這一部分有較為成熟的理論與確切的解法，還有與之匹配的各種算法。
蟻群系統(tǒng)(Ant System(AS)或Ant Colony System(ACS))是由意大利學(xué)者Dorigo、Maniezzo等人于20世紀(jì)90年代首先提出來(lái)的。他們?cè)谘芯课浵佉捠车倪^(guò)程中，發(fā)現(xiàn)蟻群整體會(huì)體現(xiàn)一些智能的行為，例如蟻群可以在不同的環(huán)境下，尋找最短到達(dá)食物源的路徑。
后經(jīng)進(jìn)一步研究發(fā)現(xiàn)，這是因?yàn)槲浵仌?huì)在其經(jīng)過(guò)的路徑上釋放一種可以稱之為“信息素(pheromone)”的物質(zhì)，蟻群內(nèi)的螞蟻對(duì)“信息素”具有感知能力，它們會(huì)沿著“信息素”濃度較高路徑行走，而每只路過(guò)的螞蟻都會(huì)在路上留下“信息素”，這就形成一種類似正反饋的機(jī)制，這樣經(jīng)過(guò)一段時(shí)間后，整個(gè)蟻群就會(huì)沿著最短路徑到達(dá)食物源了。
由上述螞蟻找食物模式演變來(lái)的算法，即是蟻群算法。這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法。在數(shù)字時(shí)代背景下，蟻群算法在網(wǎng)絡(luò)路由中的應(yīng)用受到越來(lái)越多學(xué)者的關(guān)注，并提出了一些新的基于螞蟻算法的路由算法。
同傳統(tǒng)的路由算法相比較，該算法在網(wǎng)絡(luò)路由中具有信息分布式性、動(dòng)態(tài)性、隨機(jī)性和異步性等特點(diǎn)，而這些特點(diǎn)正好能滿足網(wǎng)絡(luò)路由的需要。
2.蟻群算法原理
蟻群算法是從自然界中真實(shí)螞蟻覓食的群體行為得到啟發(fā)而提出的，其很多觀點(diǎn)都來(lái)源于真實(shí)蟻群，因此算法中所定義的人工螞蟻與真實(shí)螞蟻存在一定的辯證關(guān)系。
自組織行為特征
蟻群的自組織行為特征主要有：
高度結(jié)構(gòu)化的組織
雖然螞蟻的個(gè)體行為極其簡(jiǎn)單，但由個(gè)體組成的蟻群卻構(gòu)成高度結(jié)構(gòu)化的社會(huì)組織，螞蟻社會(huì)的成員有分工，有相互的通信和信息傳遞。自然優(yōu)化
蟻群在覓食過(guò)程中，在沒(méi)有任何提示下總能找到從蟻巢到食物源之間的最短路徑；當(dāng)經(jīng)過(guò)的路線上出現(xiàn)障礙物時(shí)，還能迅速找到新的最優(yōu)路徑。
信息正反饋
螞蟻在尋找食物時(shí)，在其經(jīng)過(guò)的路徑上釋放信息素（外激素）。螞蟻基本沒(méi)有視覺(jué)，但能在小范圍內(nèi)察覺(jué)同類散發(fā)的信息素的軌跡，由此來(lái)決定何去何從，并傾向于朝著信息素強(qiáng)度高的方向移動(dòng)。自催化行為
某條路徑上走過(guò)的螞蟻越多，留下的信息素也越多（隨時(shí)間蒸發(fā)一部分），后來(lái)螞蟻選擇該路徑的概率也越高。
算法基本思想
根據(jù)具體問(wèn)題設(shè)置多只螞蟻，分頭并行搜索。 每只螞蟻完成一次周游后，在行進(jìn)的路上釋放信息素，信息素量與解的質(zhì)量成正比。 螞蟻路徑的選擇根據(jù)信息素強(qiáng)度大?。ǔ跏夹畔⑺亓吭O(shè)為相等），同時(shí)考慮兩點(diǎn)之間的距離，采用隨機(jī)的局部搜索策略。這使得距離較短的邊，其上的信息素量較大，后來(lái)的螞蟻選擇該邊的概率也較大。 每只螞蟻只能走合法路線（經(jīng)過(guò)每個(gè)城市 1次且僅1次），為此設(shè)置禁忌表來(lái)控制。所有螞蟻都搜索完一次就是迭代一次，每迭代一次就對(duì)所有的邊做一次信息素更新，原來(lái)的螞蟻死掉，新的螞蟻進(jìn)行新一輪搜索。 更新信息素包括原有信息素的蒸發(fā)和經(jīng)過(guò)的路徑上信息素的增加。 達(dá)到預(yù)定的迭代步數(shù)，或出現(xiàn)停滯現(xiàn)象（所有螞蟻都選擇同樣的路徑，解不再變化），則算法結(jié)束，以當(dāng)前最優(yōu)解作為問(wèn)題的最優(yōu)解。
了解了基本思想，我們來(lái)關(guān)注幾個(gè)必須得知道的問(wèn)題：上述第2步中，螞蟻完成一次周游后各路徑上的信息素怎么計(jì)算？計(jì)算公式如下：
其中，為邊上的信息素量，剛開(kāi)始時(shí)，為本次迭代邊上的信息素增量，為第k只螞蟻在本次迭代中留在邊上的信息素量，為信息素?fù)]發(fā)系數(shù)。Q是正常數(shù)，m是螞蟻數(shù)量，n是城市數(shù)量，為螞蟻k在本次周游中所走路徑的長(zhǎng)度。
第三步中螞蟻的轉(zhuǎn)移概率計(jì)算公式如下：
其中為信息素的相對(duì)重要程度，為啟發(fā)式因子的相對(duì)重要程度，而是螞蟻k下一步允許選擇的城市集合。
為啟發(fā)式因子，反應(yīng)螞蟻由城市i轉(zhuǎn)移到城市j的啟發(fā)程度，為城市之間的距離。
算法步驟
我們了解了信息素計(jì)算公式和螞蟻的轉(zhuǎn)移概率之后，看下具體流程圖如下：
初始化參數(shù)：開(kāi)始時(shí)，每條邊的信息素量都相等，即：，. 將各只螞蟻放置各頂點(diǎn)，禁忌表為對(duì)應(yīng)的頂點(diǎn)。 取 1只螞蟻，計(jì)算轉(zhuǎn)移概率，按照輪盤賭的方式選擇下一個(gè)頂點(diǎn)，更新禁忌表，再計(jì)算概率，再選擇頂點(diǎn)，再更新禁忌表，直至遍歷所有頂點(diǎn)一次。計(jì)算該只螞蟻留在各邊的信息素量，該螞蟻死去。 重復(fù) 3-4步，直至m只螞蟻都周游完畢。計(jì)算各邊的信息素增量和信息素量。 計(jì)算本次迭代的路徑，更新當(dāng)前的最優(yōu)路徑，清空禁忌表。 判斷是否達(dá)到預(yù)定的迭代步數(shù)，或者是否出現(xiàn)停滯現(xiàn)象，若是則算法結(jié)束，輸出當(dāng)前最優(yōu)路徑，否則轉(zhuǎn)到步驟2，進(jìn)行下一次迭代。
算法特點(diǎn)
與其他優(yōu)化算法相比，蟻群算法具有以下幾個(gè)特點(diǎn)：
采用正反饋機(jī)制，使得搜索過(guò)程不斷收斂，最終逼近最優(yōu)解。 每個(gè)個(gè)體可以通過(guò)釋放信息素來(lái)改變周圍的環(huán)境，且每個(gè)個(gè)體能夠感知周圍環(huán)境的實(shí)時(shí)變化，個(gè)體間通過(guò)環(huán)境進(jìn)行間接地通訊。 搜索過(guò)程采用分布式計(jì)算方式，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，大大提高了算法的計(jì)算能力和運(yùn)行效率。 啟發(fā)式的概率搜索方式不容易陷入局部最優(yōu)，易于尋找到全局最優(yōu)解。
3.蟻群算法實(shí)例
該算法應(yīng)用于其他組合優(yōu)化問(wèn)題，如旅行商問(wèn)題、指派問(wèn)題、Job—shop調(diào)度問(wèn)題、車輛路由問(wèn)題、圖著色問(wèn)題和網(wǎng)絡(luò)路由問(wèn)題等。
知道了上面的算法原理，我們來(lái)看下開(kāi)頭的那個(gè)問(wèn)題，一個(gè)快遞小哥有5個(gè)包裹要送，如何確定一條最短的行進(jìn)路線？
假設(shè)由于某種原因，城市道路均是單行道，即A->B和B->A的距離不相同，也就是說(shuō)這是一個(gè)不對(duì)稱的TSP問(wèn)題?，F(xiàn)在城市距離信息如下表：
設(shè)置參數(shù)：，為禁忌表，那么第一次迭代第一只螞蟻周游如下：
第一次迭代第二只螞蟻周游如下：
依次類推，第一次迭代完成之后，我們得到信息素矩陣如下：
接著進(jìn)行第二次迭代，第二次迭代第一只螞蟻周游如下：
依次類推，發(fā)現(xiàn)第二次迭代的時(shí)候，假如五只螞蟻?zhàn)叩氖峭粭l路，那么算法收斂結(jié)束。最優(yōu)路徑為A->E->D->C->B->A,最優(yōu)路徑的距離為9.
至此，我們從蟻群算法的簡(jiǎn)介，原理以及實(shí)例方面對(duì)蟻群算法進(jìn)行了詳細(xì)的闡述，希望對(duì)大家有所幫助。
?點(diǎn)個(gè)贊再走唄?