基于蟻群優(yōu)化算法的TSP問(wèn)題研究.pdf

1、TSP問(wèn)題(traveling salesman problem)是一個(gè)組合優(yōu)化方面的問(wèn)題,已經(jīng)成為并將繼續(xù)成為測(cè)試組合優(yōu)化新算法的標(biāo)準(zhǔn)問(wèn)題.從理論上講,使用窮舉法不但可以求解TSP問(wèn)題,而且還可以求出該問(wèn)題的最優(yōu)解.但是對(duì)現(xiàn)有的計(jì)算機(jī)來(lái)說(shuō),使用常規(guī)的窮舉法在如此龐大的搜索空間中尋求最優(yōu)解,幾乎是不可能的.所以,各種求TSP問(wèn)題近似解的優(yōu)化算法應(yīng)運(yùn)而生了,本文所用到的蟻群優(yōu)化算法也在其中.蟻群算法作為一類啟發(fā)式算法,已經(jīng)成功地應(yīng)用于求解

2、TSP問(wèn)題.螞蟻通過(guò)分泌信息素來(lái)加強(qiáng)較好路徑上的信息素的強(qiáng)度,同時(shí)按照路徑上的信息素強(qiáng)度來(lái)選擇下一步所選擇的路徑,好的路徑將會(huì)被越來(lái)越多的螞蟻選擇,因此更多的信息素將會(huì)覆蓋較好的路徑,最終所有的螞蟻都集中到了好的路徑上.螞蟻的這種基于信息素的正反饋原理正是整個(gè)算法的關(guān)鍵所在.首先,本文對(duì)蟻群系統(tǒng)算法(ACS)的全局收斂性和關(guān)鍵參數(shù)的設(shè)置進(jìn)行了深入的研究.ACS尋優(yōu)性質(zhì)優(yōu)良,但搜索時(shí)間長(zhǎng)、收斂速度慢、容易收斂到局部最優(yōu)解,從而使其進(jìn)一步推

3、廣應(yīng)用受到局限.我們通過(guò)對(duì)算法的全局收斂性以及算法的全局搜索能力進(jìn)行深入的理論研究,從改善算法全局收斂性的角度提出了一系列改良途徑;同時(shí)對(duì)蟻群算法中參數(shù)α、β、ρ的作用作了理論上的研究,對(duì)算法參數(shù)的最優(yōu)化配置進(jìn)行了分析,并利用Eil51這一典型的TSP問(wèn)題進(jìn)行了仿真實(shí)驗(yàn),得出了比較適當(dāng)參數(shù)配置方案.在此之后,本文介紹了蟻群算法中一種新的信息素更新和路徑選擇機(jī)制并應(yīng)用于求解TSP問(wèn)題.在ACS基礎(chǔ)上,改良的蟻群算法采用了更為高效的信息素更