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

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

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

　將基本的ACA算法和改進(jìn)后的ACA自適應(yīng)算法同時(shí)用于TSP中進(jìn)行比較分析，通過(guò)Matlab繪出的最優(yōu)解變化圖形如圖2、圖3所示。在Matlab7.0中編程對(duì)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問(wèn)題，描述了TSP的相關(guān)問(wèn)題和蟻群算法原理。基本的蟻群算法具有較強(qiáng)的魯棒性，但收斂速度緩慢。針對(duì)傳統(tǒng)蟻群算法存在搜索時(shí)間長(zhǎng)、易陷局部最優(yōu)解，在算法中改進(jìn)重要的參量——信息素與信息素殘留因子，形成動(dòng)態(tài)的自適應(yīng)信息素，并應(yīng)用于TSP問(wèn)題中使運(yùn)算。論證了將改進(jìn)后蟻群算法在TSP問(wèn)題研究應(yīng)用的可行性，平衡各路徑的信息量，使螞蟻在初始階段在較大范圍內(nèi)進(jìn)行搜索，能盡快地找到目標(biāo)點(diǎn)，并找到最優(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] 楊志曉，郭勝國(guó)，等．基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃算法[J]．微計(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é)報(bào)，2002，14（1）：31-33.