陳德祥　宋武　汪文彬

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

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

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044（2012）30-7319-02

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

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

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

1 螞蟻算法

螞蟻算法是一種用來在圖中尋找優(yōu)化路徑的一種算法。它由Marco Dorigo觀察螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，于1992年在他的博士論文中引入。因為其有多樣性和正反饋的特點，其改進型不僅用于類圖問題，還可用于實參數(shù)優(yōu)化，系統(tǒng)辨識等。其算法的基本框架如下：

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

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

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

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

其一般的算法流程如下：

Step3：如果停機條件滿足，輸出最佳路徑，否則跳轉到step2；

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

2 具有記憶機制的螞蟻行為

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

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

Else

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

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

3 實驗

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

4 結論

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

（下轉第7334頁）

（上接第7320頁）

參考文獻：

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

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

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

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