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

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

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

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