一種改進(jìn)的蟻群算法求解旅行商問題.pdf

1、20世紀(jì)90年代初，意大利學(xué)者等人受螞蟻在覓食過程中可以找出從巢穴到食物源的最短路徑的啟發(fā)，提出了蟻群算法(ant colony algorithm)，它是繼禁忌搜索算法、模擬退火算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等啟發(fā)式搜索算法之后出現(xiàn)的一種新的啟發(fā)式搜索算法。蟻群算法不僅能夠智能搜索、全局優(yōu)化，而且具有穩(wěn)健性、正反饋、分布式計算、易與其它算法結(jié)合等特點，魯棒性強(qiáng)，在基本蟻群算法模型的基礎(chǔ)上進(jìn)行修改，便可用于其它問題；正反饋過程使得該方法能

2、很快發(fā)現(xiàn)較好解；分布式計算使得該方法易于并行實現(xiàn)，個體之間不斷進(jìn)行信息交流和傳遞，有利于發(fā)現(xiàn)較好解，不容易陷入局部最優(yōu)；與啟發(fā)式算法相結(jié)合，可改善算法的性能。它成功應(yīng)用于解決許多組合優(yōu)化問題。一些初步研究和應(yīng)用已顯示出蟻群算法在求解復(fù)雜優(yōu)化問題方面的一些優(yōu)越性，特別是離散優(yōu)化問題。因此，蟻群算法已成為當(dāng)前群智能領(lǐng)域中最令人感興趣和最富有魅力的研究課題之一。目前的研究主要集中在比利時、意大利、德國等國家，國內(nèi)的研究主要在上海、北京、東北少

3、數(shù)幾個學(xué)校和研究所開展了此項工作，主要圍繞旅行商及相關(guān)問題的實驗仿真。 本課題的主要工作包括以下三個方面：首先對蟻群算法進(jìn)行基礎(chǔ)理論研究，旨在對蟻群算法近年來的研究進(jìn)展進(jìn)行總結(jié)，歸納算法的成功應(yīng)用領(lǐng)域和存在的不足，并對不足之處進(jìn)行深入理論分析，目的在于提高蟻群算法的總體性能。第二是針對算法容易陷入局部最優(yōu)解，在算法中加入擾動量，擴(kuò)大搜索范圍，從而有效控制算法陷入局部最優(yōu)解。針對蟻群算法收斂速度慢，本文充分利用蟻群在最差路徑上的信