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

?

求解最小比率旅行商問(wèn)題的混合行為蟻群算法

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

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

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

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

旅行商問(wèn)題（traveling salesman problem，TSP）是一類(lèi)典型的組合優(yōu)化問(wèn)題，同時(shí)也是NP-Hard問(wèn)題。通常可簡(jiǎn)單描述為：有一旅行商欲前往n個(gè)城市推銷(xiāo)商品，從某一城市出發(fā)，經(jīng)過(guò)各個(gè)城市一次后返回出發(fā)城市，問(wèn)該旅行商應(yīng)如何選擇出行路線(xiàn)，使得總路程最短。最小比率旅行商問(wèn)題（MRTSP）是從經(jīng)典TSP中引申出來(lái)的一個(gè)變形問(wèn)題，它在原TSP的基礎(chǔ)上增加了收益假定，即旅行商從城市i走到城市j能獲得一定收益pij，現(xiàn)在的問(wèn)題變成：確定一條路線(xiàn)，使得總路程與總收益的比最小。這種思想類(lèi)似于經(jīng)濟(jì)學(xué)中的費(fèi)用效益，既考慮到了成本同時(shí)又考慮到了收益。相比于TSP中只考慮路程，研究MRTSP往往更具實(shí)際意義。

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

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

1　問(wèn)題模型

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

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

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

2　混合行為蟻群算法

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

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

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

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

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

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

規(guī)則4以螞蟻?zhàn)赃m應(yīng)系統(tǒng)中的轉(zhuǎn)移概率去選擇下一個(gè)要到達(dá)的城市j：

規(guī)則5隨機(jī)從allowedk中選擇一個(gè)城市作為下一個(gè)要訪(fǎng)問(wèn)的城市。

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

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

2.2信息素更新策略

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

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

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

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

2.3交換策略

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

2.4災(zāi)變策略

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

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

2.5算法流程

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

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

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

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

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

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

（7）判斷是否連續(xù)m次迭代得到的是相同的最優(yōu)路徑。若是則以概率P對(duì)Llocal上的路徑實(shí)行災(zāi)變策略，被災(zāi)變所影響的路徑上的信息素為τ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，若是則重復(fù)步驟（2）至步驟（8），否則流程結(jié)束，輸出Lglobal以及f （Lglobal）。

3　算例分析

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

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

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

已知目前2個(gè)算例的最優(yōu)解分別為0.639 10 和0.408 71。運(yùn)用本文算法對(duì)2個(gè)算例分別運(yùn)行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）、競(jìng)爭(zhēng)決策算法（competitive decision algorithm，CDA）、改進(jìn)遺傳算法［9］（improved genetic algorithm，IGA）以及改進(jìn)蟻群算法［10］（improved ant colony algorithm，IACA）上運(yùn)行10次，運(yùn)行結(jié)果見(jiàn)表1所列。

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

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

4　結(jié)束語(yǔ)

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

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

［3］寧愛(ài)兵，馬良.最小比率旅行商（MRTSP）問(wèn)題競(jìng)爭(zhēng)決策算法［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41（11）：30-32.

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

［5］王穎，謝劍英.一種自適應(yīng)蟻群算法及其仿真研究［J］.系統(tǒng)仿真學(xué)報(bào)，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］何文玲，倪郁東，汪婷婷.基于混合行為蟻群算法的車(chē)輛路徑問(wèn)題［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，37（7）：883-887.

［8］潘夏福.混合蟻群算法求解0-1背包問(wèn)題［D］.廈門(mén)：廈門(mén)大學(xué)，2008.

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

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

（責(zé)任編輯馬國(guó)鋒）

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

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

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

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

Doi：10.3969/j.issn.1003-5060.2016.01.026

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-5060（2016）01-0140-05