大規(guī)模組合優(yōu)化問題蟻群算法應(yīng)用研究.pdf

1、蟻群算法作為一種新型的模擬進(jìn)化算法，是由意大利學(xué)者M(jìn)acroDorigo等最早提出，它在解決組合優(yōu)化問題方面效果顯著。但是蟻群算法在求解大規(guī)模組合優(yōu)化問題時其求解速度過慢，為了將蟻群算法成功的引入大規(guī)模組合優(yōu)化問題的解決當(dāng)中，本文在深入的探討了組合優(yōu)化問題和蟻群系統(tǒng)的基礎(chǔ)上，結(jié)合了基本蟻群算法解決大規(guī)模組合優(yōu)化問題的缺點，給出了如何運用蟻群算法解決大規(guī)模組合優(yōu)化問題的策略以及相應(yīng)的算法。 由于基本蟻群算法魯棒性很強可以很容易和別

2、的算法結(jié)合，所以改進(jìn)后的算法運用了數(shù)據(jù)聚類，規(guī)則集挖掘，遺傳算法等知識。為了解決蟻群算法求解大規(guī)模TSP問題時速度較慢的缺點，本文提出了幾點改進(jìn)措施，首先，利用遺傳算法對蟻群的參數(shù)進(jìn)行了進(jìn)化，得到了較為理想的參數(shù)配置，該參數(shù)配置可以針對問題規(guī)模的大小對參數(shù)進(jìn)行合理配置，而合理配置的蟻群算法參數(shù)有利于算法運行速度的提高和得到較優(yōu)的運行結(jié)果。其次，利用聚類算法對所給問題進(jìn)行聚類得到幾個規(guī)模較小的子問題，對每個子問題分配參數(shù)，然后并行運算，同

3、時針對聚類算法的波動性進(jìn)行了一定的探討。其三，針對蟻群算法中當(dāng)循環(huán)進(jìn)行到一定程度的時候，在局部內(nèi)可能已經(jīng)存在的局部最優(yōu)路徑，可以通過分類算法將這些局部內(nèi)的最優(yōu)路徑找出來，歸并為一個城市，并且利用模式學(xué)習(xí)不斷的分析判斷求解得到的局部最優(yōu)路徑是否出現(xiàn)在全局最優(yōu)路徑終，由此可以避免大量的重復(fù)計算，進(jìn)而減少收斂時間。其四，利用信息熵作為判斷算法結(jié)束的條件，改變原有的利用迭代次數(shù)最為結(jié)束條件的方法。 通過選取TSPLIB95中幾個經(jīng)典的T