蟻群算法的基本原理

1、2.12.1蟻群算法的基本原理蟻群算法的基本原理蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設(shè)計(jì)出的一種群集智能算法。螞蟻在覓食過(guò)程中能夠在其經(jīng)過(guò)的路徑上留下一種稱之為信息素的物質(zhì)，并在覓食過(guò)程中能夠感知這種物質(zhì)的強(qiáng)度，并指導(dǎo)自己行動(dòng)方向，它們總是朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對(duì)信息素的正反饋現(xiàn)象。某一條路徑越短，路徑上經(jīng)過(guò)的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高

2、，由此構(gòu)成的正反饋過(guò)程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑。螞蟻在覓食過(guò)程時(shí)，是以信息素作為媒介而間接進(jìn)行信息交流，當(dāng)螞蟻從食物源走到蟻穴，或者從蟻穴走到食物源時(shí)，都會(huì)在經(jīng)過(guò)的路徑上釋放信息素，從而形成了一條含有信息素的路徑，螞蟻可以感覺(jué)出路徑上信息素濃度的大小，并且以較高的概率選擇信息素濃度較高的路徑。蟻穴食物源AB15cm(a)蟻穴12食物源AB(b)人工螞蟻的搜索主要包括三種智能行為：（1）螞蟻的記憶行為。一只螞蟻搜索過(guò)的路徑在

3、下次搜索時(shí)就不再被該螞蟻選擇，因此在蟻群算法中建立禁忌表進(jìn)行模擬。（2）螞蟻利用信息素進(jìn)行相互通信。螞蟻在所選擇的路徑上會(huì)釋放一種信息素的物質(zhì)，當(dāng)其他螞蟻進(jìn)行路徑選擇時(shí)，會(huì)根據(jù)路徑上的信息素濃度進(jìn)行選擇，這樣信息素就成為螞蟻之間進(jìn)行通信的媒介。（3）螞蟻的集群活動(dòng)。通過(guò)一只螞蟻的運(yùn)動(dòng)很難達(dá)到事物源，但整個(gè)蟻群進(jìn)行搜索就完全不同。當(dāng)某些路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，路徑上留下的信息素?cái)?shù)量也就越多，導(dǎo)致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率隨之

4、增加，從而進(jìn)一步增加該路徑的信息素強(qiáng)度，而通過(guò)的螞蟻比較少的路徑上的信息素會(huì)隨著時(shí)間的推移而揮發(fā)，從而變得越來(lái)越少。3.3.1螞蟻系統(tǒng)螞蟻系統(tǒng)螞蟻系統(tǒng)是最早的蟻群算法。其搜索過(guò)程大致如下：在初始時(shí)刻，只螞蟻隨機(jī)放置于城市中，各條路徑上的信息素初始值相m等，設(shè)為：為信息素初始值，可設(shè)，是由最近鄰啟發(fā)式0(0)ij???0mmL??mL方法構(gòu)造的路徑長(zhǎng)度。其次，螞蟻，按照隨機(jī)比例規(guī)則選擇下一(12)kkm??其中，的定義方法跟以前的相同，的

5、定義則如式（3.4）：)(tkij??)(tbsij??（3.4）????????otherwise0Tj)(if1)(bs，，iLtbsbsij?Digo等人的文章列舉的計(jì)算結(jié)果表明，使用精英策略并選取一個(gè)適當(dāng)?shù)膃值將使得AS算法不但可以得到更好的解，而且能夠在更少的迭代次數(shù)下得到一些更好的解。3.3.3最大最大最小螞蟻系統(tǒng)最小螞蟻系統(tǒng)最大最小螞蟻系統(tǒng)（MMAS[1315]）是到目前為止解決TSP問(wèn)題最好的ACO算法方案之一。MMAS

6、算法是在AS算法的基礎(chǔ)之上，主要作了如下的改進(jìn)：（1）為避免算法過(guò)早收斂于局部最優(yōu)解，將各條路徑可能的外激素濃度限制于，超出這個(gè)范圍的值被強(qiáng)制設(shè)為或者是，可以有效地??maxmin??min?max?避免某條路徑上的信息量遠(yuǎn)大于其余路徑，避免所有螞蟻都集中到同一條路徑上；（2）強(qiáng)調(diào)對(duì)最優(yōu)解的利用。每次迭代結(jié)束后，只有最優(yōu)解所屬路徑上的信息被更新，從而更好地利用了歷史信息；（3）信息素的初始值被設(shè)定為其取值范圍的上界。在算法的初始時(shí)刻，取

7、較小的值時(shí)，算法有更好的發(fā)現(xiàn)較好解?的能力。所有螞蟻完成一次迭代后，按（3.5）式對(duì)路徑上的信息作全局更新：（3.5）??????????1011????????????tttbestijijij（3.6）?????????中中中中中中中中中中中中中中01jiLbestbestij?允許更新的路徑可以是全局最優(yōu)解，或本次迭代的最優(yōu)解。實(shí)踐證明逐漸增加全局最優(yōu)解的使用頻率，會(huì)使該算法獲得較好的性能。3.3.4基于排序的蟻群算法基于排序的蟻

8、群算法基于排序的螞蟻系統(tǒng)（ASrank）[16]是對(duì)AS算法的一種改進(jìn)。其改進(jìn)思想是：在每次迭代完成后，螞蟻所經(jīng)路徑將按從小到大的順序排列，即。算法根據(jù)路徑長(zhǎng)度賦予不同的權(quán)重，路徑長(zhǎng)度越短權(quán)重)()()(21tLtLtLm???越大。全局最優(yōu)解的權(quán)重為w，第r個(gè)最優(yōu)解的權(quán)重為，則ASrank??rw?0max的信息素更新規(guī)則為：（3.7）??????????????gbgbijrrijgbijrijwrijijLttLttwtrwtt1