求解最小比率旅行商問題的混合行為蟻群算法

倪郁東，趙　群，沈吟東，張玉潔（.合肥工業(yè)大學數(shù)學學院，安徽合肥　30009；.華中科技大學自動化學院，湖北武漢　430074）

?

求解最小比率旅行商問題的混合行為蟻群算法

倪郁東1，趙群1，沈吟東2，張玉潔1
（1.合肥工業(yè)大學數(shù)學學院，安徽合肥230009；2.華中科技大學自動化學院，湖北武漢430074）

摘要：為了快速并且有效地求解最小比率旅行商問題，文章提出了一種混合行為蟻群算法。通過對蟻群算法中轉(zhuǎn)移概率以及信息素更新策略加以改進，使螞蟻能夠隨機性地選擇自己的行為規(guī)范，將蟻群進一步智能化；為防止陷入局部最優(yōu)，算法中設計了交換策略與災變策略。仿真實驗結果表明，改進后的算法能夠有效求解最小比率旅行商問題。

關鍵詞：最小比率旅行商問題；蟻群算法；混合行為；優(yōu)化

沈吟東（1965-），女，安徽合肥人，博士，華中科技大學教授，博士生導師.

旅行商問題（traveling salesman problem，TSP）是一類典型的組合優(yōu)化問題，同時也是NP-Hard問題。通?？珊唵蚊枋鰹椋河幸宦眯猩逃巴鵱個城市推銷商品，從某一城市出發(fā)，經(jīng)過各個城市一次后返回出發(fā)城市，問該旅行商應如何選擇出行路線，使得總路程最短。最小比率旅行商問題（MRTSP）是從經(jīng)典TSP中引申出來的一個變形問題，它在原TSP的基礎上增加了收益假定，即旅行商從城市i走到城市j能獲得一定收益pij，現(xiàn)在的問題變成：確定一條路線，使得總路程與總收益的比最小。這種思想類似于經(jīng)濟學中的費用效益，既考慮到了成本同時又考慮到了收益。相比于TSP中只考慮路程，研究MRTSP往往更具實際意義。

與標準TSP不同，MRTSP的目標函數(shù)是非線性的，這使得問題的求解變得更加困難。目前求解這類問題的方法主要有蟻群優(yōu)化算法［1］、模擬退火算法［2］、競爭決策算法［3］以及大洪水算法［4］。蟻群算法是一類群體優(yōu)化算法，雖然具有很強的全局搜索能力，但是算法的運行時間以及解的質(zhì)量很難讓人滿意。模擬退火算法、競爭決策算法以及大洪水算法屬于單點搜索優(yōu)化算法，極易陷入局部最優(yōu)。

本文提出的混合行為蟻群算法中，螞蟻擁有自己的行為，能夠按照自己的方式選擇下一個城市。在設定信息素的更新策略時，采用了自適應蟻群算法［5］和最大-最小蟻群算法［6］各自的優(yōu)點并將其混合使用。此外，為防止陷入局部最優(yōu)，算法中加入了交換策略和災變策略，最后經(jīng)過算例測試對本文算法進行了驗證。

1　問題模型

G（V，E）為給定的賦權完全圖，V＝（1，2，…，n）表示頂點集，E＝{（i，j）| i，j∈V且i≠j}為邊集。距離矩陣D＝［dij］n×n，當i≠j時，dij＝dji；當i ＝j時，dij＝＋∞。收益矩陣P＝［pij］n×n，當i≠j時，pij＝pji；當i＝j時，pij＝0。xij＝1表示邊（i，j）在回路上，否則xij＝0。

MRTSP的數(shù)學模型描述如下：

其中，|S|表示集合S中含圖G的頂點個數(shù)。前2條約束條件意味著每個頂點只有一條邊進和一條邊出，第3條約束條件說明沒有產(chǎn)生子回路解。因此，同時滿足以上3個約束條件的解能構成一條Hamilton回路。

2　混合行為蟻群算法

目前，混合行為蟻群算法已在求解車輛路徑問題［7］、0-1背包問題［8］等一些領域上取得了良好的效果，能否適用于求解MRTSP是本文研究的重點。與經(jīng)典TSP不同，在求解MRTSP時，啟發(fā)式因子可以設定為ηij＝pij/dij。啟發(fā)式因子的作用在于幫助螞蟻以貪婪的方式選擇那些收益更大、路程更短的城市。

2.1轉(zhuǎn)移概率的改進

蟻群算法中，螞蟻在經(jīng)過的路徑上會留下信息素，而信息素濃度的大小未必能反映出最優(yōu)路徑的方向，而且可能會使較差解所在路徑上的信息素濃度得到不應有的加強，干擾了后續(xù)螞蟻的尋優(yōu)。因此，本文采用隨機性選擇的方式來改進轉(zhuǎn)移概率，首先給出以下5個規(guī)則。

規(guī)則1螞蟻k以貪婪的方式選擇下一個要到達的城市j：

規(guī)則2選擇方式只與路徑上的信息素濃度有關：

規(guī)則3采用ant-system中的轉(zhuǎn)移概率：

規(guī)則4以螞蟻自適應系統(tǒng)中的轉(zhuǎn)移概率去選擇下一個要到達的城市j：

規(guī)則5隨機從allowedk中選擇一個城市作為下一個要訪問的城市。

螞蟻k在進行下一個城市的選擇時，從以上5個規(guī)則中隨機選擇一個作為自己的轉(zhuǎn)移概率。

擁有混合行為的蟻群在搜索的過程中具有極強的隨機性，當算法陷入局部最優(yōu)時，仍有可能從局部最優(yōu)中跳出，避免“早熟”現(xiàn)象的發(fā)生。

2.2信息素更新策略

在ant cycle system中，信息素更新策略為：

其中，ρ為信息素保留系數(shù)，取值在0～1之間；M為螞蟻的個數(shù)；Q為螞蟻在一個周期中攜帶的信息素量，通常為大于0的常數(shù)；Lk為螞蟻k所走的路徑；f（Lk）為螞蟻k所走路徑的總長度。

當問題的規(guī)模較大時，由于揮發(fā)系數(shù)（1-ρ）的存在，一些未被搜索到的路徑或者很少被搜索到的路徑上的信息素會一直減少甚至接近于0，從而降低了算法的搜索能力。另外，ρ過小會導致之前被搜索到的路徑有更大的可能性會被再次搜索到，過大則會使算法的收斂速度降低。這里采用自適應改變ρ的值來解決以上問題，即ρ的初始值ρ（0）＝1，當算法求得的最優(yōu)值在多次循環(huán)內(nèi)沒有變化時，ρ（t）改寫為：

其中，ρmin為ρ的最小值。

2.3交換策略

在局部搜索算法中，2-opt是一類能夠有效解決組合優(yōu)化問題的方法。當用于解決MRTSP問題時，其基本原理為：對目前產(chǎn)生的最優(yōu)解，隨機交換2個城市點的位置，交換之后再將2個城市之間的路徑反向。比如，對于n個城市的MRTSP問題，若目前的最優(yōu)解為j1—j2—…—jn-1—jn—j1，其中j1，j2，…，jn為12，…，n的一個排列組合。隨機交換2個城市點的位置，不妨設為ji和jk，則交換后的解為j1—j2…ji-1—jk-jk-1…—ji—jk＋1…jn—j1。若實行2-opt交換能夠使目標函數(shù)變小，則進行交換，否則保持原最優(yōu)路徑不變。

2.4災變策略

蟻群算法在擁有較快搜索速度的同時，也容易陷入局部最優(yōu)。為此，考慮螞蟻搜索到食物后，如果在搜索食物的路上遇到障礙，比如自然災害，螞蟻依然能夠通過更換路徑找到食物。因此，通過引入災變算子來解決算法的“早熟”問題。

災變算子的設計方法與遺傳算法中的變異類似。當多次得到的是相同的結果、算法傾向于陷入局部最優(yōu)時，引入災變。在局部最優(yōu)路徑上選擇一段或者若干段，讓這些路徑上的信息素大幅減少。于是螞蟻在下次搜索的過程中，有更大概率放棄該段路徑轉(zhuǎn)而去尋找更好的路徑。在發(fā)生災變路徑的選擇上，與遺傳算法類似，采用小隨機概率來決定，因為如果發(fā)生災變的路徑過多，可能會導致螞蟻的搜索過程往壞的方向發(fā)展。

2.5算法流程

（1）參數(shù)初始化。每條路徑上的信息素τij（0）＝c，c為常數(shù)。迭代計數(shù)器N＝0，最大迭代次數(shù)Nmax＝max；

（2）將M只螞蟻隨機放到n個城市中，為每只螞蟻建立禁忌表并把它們當前所在的第1個城市記錄在禁忌表中。

（3）螞蟻從所在的第一個城市出發(fā)，依照2.1中的轉(zhuǎn)移概率選擇下一個訪問的城市并將該城市記錄在對應的禁忌表中。

（4）重復步驟（3），直至訪問完所有城市，這樣就形成了M條閉合的回路，即L1，L2，…，LM。

（5）分別計算L1，L2，…，LM對應的目標函數(shù)值f（L1），f（L2），…，f（LM）。將最小目標函數(shù)值所對應的路徑實施n次2-opt交換，保存此時的最優(yōu)路徑Llocal。

（6）按照2.2中的策略對路徑上的信息素進行更新。更新完成后，采用MMAS算法與信息素平滑的思想，當τij＞τmax時，置τij＝τmax；當τij＜τmin時，置τij＝（τmax＋τmin）/2，便于螞蟻發(fā)現(xiàn)新的路線。τmax＝Q/f（Llocal），τmin＝τmax/2M。

（7）判斷是否連續(xù)m次迭代得到的是相同的最優(yōu)路徑。若是則以概率P對Llocal上的路徑實行災變策略，被災變所影響的路徑上的信息素為τmin。m＝Nmax/10，P＝0.1。

（8）比較本次迭代的最優(yōu)路徑Llocal與全局最優(yōu)路徑Lglobal，若f（Llocal）＜f（Lglobal），置Lglobal＝ Llocal。

（9）N＝N＋1，判斷N＜Nmax，若是則重復步驟（2）至步驟（8），否則流程結束，輸出Lglobal以及f （Lglobal）。

3　算例分析

運用文獻［4］中的2個算例測試本文算法的性能。經(jīng)Matlab實驗調(diào)試，算法參數(shù)設置為：α＝1，β＝5，ρmin＝0.5，a＝0.1。算例1中Q＝0.7；算例2中Q＝0.5，各路徑初始信息素c＝1。螞蟻的個數(shù)M＝50，最大迭代次數(shù)Nmax＝300。

算例1設G（V，E）為給定的賦權完全圖，距離矩陣D與收益矩陣P如下所示：

算例2設G（V，E）為給定的賦權完全圖，距離矩陣D與收益矩陣P如下所示：

已知目前2個算例的最優(yōu)解分別為0.639 10 和0.408 71。運用本文算法對2個算例分別運行10次，均獲得了最優(yōu)解。

算例1的最優(yōu)路徑為1—4—6—7—5—8—2—3—1，總路程為255，總收益為399。

算例2的最優(yōu)路徑為1—4—2—6—5—3—7—10—9—8—1，總路程為2 845，總收益為6 961。

為了便于比較，將算例分別在大洪水算法（great deluge algorithm，GDA）、競爭決策算法（competitive decision algorithm，CDA）、改進遺傳算法［9］（improved genetic algorithm，IGA）以及改進蟻群算法［10］（improved ant colony algorithm，IACA）上運行10次，運行結果見表1所列。

通過比較5種算法得到的結果可以發(fā)現(xiàn)，無論是從獲得最優(yōu)解的次數(shù)還是解的整體質(zhì)量上來看，本文算法要明顯優(yōu)于另外的4種算法。此外，從獲得最優(yōu)解的平均耗時來看，本文算法也略勝一籌。

表1　實驗結果

4　結束語

作為從經(jīng)典TSP引申出來的擴展問題，MRTSP在國內(nèi)的研究還比較少。本文提出的混合行為蟻群算法可以在保證收斂速度的情況下提高解的質(zhì)量，為求解MRTSP提供了新的思路。

［參考文獻］

［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］馬良.求解最小比率TSP的一個算法［J］.系統(tǒng)工程，1998，16（4）：62-65.

［3］寧愛兵，馬良.最小比率旅行商（MRTSP）問題競爭決策算法［J］.計算機工程與應用，2005，41（11）：30-32.

［4］盛虹平.求解最小比率旅行商問題的大洪水算法［J］.杭州師范大學學報：自然科學版，2010，9（6）：401-405.

［5］王穎，謝劍英.一種自適應蟻群算法及其仿真研究［J］.系統(tǒng)仿真學報，2005（1）：31-33.

［6］St¨utzle T，Hoos H.MAX-MIN ant system and local search for the traveling salesman problem［C］//IEEE International Conference on Evolutionary Computation，1997.IEEE，1997：309 -314.

［7］何文玲，倪郁東，汪婷婷.基于混合行為蟻群算法的車輛路徑問題［J］.合肥工業(yè)大學學報：自然科學版，2014，37（7）：883-887.

［8］潘夏福.混合蟻群算法求解0-1背包問題［D］.廈門：廈門大學，2008.

［9］周澤巖，張喜.基于改進遺傳算法的TSP問題求解的研究［J］.物流技術，2012，31（9）：220-223.

［10］王忠英，白艷萍，岳利霞.經(jīng)過改進的求解TSP問題的蟻群算法［J］.數(shù)學的實踐與認識，2012，42（4）：133-140.

（責任編輯馬國鋒）

Mixing behavior ant colony algorithm for solving minimum ratio traveling salesman problem

NI Yu-dong1，ZHAO Qun1，SHEN Yin-dong2，ZHANG Yu-jie1
（1.School of Mathematics，Hefei University of Technology，Hefei 230009，China；2.School of Automation，Huazhong University of Science and Technology，Wuhan 430074，China）

Abstract：In order to optimize the minimum ratio traveling salesman problem（MRTSP）quickly and effectively，a kind of mixing behavior ant colony optimization（ACO）is proposed.By improving ACO’s transition probabilities and strategy of updating pheromone，every ant can select its behavior rules randomly，which makes the ant colony more intelligentialized.Exchange strategy and catastrophe strategy are designed in the algorithm to avoid falling into local optimum.The results of simulation experiment indicate that the modified algorithm can optimize MRTSP effectively.

Key words：minimum ratio traveling salesman problem（MRTSP）；ant colony optimization（ACO）；mixing behavior；optimization

作者簡介：倪郁東（1963-），男，安徽合肥人，合肥工業(yè)大學副教授，碩士生導師；

基金項目：國家自然科學基金資助項目（71171087）；合肥工業(yè)大學教學研究資助項目（XJ2009005）

收稿日期：2014-12-26；修回日期：2015-03-23

Doi：10.3969/j.issn.1003-5060.2016.01.026

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1003-5060（2016）01-0140-05