基于演化蟻群算法的TSP問題研究及應用.pdf

1、蟻群算法是最近幾年才提出來的一種新的仿生優(yōu)化算法,它是由意大利學者M.Dorigo,V.Mahiezzo,A.Colorni等人受自然界中真實螞蟻群體尋找食物過程的啟發(fā)而率先提出來的。他們利用螞蟻搜索食物的過程與旅行商問題之間的相似性,通過人工模擬螞蟻搜索食物的過程中螞蟻個體之間的相互協(xié)作與信息交流,最終找到從巢穴到食物源最短路徑的原理來解決旅行商問題(TSP),并取得了較好的效果。該算法具有高度的本質(zhì)并行性、較強的魯棒性、優(yōu)良的分布式

2、計算機制,易于與其他方法相結(jié)合等優(yōu)點。自蟻群算法提出以來,引起了國內(nèi)外學者的極大關注,在十多年的時間里,已在組合優(yōu)化、數(shù)據(jù)挖掘、網(wǎng)絡路由,機器人路徑優(yōu)化,連續(xù)函數(shù)優(yōu)化問題上得到了廣泛的應用,顯示出其在求解復雜優(yōu)化問題方面的優(yōu)越性。因此,蟻群算法的研究無論是從理論上還是應用上都具有較高的價值。
　　作為一種近年提出的新型優(yōu)化算法,還沒有像遺傳算法,模擬退火算法等那樣形成系統(tǒng)的分析方法和堅實的數(shù)學基礎,許多理論問題有待研究,比如算法搜

3、索時間較長,運行過程中容易出現(xiàn)收斂過早或停滯現(xiàn)象,不能擴大解的搜索范圍等。針對這些缺陷,近年來國內(nèi)外學者對蟻群算法提出了大量的改進方法。
　　TSP是一個具有廣泛應用背景和重要理論價值的組合優(yōu)化問題,已經(jīng)成為并將繼續(xù)成為測試組合優(yōu)化算法的標準問題。本論文圍繞蟻群算法的原理,理論及應用,針對目前蟻群算法在解決TSP時存在的一些缺陷,在閱讀大量相關文獻的基礎上提出了幾點改進方法。
　　本論文的主要研究成果包括:
　　第一、

4、在信息素更新方式上,引入反饋因子,利用先前的反饋信息,盡力避免不必要的搜索,在信息素更新時,對所有的解不使用統(tǒng)一的信息素更新方式,而是根據(jù)反饋因子采取不同解不同對待的策略,對每次循環(huán)中的最優(yōu)解、最差解及一般解分別執(zhí)行不同的信息素更新方式,增強一般解的信息素,對最優(yōu)解進行更大限度的增強,對較差解進行削弱,使得屬于最優(yōu)路徑的邊與屬于較差路徑的邊之間的信息素量差異進一步增大,以便更好的利用螞蟻先前的反饋信息,使螞蟻的搜索行為更集中于最優(yōu)解附近

5、,從而引導問題的解向著全局最優(yōu)的方向不斷進化。
　　第二、提出一種新的啟發(fā)式演化交叉算子,這種演化交叉不只是單純的進行隨機交叉,而是綜合父代基因,再根據(jù)各個城市之間的連接關系的一種啟發(fā)式交叉方式。將這種交叉算子應用到蟻群算法中,隨機選擇一條路徑與最優(yōu)路徑執(zhí)行這種啟發(fā)式交叉,通過這種交叉得到的子代將會有效的繼承父代較好的基因,從而有利于發(fā)現(xiàn)最優(yōu)解,加快算法的收斂速度。
　　第三、為了進一步防止算法過早陷入局部最優(yōu),本論文采用確