改進(jìn)的蟻群優(yōu)化算法及其在TSP中的應(yīng)用.pdf

1、意大利學(xué)者M(jìn).Dorigo，V.Maniezzo和A.Colorni于1992年通過模擬螞蟻的覓食行為提出了一種基于種群的模擬進(jìn)化算法-蟻群算法，并成功應(yīng)用于求解著名的TSP問題，而后滲透到多個(gè)應(yīng)用領(lǐng)域，從解決一維靜態(tài)優(yōu)化問題到解決多維動(dòng)態(tài)組合優(yōu)化問題，從離散范圍內(nèi)的研究逐漸拓展到連續(xù)范圍內(nèi)的研究，如在系統(tǒng)控制、人工智能、模式識(shí)別、生產(chǎn)調(diào)度等方面。
　　 本文主要圍繞蟻群算法的改進(jìn)及其在TSP中的應(yīng)用展開，就如何改進(jìn)蟻群算法、抑

2、制算法出現(xiàn)停滯、以及在TSP中的應(yīng)用進(jìn)行了深入研究。文章的主要研究工作如下：
　　 針對(duì)蟻群算法容易早熟、收斂速度慢等缺點(diǎn)，提出了兩種改進(jìn)的蟻群算法。
　　 1、基于交稅的蟻群算法。首先在螞蟻搜索過程中采用動(dòng)態(tài)偽隨機(jī)比例選擇機(jī)制，在搜索的前期，保證了搜索的范圍較大，在搜索后期，保證了算法的收斂性；同時(shí)，根據(jù)繳納個(gè)人所得稅的方式，在進(jìn)行全局信息素更新的時(shí)候，每隔一段時(shí)間，當(dāng)前最優(yōu)路徑再繳納一定的信息素稅，從而提高了算法搜索

3、較好解的能力。
　　 2、帶路徑評(píng)估的蟻群算法。所有螞蟻每完成一次路徑搜索，記錄下每只螞蟻搜索到的路徑長度，根據(jù)改進(jìn)的標(biāo)準(zhǔn)方差計(jì)算公式來評(píng)估當(dāng)前搜索的情況，決定是否要進(jìn)行信息素全局更新；同時(shí)，采用區(qū)間壓縮函數(shù)，如果在一段搜索時(shí)間內(nèi)沒有出現(xiàn)更優(yōu)的解，可能出現(xiàn)了早熟現(xiàn)象，這時(shí)，對(duì)所有路徑上的信息素壓縮，調(diào)整螞蟻對(duì)每個(gè)城市的搜索概率。
　　 通過仿真試驗(yàn)，并與螞蟻系統(tǒng)和蟻群系統(tǒng)進(jìn)行比較，試驗(yàn)結(jié)果表明，這兩種改進(jìn)的算法在避免早熟