改進(jìn)蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究.pdf

1、路徑規(guī)劃問題是組合優(yōu)化和運(yùn)籌學(xué)領(lǐng)域研究的熱點(diǎn)問題之一，具有重要的理論和現(xiàn)實(shí)意義。蟻群優(yōu)化算法是受蟻群覓食行為啟發(fā)而提出的一類群智能優(yōu)化算法，該算法能有效地解決具有NP-Hard特性的組合優(yōu)化問題。由于蟻群算法在求解離散問題的優(yōu)勢(shì)和對(duì)路徑的敏感性，使它對(duì)路徑規(guī)劃問題的求解一直備受關(guān)注。
　　 本文針對(duì)旅行售貨員問題、多智能體的編隊(duì)控制問題、車輛路由問題以及智能體路徑規(guī)劃問題，分別提出改進(jìn)的蟻群算法進(jìn)行求解。主要的研究?jī)?nèi)容和創(chuàng)新點(diǎn)如

2、下：⑴提出了一種求解旅行售貨員問題的改進(jìn)蟻群算法。該算法在信息素更新過程中，使用一種信息素局部更新和全局動(dòng)態(tài)更新結(jié)合的方法，使當(dāng)前最優(yōu)路徑上的信息素能夠根據(jù)當(dāng)前最優(yōu)解動(dòng)態(tài)地進(jìn)行調(diào)配，避免算法陷入停滯狀態(tài)。在局部搜索過程中，僅對(duì)部分走出更優(yōu)路徑的售貨員使用2-opt方法，提高了求解的精度，加快了最優(yōu)解的收斂速度。仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性，與其它算法相比，算法在求解質(zhì)量和收斂速度上都顯示出了良好的性能。⑵提出了一種多智能體編隊(duì)控制問題的改

3、進(jìn)蟻群算法。針對(duì)多智能體在編隊(duì)過程中的最短編隊(duì)距離問題，使用改進(jìn)的蟻群算法對(duì)其求解。該算法每次迭代時(shí)，會(huì)給每個(gè)智能體一個(gè)隨機(jī)的初始位置，以增強(qiáng)搜索的多樣性。在搜索過程中，使用智能體當(dāng)前位置與目標(biāo)位置距離的倒數(shù)作為啟發(fā)式信息，以引導(dǎo)智能體向路徑更短的目標(biāo)位置進(jìn)行移動(dòng)。局部搜索過程采用一種交換搜索的方式，能夠擴(kuò)大搜索的范圍，加快最優(yōu)解的收斂速度。仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。⑶提出一種帶容量約束車輛路由問題的改進(jìn)蟻群算法。該算法使用一種新的車

4、輛位置初始化方式，增加了車輛走出最優(yōu)路徑的可能性。在搜索過程中，使用客戶之間路徑的節(jié)省量作為啟發(fā)式信息，以引導(dǎo)車輛向路徑更節(jié)省的客戶移動(dòng)。信息素更新采用一種動(dòng)態(tài)更新的方法，能夠根據(jù)當(dāng)前車輛所構(gòu)建路徑的情況對(duì)信息素進(jìn)行更新，避免算法陷入停滯狀態(tài)。局部搜索除使用2-opt方法外，針對(duì)不同車輛訪問的客戶，還增加了交換搜索和插入搜索，以擴(kuò)大搜索的范圍。仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。⑷提出了一種靜態(tài)環(huán)境下智能體路徑規(guī)劃問題的端點(diǎn)逼近蟻群算法，該算法