基于變異和啟發式選擇的蟻群優化算法

方霞，席金菊

湖南文理學院計算機科學與技術學院，湖南常德 415000

基于變異和啟發式選擇的蟻群優化算法

方霞，席金菊

湖南文理學院計算機科學與技術學院，湖南常德 415000

蟻群算法是一種較好地解決組合優化問題的新型進化算法，是繼模擬退火、遺傳算法、禁忌搜索等之后的又一啟發式智能優化算法。20世紀90年代初期，它由意大利學者M.Dorigo等人首先提出[1]，并成功應用于求解TSP、二次分配、圖著色、車輛調度、集成電路設計及通信網絡負載等問題[2-5]。

由于蟻群算法具有良好的魯棒性、正反饋、分布式及并行計算等特點，所以受到學者們的廣泛關注，蟻群算法的理論框架頁日趨成熟。但是隨著問題規模n上升，蟻群算法暴露出收斂速度慢，計算時間長，易于過早陷入局部最優，難以滿足實際需求的不足。針對這些問題，王穎提出了自適應蟻群算法[6]，黃國銳使用信息素擴散等辦法來提高全局搜索能力和搜索速度[7]，丁建立等提出了GAAA算法融合遺傳算法和蟻群算法的各自優點，來取長補短[8]。結合信息素的更新和搜索機制的改進是目前優化蟻群算法的集中方略，如文獻[9]提出分段優化策略加速解的構造；文獻[10]通過視覺反饋與行為記憶加快局部收斂；文獻[11]進行啟發式修正來加速收斂；文獻[12]通過不同的螞蟻種群構造解的多樣性，使得收斂平衡。文獻[13-14]分別對于蟻群算法進行了綜述以及各項參數對于算法的影響。這些改進蟻群算法都進一步提高了算法的收斂速度，改進了求解質量，這些學者的研究都在一定程度上改善了蟻群算法的性能，但是收斂速度慢、求解質量和求解效率的矛盾等問題仍然是制約蟻群算法廣泛應用特別是在較大規模優化問題中應用的主要瓶頸。因此，本文從一些經典TSP問題出發，提出了一種基于變異和啟發式選擇的蟻群優化算法（ACO algorithm based on Mutation Features and Selected Heuristic，MFSHACO）。首先利用較優路徑中城市相互之間的鄰接特點，產生較好的初始解，極大提高了算法的效率，在不同階段進行變異，既提高了變異效率，也改進了變異質量，在一些經典TSP問題上新算法表現出很好的性能。

1 TSP問題描述

已知n個城市及各城市之間的距離，求一條經過各城市一次且僅一次的最短回路。圖論描述為G=(V,A)，V={v1,v2,…,vn}是n個城市的頂點集，vi,vj∈V}是V中各頂點相互連接組成的弧集，已知各城市間的距離dij，求一條最短的Hamilton回路，即在點集V= {v1,v2,…,vn}中，對n個城市遍歷且只遍歷一次的最短封閉曲線。本文算法采用具備dij=dji特征的TSP問題進行探討。

2 基本蟻群算法

常規蟻群算法求解TSP問題描述：

將m只螞蟻隨機放置在n個城市上，設初始時刻城市之間每一條邊上信息素τs(0)=const，const是一個常量，tabuk是禁忌表，用來記錄螞蟻k所遍歷城市節點，初始時刻是第一個城市節點，隨著tabuk進化作動態調整，凡是寫入禁忌表tabuk中城市節點，螞蟻不允許再遍歷該城市節點。當n個城市節點都寫入禁忌表tabuk中，表示螞蟻完成一次循環。當本次循環完成后，禁忌表tabuk被清空，該螞蟻又可以重新自由地進行選擇。在路徑搜索過程中，螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率。如果(t)＜p0（0＜p0＜1，為轉移概率門檻值），在t時刻，螞蟻k在城市i選擇城市j的轉移概率(t)按公式（1）來求解：

其中τij(t)表示t時刻在節點i和節點j路徑上的信息素。螞蟻k(k=1,2,…,n)在運動過程中，根據各條路徑上的信息素的濃度決定轉移方向；(t)表示在t時刻螞蟻k從節點i轉移到節點j的概率；dij(i,j=1,2,…,n)表示節點i和節點j之間的距離，ηij為能見度啟發因子，表示目標點的能見度，它與距離因子dij成反比，ηij=1/dij；allowedk={1,2,…,n}表示螞蟻k下一步允許選擇的城市，轉移概率成正比。

經過n個時刻，螞蟻完成一次循環，各路徑上信息量根據公式（2）調整：

Δτij(t,t+1)表示本次循環中路徑(i,j)的信息素的增量，計算方法根據計算模型而定，本文算法采用蟻周系統模型（Ant Cycle System）：

Lk是節點i與j之間的距離。基本的蟻群算法有兩個基本缺陷：搜索時間過長和容易陷入局部解。新算法采用MMAS（最大最小螞蟻系統，MAX-MIN Ant System）在很大程度上克服了這兩個缺陷，取得了良好的結果。

3 MFSHACO算法

3.1 MFSHACO算法原理

3.1.1 緊鄰信息優先機制

大量的實驗表明，實際優化回路中城市i的鄰接節點僅僅是離城市i較近的有限幾個城市，結合視覺能見度分析，可以有選擇地進行，由此提出緊鄰信息優先機制：螞蟻k以當前節點i為中心，按照距離路徑長短dij的非遞減排序，選取一定數量的節點作為有限的能見城市，作為下一個節點j的可選范圍，具體數量可以根據情況動態設定，也可簡單設定有限視覺數量為w=n/r，r=1,2,…,20（r的值根據問題規模n的大小進行適當調整），即從w個節點中找出還未經過的節點加入禁忌表tabuk。

算法根據dij距離矩陣信息進行排序得到一個n行w列的有序矩陣，以及對應的城市編號信息矩陣。則在t時刻螞蟻k在當前節點，至多需要檢測編號信息矩陣中w個節點與禁忌表中信息進行比較，從而亦能降低可行節點的數目，隨之可行節點的轉移概率計算量也大大下降，總體時間復雜度由O(mn2)變為O(w·mn)，而w是一個相對穩定的常量，不會隨著問題規模n的增長而增長，亦可記為O(mn)，蟻群算法的計算速度大大提高，同時初始解的螞蟻群較好，排除了出現大量較差解的可能。

大量的實例計算可以發現，蟻群算法選擇下一個城市時，往往是選擇最近的幾個，也就是從allowedk所列的城市中，僅選擇符合dij較小的幾個城市。隨著每一只螞蟻走完大半路徑后，備選城市越來越少，很有可能被迫從一個邊區跳躍至另一個邊區，出現路徑交叉，產生較差的解，影響整個蟻群算法的搜索效率。最明顯的情況就是每一只螞蟻搜索到最后兩三個城市時，這幾個城市間距又很遠，螞蟻已經無法進行更多的選擇，出現這種情況主要是因為ACS中螞蟻選擇路徑是沒有考慮所有剩下城市的布局，這就出現了選擇的沖突。從ACS的搜索過程中，查看一些螞蟻歷經的城市連線，絕大部分都不可避免地存在這個問題，而到目前為止尚無合適的解決方案。本文算法采用變異策略解決該沖突。

3.1.2 變異機制

新算法采用變異策略解決該沖突：當w個備用節點均和禁忌表tabuk相沖突時，則突破w個視覺范疇，轉向全部的節點數據來和禁忌表檢測，找到合理的節點作為下一節點。一般這時找到的節點不能得到較好的解，為了保證尋找到較優的解，隨即采用一定的概率進行變異，變異時只對路徑后面發生沖突的部分采用2-opt變異，同時檢測以防止出現路徑交叉的現象，得到比較理想的解。變異策略如下：

其中c為變異次數，一般取為(n+1)/8，t為當前發生沖突時在當前搜索路徑中所處的位置，n為路徑長度。

在所有螞蟻進行一次周游完成以后，全局也進行一次2-opt變異，充分利用其簡潔高效的特點，使每一輪能得到較好解，有效提高收斂速度，期望得到全局最優解。

3.1.3 啟發式選擇調整

在基本蟻群算法中，啟發式信息在指導螞蟻的路徑搜索方面會產生一定的影響，但是隨著搜索過程的不斷深入，較好路徑上的信息素累積越來越多，啟發式信息的影響程度越來越弱；在算法后期，啟發式信息對搜索過程的影響已經微乎其微。因此，為了更加有效地利用啟發式信息，本文在算法后期通過動態調整啟發式信息來保證算法快速收斂于最優解。

信息素指數β采用模擬退火法進行調整。蟻群完成一次周游后得到路徑長度的最短路徑Lbest和平均路徑長度LAver，β值根據如下公式進行計算：

其中nc為當前迭代數，初始β為一指定常量β0。

相較于文獻[10]中DEAHACO算法定義的路徑期望值PExpect進行當前路徑調整，算法計算數據大大下降，時間復雜度也相應降低。

3.2 MFSHACO算法步驟

步驟1初始化m,α,β0,ρ,Q,NC,w，計算得到緊鄰矩陣信息D_sort，R_sort。

步驟2隨機選擇每只螞蟻的初始位置。

步驟3開始周游，首先根據緊鄰矩陣信息并按照公式（1）找到下一個城市節點；如果緊鄰節點發生沖突成為不可選，則突破緊鄰矩陣的限制，在全部可選范圍處理，同時記憶當前位置t，該螞蟻周游完成后隨即進行變異操作。

步驟4所有螞蟻周游一次完成后，進行變異操作。

步驟5根據公式（2）～（4）更新信息素濃度τij，采用了MMAS算法。

步驟6計算本次周游得到的最短路徑Lbest和最長路徑Lworst，根據公式（5）更新β值。

步驟7判斷是否達到指定的迭代次數NC或者所求的解在最近若干代中無明顯改進，若是，則結束迭代，輸出最后的優化結果；否則轉步驟2。

4 實驗分析

為了探索改進算法的各項性能指標，將MFSHACO算法應用于TSPLIB數據集（http：//elib，zib，de/pub/mp-testdata/tsp/tsplib）中eil51實例，結合Matlab編程實驗環境，實驗中使用的參數均通過驗證確認。

4.1 MFSHACO算法性能比較

設置參數Q=100，τmax=10，τmin=0.1。在每種情況運行10次，每次最大迭代次數NC為100的實驗數據結果基礎上，得到的平均數據如表1所示。

表1 改進算法加入變異和啟發式選擇機制的優化結果

從表1中數據可以看出：改進蟻群算法MFSHACO在求得最優解和收斂速度上有明顯優勢，算法通過引入合理的變異機制和進行啟發式選擇可以大大提高算法的收斂性能，在求解質量方面都得到明顯改善，說明MFSHACO算法是有效又實用的。

為了驗證該算法的有效性，根據不同的緊鄰信息數據w，表2為應用于eil51實例在不同參數下得到的實驗統計結果。由表2可知將變異機制、啟發式選擇機制、MMAS算法等融合之后算法在全局搜索能力和收斂速度方面得到了較好的平衡，整個程序的計算速度得到了大幅提升，隨著問題規模的上升，可以更好地體現其優越性。

表2 MFSHACO算法解決eil51實例不同參數下的實驗結果

4.2 MFSHACO算法收斂性分析

圖1為MFSHACO算法應用到eil51實例所得到的一個最優路徑模擬仿真和收斂效果圖。具有MFSHACO算法的一般特征，算法參數為：m=n=51，Q=100，α=2，β0= 3，ρ=0.1，NC=100，橫坐標表示算法的迭代次數，縱坐標表示當前路徑的長度。收斂曲線分別為每次迭代所得到的最短路徑長度和平均路徑長度。

圖1 MFSHACO算法在eil51實例上的收斂性

由實驗收斂效果圖可以看出，MFSHACO算法在運行初期急速收斂，迭代至10～25次時能夠接近于最優解，而基本MMAS算法大約需要迭代2 500次以后才收斂，經過多次實驗，參考表2中的數據，根據參數選擇設置的不同，達到收斂所需進化代數最小值略有差異，但是相較于基本蟻群算法，無論時間復雜度，還是收斂效果方面，本文MFSHACO算法都是一種高效的求解TSP問題的蟻群優化算法。

5 結束語

針對傳統蟻群算法初始較好解產生困難、計算搜索時間長、收斂速度慢、易于停滯等特點，本文提出了MFSHACO算法，該算法采用節點之間的緊鄰信息，動態進行啟發式的選擇，能夠合理有效地產生較好的初始解，避免了大范圍搜索，并且能夠極大提高算法的計算速度。同時充分采用局部和全局變異策略，指導算法加速收斂，使得變異結果的質量有較大改善。實驗數據表明，MFSHACO算法不僅能夠獲得高質量優化解，而且收斂速度大幅提升，整體運行時間大幅下降，特別隨著問題規模n的增大，有很強的實用意義。本文各種參數的選擇主要依靠經驗，后期將針對不同的變異策略和組合參數之間的關系進行深入研究。

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

[2]常智勇，楊建新，趙杰，等.基于自適應蟻群算法的工藝路線優化[J].機械工程學報，2012，48（9）：163-169.

[3]潘杰，王雪松，程玉虎.基于改進蟻群算法的移動機器人路徑規劃[J].中國礦業大學學報，2012，41（1）：108-113.

[4]于宏濤，高立群.容量受限工廠選址問題模型及貪婪蟻群算法求解[J].東北大學學報：自然科學版，2011，32（12）：1688-1691.

[5]冀俊忠，黃振，劉椿年.基于變異和信息素擴散的多維背包問題的蟻群算法[J].計算機研究與發展，2009，46（4）：644-654.

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

[7]黃國銳，曹先彬，王煦法.基于信息素擴散的蟻群算法[J].電子學報，2004，32（5）：865-868.

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

[9]冀俊忠，黃振，劉椿年，等.基于多粒度的旅行商問題描述及其蟻群優化算法[J].計算機研究與發展，2010，47（3）：434-444.

[10]郭禾，程童，陳鑫，等.一種使用視覺反饋與行為記憶的蟻群優化算法[J].軟件學報，2011，22（9）：1994-2005.

[11]劉全，陳浩，張永剛，等.一種動態發揮率和啟發式修正的蟻群優化算法[J].計算機研究與發展，2012，49（3）：620-627.

[12]張曉偉，李笑雪.新型的雙種群蟻群算法[J].計算機工程與應用，2011，47（13）：39-41.

[13]Hu Yurong，Ding Lixin，Xie Datong.The setting of parameters in an improved Ant Colony Optimization algorithm for feature selection[J].Journal of Competational Information Systems，2012，8（19）：8231-8238.

[14]Hu Xiayun，Zhu Yanfei.Researches and applications of ant colony algorithm[C]//Proc of the 2nd International Conference on Computer Application and System Modeling.Paris：Atlantis Press，2012：859-862.

FANG Xia,XI Jinju

School of Computer Science and Technology,Hunan University of Arts and Science,Changde,Hunan 415000,China

There are some shortcomings in the traditional ant colony algorithm as the algorithm costs too much time to get an optimal solution and easily falls into a stagnation behavior.To solve these problems,this paper puts forward a new ant colony algorithm based on mutation features and selected heuristic.The new algorithm uses the basic characteristics between the adjacent nodes in the optimal path,avoiding the large scope searching.It can get better initial solutions and greatly reduces the time complexity of the algorithm.It also uses the selected heuristic to accelerate the convergence process.With the 2-exchanged method, the mutation strategy not only enhances the mutation efficiency,but also improves the mutation quality.Combined with classic TSP instances,the MFSHACO algorithm shows good performance.

ants colony system;Traveling Salesman Problem（TSP）;mutation;selected heuristic

為了解決傳統蟻群算法求解TSP問題的求解時間較長、易于局部收斂的問題，提出了一種基于變異和啟發式選擇的蟻群優化算法。利用較優路徑中城市相互之間的鄰接特點，避免了大范圍搜索求解，使得能具有較好的初始解，將算法的時間復雜度大大降低；同時為了加快算法的收斂速度，對于路徑的啟發式選擇進行重新定義；引入變異機制，充分利用2-交換法簡潔高效的特點，既提高了變異效率，也改進了變異質量。實驗結果證明，在一些經典TSP問題上新算法表現出很好的性能。

蟻群算法；旅行商問題（TSP）；變異；啟發式選擇

A

TP301；TP18

10.3778/j.issn.1002-8331.1306-0238

FANG Xia,XI Jinju.Ant colony algorithm based on mutation features and selected heuristic.Computer Engineering and Applications,2013,49（24）：24-27.

湖南省教育廳項目（No.09C704）。

方霞（1972—），女，高級實驗師，主要研究方向：計算機應用，智能控制與優化；席金菊（1965—），女，教授，主要研究方向：計算機應用。E-mail：yufangxia@163.com

2013-06-21

2013-08-05

1002-8331（2013）24-0024-04

CNKI出版日期：2013-10-14http://www.cnki.net/kcms/detail/11.2127.TP.20131014.1655.003.html