求解最小比率旅行商問題的大洪水算法

盛虹平

(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)粘Ｉ钪薪?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.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ù)設置不當造成的誤差機率.

2 MRTSP大洪水算法

從以上分析可以看出，大洪水算法實施的關鍵在于鄰域搜索的設計.對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)，算法的運行效率非常之高.

3 算例測試

由于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計算結果與比較

4 結束語

目前對大洪水算法的研究還不多，相比其他算法，該算法思想簡單，參數(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.