盛虹平
(1.杭州師范大學 錢江學院,浙江 杭州 310012;2.上海理工大學 管理學院,上海 200093)
旅行商問題(Travelling Salesman Problem,簡稱TSP)是運籌學中一個經(jīng)典的組合優(yōu)化問題,有著明顯的實際意義,已經(jīng)證明是一個NP-Hard問題.其一般提法為:給定n個城市和每兩個城市i,j之間的距離dij,某旅行商從一個城市出發(fā),到其他城市去推銷貨物,要求每個城市僅被訪問一次,最后回到出發(fā)城市,問該旅行商應如何選擇行走路線,才能使總行程最短?當dij=dji時,問題被稱為對稱型TSP.從這種標準的TSP還可以延伸出許多擴展型TSP[1-2],如瓶頸TSP、最小比率TSP、多人TSP、時間約束TSP、Prize-collecting TSP、多目標TSP、Hamilton路、車輛路徑問題等.這里只討論最小比率TSP(Minimum Ratio Travelling Salesman Problem,簡稱MRTSP),它是在標準型基礎上增加收益假定,即假定旅行商從城市i到達城市j會獲得某種收益pij,問題變?yōu)橐_定最佳行走路線,使得回路的總行程與總收益之比最小.問題目標類似于人們?nèi)粘I钪薪?jīng)常使用的費用效益比,與單純的總行程最短相比,往往更具實際意義.
MRTSP相比標準TSP,目標函數(shù)由線性變?yōu)榉蔷€性,使得問題的求解變得更為困難.文獻中已嘗試使用模擬退火算法[3]、蟻群算法[1]、元胞蟻群算法[4]、競爭決策算法[5]等啟發(fā)式算法對此類擴展型TSP進行了求解.該文基于大洪水算法(Great Deluge Algorithm)尋優(yōu)思想,給出一種采用兩城市互換策略進行鄰域搜索的大洪水算法,能快速求解對稱型MRTSP,經(jīng)過數(shù)據(jù)測試和驗證,獲得了較好的結果.
1.1 MRTSP數(shù)學模型
TSP在圖論意義下常常被稱為最小Hamilton圈問題(Minimum Hamiltonian Cycle Problem).此處用數(shù)學語言描述如下:
記G=(V,E)為給定的對稱賦權完全圖,V=(1,2,…,n)為頂點集,E為邊集.已知距離矩陣
D=[dij]n×n,dij=dji,dii=∞,dij>0(i,j∈V),收益矩陣P=[pij]n×n,pij=pji,pii=0,
pij>0(i,j∈V).
若設
則MRTSP數(shù)學模型可描述為:
其中|S|為集合S中所含圖G的頂點個數(shù).約束(1)和(2)表示每個頂點都只有一條邊進和一條邊出,約束(3)則保證沒有任何子回路解的產(chǎn)生.因此,滿足約束(1)~(3)的解構成了一條Hamilton回路[6-7].這里,dij=dji,pij=pji,(i,j∈V),問題又稱為對稱型MRTSP.
1.2 大洪水算法基本思想
大洪水算法最早由G. Dueck于1993年提出[8],是一類啟發(fā)式優(yōu)化算法,它通過模擬洪水上漲過程來進行全局尋優(yōu).該算法基本思想可以描述為:假想有一群山脈,高低不平,山脈的最高點有一艘救生艇,某個攀巖者處于山脈中的某處位置.假定這個攀巖者有特定的工具,他可以從山脈中任意一處到達另一處位置.這時,大洪水爆發(fā)了,奔涌而來的洪水沒過山腳,迅速向上蔓延.為了求生,攀巖者必須不斷向上尋求最高點.隨著洪水的上漲逼近,攀巖者最終將到達山脈的最高點,成功登上救生艇得以逃生.對于極小化問題,可以將大洪水算法理解為大旱算法(Great Drought Algorithm),即山脈變?yōu)榇蠛?,大旱使得海水持續(xù)蒸發(fā),某海洋生物為了求生不斷向低處尋找水資源.
基于目標極小化的大洪水算法核心步驟如下:
步驟1初始化:
count←迭代次數(shù);it←1(迭代因子);
up←海平面下降水位高度;
初始H0←滿足問題條件的初始解,一般隨機產(chǎn)生;
WaterLevel←Z(H0)(海平面高度);
步驟2對H0進行鄰域搜索,得到一個新的解H,計算對應的目標函數(shù)值Z(H);如果Z(H) 步驟3it←it+1;若it 步驟4輸出H0和Z(H0). 可見,大洪水算法和模擬退火算法(SA)有著相似的結構,區(qū)別僅是迭代中候選解的接受規(guī)則不一樣.相對其他啟發(fā)式算法,該算法最大優(yōu)勢在于只有唯一的一個參數(shù)up,而且還可以對這一參數(shù)動態(tài)賦值,大大減小了因參數(shù)設置不當造成的誤差機率. 從以上分析可以看出,大洪水算法實施的關鍵在于鄰域搜索的設計.對TSP而言,鄰域搜索可理解為對當前回路實施某種變換來生成新的回路.常用的TSP鄰域搜索策略包括相鄰兩城市互換、兩城市互換、單城市移位、城市子排列移位、城市子排列反序和城市子排列反序并移位等[9].考慮MRTSP的目標函數(shù)特點和大洪水算法的高效性,筆者采取兩城市互換策略,即對回路中任意兩個點對應的城市i與j進行位置交換來生成新的回路. 下面用一個簡單的例子[9]說明兩城市互換策略的變換思想: 設編號1,2,…,10代表10個城市,H0,H1表示解狀態(tài),H0路徑編碼為: H0←1 2 3 4 5 6 7 8 9 10 對編號為3和7的城市實施兩城市互換策略,路徑變?yōu)椋?/p> H1←1 2 7 4 5 6 3 8 9 10 下面給出具體求解MRTSP的大洪水算法,按偽碼形式敘述如下: Begin 初始化: count←迭代次數(shù);it←迭代因子; 構造初始路徑H0(1到n的隨機排列); route[ ]←H0路徑編碼; 計算初始回路H0的總路程DWeight和總收益TWeight; Loop Forit←1 tocountdo Begin Fori←1 tondortemp[i]←route[i]; Repeat xx←random(n)+1;yy←random(n)+1; Untilxx≠yy; 交換rtemp[xx]與rtemp[yy],生成新回路H′; 計算回路H′的總路程DWeight′和總收益TWeight′; IfZ′ Begin H0←H′;Z←Z′; up←(WaterLevel-Z)/500; Ifup<0.01 thenup←0.01; WaterLevel←WaterLevel-up; End End EndLoop 輸出最好解H0和相應目標函數(shù)值Z; End 該算法已用Delphi 7編程實現(xiàn).不難看出,該算法的時間復雜度為O(n),算法的運行效率非常之高. 由于MRTSP缺乏有關實際數(shù)據(jù),筆者采用隨機生成的數(shù)值算例進行測試[3-5].實驗所用的硬件環(huán)境為雙核Intel CPU T2250,1.73GHz,2GB RAM,軟件環(huán)境為Windows XP和Delphi 7.0,問題規(guī)模n∈[8,100],dij,pij∈[1,1 000),求解精度為5.大量計算表明,大洪水算法對MRTSP而言,也是一種行之有效的算法,而且算法的運行速度非???,當規(guī)模n=100時,迭代10 000次,算法運行時間只需30 s左右.下面給出文獻[3]中的算例和大洪水算法求解結果. 算例1設給定對稱賦權完全圖G=(V,E),n=8,距離矩陣D和收益矩陣P如下: 運算大洪水算法,最好結果為有效迭代129次,最小比率Z=0.639 10,最優(yōu)TSP回路H0={1,4,6,7,5,8,2,3,1},總路程DWeight=255,總收益PWeight=399. 為進一步測試大洪水算法的性能,再選用文獻[4]中的算例進行對比測試. 算例2設給定對稱賦權完全圖G=(V,E),n=10,距離矩陣D和收益矩陣P如下: 對算法循環(huán)調(diào)用,可以方便地得到目標最小比率值的平均值和最佳值,算例2的求解結果見表1. 可見,大洪水算法也能求得最小比率值0.408 71,但都在迭代10 000次的情況下,大洪水算法最佳值出現(xiàn)的機率要比蟻群算法和元胞蟻群算法都好,而且在收斂速度上也更勝一籌. 表1 算例2計算結果與比較 目前對大洪水算法的研究還不多,相比其他算法,該算法思想簡單,參數(shù)依賴度低.筆者將其用于連續(xù)型優(yōu)化問題及大規(guī)模TSP等一系列組合優(yōu)化問題的求解,都獲得了令人滿意的結果,而且表現(xiàn)出強魯棒性、高收斂速度和高精度等優(yōu)點.對該算法稍作修改,還可用于其他擴展型TSP的求解,算法的通用性和實用性也較強.可見,大洪水算法在優(yōu)化領域中也不失為一種好的求解手段和工具,筆者將繼續(xù)深入展開研究. [1] 馬良,項培軍.螞蟻算法在組合優(yōu)化中的應用[J].管理科學學報,2001,4(2):32-37. [2] 馬良,寧愛兵.高級運籌學[M].北京:機械工業(yè)出版社,2008:91-93. [3] 馬良.求解最小比率TSP的一個算法[J].系統(tǒng)工程,1998,16(4):62-65. [4] 朱剛,馬良,姚儉.若干擴展TSP的元胞螞蟻算法[J].系統(tǒng)管理學報.2007,16(5):492-496. [5] 寧愛兵,馬良.最小比率旅行商(MRTSP)問題競爭決策算法[J].計算機工程與應用,2005,41(11):30-32. [6] Laport G. The travelling salesman problem: an overview of exact and approximate algorithms[J]. European Journal of Operational Research,1992,59(2):231-247. [7] 馬良.旅行推銷員問題的算法綜述[J].數(shù)學的實踐與認識,2000,30(2):156-165. [8] Dueck G. New optimization heuristics: the great deluge algorithm and the record-to-record travel[J]. Journal of Computational Physics,1993,104(1):86-92. [9] 馬良,朱剛,寧愛兵.蟻群優(yōu)化算法[M].北京:科學出版社,2008:34.2 MRTSP大洪水算法
3 算例測試
4 結束語