改進(jìn)的蟻群算法在tsp問題上的應(yīng)用

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-09-27 11:17:49   瀏覽：7155次  

旅行商問題（traveling salesman problem，tsp）是近代組合優(yōu)化領(lǐng)域的一個(gè)典型難題�，F(xiàn)實(shí)生活中的很多問題都可以轉(zhuǎn)化為tsp問題，如郵路問題、通訊網(wǎng)絡(luò)設(shè)計(jì)、大規(guī)模集成電路的綜合布線設(shè)計(jì)等。因此，對tsp問題的研究具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。然而關(guān)于tsp問題的完全有效的算法目前尚未找到，這促使人們長期以來不斷地探索并積累了大量的算法。本文所用到的蟻群算法也在其中。 蟻群算法是受大自然中螞蟻覓食啟發(fā)而提出的一種智能仿生算法，具有較強(qiáng)的魯棒性、分布式計(jì)算、易于與其它方法結(jié)合等優(yōu)點(diǎn)。本文提出一種基于模糊集合的改進(jìn)蟻群算法，該算法根據(jù)隸屬度對種群進(jìn)行評價(jià)，并依此進(jìn)行信息素的更新，在求解速度和解的質(zhì)量上取得一個(gè)較好的平衡。通過對改進(jìn)算法的仿真實(shí)驗(yàn)，驗(yàn)證了該算法的可行性及有效性。本文主要的研究工作如下: 1．闡述了論文研究的背景及意義，總結(jié)了迄今為止出現(xiàn)的求解tsp問題的各種方法，并對常見的求解方法的優(yōu)缺點(diǎn)進(jìn)行了詳細(xì)的分析，最后，分析了蟻群算法國內(nèi)外研究現(xiàn)狀。 2．給出了蟻群算法的基本原理、算法模型以及特點(diǎn)。 3．提出一種改進(jìn)的蟻群算法。該算法引入模糊集合的概念，利用隸屬度對蟻群尋找到的路徑進(jìn)行模糊評價(jià)，并根據(jù)模糊評價(jià)結(jié)果對路徑上的信息素進(jìn)行更新，從而加快了算法收斂速度，提高了算法的性能。 4．采用均勻設(shè)計(jì)法設(shè)置改進(jìn)算法的參數(shù)，通過數(shù)值實(shí)驗(yàn)，驗(yàn)證了改進(jìn)算法的可行性和有效性。

贊助本站