旅行商問題推廣及其混合智能算法

陳冬華

（華東交通大學基礎科學學院，江西南昌 330013）

1TSP與CTSP

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

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

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

TSP是典型的NP-hard問題，是組合優化領域研究中研究最多的問題之一，也是目前解決旅行優化領域里的研究熱點。也有不少研究者對TSP進行了推廣，如多旅行商問題[3-6]，廣義旅行商問題[7-14]，中國旅行商問題[15]，有向黑白旅行商問題[16]。

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

顯然，CTSP具有現實實用價值與意義，也有些其它領域的問題可以轉化為CTSP，比如信息檢索等，但目前為止，CTSP少有人進行研究。

2GA、ACS算法與CTSP描述

遺傳算法[17]（genetic algorithm，GA）是一類仿生優化算法，具有快速隨機的大范圍全局搜索能力，很容易與其它算法結合，但對于系統中的反饋信息利用不夠，當求解到一定范圍時往往做大量無為的冗余迭代，求精確解效率低。因為GA不受函數連續性、可導性等條件的約束，并以其固有的并行性，使GA廣泛應用于組合優化、圖像處理、人工智能、機器學習、專家系統等很多領域。

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

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

設城市i所需求的貨物需求向量Ai=（a1i，a2i，…，asi），其中aji（i=1，2，…，n；j=1，2，…，s）均為非負值，表示城市i需求某種貨物j的數量。完成銷售任務必需滿足旅行商具有貨物資源（供應向量）B=（b1，b2，…，bs），其中bj（j=1，2，…，s）表示該銷售任務的第j種貨物的數量。那些需求向量的每一維分量均大于供應量的城市完成銷售任務的概率較大，即城市的需求模式和旅行商銷售任務的供給模式越匹配，其完成任務的概率也就越大。可以按照如下公式對旅行商在i城市完成任務的概率pi進行預測

式中：T表示向量轉置。

解決了CTSP，可以給出旅行商在不同城市的最優旅行路線，保證旅行商可以在最短時間內銷售完商品，這在實際生活中具有指導意義，并且在其它領域應用中發揮作用，如在網絡信息庫中進行某種信息檢索時，對檢索系統規劃出檢索路徑等等。

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

ACS算法在求解TSP問題時，只需考慮城市之間的距離。CTSP除了需要考慮城市間距離上路徑延時之外，還需要考慮在各城市完成任務概率和銷售時間。旅行商螞蟻除了會傾向于以較高的概率選擇花費時間短、外激素濃度高的城市間路徑之外，還會優先考慮那些完成任務概率高、銷售時間短的城市，這是因為旅行商螞蟻在訪問過若干完成任務概率高、銷售時間短的城市之后很可能就已經完成了預定任務，由此即可直接返回出發點城市而無須繼續訪問其余城市。按照這一基本思想，旅行商螞蟻選擇下一城市的概率為

在系統尚未收斂到全局最優解前，當前最優解很可能對應著局部極小值，這很有可能使得整個蟻群系統陷入局部極小而停止進化，為了避免此種情況發生，可對全局更新規則進行推廣：在蟻群系統中只有當前循環中最優的那一只螞蟻能夠進行全局更新，令最優的k只螞蟻同時更新所經路徑上的信息素濃度，則將公式（2）修改為

式中：m為所對應的螞蟻；Tm為第m最優解對應的螞蟻完成任務的時間。

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

4 CIA描述與實例

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

步驟一：定義目標函數和適應度函數；初始化GA中相關參數；隨機生成一組實數編碼；置GC：=0，GC為GA算法運行次數。

步驟二：設置控制遺傳代數t：=0。

步驟三：根據適應度函數選擇X，Y；對X，Y進行OX交叉；對X，Y進行逆轉變異。

步驟四：設置控制遺傳代數標準T；若t＜T，則置t：=t+1，轉入步驟三，否則繼續。

步驟五：設置GA控制運行次數GCmax；若GC＜GCmax（其中GCmax為GA最大運行次數），則轉入步驟二，否則繼續。

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

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

步驟八：設置ACS算法控制運行次數NCmax；若NC＜NCmax（其中NCmax為ACS最大運行次數），則轉入步驟七，否則繼續。

步驟九：輸出CIA的最優解。

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

為了驗證CIA與GA及ACS算法的尋優效率，下面研究一個實例，如：求旅行商去16座城市銷售的最佳路線。16座城市（城市編號為1至16）地理位置橫坐標與縱坐標（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仿真平臺，在Pentium4，2.8 GHz，512 MB內存的微機上進行仿真實驗。求出的最優解（用城市編號順序表示路線）為：1，14，13，12，7，6，15，5，11，9，10，16，3，2，4，8。3種算法的效果見表1。

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

實驗表明，CIA比GA及ACS算法尋優效率更高、更好。

[1]王有為.基于禁忌表的捕魚搜索算法及其在旅行商問題中的實驗研究[J].系統工程理論與實踐，2008，2（2）：230-631.

[2]劉新，劉任任，侯經川.求解旅行商問題的整體優先算法[J].計算機應用，2007，5（5）：1204-1207.

[3]李天龍，呂勇哉.基于自組織優化算法的一類多旅行商問題[J].計算機應用，2010，2（2）：458-460.

[4] 黨建武，靳蕃.神經網絡求解MTSP的應用研究[J].鐵道學報，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]代坤，魯士文，蔣祥剛.基于遺傳算法的多人旅行商問題求解[J].計算機工程，2004，30（16）：139-141.

[7]黃可為，汪定偉.熱軋計劃中的多旅行商問題及其計算方法[J].計算機應用研究，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]趙曦，葉和平.廣義旅行商問題及其求解[J].東莞理工學院學報，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]余國興，丁玉成，李滌塵.平面多輪廓加工路徑優化模型及其近似算法[J].西安交通大學學報，2004，1（38）：39-42.

[15]王怡雯，叢爽.用隨機神經網絡優化求解C-TSP[J].吉林大學學報：信息科學版，2004，4（22）：359-363.

[16]江賀，張憲超，陳國良.有向黑白旅行商問題[J].計算機學報，2007，3（3）：431-439.

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

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