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

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

關鍵詞：蟻群算法ACS；TSP；有限視覺能見度

引言

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

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

1 TSP問題

已知n個城市V={v1，v2，…，vn}和各城市之間的距離dij，尋找一條經過各個城市一次且僅一次的最短路徑。

文章選取對稱TSP為基礎，即具備dij=dji特征的對稱矩陣信息來探討TSP問題，特別針對于較大n規模的TSP問題分析探討。

2 傳統蟻群算法

初始隨機將m只螞蟻放置在n個城市上，設置兩兩城市間鄰接邊上初始信息素τs（0）=const（const為一個常量）；禁忌表tabuk記憶螞蟻k已經遍歷的城市節點，初始時刻是起始第一個城市節點，隨著螞蟻運動軌跡的變化動態調整，凡是已經遍歷過的城市節點，螞蟻不允許再遍歷該城市節點。當n個城市節點全部都寫入禁忌表tabuk中，得到一條優化路徑。一次循環完成后，禁忌表tabuk置空，螞蟻又可重新開始選擇，重復上述過程得到不同路徑。

在生成路徑的過程中，螞蟻根據當前所在位置城市i所對應鄰接城市節點路徑上各信息素及能見度啟發信息來計算選取下一個節點的轉移概率。規則如下：若pkij（t）

其中pkij（t）表示在t時刻螞蟻k從節點i轉移到節點j的轉移概率；τij（t）表示t時刻在節點i和節點j路徑上的信息素強度；ηij為能見度啟發因子，表示目標城市節點的能見度，它與距離因子dij成反比，ηij=1/dij；α為信息啟發因子，表示軌跡重要性；β為期望啟發因子，表示能見度重要性，不同的數據環境需要根據情況來設置調整相應的α和β值。allowedk={1，2，...，n}表示螞蟻k下一步可以選擇的城市，與禁忌表tabuk對應。轉移概率pkij（t）與ταij（t）ηβij（t）成正比。

當螞蟻完成一次循環，得到相應的優化解之后，所有路徑段上信息素需要根據公式（2）調整：

其中，Δτkij（t，t+1）表示螞蟻k在時刻（t，t+1）釋放在路徑（i，j）上的信息素，路徑越短，信息素釋放的量就越多；Δτij（t，t+1）表示所有螞蟻在本次循環中經過路徑（i，j）時信息素的增量之和；信息素的衰減系數ρ決定蟻群算法的全局搜索能力及算法的收斂速度，設置系數ρ<1來避免路徑上軌跡量的無限增加，（1-ρ）反映螞蟻個體之間相互影響的能力。

3 改進蟻群算法

傳統ACS中螞蟻k從當前節點i選擇下一個節點j時，需要將n-1個節點與禁忌表比較，時間復雜度為O（mn）2，再計算n-1個節點的轉移概率，螞蟻在選擇下一節點之前需要考慮所有可能的節點集合，時間量也相應增大，對于較大規模的實際問題，搜索時間很長。

3.1 有限視覺能見度機制

無數實例表明，在最優解對應的優化回路中城市節點i的鄰接點僅是離城市i較近的幾個有限城市。為了優化選擇，采用有限視覺能見度策略：以螞蟻k所在當前節點i為中心，將螞蟻k的所有可選鄰接點優先順序按距離路徑非遞減排列，設置w個節點作為有限可選范圍，其中w=n/r，r=1，2，…，20（r的值根據問題規模n的大小進行適當調整）[8]。

算法設計一個n×w維有序矩陣，用來記錄每一個節點對應的w個優先鄰接城市節點編號信息矩陣。采用有限視覺能見度，t時刻螞蟻k在節點i，僅需檢測其所在編號信息矩陣中w個節點，并與禁忌表tabuk中節點信息進行比較，大大降低可行節點數目，同時轉移概率計算量也隨之下降，不計算總的迭代次數NC_max在內，時間復雜度由O（mn2）變為O（wmn），其中w是一個常數，不隨問題規模n的變化而變化，所以亦可記為O（mn），改進蟻群算法計算速度極大提高，由于這種策略得到的螞蟻群初始解較好，避免了過早收斂，出現較差解的可能。

3.2 沖突解決策略

螞蟻k在選擇下一個鄰接點時，往往是選擇幾個距離最近的節點，即從allowedk所列表中，僅選擇符合dij較小的幾個城市。這種情況下采用ACS在求解大規模TSP時存在一個很大問題：在求解路徑的后期，第i只螞蟻走完大多數城市后，搜索到回路中最末尾幾個城市時，剩下可選城市范圍越來越窄，螞蟻i已經無法進行更多的選擇，這幾個城市間距很遠，極有可能出現路徑交叉，從一個邊界區域跳躍至另一個邊界區域，產生較差的解，影響整個蟻群算法的搜索效率。從ACS的大量實例求解中，可以看到螞蟻優化解，這個問題是一個突出矛盾，目前為止尚無好的解決方案。這種現象出現的主要原因是，ACS中螞蟻選擇路徑時沒有考慮剩下城市的整體布局，從而出現了這樣的選擇沖突。

新算法用于解決沖突解決策略采用變異機制：尋找路徑后期，當w個鄰接節點和禁忌表tabuk相沖突或者路徑長度不能達到預期優化數據時，則轉向全局節點數據檢測，突破w個視覺范疇，找到合理的節點作為下一節點。同時為了保證尋找的解的優越性，采用一定的概率進行變異，比較變異前后可行解的差異，選擇兩者中較優解為調整后的結果。

4 實驗數據

結合Matlab編程實驗環境，實現了用傳統蟻群算法ACS和改進蟻群算法解決較大規模TSP問題并仿真，以TSPLIB提供的a280和pr1002問題為例。設置參數α=2，β=3，在a280問題中螞蟻數量m=50，近距離城市數量w=20，pr1002問題中設置螞蟻數量m=300，近距離城市w=30。每種情況進行運行10次以上的試驗運行，得到的平均數據結果如表1所示。

基于有限視覺范圍和變異機制的改進蟻群算法在時間復雜度上有明顯優勢，大大提高了算法的計算能力，而且能夠產生良好的蟻群初始解，問題規模越大，效果越顯著。

圖1為實驗選取a280問題的改進算法運行結果仿真之一，在多次求解得到較好解的優化路徑曲線和迭代進化曲線（平均路徑長度和最短路徑長度）。雖然與圖2中目前已求得的a280問題次優路徑曲線有一定差距，但是求解速度已不在同一級別上[8]。

5 結束語

針對傳統蟻群算法產生初始較好解困難，計算搜索時間過長的特點，結合較大規模TSP問題，提出了有限視覺范圍的機制，使得算法時間復雜度實現了質的飛躍，從二維變為了線性增長，由O（mn2）改進為O（mn），極大提高計算速度。對于較大規模的問題，這點非常必要也是非常重要的，實驗數據表明，改進算法效率顯著，可行有效。

基于有限視覺能見度的改進算法經過變異機制完善，求解得到的較優解也并不遜色于傳統ACS算法，雖然離TSPLIB提供的最優解還有一定差距，這也正是該算法的魅力所在，需要我們思考和不斷探索更多更先進的方法來輔助完善。

參考文獻

[1]Dorigo M， Maniezzo V， Colorni A. The ant system： optimization by a colony of cooperating agents[J].IEEE Trans. on Systems， Man and Cybernetics，1996，1（26）：29-41.

[2]White T，Pagurek B，Oppacher F.ASGA：Improving the ant system by integration with genetic algorithms[R].Canada：Systems and Computer Engineering，Carleton University，1998.

[3]Stützle T，Hoos H.Max-min ant system[J].Future Generation System，2000，16：889-914.

[4]張紀會，高齊圣，徐心和.自適應蟻群算法[J].控制理論與應用， 2000，17（1）：1-3.

[5]王穎，謝劍英.一種自適應蟻群算法及仿真研究[J].系統仿真學報， 2002，14（1）：31-33.

[6]丁建立，陳增強，袁著祉.遺傳算法與蟻群算法的融合[J].計算機研究與發展，2003，40（9）：1351-1356.

[7]尚鮮連，陳靜，姒茂新.改進的智能蟻群算法在TSP問題中的應用[J].計算機仿真，2009，26（12）：160-163.

[8]方霞，席金菊.基于變異和啟發式選擇的蟻群優化算法[J].計算機工程與應用，2013，49（24）：24-27.