旅行商問(wèn)題推廣及其混合智能算法

陳冬華

（華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西南昌 330013）

1TSP與CTSP

從上個(gè)世紀(jì)50年代起，學(xué)術(shù)界出版了大量關(guān)于旅行商問(wèn)題[1]的文獻(xiàn)。旅行商問(wèn)題（traveling salesman problem，TSP）是指這樣一個(gè)組合優(yōu)化問(wèn)題：某個(gè)商人欲到n座城市A=（a1，a2，…，an）去推銷(xiāo)商品，希望選擇一條路線使得商人走遍每座城市后（僅能訪問(wèn)一次）回到起點(diǎn)且所走路程最短。用圖論術(shù)語(yǔ)來(lái)說(shuō)[2]，假設(shè)有一個(gè)圖g=（v，e），其中v是頂點(diǎn)集（頂點(diǎn)對(duì)應(yīng)于某個(gè)城市），e是邊集（城市之間的連接狀態(tài)，每邊賦予權(quán)重表示城市間距離），設(shè)D是由頂點(diǎn)i與頂點(diǎn)j之間的距離所組成的距離矩陣，如果任意兩個(gè)城市的距離都是對(duì)稱(chēng)的，它所對(duì)應(yīng)的是圖論中的無(wú)向圖，若兩個(gè)城市間的距離是非對(duì)稱(chēng)的，它所對(duì)應(yīng)于圖論中的有向圖。旅行商問(wèn)題就是求出一條經(jīng)過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只經(jīng)過(guò)一次的具有最短路徑的回路。

如果令城市ai與aj的距離為dij，用xij表示商人是否以順序i訪問(wèn)城市ai后接著訪問(wèn)城市aj（即，xij=1表示商人以順序i訪問(wèn)城市ai后接著訪問(wèn)城市aj，否則xij=0），則TSP問(wèn)題可以描述成如下優(yōu)化問(wèn)題

式中：s.t.為約束條件。

TSP是典型的NP-hard問(wèn)題，是組合優(yōu)化領(lǐng)域研究中研究最多的問(wèn)題之一，也是目前解決旅行優(yōu)化領(lǐng)域里的研究熱點(diǎn)。也有不少研究者對(duì)TSP進(jìn)行了推廣，如多旅行商問(wèn)題[3-6]，廣義旅行商問(wèn)題[7-14]，中國(guó)旅行商問(wèn)題[15]，有向黑白旅行商問(wèn)題[16]。

下面將TSP變形推廣成全體旅行商問(wèn)題（caboodle traveling salesman problem，CTSP）。CTSP定義如下：某個(gè)商人擁有s種貨物B=（b1，b2，…，bs），其中bj（j=1，2，…，s）表示第j種貨物的數(shù)量，欲到n座城市A=（A1，A2，…，An）去推銷(xiāo)這些商品，Ai=（a1i，a2i，…，asi），其中aji（i=1，2，…，n；j=1，2，…，s）表示第i座城市Ai對(duì)這s種貨物各自的需求數(shù)量，商人事先不知道各座城市需求情況但希望找到一座城市一次性銷(xiāo)售掉所有的商品（沿途不賣(mài)），銷(xiāo)售完商品后隨即返回不再訪問(wèn)其它剩余城市，需要選擇一條路線使得商人推銷(xiāo)完商品后（每座城市僅能訪問(wèn)一次，走過(guò)所有的城市后沒(méi)有銷(xiāo)售完商品即生意失敗也返回起點(diǎn)城市）回到起點(diǎn)且所花時(shí)間最短（假設(shè)商人在途中速度始終不變）。

顯然，CTSP具有現(xiàn)實(shí)實(shí)用價(jià)值與意義，也有些其它領(lǐng)域的問(wèn)題可以轉(zhuǎn)化為CTSP，比如信息檢索等，但目前為止，CTSP少有人進(jìn)行研究。

2GA、ACS算法與CTSP描述

遺傳算法[17]（genetic algorithm，GA）是一類(lèi)仿生優(yōu)化算法，具有快速隨機(jī)的大范圍全局搜索能力，很容易與其它算法結(jié)合，但對(duì)于系統(tǒng)中的反饋信息利用不夠，當(dāng)求解到一定范圍時(shí)往往做大量無(wú)為的冗余迭代，求精確解效率低。因?yàn)镚A不受函數(shù)連續(xù)性、可導(dǎo)性等條件的約束，并以其固有的并行性，使GA廣泛應(yīng)用于組合優(yōu)化、圖像處理、人工智能、機(jī)器學(xué)習(xí)、專(zhuān)家系統(tǒng)等很多領(lǐng)域。

蟻群系統(tǒng)（ant colony system，ACS）算法[18]是意大利學(xué)者M(jìn).Dorigo等人于1991年首先提出的。1996年，M.Dorigo等又應(yīng)用該算法求解非對(duì)稱(chēng)TSP以及車(chē)間作業(yè)調(diào)度問(wèn)題（job-shop scheduling problem，JSP），且對(duì)蟻群算法中初始化參數(shù)對(duì)其性能的影響作了初步探討，該算法可以使得螞蟻在行進(jìn)過(guò)程中不再局限于按照已積累的信息濃度信息選擇路徑，而是可以做到利用已有信息與搜索新路徑并重，通過(guò)適當(dāng)提高解的隨機(jī)性和多樣性，從而大大增強(qiáng)了基本蟻群算法的魯棒性。ACS算法具有分布式并行全局搜索能力，能較大程度避免候選解陷入局部極小并導(dǎo)致系統(tǒng)收斂到偽最優(yōu)解從而停止進(jìn)化，但存在初期信息匱乏求解速度慢的缺點(diǎn)。我國(guó)在蟻群算法領(lǐng)域的研究起步較晚，從公開(kāi)發(fā)表的論文來(lái)看，國(guó)內(nèi)最早研究蟻群算法的是東北大學(xué)控制仿真研究中心的張紀(jì)會(huì)博士與徐心和教授，以投稿日期為標(biāo)準(zhǔn)，時(shí)間是1997年10月。

為了使用智能算法對(duì)CTSP進(jìn)行路徑規(guī)劃，CTSP定義重新描述為：某地區(qū)共有n座城市，其編號(hào)分別為1，2，…，n，旅行商從城市1出發(fā)去執(zhí)行銷(xiāo)售任務(wù)，旅行商在城市i完成其銷(xiāo)售任務(wù)的概率為pi，pi與pj（i≠j）相互獨(dú)立（i=1，2，…，n；j=1，2，…，n）。不論旅行商在城市i是否能完成其銷(xiāo)售任務(wù)，其在城市i因嘗試執(zhí)行任務(wù)而造成的時(shí)延均為ti。對(duì)城市1而言，p1=0，t1=0。旅行商從城市i旅行到城市j所需的時(shí)間為tij（從城市i旅行到城市j距離dij=vtij，假設(shè)v為常數(shù)。所以tij也可以用dij來(lái)代替）。若旅行商在某城市完成任務(wù)，則可由該城市直接返回出發(fā)城市1，而無(wú)需繼續(xù)訪問(wèn)其余城市；若未能完成任務(wù)，則旅行商需要繼續(xù)旅行到另一座城市直至其任務(wù)完成或遍歷所有城市均不能完成其任務(wù)即任務(wù)失敗為止（途中每座城市至多訪問(wèn)一次）。要求制定一個(gè)旅行商路徑計(jì)劃，使得旅行商完成任務(wù)所需時(shí)間的期望值最小。

設(shè)城市i所需求的貨物需求向量Ai=（a1i，a2i，…，asi），其中aji（i=1，2，…，n；j=1，2，…，s）均為非負(fù)值，表示城市i需求某種貨物j的數(shù)量。完成銷(xiāo)售任務(wù)必需滿足旅行商具有貨物資源（供應(yīng)向量）B=（b1，b2，…，bs），其中bj（j=1，2，…，s）表示該銷(xiāo)售任務(wù)的第j種貨物的數(shù)量。那些需求向量的每一維分量均大于供應(yīng)量的城市完成銷(xiāo)售任務(wù)的概率較大，即城市的需求模式和旅行商銷(xiāo)售任務(wù)的供給模式越匹配，其完成任務(wù)的概率也就越大?？梢园凑杖缦鹿綄?duì)旅行商在i城市完成任務(wù)的概率pi進(jìn)行預(yù)測(cè)

式中：T表示向量轉(zhuǎn)置。

解決了CTSP，可以給出旅行商在不同城市的最優(yōu)旅行路線，保證旅行商可以在最短時(shí)間內(nèi)銷(xiāo)售完商品，這在實(shí)際生活中具有指導(dǎo)意義，并且在其它領(lǐng)域應(yīng)用中發(fā)揮作用，如在網(wǎng)絡(luò)信息庫(kù)中進(jìn)行某種信息檢索時(shí)，對(duì)檢索系統(tǒng)規(guī)劃出檢索路徑等等。

3 混合智能算法（combined intelligent algorithm，CIA）

ACS算法在求解TSP問(wèn)題時(shí)，只需考慮城市之間的距離。CTSP除了需要考慮城市間距離上路徑延時(shí)之外，還需要考慮在各城市完成任務(wù)概率和銷(xiāo)售時(shí)間。旅行商螞蟻除了會(huì)傾向于以較高的概率選擇花費(fèi)時(shí)間短、外激素濃度高的城市間路徑之外，還會(huì)優(yōu)先考慮那些完成任務(wù)概率高、銷(xiāo)售時(shí)間短的城市，這是因?yàn)槁眯猩涛浵佋谠L問(wèn)過(guò)若干完成任務(wù)概率高、銷(xiāo)售時(shí)間短的城市之后很可能就已經(jīng)完成了預(yù)定任務(wù)，由此即可直接返回出發(fā)點(diǎn)城市而無(wú)須繼續(xù)訪問(wèn)其余城市。按照這一基本思想，旅行商螞蟻選擇下一城市的概率為

在系統(tǒng)尚未收斂到全局最優(yōu)解前，當(dāng)前最優(yōu)解很可能對(duì)應(yīng)著局部極小值，這很有可能使得整個(gè)蟻群系統(tǒng)陷入局部極小而停止進(jìn)化，為了避免此種情況發(fā)生，可對(duì)全局更新規(guī)則進(jìn)行推廣：在蟻群系統(tǒng)中只有當(dāng)前循環(huán)中最優(yōu)的那一只螞蟻能夠進(jìn)行全局更新，令最優(yōu)的k只螞蟻同時(shí)更新所經(jīng)路徑上的信息素濃度，則將公式（2）修改為

式中：m為所對(duì)應(yīng)的螞蟻；Tm為第m最優(yōu)解對(duì)應(yīng)的螞蟻完成任務(wù)的時(shí)間。

這樣全局更新規(guī)則的推廣使得解的多樣性得到了適當(dāng)提高，在很大程度上避免了候選解陷入局部極小并導(dǎo)致系統(tǒng)收斂到偽最優(yōu)解而停止進(jìn)化。并在此ACS算法基礎(chǔ)上引入GA，基本思想是汲取兩種算法的優(yōu)點(diǎn)，克服各自缺點(diǎn)，起到優(yōu)勢(shì)互補(bǔ)作用，本文針對(duì)CTSP提出一種新的混合智能算法（combined intelligent algorithm，CIA）。CIA在求解速度效率上優(yōu)于ACS算法，在求解精確度上效率優(yōu)于GA，是收斂速度快與求解效率高的比較好的一種啟發(fā)式算法。

4 CIA描述與實(shí)例

CIA基本思路是首先采用GA，充分利用GA的快速性、隨機(jī)性、全局收斂性，并把GA產(chǎn)生的結(jié)果作為有關(guān)問(wèn)題的初始信息素分布，然后再采用ACS算法，在有一定初始信息素分布的情況下，利用ACS算法的并行性、正反饋性、求解精度效率高等特點(diǎn)。CIA運(yùn)算如下：

步驟一：定義目標(biāo)函數(shù)和適應(yīng)度函數(shù)；初始化GA中相關(guān)參數(shù)；隨機(jī)生成一組實(shí)數(shù)編碼；置GC：=0，GC為GA算法運(yùn)行次數(shù)。

步驟二：設(shè)置控制遺傳代數(shù)t：=0。

步驟三：根據(jù)適應(yīng)度函數(shù)選擇X，Y；對(duì)X，Y進(jìn)行OX交叉；對(duì)X，Y進(jìn)行逆轉(zhuǎn)變異。

步驟四：設(shè)置控制遺傳代數(shù)標(biāo)準(zhǔn)T；若t＜T，則置t：=t+1，轉(zhuǎn)入步驟三，否則繼續(xù)。

步驟五：設(shè)置GA控制運(yùn)行次數(shù)GCmax；若GC＜GCmax（其中GCmax為GA最大運(yùn)行次數(shù)），則轉(zhuǎn)入步驟二，否則繼續(xù)。

步驟六：生成若干組GA優(yōu)化解；初始化ACS算法中相關(guān)參數(shù)；根據(jù)GA的優(yōu)化解生成信息素初始分布，將m只旅行商螞蟻置于n座城市；置NC：=0，NC為ACS算法運(yùn)行次數(shù)。

步驟七：每只螞蟻根據(jù)公式（1）狀態(tài)轉(zhuǎn)換規(guī)則旅行到下一座城市，并按公式（3）進(jìn)行信息素局部更新；m只螞蟻遍歷n座城市后，按公式（4）進(jìn)行信息素強(qiáng)度范圍進(jìn)行控制；將m只螞蟻隨機(jī)置于n座城市，對(duì)禁忌表和路徑序列進(jìn)行初始化。

步驟八：設(shè)置ACS算法控制運(yùn)行次數(shù)NCmax；若NC＜NCmax（其中NCmax為ACS最大運(yùn)行次數(shù)），則轉(zhuǎn)入步驟七，否則繼續(xù)。

步驟九：輸出CIA的最優(yōu)解。

應(yīng)用CIA求解CTSP時(shí)，在求解初始階段采用GA，充分利用GA的全局優(yōu)化機(jī)制在較短時(shí)間內(nèi)取得一組優(yōu)化解，然后將這組優(yōu)化解轉(zhuǎn)化為對(duì)應(yīng)路徑上信息素的初始濃度，從而引導(dǎo)螞蟻的尋找路徑過(guò)程，減少了單獨(dú)使用ACS算法時(shí)初始計(jì)算過(guò)程的盲目性與隨機(jī)性。在構(gòu)造解的過(guò)程中按照ACS算法的局部更新規(guī)則在所經(jīng)過(guò)的路徑上分泌信息素，并且每一代的前k個(gè)優(yōu)勝解都會(huì)按照ACS算法的全局更新規(guī)則對(duì)所經(jīng)過(guò)的路徑進(jìn)行信息濃度更新。經(jīng)過(guò)若干代之后，那些延時(shí)短且沿途城市銷(xiāo)售完成任務(wù)概率高、總時(shí)間費(fèi)時(shí)短的路徑上信息濃度會(huì)逐漸高于其它路徑，后繼螞蟻在信息素指引下，會(huì)以更高的概率選擇那些比較優(yōu)化的路徑，如此反復(fù)就構(gòu)成了一個(gè)正反饋過(guò)程，這樣會(huì)使得絕大多數(shù)螞蟻首選優(yōu)化路徑，從而快速給出最優(yōu)解。

為了驗(yàn)證CIA與GA及ACS算法的尋優(yōu)效率，下面研究一個(gè)實(shí)例，如：求旅行商去16座城市銷(xiāo)售的最佳路線。16座城市（城市編號(hào)為1至16）地理位置橫坐標(biāo)與縱坐標(biāo)（x，y）分別為：1（38.24，20.42），2（39.57，26.15），3（40.56，25.32），4（36.26，23.12），5（33.48，10.54），6（37.56，12.19），7（38.42，13.11），8（37.52，20.44），9（41.23，9.10），10（41.17，13.05）11（36.08，-5.21），12（38.47，15.13），13（38.15，15.35），14（37.51，15.17），15（35.49，14.32），16（39.36，19.56）。采用Matlab2008a仿真平臺(tái)，在Pentium4，2.8 GHz，512 MB內(nèi)存的微機(jī)上進(jìn)行仿真實(shí)驗(yàn)。求出的最優(yōu)解（用城市編號(hào)順序表示路線）為：1，14，13，12，7，6，15，5，11，9，10，16，3，2，4，8。3種算法的效果見(jiàn)表1。

表1 三種算法效果表Tab.1 Effect of three algorithms

實(shí)驗(yàn)表明，CIA比GA及ACS算法尋優(yōu)效率更高、更好。

[1]王有為.基于禁忌表的捕魚(yú)搜索算法及其在旅行商問(wèn)題中的實(shí)驗(yàn)研究[J].系統(tǒng)工程理論與實(shí)踐，2008，2（2）：230-631.

[2]劉新，劉任任，侯經(jīng)川.求解旅行商問(wèn)題的整體優(yōu)先算法[J].計(jì)算機(jī)應(yīng)用，2007，5（5）：1204-1207.

[3]李天龍，呂勇哉.基于自組織優(yōu)化算法的一類(lèi)多旅行商問(wèn)題[J].計(jì)算機(jī)應(yīng)用，2010，2（2）：458-460.

[4] 黨建武，靳蕃.神經(jīng)網(wǎng)絡(luò)求解MTSP的應(yīng)用研究[J].鐵道學(xué)報(bào)，1997，19（2）：63-69.

[5]WAC E，HAN J，MANN R C.Aneural network algorithm for the multiple traveling salesmen problem[J].Biological Cybernetics，1989，61（1）：11-19.

[6]代坤，魯士文，蔣祥剛.基于遺傳算法的多人旅行商問(wèn)題求解[J].計(jì)算機(jī)工程，2004，30（16）：139-141.

[7]黃可為，汪定偉.熱軋計(jì)劃中的多旅行商問(wèn)題及其計(jì)算方法[J].計(jì)算機(jī)應(yīng)用研究，2007，7（24）：43-57.

[8]HAYKIN S，LABORDERE A L.The record balancing problem：A dynamic programming solution of a generalized traveling salesman problem[J].Real WorldApplications，1969（2）：43-49.

[9]SAKSENA J P.Mathematical mode of scheduling clients through welfare agencies[J].Computers&Structures，1970（8）：185-200.

[10]SRIVASTAVA S S，KUMAR S，GARG R C，et al.Generalized traveling salesman problem through n sets of nodes[J].Computers&Structures，1969（7）：97-101.

[11]趙曦，葉和平.廣義旅行商問(wèn)題及其求解[J].東莞理工學(xué)院學(xué)報(bào)，2007，5（14）：75-80.

[12]LIEN Y N，MA E.Transformation of the generalized traveling salesman problem into the standard traveling salesman problem[J].Information Sciences，1993（74）：177-189.

[13]VLADIMIR D，ZORAN S.An efficient transformation of the generalized traveling salesman problem into the traveling salesman on digraphs[J].Informatics and Computer Science，1997（192）：105-110.

[14]余國(guó)興，丁玉成，李滌塵.平面多輪廓加工路徑優(yōu)化模型及其近似算法[J].西安交通大學(xué)學(xué)報(bào)，2004，1（38）：39-42.

[15]王怡雯，叢爽.用隨機(jī)神經(jīng)網(wǎng)絡(luò)優(yōu)化求解C-TSP[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2004，4（22）：359-363.

[16]江賀，張憲超，陳國(guó)良.有向黑白旅行商問(wèn)題[J].計(jì)算機(jī)學(xué)報(bào)，2007，3（3）：431-439.

[17]吳微，周春光，梁艷春.智能計(jì)算[M].北京：高等教育出版社.2009：119-146.

[18]徐宗本.計(jì)算智能[M].北京：高等教育出版社.2006：111-114.