摘  要： 圍繞蟻群優(yōu)化算法的理論及應用，針對蟻群算法在TSP規(guī)劃中求解能力不足的難題，運用了一種基于自適應的螞蟻算法，并對TSP規(guī)劃進行了設計。為了提高路徑規(guī)劃的效率，將自適應與傳統(tǒng)的螞蟻算法相結合形成了自適應蟻群算法。仿真實驗結果表明，改進后算法能夠在較短時間內(nèi)找到全局最優(yōu)路徑，相對于基本的蟻群算法在收斂速度、搜索質量和局部尋優(yōu)方面都有了明顯的提高。
關鍵詞： 蟻群算法；自適應；旅行商問題

　旅行商問題[1]（TSP）是數(shù)學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑。限制條件是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是所有路程之中的最小值。TSP問題是一個組合優(yōu)化問題，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
　蟻群算法[2]是源于生物世界仿生類隨機搜索算法，它應用于組合優(yōu)化中具有很強的發(fā)現(xiàn)解的能力，且具有分布式計算、易于與其他方法相結合及魯棒性強的優(yōu)點。在仿真中表現(xiàn)出高度的靈活性、健壯性。但是還存在較多的問題，例如搜索速度慢，局部尋優(yōu)能力差等。針對這些問題，將算法進行改進，調(diào)節(jié)信息素Q與信息素揮發(fā)系數(shù)ρ，使其變?yōu)閯討B(tài)的自適應信息素與動態(tài)的信息素揮發(fā)系數(shù)，進行仿真測試改進的優(yōu)化算法，從而達到更優(yōu)的結果。
1 基本蟻群算法及其改進
1.1 基本蟻群算法
　螞蟻在尋找食物過程中總能找到一條食物所在地和蟻穴地之間的最短路程，經(jīng)研究發(fā)現(xiàn)螞蟻會在其走過的路徑上留下稱之為信息素的物質，其他螞蟻可以感知這種物質并以此指引其運動的方向。這種信息素允許疊加，走過同一條路徑的螞蟻數(shù)量越多，這條路徑上的信息素濃度越大。由此可以吸引其他螞蟻以更大的概率走此路徑。反之，走過的螞蟻越少，信息素的濃度就越低，行走該路徑的概率就越小，同時，這種信息素還會隨著時間的推移而揮發(fā)[3]。
　設m表示螞蟻總數(shù)量，dij（i，j=0，1，…n-1）表示節(jié)點i和節(jié)點j之間的距離，τij（t）表示t時刻i、j在連線上的信息素。在算法的初始時刻，將m只螞蟻隨機地放到n個節(jié)點上，此時各路徑上的信息素相等，設τij（0）為常數(shù)，每只螞蟻根據(jù)路徑上保留的信息素獨立地選擇下一個節(jié)點。在時刻t，螞蟻k從節(jié)點i轉移到節(jié)點j的概率為：

　在基本的算法中信息素揮發(fā)系數(shù)ρ為常數(shù)，當處理的問題規(guī)模比較大時，由于ρ的存在會使那些從未被搜索到的路徑信息素減小到幾乎為0，因而降低了算法的全局搜索能力。而當ρ過大時，以前搜索過的路徑被再次選擇的可能性過大，也會影響算法的隨機性和全局搜索能力；反之，通過減小ρ雖然可以提高算法的隨機性能和全局搜索能力，但又會使算法的收斂速度降低[1]。因此本文采取自適應改變ρ的值，初始值ρ=1，當最優(yōu)解在一段時間內(nèi)無明顯改進時，ρ會按式（7）進行自適應調(diào)節(jié)以加快收斂速度，提高搜索質量。

　將基本的ACA算法和改進后的ACA自適應算法同時用于TSP中進行比較分析，通過Matlab繪出的最優(yōu)解變化圖形如圖2、圖3所示。在Matlab7.0中編程對ACA算法和改進后自適應ACA算法參數(shù)進行設置、種群初始化及尋找初始最優(yōu)值。圖2（a）與圖2（b）為兩次運行基本蟻群算法所得出的最優(yōu)解，分別為433.623和438.302 2，即所得到的結果穩(wěn)定性很不好，且每次運行得出的結果相差都較大。圖3為改進后算法所得最優(yōu)路徑，仿真中輸出為426.465 3。在圖中可清晰看到最優(yōu)值明顯比基本算法中有所改進，表明改進后的自適應蟻群算法搜索效率和收斂速度明顯提高了。

　本文研究基于蟻群算法的TSP問題，描述了TSP的相關問題和蟻群算法原理?；镜南伻核惴ň哂休^強的魯棒性，但收斂速度緩慢。針對傳統(tǒng)蟻群算法存在搜索時間長、易陷局部最優(yōu)解，在算法中改進重要的參量——信息素與信息素殘留因子，形成動態(tài)的自適應信息素，并應用于TSP問題中使運算。論證了將改進后蟻群算法在TSP問題研究應用的可行性，平衡各路徑的信息量，使螞蟻在初始階段在較大范圍內(nèi)進行搜索，能盡快地找到目標點，并找到最優(yōu)路徑，以避免陷入局部最優(yōu)。仿真結果表明，相比一般ACA算法，使用改進后的算法可以完成預期的規(guī)劃效果，在收斂速度、搜索質量和局部尋優(yōu)方面有了顯著的提高。
參考文獻
[1] DORIGO M， GAMBARDELLA L M. Ant colonies for the traveling salesman problem[J]. Bio-Systems， 1997， 43（2）：73-81.
[2] DORIGO M， MANIEZZO V， COLORNI A. The ant system： Optimization by a colony of coorperating agents[J].IEEE Transations on System， Man， and Cybernetics-Part B，1996：26（1）：29-41.
[3] 段海濱.蟻群算法原理及其應用[M].北京：科技出版社，2005.
[4] 楊志曉，郭勝國，等．基于改進蟻群算法的機器人路徑規(guī)劃算法[J]．微計算機信息，2008（7-2）：252-253.
[5] 覃剛力，楊家木.自適應調(diào)整信息索的蟻群算法[J].信息與控制，2002，31（13）：198-201.
[6] 王穎，謝劍英.一種自適應蟻群算法及其仿真研究[J].系統(tǒng)仿真學報，2002，14（1）：31-33.