一種帶粒子群記憶行為的螞蟻算法

陳德祥　宋武　汪文彬

摘要：為了解決TSP問題，該文在螞蟻算法的基礎(chǔ)上借鑒粒子群的局部極值的概念，賦予每個尋路的螞蟻記憶以前所搜尋到的最佳路徑，從而使螞蟻算法加快了算法的收斂能力。實(shí)驗(yàn)結(jié)果證明了算法的有效性。

關(guān)鍵詞： TSP問題；螞蟻系統(tǒng)；粒子群；局部優(yōu)化

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044（2012）30-7319-02

作為人們所廣泛研究的典型NP難組合優(yōu)化問題的一種旅行商問題（TSP） ， 目前還找不到一個算法能保證在多項(xiàng)式時間內(nèi)得到最優(yōu)解.在解決離散優(yōu)化問題中，作為一種研究分散型的自組織系統(tǒng)中的集體行為的人工智能技術(shù)，群集智能受到了越來越多的關(guān)注，一般來說，群集智能借鑒自然界的生物行為，進(jìn)行模擬。典型的群集智能系統(tǒng)由一群簡單的主體構(gòu)成，每個主體和其它主體以及它們的環(huán)境作局部的交互。盡管通常沒有集中控制機(jī)制來指示這些主體如何協(xié)作，但這些簡單的局部交互行為通常能涌現(xiàn)出復(fù)雜的全局行為。

當(dāng)前主要的幾種群集智能方法包括蟻群算法[1]和粒子群[2]優(yōu)化。蟻群算法模擬螞蟻的尋食行為，以環(huán)境中信息素的揮發(fā)機(jī)制進(jìn)行螞蟻的信息的交互，成而完成尋優(yōu)的過程，而粒子群算法模擬鳥類的信息，通過歷史上種群和個體所搜尋到的最優(yōu)解，進(jìn)行信息的交互。無數(shù)的文獻(xiàn)表明這兩種算法在解決各類優(yōu)化問題時，取得了比傳統(tǒng)的優(yōu)化算法更好地結(jié)果。

針對基本的蟻群算法，容易陷入局部最優(yōu)的缺點(diǎn)，已有工作[3][4]借鑒粒子群算法的局部極值的概念，利用歷史上的所搜尋到的最好信息，在螞蟻構(gòu)建城市的過程中，混合信息素機(jī)制與局部機(jī)制。實(shí)驗(yàn)表明算法能夠?qū)τ赥SP問題能夠更好地進(jìn)行搜索。

1 螞蟻算法

螞蟻算法是一種用來在圖中尋找優(yōu)化路徑的一種算法。它由Marco Dorigo觀察螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，于1992年在他的博士論文中引入。因?yàn)槠溆卸鄻有院驼答伒奶攸c(diǎn)，其改進(jìn)型不僅用于類圖問題，還可用于實(shí)參數(shù)優(yōu)化，系統(tǒng)辨識等。其算法的基本框架如下：

設(shè)m個螞蟻，隨機(jī)分布在n個城市的問題。每只螞蟻通過狀態(tài)轉(zhuǎn)移概率選擇下一個要訪問的城市， 每只螞蟻趨向于訪問具有較高激素濃度的路徑， 同時進(jìn)行局部信息更新。當(dāng)所有螞蟻完成了一次巡回后， 即啟動全局激素更新機(jī)制。算法反復(fù)迭代，直到滿足停止條件為止。

1） 狀態(tài)轉(zhuǎn)移規(guī)則

各螞蟻放在不同的城t時刻在連接第i，j兩城市間的道路留下的外激素量為bij（t）第k個螞蟻從i城市到j(luò)城市的概率

其中外激素量bij（t）有許多不同的定義，如可定義為：b（t）=e-ct，c>0；或定義為：

其一般的算法流程如下：

Step3：如果停機(jī)條件滿足，輸出最佳路徑，否則跳轉(zhuǎn)到step2；

除了基本的螞蟻算法，縱多的研究者還開發(fā)了大量的其它螞蟻群落系統(tǒng)，諸如蟻周系統(tǒng)和最大最小螞蟻系統(tǒng)等。

2 具有記憶機(jī)制的螞蟻行為

在粒子群優(yōu)化算法中，每一個粒子保存所搜尋的最好解，作為局部極值，在每一次更新時借助所保存的局部極值，對速度和位置進(jìn)行更新，從而完成尋優(yōu)過程。一般來說，本文所建議的帶有記憶機(jī)制的螞蟻借鑒了粒子群算法局部極值的概念，在巡游的過程中將螞蟻算法所搜索的最好的解保存下來，在以后螞蟻算法的運(yùn)行中，指導(dǎo)螞蟻算法的搜索，這樣就帶有了粒子群的行為特征。具體的指導(dǎo)行為方式是在螞蟻構(gòu)建一個路徑的過程中，結(jié)合信息素與局部極值兩個因素，在螞蟻選擇下一個城市中，隨機(jī)生成一個隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)，決定是根據(jù)局部最好的城市選擇下一個城市還是根據(jù)信息素機(jī)制選擇下一個城市。其算法如下：

Ant選擇下一個城市，根據(jù)局部最好的城市；

Else

根據(jù)信息素更新機(jī)制選擇下一個城市；

這樣我們就可以算法根據(jù)以前的搜索信息加快算法的搜索。

3 實(shí)驗(yàn)

在TSP問題的測試庫中TSPlib中，選取了Lin318.tsp，Pcb442.tsp，Rat783.tsp，D198.tsp與基本的螞蟻算法進(jìn)行比較，給出了平均的算法所搜尋到的最優(yōu)解，算法的最優(yōu)解出現(xiàn)的迭代次數(shù)，以及平均的運(yùn)行時間。

4 結(jié)論

本文提出了帶局部最優(yōu)機(jī)制的螞蟻算法，利用歷史上的所搜尋到的最好信息作為螞蟻的局部極值，在螞蟻構(gòu)建城市的過程中，混合信息素機(jī)制與這種機(jī)制。最后測試了幾個TSP問題，實(shí)驗(yàn)證明了本文提出的算法具有較快的收斂能力，以及較少的迭代次數(shù)。

（下轉(zhuǎn)第7334頁）

（上接第7320頁）

參考文獻(xiàn)：

[1] Dorigo M.Gambardella L M Ant Colony System：A Co-operative Learning Approach to the Traveling Salesman Problem，1997（1）.

[2] 楊維，李歧強(qiáng).粒子群優(yōu)化算法綜述[J].中國工程科學(xué)，2004（5）.

[3] 黃國銳，曹先彬，王煦法.基于信息素擴(kuò)散的蟻群算法[J].電子學(xué)報，2004（5）.

[4] 吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機(jī)學(xué)報，2001（12）.