• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2010-11-23 00:51:57盛虹平
    關鍵詞:馬良算例鄰域

    盛虹平

    (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.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.

    猜你喜歡
    馬良算例鄰域
    稀疏圖平方圖的染色數(shù)上界
    我想成為神筆馬良
    基于鄰域競賽的多目標優(yōu)化算法
    自動化學報(2018年7期)2018-08-20 02:59:04
    Мероприятия и контакты
    中國(俄文)(2018年5期)2018-05-24 13:53:06
    我的神筆馬良
    童話世界(2017年11期)2017-05-17 05:28:26
    小馬良認錯
    關于-型鄰域空間
    基于振蕩能量的低頻振蕩分析與振蕩源定位(二)振蕩源定位方法與算例
    互補問題算例分析
    基于CYMDIST的配電網(wǎng)運行優(yōu)化技術及算例分析
    奉化市| 杭锦旗| 宁城县| 犍为县| 胶南市| 龙海市| 朝阳县| 维西| 师宗县| 呼和浩特市| 江都市| 十堰市| 左云县| 淮滨县| 武城县| 页游| 上蔡县| 尼木县| 烟台市| 光泽县| 株洲县| 乌兰县| 东安县| 鄂尔多斯市| 宁阳县| 宣汉县| 宁乡县| 丰原市| 南平市| 九江市| 莲花县| 隆尧县| 建平县| 吴堡县| 平顶山市| 固镇县| 宁武县| 韶山市| 通城县| 颍上县| 河南省|