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

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

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

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