陳 芳

（大同市安福儀器儀表有限責(zé)任公司，山西大同037003）

多元組合ACS-TSP系統(tǒng)

陳 芳

（大同市安福儀器儀表有限責(zé)任公司，山西大同037003）

文章提出了用多算法結(jié)合蟻?zhàn)逑到y(tǒng)（ACS）求解旅行商問(wèn)題（TSP）的方法，介紹了在ACS-TSP問(wèn)題上的遺傳算法，目的是為了尋找處理旅行商早期停滯現(xiàn)象的解空間。此外，還提出了一種新的最小生成樹(shù)（MST）算法，結(jié)合最近鄰（NN）來(lái)創(chuàng)建一個(gè)初始架構(gòu)，以便又快又好地解決旅行商問(wèn)題。

ACS-TSP；遺傳算法；最小生成樹(shù)；最近鄰

螞蟻系統(tǒng)（AS）[1-2]也稱為蟻?zhàn)逑到y(tǒng)（ACS）[3]，是由Dorigo和他的同事首先提出的，后來(lái)經(jīng)過(guò)不斷地完善而發(fā)展起來(lái)的一種蟻群算法。蟻?zhàn)逑到y(tǒng)已經(jīng)被成功地應(yīng)用于許多領(lǐng)域，如旅行商問(wèn)題（TSP）[4]、二次分配問(wèn)題[5]、數(shù)據(jù)挖掘[6]、空間規(guī)劃[7]、作業(yè)車間調(diào)度和其他方面[8-9]。

ACS-TSP算法與遺傳算法（GA）、模擬退火（SA）和進(jìn)化規(guī)劃（EP）[10]等算法相比較能夠產(chǎn)生更好的效果，但仍然需要解決兩類問(wèn)題，即早期停滯和收斂時(shí)間。早期停滯是一種現(xiàn)象，當(dāng)信息素幾個(gè)弧的強(qiáng)度變的很高時(shí)，螞蟻將一次又一次地構(gòu)建相應(yīng)的路線，這就使得在選擇最優(yōu)路徑時(shí)變得不可能。本文的目的是結(jié)合其他算法解決上述問(wèn)題。

1 基于蟻?zhàn)逑到y(tǒng)的TSP問(wèn)題

蟻?zhàn)逑到y(tǒng)是在螞蟻行為尤其是覓食行為的啟發(fā)下產(chǎn)生的，自然界中的螞蟻通過(guò)信息素來(lái)存放信息，以實(shí)現(xiàn)互相溝通。螞蟻的選擇傾向于以正相關(guān)的強(qiáng)度來(lái)發(fā)現(xiàn)線索的特定路徑。如果其他螞蟻沒(méi)有獲得更多的信息素，那么信息素就會(huì)消失，即信息失去強(qiáng)度。相反，如果許多螞蟻選擇某一路徑下的信息素，會(huì)使得路徑的信息強(qiáng)度增大，從而吸引越來(lái)越多的螞蟻。

應(yīng)用ACS解決TSP的工作原理是：M螞蟻?zhàn)畛醣浑S機(jī)定位在n個(gè)城市，每只螞蟻根據(jù)轉(zhuǎn)移概率規(guī)則來(lái)選擇城市，從而制定完整的路線。在構(gòu)建路線的同時(shí)，螞蟻通過(guò)應(yīng)用本地更新規(guī)則來(lái)改變信息素的數(shù)量，當(dāng)所有螞蟻構(gòu)建完成了他們的路線時(shí)，全局性的更新將被應(yīng)用。ACS算法框架為：

1.1 狀態(tài)轉(zhuǎn)換規(guī)則

k螞蟻的任務(wù)是構(gòu)建一條訪問(wèn)所有城市，然后回到起點(diǎn)的路線。與k相關(guān)的還有待參觀的城市Jk(r)，其中，r是螞蟻k目前所處的城市。螞蟻k從城市r到城市s所使用的規(guī)則稱為偽隨機(jī)比例選擇規(guī)則（或稱狀態(tài)轉(zhuǎn)換規(guī)則）：

其中，τ(r,u)代表邊緣信息素的量；η(r,u)是城市r和城市u之間距離倒數(shù)的啟發(fā)式函數(shù)；β是用來(lái)衡量信息素路徑相對(duì)重要性的參數(shù)；q表示在區(qū)間[0,1]上隨機(jī)選擇的概率；q0是一個(gè)參數(shù)，0≤q0≤1；s是隨機(jī)變量，表明了螞蟻從城市r選擇去城市s的可能路徑。

s由下述方程給出：

1.2 局部更新規(guī)則

構(gòu)建一個(gè)解決TSP的方案，螞蟻通過(guò)應(yīng)用下面的本地更新規(guī)則來(lái)訪問(wèn)邊緣路徑和改變信息素路徑的數(shù)量：

其中，ρ表示信息素衰減的參數(shù)，0＜ρ＜1；Δτ(r,s)代表初始信息素的水平，Δτ(r,s)＝(n*Lnn)-1；Lnn代表由最近鄰啟發(fā)式產(chǎn)生的路徑長(zhǎng)度；n代表節(jié)點(diǎn)數(shù)。

1.3 全局更新規(guī)則

全局更新是在所有螞蟻已經(jīng)完成了他們的路徑之后被執(zhí)行的，信息素的數(shù)量是通過(guò)應(yīng)用下面的全局更新規(guī)則來(lái)更新的：

其中，α代表信息素衰減參數(shù)，0＜α＜1；Lgb是最優(yōu)路徑長(zhǎng)度。

2 解決方案

本文運(yùn)用遺傳算法來(lái)尋找解空間，以避免出現(xiàn)早期停滯現(xiàn)象，從而獲得解決TSP問(wèn)題的全局最優(yōu)解。此外，應(yīng)用最小生成樹(shù)（MST）構(gòu)建初始路徑來(lái)提高算法的效率。

2.1 遺傳算法

在每次循環(huán)中，通過(guò)讓最好的螞蟻去更新路徑來(lái)提高ACS的性能。但太早排除其他潛在的螞蟻會(huì)導(dǎo)致早期停滯現(xiàn)象，所以在解決ACS問(wèn)題上引入遺傳算法來(lái)處理早期停滯現(xiàn)象。

遺傳算法（GA）[11]是一種基于遺傳和自然選擇原則的優(yōu)化和搜索技術(shù)，由John Holland等人開(kāi)發(fā)。遺傳算法是在基因概念的基礎(chǔ)上衍生出來(lái)的，其中包括三個(gè)重要的環(huán)節(jié)，即復(fù)制、交叉和變異。這些基因操作只使用原始操作，如復(fù)制、交換和翻轉(zhuǎn)基因。利用遺傳算法求解最優(yōu)化問(wèn)題的優(yōu)點(diǎn)：（1）遺傳算法包括開(kāi)發(fā)以及在操作過(guò)程中的探索，這與優(yōu)化的方法（如梯度下降法）不同；（2）通過(guò)利用遺傳算法，不僅能夠解決線性與非線性規(guī)劃，還能解決整數(shù)規(guī)劃。

在全局更新階段，采用了兩相策略來(lái)提高尋找解空間的能力。在第一階段，當(dāng)所有螞蟻完成了他們的路線后，在所有的螞蟻路徑中選擇三條有代表性的路徑：一是最優(yōu)路徑，二是中等路徑，三是最劣路徑。對(duì)于這三條路徑，應(yīng)用遺傳算法交叉算子的后代方法。在第二階段，應(yīng)用最優(yōu)路徑和GA所構(gòu)建的三條其他路徑來(lái)解決全局邊緣信息素的更新問(wèn)題。全局更新規(guī)則為：

利用上述方法，可以改進(jìn)ACS-TSP算法框架為：

2.2 旅行商問(wèn)題的構(gòu)建方法

最近鄰（NN）方法通常是用來(lái)構(gòu)建一個(gè)旅行商路線，但這樣的方法可能會(huì)產(chǎn)生嚴(yán)重的錯(cuò)誤。最小生成樹(shù)（MST）的問(wèn)題是找到一個(gè)最小總成本的生成樹(shù)圖，可以由krushal和Prim算法驗(yàn)證，一個(gè)最優(yōu)路徑通常包含70～80%的邊緣最小生成樹(shù)。

基于上述現(xiàn)象，采用一種新的與NN相結(jié)合的MST方法來(lái)構(gòu)建一個(gè)初始路徑。根據(jù)具體的TSP問(wèn)題，構(gòu)建相應(yīng)的MST樹(shù)，形成屬于MST樹(shù)的候選邊緣集。因?yàn)镸ST是一個(gè)n樹(shù)，其節(jié)點(diǎn)的自由度大于2，選擇最長(zhǎng)的路徑，把從后代節(jié)點(diǎn)到祖先節(jié)點(diǎn)作為起始路線。然后，把初始路徑的結(jié)束點(diǎn)作為新的起始節(jié)點(diǎn)。選擇下一個(gè)節(jié)點(diǎn)方法為：（1）存在一個(gè)沒(méi)有被候選邊緣集訪問(wèn)的邊緣，該邊緣連接新的起始節(jié)點(diǎn)。（2）如果上述方法不成功，則運(yùn)用NN方法選擇最近的沒(méi)有被訪問(wèn)的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)。

在初始階段，利用上面提到的方法，增加少量的信息素以便螞蟻尋找路徑，從而減少收斂時(shí)間，最初的路徑構(gòu)建程序框架如下：

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證上述方法的合理性，在計(jì)算機(jī)上進(jìn)行模擬。在實(shí)驗(yàn)中設(shè)置如下參數(shù)：q0=0.9，ρ=0.5，α=1，β=2，計(jì)算機(jī)模擬運(yùn)行=50。此外，在實(shí)驗(yàn)中使用了20只螞蟻，與之前Dorigo提出的ACSTSP方法相比較，試驗(yàn)結(jié)果表明：a280、att532、rat783、u1060、fl1400、rl1889是基準(zhǔn)問(wèn)題。圖1顯示的是ACS-TSP路徑長(zhǎng)度和使用rl1889基準(zhǔn)問(wèn)題的對(duì)比情況。ACS+TSP+ls與Improved+ls計(jì)算路徑長(zhǎng)度的對(duì)比結(jié)果，見(jiàn)表1。結(jié)果表明，利用TSP與遺傳算法以及最小生成樹(shù)相結(jié)合的方法，較好地解決了全局最優(yōu)解或接近全局最優(yōu)解的問(wèn)題。

圖1 ACS-TSP路徑長(zhǎng)度和使用rl1889基準(zhǔn)問(wèn)題的對(duì)比

表1 ACS+TSP+ls與Improved+ls計(jì)算路徑長(zhǎng)度的對(duì)比

4 結(jié)語(yǔ)

多元組合ACS-TSP系統(tǒng)是一種新的可以迅速提高初始路徑的戰(zhàn)略方法，對(duì)大型TSPs決策也能勝任。

[1]Colori A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[A].Varela F,Bourgine P.Proceedings of the first Europe an conference on artificial life[C].Paris:Elsevier Publishing,1991:134-142.

[2]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.

[3]Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,l(1):53-66.

[4]Tsai Cheng-fa,Tsai Chun-wei,Tseng Ching-chang.A new Hybrid heuristic approach for solving large traveling salesman problem[J].Information Sciences,2004,166(1-4):67-81.

[5]Maniezzo V,Colorni A.The ant system applied to the quadratic assignment problem[J].IEEE Transactions on Knowledge and Data Engineering,1999,11(5):769-778.

[6]Parpinelli R S,Lopes H S,Freitas A A.Data mining with an ant colony optimization algorithm[J].IEEE Transactions on Evolutionary Computation,2002,6(4):321-328.

[7]Bland J A.Space-planning by ant colony optimization[J].International Journal of Computer Applications in Technology,1999,12(6):320-328.

[8]Blum Christian.Ant colony optimization:introduction and recent trends[J].Physics of Life Reviews,2005,2(4):353-373.

[9]Dorigo M,Caro G D,Gambardella L M.Ant algorithms for discrete optimization[J].Artificial Life,1999,5(2):137-172.

[10]Bonabeau E,Dorigo M,Theraulaz G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999.

[11]Holland J.Adaptation in Natural and Artificial Systems[M].Ann Arbor:University of Michigan Press,1975.

A Multi-Metaheuristic Combined ACS-TSP System

CHEN Fang
（Datong Anfu Instrument and Meter Limited Liability Company,Datong Shanxi,037003)

This paper presents a Multi-Metaheuristic combined Ant Colony System(ACS)-Travelling Salesman Problem(TSP)al?gorithm for solving the TSP.We introduce genetic algorithm in ACS-TSP to search solutions space for dealing with the early stagnation problem of the traveling salesman problem.Moreover,we present a new strategy of Minimum Spanning Tree(MST)coupled with Nearest Neighbor(NN)to construct a initial tour for improving TSP thus obtaining good solutions quickly.According to our simulation results,the new algorithm can provide a significant improvement for obtaining a global optimum solution or a near global optimum solution in large TSPs.

ACS-TSP;genetic algorithm;minimum spanning tree;nearest neighbor

TP301

A

1674-0874(2015)05-0069-04

2015-09-20

陳芳（1991-），女，山西大同人，助理工程師，研究方向：企業(yè)信息化軟件開(kāi)發(fā)與應(yīng)用。

〔責(zé)任編輯 王東〕