基于變異和啟發(fā)式選擇的蟻群優(yōu)化算法

方霞，席金菊

湖南文理學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院，湖南常德 415000

基于變異和啟發(fā)式選擇的蟻群優(yōu)化算法

方霞，席金菊

湖南文理學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院，湖南常德 415000

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

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

1 TSP問題描述

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

2 基本蟻群算法

常規(guī)蟻群算法求解TSP問題描述：

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

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

經(jīng)過n個時刻，螞蟻完成一次循環(huán)，各路徑上信息量根據(jù)公式（2）調(diào)整：

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

Lk是節(jié)點(diǎn)i與j之間的距離?；镜南伻核惴ㄓ袃蓚€基本缺陷：搜索時間過長和容易陷入局部解。新算法采用MMAS（最大最小螞蟻系統(tǒng)，MAX-MIN Ant System）在很大程度上克服了這兩個缺陷，取得了良好的結(jié)果。

3 MFSHACO算法

3.1 MFSHACO算法原理

3.1.1 緊鄰信息優(yōu)先機(jī)制

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

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

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

3.1.2 變異機(jī)制

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

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

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

3.1.3 啟發(fā)式選擇調(diào)整

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

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

其中nc為當(dāng)前迭代數(shù)，初始β為一指定常量β0。

相較于文獻(xiàn)[10]中DEAHACO算法定義的路徑期望值PExpect進(jìn)行當(dāng)前路徑調(diào)整，算法計算數(shù)據(jù)大大下降，時間復(fù)雜度也相應(yīng)降低。

3.2 MFSHACO算法步驟

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

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

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

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

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

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

步驟7判斷是否達(dá)到指定的迭代次數(shù)NC或者所求的解在最近若干代中無明顯改進(jìn)，若是，則結(jié)束迭代，輸出最后的優(yōu)化結(jié)果；否則轉(zhuǎn)步驟2。

4 實(shí)驗分析

為了探索改進(jìn)算法的各項性能指標(biāo)，將MFSHACO算法應(yīng)用于TSPLIB數(shù)據(jù)集（http：//elib，zib，de/pub/mp-testdata/tsp/tsplib）中eil51實(shí)例，結(jié)合Matlab編程實(shí)驗環(huán)境，實(shí)驗中使用的參數(shù)均通過驗證確認(rèn)。

4.1 MFSHACO算法性能比較

設(shè)置參數(shù)Q=100，τmax=10，τmin=0.1。在每種情況運(yùn)行10次，每次最大迭代次數(shù)NC為100的實(shí)驗數(shù)據(jù)結(jié)果基礎(chǔ)上，得到的平均數(shù)據(jù)如表1所示。

表1 改進(jìn)算法加入變異和啟發(fā)式選擇機(jī)制的優(yōu)化結(jié)果

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

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

表2 MFSHACO算法解決eil51實(shí)例不同參數(shù)下的實(shí)驗結(jié)果

4.2 MFSHACO算法收斂性分析

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

圖1 MFSHACO算法在eil51實(shí)例上的收斂性

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

5 結(jié)束語

針對傳統(tǒng)蟻群算法初始較好解產(chǎn)生困難、計算搜索時間長、收斂速度慢、易于停滯等特點(diǎn)，本文提出了MFSHACO算法，該算法采用節(jié)點(diǎn)之間的緊鄰信息，動態(tài)進(jìn)行啟發(fā)式的選擇，能夠合理有效地產(chǎn)生較好的初始解，避免了大范圍搜索，并且能夠極大提高算法的計算速度。同時充分采用局部和全局變異策略，指導(dǎo)算法加速收斂，使得變異結(jié)果的質(zhì)量有較大改善。實(shí)驗數(shù)據(jù)表明，MFSHACO算法不僅能夠獲得高質(zhì)量優(yōu)化解，而且收斂速度大幅提升，整體運(yùn)行時間大幅下降，特別隨著問題規(guī)模n的增大，有很強(qiáng)的實(shí)用意義。本文各種參數(shù)的選擇主要依靠經(jīng)驗，后期將針對不同的變異策略和組合參數(shù)之間的關(guān)系進(jì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]常智勇，楊建新，趙杰，等.基于自適應(yīng)蟻群算法的工藝路線優(yōu)化[J].機(jī)械工程學(xué)報，2012，48（9）：163-169.

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

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

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

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

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

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

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

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

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

[12]張曉偉，李笑雪.新型的雙種群蟻群算法[J].計算機(jī)工程與應(yīng)用，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

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

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

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—），女，高級實(shí)驗師，主要研究方向：計算機(jī)應(yīng)用，智能控制與優(yōu)化；席金菊（1965—），女，教授，主要研究方向：計算機(jī)應(yīng)用。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