一種基于動(dòng)態(tài)局部搜索的蟻群算法及其對(duì)TSP問(wèn)題的求解.pdf

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

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

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