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

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

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

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