基于吸引場的蟻群算法在TSP中的應(yīng)用

王 雷，李 明，劉志虎

（安徽工程大學(xué)機械與汽車工程學(xué)院，安徽蕪湖241000）

基于吸引場的蟻群算法在TSP中的應(yīng)用

王 雷，李 明，劉志虎

（安徽工程大學(xué)機械與汽車工程學(xué)院，安徽蕪湖241000）

針對傳統(tǒng)蟻群算法容易陷入局部最優(yōu)解等缺陷，提出了一種基于吸引場的改進的蟻群算法.首先，詳細分析了基于信息素的吸引場原理，在此基礎(chǔ)上建立了基于信息素的吸引場模型.其次，設(shè)計了吸引場因子，給出了信息素更新策略，使相距較近的螞蟻之間能更好地進行協(xié)作.最后，針對標(biāo)準(zhǔn)的30個城市的旅行商問題，使用所提出的算法與基本蟻群算法、其他改進的蟻群算法進行優(yōu)化分析，并進行了結(jié)果對比.結(jié)果表明：所提出的蟻群算法可以獲得TSP問題的最優(yōu)解423.74，Oliver30問題計算結(jié)果最優(yōu)值為423.74，平均值為423.96，具有較好的搜索全局最優(yōu)解的能力.

路徑規(guī)劃；旅行商問題；蟻群算法；信息素；吸引場

仿生學(xué)家的研究結(jié)果表明，螞蟻個體之間可以通過分泌信息素（pheromone）來傳遞信息，螞蟻在行動的過程中會在經(jīng)過的路徑上留下信息素，后面的螞蟻通過感知這種物質(zhì)的濃度來選擇自己的路徑.因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：在較短的路徑上留下的信息素濃度較大，因而螞蟻總是可以找到更短的路徑取食.

受自然界中真實蟻群行為的啟發(fā)，意大利學(xué)者Macro Dorigo提出了蟻群算法（ant colony optimization，ACO）［1］，并將其應(yīng)用于各種優(yōu)化問題的求解，取得了不錯的效果［2-5］.蟻群算法主要是通過螞蟻群體之間的信息傳遞而達到尋優(yōu)的目的，其優(yōu)點：①具有正反饋機制，通過信息素的不斷更新達到查詢最優(yōu)路徑；②通用型隨機優(yōu)化方法，它不是對實際螞蟻的一種簡單模擬，而是更多地融入了人的智能；③一種全局優(yōu)化的方法，不僅求解單目標(biāo)優(yōu)化問題，而且可求解多目標(biāo)優(yōu)化問題.但是ACO也具有速度慢、易陷入局部最優(yōu)等缺點.為了克服以上存在的問題，許多學(xué)者對基本蟻群算法進行了多方面的改進［6-8］.這些改進方法對一些特定問題的求解已取得了一些效果，但整體而言這些工作還不夠完善，仍然需要進一步的研究.文中在分析蟻群算法模型缺陷的基礎(chǔ)上，提出一種基于吸引場的蟻群算法（attractive field based ant colony optimization，AFACO）.

1 求解旅行商問題的基本蟻群算法

1.1 旅行商問題路徑規(guī)劃描述

旅行商問題（travelling salesman problem，TSP）的路徑規(guī)劃描述可以描述如下［9］：已知n個城市v=｛v1，v2，…，vn｝，以及任意2個城市之間的距離dij=｛vi，vj｝，求一條經(jīng)過v中所有城市一次且僅一次的閉合路徑｛vx1，vx2，…，vxn｝，使得總的行程最小，即

1.2 基本蟻群算法描述

蟻群算法求解TSP路徑規(guī)劃可以簡單表述如下：初始化，將m只螞蟻隨機放在n個網(wǎng)絡(luò)城市節(jié)點上，節(jié)點間的每一條邊都有初始化信息素тij（0），tabuk（s）表示螞蟻k的禁忌表，該表的第1個元素設(shè)置為其初始節(jié)點，它隨著螞蟻的行走動態(tài)調(diào)整；然后每只螞蟻依據(jù)概率函數(shù)（見式（2））選擇路線，即選擇下一步要去的城市節(jié)點，該節(jié)點滿足j∈allowedk，allowedk是第k只螞蟻下一步可以選擇的節(jié)點集，即為

式中：тij（t）為路徑i，j上信息素的強度；ηij（t）為節(jié)點間距離因子，通常取值為1/dij，其中dij表示節(jié)點i，j之間的距離.信息啟發(fā)式因子α體現(xiàn)信息素在選擇概率上的作用（α≥0），期望值啟發(fā)式因子β體現(xiàn)路徑長度在選擇概率上的作用（β≥0）.蟻群算法的全局尋優(yōu)性能，首先要求蟻群的搜索過程必須有很強的隨機性；而蟻群算法的快速收斂性能，又要求蟻群的搜索過程必須要有較高的確定性.前者受期望值啟發(fā)式因子β影響，后者受信息啟發(fā)式因子α的影響.

當(dāng)所有螞蟻都完成一次求解，則完成一次循環(huán).將本次循環(huán)找到的最短路徑的解作為當(dāng)前最優(yōu)解，并按（3）式更新信息素的強度.

式中ρ為一個取值范圍在0到1之間的常數(shù)，表示殘留信息素的相對重要程度，而（1-ρ）則表示信息素的揮發(fā)，是第k只螞蟻在時刻t到t+1之間，在路徑（i，j）上增加的信息素濃度.

式中：Q為一個常量，用來表示每只螞蟻所釋放的信息素總量；Lk為第k只螞蟻在本次循環(huán)中所走路徑的總長度.在ant-quantity模型中：

式中dij為第k只螞蟻在節(jié)點i和j之間所走的長度.在ant-density模型中：

它們的區(qū)別在于前者利用的是全局信息，而后2種模型中利用的是局部信息.在用傳統(tǒng)的蟻群算法中，經(jīng)過大量試驗總結(jié)研究，采用式（4）性能較好，所以ant-cycle模型是最優(yōu)的.

在以上算法中，參數(shù)m，ρ，Q，α和β的最佳組合可以由試驗而確定，停止條件可以用固定進化代數(shù)或者當(dāng)進化趨勢不明顯時便停止計算.

1.3 基本蟻群算法分析

蟻群算法本質(zhì)上仍是一種隨機搜索算法，它是通過候選解組成的群體的進化來尋求最優(yōu)解.算法由許多螞蟻共同完成，每只螞蟻在候選解的空間中獨立地搜索解，并在所尋得的解上留下一定的信息素.解的性能越好，螞蟻留在其上的信息素就越多，信息素越多的解被選擇的可能性也越大.在算法的最初階段所有解上的信息素是相同的，隨著算法的推進，較優(yōu)解上的信息素將逐漸增多，算法漸漸趨于收斂［10］.但是，該算法存在一些缺陷，主要歸納為以下2點［11］：①與其他啟發(fā)式算法相比，它通常需要較長的搜索時間，各種蟻群算法的復(fù)雜度可以很好地反映著一點；②蟻群算法容易出現(xiàn)停滯現(xiàn)象.因為在路徑規(guī)劃的初始時刻，各節(jié)點或者路徑上的信息素的濃度相同，然后通過螞蟻的路徑搜索，不斷改變各節(jié)點或者路徑上的信息素的濃度.但由于螞蟻之間的協(xié)作不足和不夠及時，當(dāng)搜索進行到一定程度后，所有個體發(fā)現(xiàn)的解完全一致，不能對解空間進一步進行搜索，不利于得到全局最優(yōu)的解.另外，路徑長短的不同將導(dǎo)致路徑上留下的信息素的量的不同，此將對后續(xù)的螞蟻產(chǎn)生一定的影響，基于此文中提出了基于吸引場的蟻群算法，并將之應(yīng)用于路徑規(guī)劃求解.

2 基于吸引場的蟻群算法

2.1 基于信息素的吸引場原理及吸引場模型

基于信息素的吸引場原理源于螞蟻的覓食思想，圖1為原理示意圖.

圖1 基于信息素的吸引場的原理

在圖1中，假設(shè)螞蟻k欲從s到e，其中節(jié)點a和b之間的距離dab為一距離很短的路徑（dab=3），而節(jié)點c和d之間的距離dcd比較大（dcd=6）.假設(shè)a，b，c，d和e節(jié)點上的信息素大小都為Q=6，同時在此以節(jié)點上的信息素量來取代路徑上的信息素的量，如用節(jié)點a和c上的信息素分別代替路徑sa和sc上遺留信息素的量.由于sc比sa短，螞蟻k將以更大的概率選擇c為下一步要到達的位置.但是由于以節(jié)點b和d為中心的信息素的濃度將向周圍進行擴散，以便對周圍路徑具有一定的吸引場（吸引力），吸引力的大小假設(shè)與距離成反比.由于距離遠近的不同，節(jié)點a上的信息素的量（Q′=Q+Q/dab= 6+6/3=8）將大于節(jié)點c上的信息素的量（Q′= Q+Q/dcd=6+6/6=7），當(dāng)大到一定程度時，螞蟻k將以更大的概率選擇a節(jié)點為下一步要到達的位置，從而使螞蟻k選擇最短路徑s-a-b-e的干擾減小.

通過對圖1的分析可知，基于信息素的吸引場的強度隨著距離的增大而減小，近似服從一個正態(tài)分布，如圖2所示.

圖2 吸引場強度與距離之間的關(guān)系模型

圖2中橫坐標(biāo)x表示與產(chǎn)生信息素的信源之間的距離，縱坐標(biāo)y表示吸引場的強度.為了計算的方便，對圖2所示的吸引場模型進行了簡化，簡化結(jié)果為

式中Q為一常數(shù).

2.2 基于吸引場的蟻群算法

用蟻群算法求解路徑規(guī)劃，可以表示成圖3的形式.

圖3 基于蟻群算法的路徑規(guī)劃網(wǎng)絡(luò)節(jié)點優(yōu)化

圖3中橢圓表示第t次訪問對應(yīng)的備選節(jié)點集，實心圓表示備選路徑對應(yīng)節(jié)點，需要解決的問題是從各組備選節(jié)點集中選出一個訪問節(jié)點，使得所有選擇路徑最短.如果將每次訪問節(jié)點看成是螞蟻爬過的一個節(jié)點，則問題的求解過程就可以轉(zhuǎn)化為如何按照1，2，…，n的順序選擇一條路徑，使得螞蟻爬過這一條路徑所走過的總路徑最短.在圖3中，為了便于螞蟻搜索節(jié)點，將所有節(jié)點可以進行統(tǒng)一編號.

為了使所求解的問題適合基于吸引場的蟻群算法求解的需要，還需經(jīng)過適當(dāng)?shù)脑O(shè)計，由于應(yīng)用蟻群算法求解問題的關(guān)鍵是確定信息素的變化，為此采用以下信息素的更新策略：

式中：右邊的第1項表示螞蟻k每爬過一段路程，每選擇一個結(jié)點時，就在該段路程留下局部信息素；λk為吸引場因子；Q為常數(shù)，表示信息素的強度為該路程的長度，設(shè)i，j分別為該路程的起點與終點，計算式為

式中E為任務(wù)次序約束有向圖中的有向邊的集合.

式（8）中右邊的第2項表示下一個被選集合節(jié)點中的節(jié)點對該節(jié)點吸引力的大小.用allowedk（t）表示螞蟻k第t次允許爬行的節(jié)點，用數(shù)組tabuk記錄螞蟻k已經(jīng)爬過的節(jié)點，如allowedk（0）=｛1，2， 3｝，allowedk（1）=｛4，5，6｝，tabuk（0）=0，則計算式寫為

吸引場因子λ可以通過以下方式動態(tài)調(diào)整.首先，螞蟻所走路徑的平均長度為

Lk是螞蟻k在某一條路徑中所走的總長度，在更新信息素時，根據(jù)吸引場的原理對所走路徑小于ˉL的螞蟻賦予一個相對較大的吸引場因子，路徑越短賦予的吸引場因子越大.對于所走路徑大于或等于ˉL的螞蟻賦予一個相對小的吸引場因子.其中，吸引場因子λ按式（12）進行調(diào)整：

式中：δ為一個很小的正數(shù)；ξ為一個很大的正數(shù).由式（12）可見，Lk越接近最優(yōu)路徑的長度（Lmin），吸引場因子λ越接近1.上述算法中首先計算了每次尋優(yōu)以后所有螞蟻所走路徑的平均值，再根據(jù)個體螞蟻所走路徑與該平均值之間的差異來對信息素進行相應(yīng)地改變，這樣就可以增加解空間的多樣性，提高蟻群的全局搜索能力，避免出現(xiàn)局部收斂和早熟現(xiàn)象，同時也不會降低蟻群算法的搜索速度.仿真結(jié)果表明，改進后的蟻群算法具有更好的搜索最優(yōu)解的能力.

2.3 基于吸引場的蟻群算法步驟

基于信息素吸引場的蟻群算法的步驟可以描述如下：

1）初始化，初始化m，ρ，Q，α，β，δ和ξ等參數(shù).

2）將m只螞蟻隨機地放置在當(dāng)n個城市節(jié)點上，把第1個城市節(jié)點寫入禁忌表tabuk中，并設(shè)置k=1可訪問節(jié)點集allowed.

3）t=0，隨機選擇每只螞蟻的初始位置，螞蟻k開始爬行，螞蟻k根據(jù)狀態(tài)轉(zhuǎn)移概率公式（2）依次選擇下一個節(jié)點，假設(shè)為j，上一個位置假設(shè)為i，j∈allowedk（t），t←t+1.

4）將螞蟻移動到的新節(jié)點號加入tabuk中，得到該螞蟻的路徑規(guī)劃序列.

5）根據(jù)公式（8）-（12）進行信息素更新.

6）如果每只螞蟻都完成了一個完整的路徑，則轉(zhuǎn)向7），否則轉(zhuǎn)向3）.

7）如果進化代數(shù)大于或等于進化最大代數(shù)時，則轉(zhuǎn)向8），否則清空禁忌表tabuk并跳轉(zhuǎn)到2）開始新一輪的進化.

8）輸出進化結(jié)果，算法結(jié)束.

3 仿真試驗

為了驗證文中算法的實用性及有效性，進行了大量的仿真試驗.試驗環(huán)境如下：windows xp操作系統(tǒng)，英特爾賽揚M440 1.86 GHz的CPU，512 MB內(nèi)存，80 GB、5 400 r·min-1的硬盤SATA，程序開發(fā)軟件為Visual C++6.0.

為了驗證文中算法的有效性，對經(jīng)典的TSP路徑規(guī)劃進行了研究.算法中各項參數(shù)的取值α=1，β=2，δ=0.01，ξ=1 000，Q=100，ρ=0.9，m=30，N=1 000.圖4是對標(biāo)準(zhǔn)的30個城市的Oliver30問題的最終優(yōu)化結(jié)果，進化過程如圖5所示.

圖4 Oliver30問題的優(yōu)化結(jié)果

圖5 尋優(yōu)進化曲線

從圖5可以看出文中算法可以獲得TSP的最優(yōu)解（423.74）.因此，通過文中算法可以自適應(yīng)地尋找到最短的路徑，從而表明該算法的可行性.

表1給出了文中算法在Oliver30上的統(tǒng)計結(jié)果.

表1 Oliver30問題計算結(jié)果比較

本算法程序獨立重復(fù)運行20次，將求解的最優(yōu)解和平均解與其他算法的計算結(jié)果進行了對比.由表1可見，在Oliver30問題計算結(jié)果的最優(yōu)值中，文中算法計算得到的最優(yōu)路徑小于基本蟻群算法和蟻群-免疫混合算法［12］的最優(yōu)路徑長度，這說明文中改進的蟻群算法具有較好的搜索最優(yōu)解的能力.與思維進化算法［13］得到一樣的最優(yōu)值，但在平均值上文中算法計算的結(jié)果要優(yōu)于其他幾種算法，從而說明文中算法具有較好的穩(wěn)定性.

通過大量的仿真試驗發(fā)現(xiàn)，文中提出的基于吸引場的蟻群算法不但具有基本蟻群算法的分布式并行計算、正反饋機制和魯棒性強等特點，而且可以較好地克服基本蟻群算法在求解問題時出現(xiàn)的容易陷入局部最優(yōu)的缺陷，具有加強解得多樣性的能力，能夠提高算法的全局搜索能力.

4 結(jié) 論

1）分析了基于信息素的吸引場原理，給出了吸引場模型，進而提出了一種基于吸引場的自適應(yīng)蟻群算法.

2）給出了信息素的更新策略以及吸引場因子的動態(tài)調(diào)整策略；設(shè)計了基于吸引場的蟻群算法步驟.

3）TSP路徑規(guī)劃仿真試驗結(jié)果表明，所提出的蟻群算法可以獲得TSP的最優(yōu)解423.74，Oliver30問題計算結(jié)果最優(yōu)值為423.74，平均值為423.96，具有較好的搜索全局最優(yōu)解的能力.

（

）

［1］Liao T J，Stützle T，de Oca M A M，et al.A unified ant colony optimization algorithm for continuous optimization［J］.European Journal of Operational Research，2014，234（3）：597-609.

［2］Wu W H，Cheng SR，Wu CC，etal.Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations［J］.Journal of Intelligent Manufacturing，2012，23（5）：1985-1993.

［3］Wang Lei，Tang Dunbing，Gu Wenbin，et al.Pheromone-based coordination for manufacturing system control［J］.Journal of Intelligent Manufacturing，2012，23（3）：747-757.

［4］黃曉瑋，鄒小波，趙杰文，等.近紅外光譜結(jié)合蟻群算法檢測花茶花青素含量［J］.江蘇大學(xué)學(xué)報：自然科學(xué)版，2014，35（2）：165-170，188. Huang Xiaowei，Zou Xiaobo，Zhao Jiewen，et al.Measurement of anthocyanin in flowering tea using near infrared spectroscopy combined with ant colony optimization［J］.Journal of Jiangsu University：Natural Science Edition，2014，35（2）：165-170，188.（in Chinese）

［5］覃志東，侯 穎，肖芳雄.基于蟻群優(yōu)化算法的同構(gòu)多核任務(wù)分配與調(diào)度［J］.江蘇大學(xué)學(xué)報：自然科學(xué)版，2014，35（6）：679-684. Qin Zhidong，Hou Ying，Xiao Fangxiong.Task allocation and scheduling for homogeneous multi-core processors based on ant colony optimization［J］.Journal of Jiangsu University：Natural Science Edition，2014，35（6）：679-684.（in Chinese）

［6］Xiao Jing，Li Liangping.A hybrid ant colony optimization for continuous domains［J］.Expert Systems with Applications，2011，38（9）：11072-11077.

［7］Hannaneh Rashidi，Reza Zanjirani Farahani.A hybrid ant colony system for partially dynamic vehicle routing problem［J］.American Journal of Operational Research，2012，2（4）：31-44.

［8］Mavrovouniotis Michalis，Yang Shengxiang.A memetic ant colony optimization algorithm for the dynamic travelling salesman problem［J］.Soft Computing，2011，15（7）：1405-1425.

［9］張敬敏，馬 麗，李媛媛.求解TSP問題的改進混合蛙跳算法［J］.計算機工程與應(yīng)用，2012，48（11）：47-50. Zhang Jingmin，Ma Li，Li Yuanyuan.Improved shuffled frog-leaping algorithm for traveling salesman problem［J］.Computer Engineering and Applications，2012，48（11）：47-50.（in Chinese）

［10］黃國銳，曹先彬，王煦法.基于信息素擴散的蟻群算法［J］.電子學(xué)報，2004，32（5）：865-868. Huang Guorui，Cao Xianbin，Wang Xufa.An ant colony optimization algorithm based on pheromone diffusion［J］.ACTA Electronica Sinica，2004，32（5）：865-868.（in Chinese）

［11］高世偉，郭 雷，杜亞琴，等.一種基于動態(tài)加權(quán)規(guī)則的自適應(yīng)蟻群算法［J］.計算機應(yīng)用，2007，27（7）：1741-1743. Gao Shiwei，Guo Lei，Du Yaqin，et al.Adaptive ant colony algorithm based on dynamic weighted rule［J］. Computer Applications，2007，27（7）：1741-1743.（in Chinese）

［12］江新姿，湯可宗，高 尚.蟻群算法與免疫算法的混合算法［J］.科學(xué)技術(shù)與工程，2008，8（5）：1327-1330. Jiang Xinzi，Tang Kezong，Gao Shang.Hybrid algorithm combining ant colony optimization algorithm with immune algorithm［J］.Science Technology and Engineering，2008，8（5）：1327-1330.（in Chinese）

［13］查 凱，曾建潮.求解TSP問題的思維進化算法［J］.計算機工程與應(yīng)用，2002，38（4）：102-104. Zha Kai，Zeng Jianchao.Solving TSP with mind evolutionary computation［J］.Computer Engineering and Applications，2002，38（4）：102-104.（in Chinese）

（責(zé)任編輯 梁家峰）

Application of an ant colony optimization based on attractive field inTSP

Wang Lei，Li Ming，Liu Zhihu
（School of Mechanical and Automotive Engineering，Anhui Polytechnic University，Wuhu，Anhui241000，China）

To overcome the default of local optimal solution in the traditional ant colony algorithm，a modified ant colony optimization（AFACO）was proposed based on attractive field.The principle of attraction field based on pheromone was analyzed in detail to establish the attractive field model.The attractive field factor based on pheromone was designed，and the pheromone updating strategy was provided to improve the collaboration among ants nearby.For the standard 30 city traveling salesman problem，the optimization results from the proposed algorithm were compared with those from basic ant colony algorithm and some other improved ant colony.The results show that the optimal solution of TSP problem is 423.74，while the optimal and the mean solution of Oliver30 are 423.74 and 423.96，respectively，which shows the improved ant colony algorithm has good ability for searching the global optimal solution.

path planning；travelling salesman problem；ant colony optimization；pheromone；attractive field

TP183

A

1671-7775（2015）05-0573-05

王 雷，李 明，劉志虎.基于吸引場的蟻群算法在TSP中的應(yīng)用［J］.江蘇大學(xué)學(xué)報：自然科學(xué)版，2015，36（5）：573-577，582.

10.3969/j.issn.1671-7775.2015.05.014

2014-12-01

國家自然科學(xué)基金資助項目（51305001，71171002）；安徽省自然科學(xué)基金資助項目（1308085ME65）；安徽省高等教育提升計劃省級自然科學(xué)研究項目（TSKJ2014B12）

王 雷（1982—），男，安徽亳州人，副教授，博士（wangdalei2000@126.com），主要從事數(shù)字化設(shè)計與智能制造研究.

李 明（1986—），男，安徽宿州人，碩士研究生（1039518062@qq.com），主要從事機器人路徑規(guī)劃研究.