摘 要： 圍繞蟻群優(yōu)化算法的理論及應(yīng)用，針對蟻群算法在TSP規(guī)劃中求解能力不足的難題，運(yùn)用了一種基于自適應(yīng)的螞蟻算法，并對TSP規(guī)劃進(jìn)行了設(shè)計。為了提高路徑規(guī)劃的效率，將自適應(yīng)與傳統(tǒng)的螞蟻算法相結(jié)合形成了自適應(yīng)蟻群算法。仿真實驗結(jié)果表明，改進(jìn)后算法能夠在較短時間內(nèi)找到全局最優(yōu)路徑，相對于基本的蟻群算法在收斂速度、搜索質(zhì)量和局部尋優(yōu)方面都有了明顯的提高。
關(guān)鍵詞： 蟻群算法；自適應(yīng)；旅行商問題
旅行商問題[1]（TSP）是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑。限制條件是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是所有路程之中的最小值。TSP問題是一個組合優(yōu)化問題，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關(guān)注。
蟻群算法[2]是源于生物世界仿生類隨機(jī)搜索算法，它應(yīng)用于組合優(yōu)化中具有很強(qiáng)的發(fā)現(xiàn)解的能力，且具有分布式計算、易于與其他方法相結(jié)合及魯棒性強(qiáng)的優(yōu)點。在仿真中表現(xiàn)出高度的靈活性、健壯性。但是還存在較多的問題，例如搜索速度慢，局部尋優(yōu)能力差等。針對這些問題，將算法進(jìn)行改進(jìn)，調(diào)節(jié)信息素Q與信息素?fù)]發(fā)系數(shù)ρ，使其變?yōu)閯討B(tài)的自適應(yīng)信息素與動態(tài)的信息素?fù)]發(fā)系數(shù)，進(jìn)行仿真測試改進(jìn)的優(yōu)化算法，從而達(dá)到更優(yōu)的結(jié)果。
1 基本蟻群算法及其改進(jìn)
1.1 基本蟻群算法
螞蟻在尋找食物過程中總能找到一條食物所在地和蟻穴地之間的最短路程，經(jīng)研究發(fā)現(xiàn)螞蟻會在其走過的路徑上留下稱之為信息素的物質(zhì)，其他螞蟻可以感知這種物質(zhì)并以此指引其運(yùn)動的方向。這種信息素允許疊加，走過同一條路徑的螞蟻數(shù)量越多，這條路徑上的信息素濃度越大。由此可以吸引其他螞蟻以更大的概率走此路徑。反之，走過的螞蟻越少，信息素的濃度就越低，行走該路徑的概率就越小，同時，這種信息素還會隨著時間的推移而揮發(fā)[3]。
設(shè)m表示螞蟻總數(shù)量，dij（i，j=0，1，…n-1）表示節(jié)點i和節(jié)點j之間的距離，τij（t）表示t時刻i、j在連線上的信息素。在算法的初始時刻，將m只螞蟻隨機(jī)地放到n個節(jié)點上，此時各路徑上的信息素相等，設(shè)τij（0）為常數(shù)，每只螞蟻根據(jù)路徑上保留的信息素獨立地選擇下一個節(jié)點。在時刻t，螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的概率為：
在基本的算法中信息素?fù)]發(fā)系數(shù)ρ為常數(shù)，當(dāng)處理的問題規(guī)模比較大時，由于ρ的存在會使那些從未被搜索到的路徑信息素減小到幾乎為0，因而降低了算法的全局搜索能力。而當(dāng)ρ過大時，以前搜索過的路徑被再次選擇的可能性過大，也會影響算法的隨機(jī)性和全局搜索能力；反之，通過減小ρ雖然可以提高算法的隨機(jī)性能和全局搜索能力，但又會使算法的收斂速度降低[1]。因此本文采取自適應(yīng)改變ρ的值，初始值ρ=1，當(dāng)最優(yōu)解在一段時間內(nèi)無明顯改進(jìn)時，ρ會按式（7）進(jìn)行自適應(yīng)調(diào)節(jié)以加快收斂速度，提高搜索質(zhì)量。
將基本的ACA算法和改進(jìn)后的ACA自適應(yīng)算法同時用于TSP中進(jìn)行比較分析，通過Matlab繪出的最優(yōu)解變化圖形如圖2、圖3所示。在Matlab7.0中編程對ACA算法和改進(jìn)后自適應(yīng)ACA算法參數(shù)進(jìn)行設(shè)置、種群初始化及尋找初始最優(yōu)值。圖2（a）與圖2（b）為兩次運(yùn)行基本蟻群算法所得出的最優(yōu)解，分別為433.623和438.302 2，即所得到的結(jié)果穩(wěn)定性很不好，且每次運(yùn)行得出的結(jié)果相差都較大。圖3為改進(jìn)后算法所得最優(yōu)路徑，仿真中輸出為426.465 3。在圖中可清晰看到最優(yōu)值明顯比基本算法中有所改進(jìn)，表明改進(jìn)后的自適應(yīng)蟻群算法搜索效率和收斂速度明顯提高了。
本文研究基于蟻群算法的TSP問題，描述了TSP的相關(guān)問題和蟻群算法原理。基本的蟻群算法具有較強(qiáng)的魯棒性，但收斂速度緩慢。針對傳統(tǒng)蟻群算法存在搜索時間長、易陷局部最優(yōu)解，在算法中改進(jìn)重要的參量——信息素與信息素殘留因子，形成動態(tài)的自適應(yīng)信息素，并應(yīng)用于TSP問題中使運(yùn)算。論證了將改進(jìn)后蟻群算法在TSP問題研究應(yīng)用的可行性，平衡各路徑的信息量，使螞蟻在初始階段在較大范圍內(nèi)進(jìn)行搜索，能盡快地找到目標(biāo)點，并找到最優(yōu)路徑，以避免陷入局部最優(yōu)。仿真結(jié)果表明，相比一般ACA算法，使用改進(jìn)后的算法可以完成預(yù)期的規(guī)劃效果，在收斂速度、搜索質(zhì)量和局部尋優(yōu)方面有了顯著的提高。
參考文獻(xiàn)
[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] 段海濱.蟻群算法原理及其應(yīng)用[M].北京：科技出版社，2005.
[4] 楊志曉，郭勝國，等．基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃算法[J]．微計算機(jī)信息，2008（7-2）：252-253.
[5] 覃剛力，楊家木.自適應(yīng)調(diào)整信息索的蟻群算法[J].信息與控制，2002，31（13）：198-201.
[6] 王穎，謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[J].系統(tǒng)仿真學(xué)報，2002，14（1）：31-33.