蟻群算法的基本原理

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

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

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

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

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

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

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

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