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

1、蟻群優(yōu)化算法是一種仿生型的智能優(yōu)化算法，具有正反饋、分布計(jì)算和啟發(fā)性搜索等特點(diǎn)。作為計(jì)算智能和群智能的重要分支之一，蟻群優(yōu)化算法已經(jīng)成功地應(yīng)用于許多組合優(yōu)化問(wèn)題的求解。 本文在對(duì)幾種常見(jiàn)的蟻群優(yōu)化算法進(jìn)行了比較深入、系統(tǒng)分析的基礎(chǔ)上，著重討論采用蟻群優(yōu)化算法求解旅行商(TSP)問(wèn)題。論文首先采用國(guó)際上通用的測(cè)試問(wèn)題庫(kù)TSPLIB中的幾種TSP問(wèn)題作為測(cè)試對(duì)象，對(duì)幾種蟻群優(yōu)化算法進(jìn)行了性能比較，并對(duì)算法參數(shù)的最優(yōu)化配置進(jìn)行了仿真實(shí)

2、驗(yàn)和分析。結(jié)果表明，對(duì)于小規(guī)模的TSP問(wèn)題，各種算法都表現(xiàn)出優(yōu)越的性能，能在較短時(shí)間內(nèi)找到最優(yōu)解；但在大規(guī)模的TSP問(wèn)題上，現(xiàn)有的算法都不能在有限的時(shí)間內(nèi)找到最優(yōu)解，容易陷入局部最優(yōu)局面，算法過(guò)早收斂停滯。因此，有必要對(duì)算法進(jìn)行改進(jìn)，使算法在中大規(guī)模的TSP問(wèn)題上有較好的性能。 針對(duì)基本蟻群算法求解TSP問(wèn)題容易出現(xiàn)停滯現(xiàn)象的缺陷，本文提出了一種改進(jìn)的蟻群算法。算法的基本思想是將信息素分為局部和全局二種不同的信息素，在搜索過(guò)程中

3、，對(duì)局部和全局信息素采用不同的更新策略和動(dòng)態(tài)的路徑選擇概率，使得在搜索的中后期能更有效地發(fā)現(xiàn)全局最優(yōu)解。利用TSPLIB的數(shù)據(jù)進(jìn)行的實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法對(duì)于中大型TSP問(wèn)題，具有更好的發(fā)現(xiàn)最優(yōu)解的能力。 本文引入了解的性能分布的概念，通過(guò)對(duì)算法求解TSP的解的性能分布分析和運(yùn)行時(shí)間分布分析，得出了一些有意義的結(jié)論：算法找到最優(yōu)解的概率是隨著運(yùn)行時(shí)間的增加而增大的；算法運(yùn)行前期改進(jìn)解的性能速度較快，但后期明顯減慢：可以通過(guò)重