一種基于動態(tài)局部搜索的蟻群算法及其對TSP問題的求解.pdf

1、分類號I￡至墨UDC碩士學位論文一種基于動態(tài)局部搜索的蟻群算法及其對TSP問題的求解論文答辯日期2Q!魚生墨旦量皇目學位授予日期答辯委員會主席一種基于動態(tài)局部搜索的蟻群算法及其對TsP問題的求解摘要蟻群算法在求解TSP問題時，有陷入局部最優(yōu)解、收斂速度太慢和求解質(zhì)量不高以及穩(wěn)定性不足等三個缺點。文章針對這三個缺點，提出了一種以基于斥候蟻實現(xiàn)的動態(tài)局部搜索為核心策略，城市分類、加大信息素濃度差和繼承式的信息素清零策略等3種策略進行輔助改進

2、的蟻群算法。城市分類即在螞蟻開始搜索時對城市進行分類，不同類別的城市代表不同的等級，會向等級高的城市更多的螞蟻，而對于等級低的城市則相反；而通過仿生學引入的斥候蟻，是在螞蟻的尋路過程中，若發(fā)生選擇困難，螞蟻很難選擇出該走那一條路的時候，則酌情派出斥候蟻幫助進行探索，之后通過對比斥候蟻和螞蟻的路徑長短來決定哪一條路徑更優(yōu)；在每次尋路完畢后，采用新的更新信息素的策略，即獲得當次迭代的最短路徑，與當次迭代前所得到的最短路徑進行求比，若比值越大

3、，信息素更新幅度也就越大；當算法陷入局部最優(yōu)時，為了不讓信息素完全被清除，采用有補償?shù)男畔⑺厍辶悴呗?，這樣不僅能跳出局部最優(yōu)，還能提高算法的效率。文章對傳統(tǒng)的蟻群算法對TSP求解的原理進行詳細的闡述，分析了蟻群算法在求解TSP問題時產(chǎn)生三大缺陷的根本原因，從根本原因入手，設(shè)計出改進蟻群算法，并通過Matlab和TSPLIB對兩種算法進行了仿真實驗。對比仿真結(jié)果表明，改進的算法在求解TSP問題時，能夠極大的優(yōu)化求解質(zhì)量，讓求解結(jié)果也變得穩(wěn)