摘要：TSP問題是一類典型的NP完全問題，蟻群算法是求解該問題的方法之一。該文在研究蟻群算法的基本優(yōu)化原理的基礎(chǔ)上，建立了求解TSP 問題的數(shù)學(xué)模型，設(shè)計(jì)了一個(gè)求解TSP問題的蟻群算法程序，并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性，分析了螞蟻規(guī)模、周游次數(shù)等因素對(duì)蟻群算法搜索結(jié)果所產(chǎn)生的影響。

關(guān)鍵詞：TSP；蟻群算法；NP完全問題

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）13-3117-03

旅行商問題（Traveling Salesman Problem，簡(jiǎn)稱TSP）是一個(gè)具有廣泛應(yīng)用背景和重要理論價(jià)值的組合優(yōu)化問題，它已被證明屬于NP難題[1]。目前對(duì)于求解該類問題的研究主要有兩個(gè)方向：一是傳統(tǒng)的數(shù)學(xué)規(guī)劃方法，這種算法可以得到全局最優(yōu)解，但復(fù)雜性往往難以接受，因而不適應(yīng)于大規(guī)模復(fù)雜問題的求解。二是近年來發(fā)展起來的各種仿生進(jìn)化算法如遺傳算法、蟻群算法等，此類算法能夠在多項(xiàng)式時(shí)間內(nèi)找到全局最優(yōu)解或近似全局最優(yōu)解[2]。蟻群算法（Ant Colony Algorithm， 簡(jiǎn)稱ACA）是受自然界中螞蟻集體尋食過程的啟發(fā)而提出來的一種新的智能優(yōu)化算法，它具有高度的本質(zhì)并行性、正反饋選擇、分布式計(jì)算、魯棒性等優(yōu)點(diǎn)，蟻群算法最早成功地應(yīng)用于解決TSP問題。

本文在研究蟻群算法的基本優(yōu)化原理的基礎(chǔ)上，編寫了一個(gè)基于VC的求解TSP問題的蟻群算法程序，并且通過多次實(shí)驗(yàn)測(cè)試，驗(yàn)證了算法的有效性，分析了螞蟻規(guī)模、周游次數(shù)等因素對(duì)蟻群算法的搜索結(jié)果和效率所產(chǎn)生的影響。

1 TSP問題建模

2 基于蟻群算法的TSP問題求解

2.2蟻群算法的基本原理

蟻群算法是一種源于自然生物界的新型仿生優(yōu)化算法，它于20世紀(jì)90年代初由意大利學(xué)者M(jìn).Dorigo，V.Maniezzo首次提出[3]，蟻群算法的特點(diǎn)是模擬自然界中螞蟻尋食的群體行為。研究表明，螞蟻會(huì)在走過的路上留下信息素，信息素會(huì)隨時(shí)間的推移逐漸揮發(fā)消失，螞蟻就是通過信息素進(jìn)行信息交流。螞蟻趨向于朝信息素積累較多的路徑移動(dòng)，信息素濃度越高的路徑，選擇它的螞蟻就越多，則該路徑上留下的信息素濃度就越大，而高濃度的信息素反過來又會(huì)吸引更多的螞蟻，從而形成一種正反饋。通過這種正反饋機(jī)制，螞蟻?zhàn)罱K可以發(fā)現(xiàn)最短的路徑，并且最后所有的螞蟻都會(huì)趨向于選擇這條最短路徑[4]。這就是蟻群算法的基本原理。

2.2求解TSP問題的蟻群算法設(shè)計(jì)

2.3算法步驟

4 結(jié)束語(yǔ)

本文探討了蟻群算法的基本優(yōu)化原理，設(shè)計(jì)并實(shí)現(xiàn)了求解TSP問題的蟻群算法程序，通過實(shí)驗(yàn)驗(yàn)證了算法的有效性，同時(shí)，經(jīng)過多次實(shí)驗(yàn)測(cè)試結(jié)果，分析了對(duì)蟻群行為和算法的解產(chǎn)生影響的各個(gè)因素。

蟻群算法作為一種新的仿生進(jìn)化算法，它在解決許多復(fù)雜組合優(yōu)化問題方面顯示出了明顯的優(yōu)勢(shì)，但也存在著諸如搜索時(shí)間較長(zhǎng)等不足之處，因此，對(duì)算法的改進(jìn)、收斂性分析及理論依據(jù)等方面還有待進(jìn)一步深入研究。

參考文獻(xiàn)：

[1] 郭平，嫣文靜.求解TSP問題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007，34（10）：181-184.

[2] 周康，強(qiáng)小利，同小軍，等.求解TSP算法[J].計(jì)算機(jī)工程與應(yīng)用，2007（29）：43-47.

[3] DORIGO M， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems，1996，26（1）：1-26.

[4] 李志偉.基于群集智能的蟻群優(yōu)化算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2003，24（8）：27-29.

[5] Dorigo M， Bonabeau E， Theraulaz G. Ant algorithms and stigmergy[J]. Future Generation Computer Systems Journal， 2000，16 （8）： 851-857.