求解較大規(guī)模TSP問題的改進蟻群算法

摘 要：為了優(yōu)化并提高傳統(tǒng)蟻群算法求解較大規(guī)模TSP問題的計算速度，提出了一種基于有限視覺能見度機制的改進蟻群優(yōu)化算法。采用初始解優(yōu)化路徑中節(jié)點間鄰接特征，縮小可選范圍搜索求解，算法時間復(fù)雜度由O（mn2）改進為O（mn），最后對可能的沖突問題給出變異解決方案。結(jié)合大規(guī)模TSP問題驗證并加以完善，實驗結(jié)果證明，新算法提高計算速度效果顯著。

關(guān)鍵詞：蟻群算法ACS；TSP；有限視覺能見度

引言

蟻群算法是繼模擬退火、禁忌搜索、遺傳算法等之后的一種新型解決組合優(yōu)化問題的啟發(fā)式智能優(yōu)化算法。蟻群算法的優(yōu)點在于：采用正反饋機制，有發(fā)現(xiàn)較好解的能力，具有很強的并行性和魯棒性等。但是收斂速度慢，計算時間較長，易過早陷入局部最優(yōu)，在求解連續(xù)優(yōu)化問題上沒有優(yōu)勢。針對這些問題，目前已有了一些改進的蟻群算法：

White T等提出了ASGA（ant system with genetic algorithm）算法加入了控制參數(shù)的調(diào)整，更加優(yōu)化[2]，Stüzle T等提出了MMAS（max-min ant system）算法避免算法過早收斂于非全局最優(yōu)解[3]，張紀會、王穎等提出了自適應(yīng)蟻群算法來提高全局搜索能力和搜索速度[4-5]，丁建立等提出了GAAA（genetic algorithm-ant algorithm）算法融合遺傳算法和蟻群算法的各自優(yōu)點，來取長補短[6]，尚鮮連等提出了一種智能蟻群優(yōu)化算法[7]，采用最近節(jié)點選擇策略進行路徑優(yōu)化，但是未能結(jié)合較大規(guī)模TSP問題實現(xiàn)驗證，未考慮處理實際使用中出現(xiàn)的特別情況。文章主要采用有限視覺能見度機制，結(jié)合大規(guī)模TSP實際應(yīng)用中的特殊情況驗證并進行完善，避免在大范圍搜索求解，產(chǎn)生較好的初始螞蟻群，極大提高計算速度，有效解決蟻群算法求解較大規(guī)模問題時的計算時間過長這一缺陷?！?br>