蟻群算法及其在TSP問題中的應(yīng)用研究.pdf

1、隨著研究對象的日益復(fù)雜化,傳統(tǒng)的基于對象精確模型的控制理論與使用確定性的優(yōu)化算法都遇到了極大的困難。人們從生物進(jìn)化及仿生學(xué)中受到啟發(fā),提出許多求解組合優(yōu)化問題近似解的啟發(fā)式智能優(yōu)化方法。蟻群算法(Ant Colony Algorithm，ACA)是一種新興的仿生類進(jìn)化算法,是繼模擬退火、遺傳算法、禁忌搜索算法之后的又一啟發(fā)式智能優(yōu)化算法。螞蟻能找到從食物源到蟻穴的最短路徑,并且能隨環(huán)境的變化,適應(yīng)性地搜索新的路徑,產(chǎn)生新的選擇。根本原因

2、是螞蟻在尋找路徑時,在其走過的路徑上釋放一種特殊的分泌物—信息素,蟻群算法通過分泌信息素來加強(qiáng)較好路徑信息素的強(qiáng)度,同時按照信息素強(qiáng)度和啟發(fā)信息來選擇下一步要經(jīng)過的城市,好的路徑將會有越來越多的螞蟻選擇,以致更多的信息素會分布在較好的路徑上,最終找到較好的路徑。蟻群算法由Dorigo等人在20世紀(jì)90年代初首先提出,并成功應(yīng)用與求解TSP問題,二次分配、圖著色、車輛調(diào)度以及網(wǎng)絡(luò)路由等問題。蟻群算法采用分布式并行計算機(jī)制,易于與其他方法結(jié)

3、合,具有較強(qiáng)的魯棒性;但搜索時間長、易于陷入局部最優(yōu)是其突出的缺點(diǎn)。
　　本文在廣泛深入地查閱國內(nèi)外文獻(xiàn)的基礎(chǔ)上,對蟻群算法的基礎(chǔ)理論和基本方法進(jìn)行了深入的理論研究和實(shí)驗(yàn)分析。主要研究了蟻群算法的改進(jìn)及應(yīng)用,并進(jìn)行了仿真實(shí)驗(yàn)。主要內(nèi)容如下:
　　系統(tǒng)、詳盡地介紹了蟻群算法的基本理論、算法模型、一般流程,以及對蟻群算法中經(jīng)典的改進(jìn)方法進(jìn)行了全面的介紹和分析,并簡要介紹了旅行商問題的基本理論和求解方法。本文對蟻群算法關(guān)鍵參數(shù)的設(shè)

4、置進(jìn)行了深入的研究并對參數(shù)的最優(yōu)化配置進(jìn)行了分析,并利用eil51這一典型的TSP問題進(jìn)行了仿真實(shí)驗(yàn),得出了比較適當(dāng)?shù)膮?shù)配置方案。
　　針對基本蟻群算法容易出現(xiàn)早熟、停滯現(xiàn)象和收斂速度慢的缺點(diǎn),本文提出了一種改進(jìn)的蟻群算法:通過采用更為高效的路徑選擇機(jī)制、限制信息素的范圍、和增加信息素的局部更新方式,減慢了信息素的堆積速度,擴(kuò)大了螞蟻的搜索空間;在最優(yōu)路徑上加入局部最優(yōu)搜索策略,增大了解突變的機(jī)率,使算法不容易陷入局部最優(yōu)解,提