基于演化蟻群算法的TSP問(wèn)題研究及應(yīng)用.pdf

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

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

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

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

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