(3.232.129.123) 您好!臺灣時間:2021/03/04 18:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:韓宇德
研究生(外文):Yu-de Han
論文名稱:貪婪演算法結合區域搜尋演算法求解TSP組合最佳化問題
論文名稱(外文):Greedy algorithm with local search algorithm for TSP combinatorial optimization problems
指導教授:吳永春
指導教授(外文):Yung-Chun Wu
學位類別:碩士
校院名稱:立德管理學院
系所名稱:應用資訊研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
畢業學年度:96
語文別:中文
論文頁數:152
中文關鍵詞:貪婪演算法區域搜尋旅行銷售員
外文關鍵詞:Greedy AlgorithmLocal SearchTSP
相關次數:
  • 被引用被引用:25
  • 點閱點閱:2368
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:323
  • 收藏至我的研究室書目清單書目收藏:0
本論文針對TSP問題,提出一種二階段的求解方法,就即先以貪婪演算法建構初始路徑,再以2-opt演算法對初始路徑作路徑成本的改善。本方法以國際性網站 TSPLIB 中的55個範例做測試以觀察其效果。在測試的結果中有8個範例比已知最佳解更佳的解,從測試的結論歸納中,本論文所提之求解方法對於聚集型(Clustered)的TSP範例具有較佳的效果。
關鍵字:貪婪演算法,區域搜尋,旅行銷售員
ABSTRACT
This thesis proposes a two-stage solution for the traveling salesman problem (TSP). First, greedy algorithm was used to construct the initial path, then 2-opt algorithm (local search) was applied to improve the path cost of the initial path. 55 instances from the international website, TSPLIB, were tested in order to observe the effects. Among the test results, solutions for 8 instances were better than the best known solutions. To sum up the test conclusions, the solution proposed in this thesis generated better effect on the clustered TSP instance.
Keywords: Greedy Algorithm ,Local Search ,traveling salesman problem
目錄

中文摘要-------------------------Ⅶ
英文摘要-------------------------Ⅷ
致謝-------------------------------Ⅸ
目錄-------------------------------Ⅹ
表目錄----------------------------ⅩⅠ
圖目錄----------------------------ⅩⅡ

第一章 緒論-----------------------------------------------------1

1.1研究動機------------------------------------------------1
1.2研究目的------------------------------------------------2
1.3研究流程及定義---------------------------------------2

第二章 文獻回顧------------------------------------------------5

2.1 TSP求解方法以及題目之類型---------------------5

第三章 啟發式方法之探討-----------------------------------9

3.1基因演算法----------------------------------------------9
3.2螞蟻群演算法--------------------------------------------------14
3.3禁忌搜尋法-----------------------------------------------------16
3.4貪婪演算法-----------------------------------------------------18
3.5鄰域搜尋演算法 ----------------------------------------------19

第四章 研究方法與流程-----------------------------------------21

4.1 以貪婪演算法建構初始路徑成本---------------------------22
4.2 隨機方式與循序方式之探討---------------------------------27
4.3 以2-opt演算法作路徑改善-----------------------------------28

第五章 實驗測試---------------------------------------------------29

5.1 測試平台---------------------------------------------------------30
5.2 TSP問題之測試題目範例以及已知範例的最佳解-------30
5.3 TSP範例題型分類探討-----------------------------------------32
5.4 測試結果---------------------------------------------------------34
5.5 求解不同數量的TSP範例所需的時間----------------------37
5.6 偏差率統計------------------------------------------------------46
5.7 以2-opt方法對初始解的改善率統計-----------------------41
5.8 效能比較---------------------------------------------------------42
第六章 結論---------------------------------------------------------46

附錄A 目前最大規模節點範例----------------------------附錄A
附錄B 呈現55個範例結果-------------- ------------------附錄B

表目錄
表4-1 圖4-2六個節點之間的距離-------------------------------22
表5-1 55個TSP範例作實測後的各項數據結果----------------35
表5-2文獻[23]的方法與本論文之結果比較--------------------42
表5-3文獻[24]的方法與本論文方法之結果比較--------------43
表5-4文獻[24]的方法與本論文之結果比較--------------------44
表5-5文獻[13]的方法與本論文之結果比較--------------------45

圖目錄
圖1-1本論文之研究流程圖-----------------------------------------4
圖2-1 TSP衍伸之相關類型問題-----------------------------------6
圖2-2常見的TSP問題求解之方法、系統發展與分類圖----7
圖2-3 說明全域最佳解以及區域最佳解之示意圖-------------8
圖3-1基因演算法的主要演算流程-------------------------------10
圖3-2 族群初始化示意圖------------------------------------------11
圖3-3 選擇染色體示意圖------------------------------------------11
圖3-4交配 (Crossover)示意圖------------------------------------12
圖3-5基因突變示意圖----------------------------------------------13
圖3-6(a)螞蟻搜尋選擇較短路徑之示意圖----------------------15
圖3-6(b)費洛蒙揮發殆盡示意圖----------------------------------15
圖3-8禁忌搜尋演算法流程圖-------------------------------------17
圖3-9 (a)由4節點連結而成的原始路徑-------------------------19
圖3-9 (b)以2-opt方法改善路徑-----------------------------------19
圖3-10(a)由6個節點連結而成的原始路徑---------------------20
圖3-10(b) 3-opt方法改善路徑--------------------------------------20
圖4-1貪婪演算法結合2-opt演算法之進行流程圖------------22
圖4-2(A) 以節點A作為起始點之路徑圖------------------------23
圖4-2(B) 以節點B 作為起始點之路徑圖-----------------------24
圖4-2(C) 以節點C 作為起始點之路徑圖-----------------------24
圖4-2(D) 以節點D 作為起始點之路徑圖-----------------------25
圖4-2(E) 以節點E 作為起始點之路徑圖------------------------25
圖4-2(F) 以節點F 作為起始點之路徑圖------------------------26
圖4-3以2-opt作路徑交換的說明----------------------------------29
圖5-1範例均勻型(Uniform)特徵-----------------------------------32
圖5-2範例聚集(Clustered)特徵--------------------------------------32
圖5-3範例矩陣型(Matrix)特徵---------------------------------------32
圖5-4範例混合型(Hybrid)特徵--------------------------------------33
圖5-5(a) 求解不同節點數量的範例所需的執行時間------------35
圖5-5(b) 將縱軸以對數方式繪製不同節點數量的範例所需的執行時間-------------------------------------------------------------------------36
圖5-5(c) 以節點分區的方式繪製求解不同節點的範例所需的執行時間-------------------------------------------------------------------------37
圖5-6 偏差率統計圖----------------------------------------------------38
圖5-7以2-opt方法對初始路徑作改善之偏差率統計--------------------------------------------------------------------------------39
圖5-8 Enhanced ACS方法與本論文方法之結果比----------------40
圖5-9 ACS,AS+rank,AS+ rank+pts方法與本論文方法之結果比較-----------------------------------------------------------------------------41
圖5-10 ASe,ASe+pts與AS方法與本論文方法之結果比較----42
圖5-11 FACO,NACO,ACO與GA方法與本論文方法之結果比較--------------------------------------------------------------------------------43
參考文獻
中文部分
[1]陳建緯,”「大規模旅行推銷員問題之研究:鄰域搜尋法與巨集啟發式解法之應用」”,國立交通大學運輸工程與管理學系碩士論文,2001年,pp1-92

[2] 陳冠樺,”「螞蟻記憶系統應用於旅行推銷員問題」”,逢甲大學交通工程與管理學系碩士班碩士論文,2004年,pp1-56

[3] 許_為元”「合式自我學習之基因演算法應用於旅行推銷員問題」”國立臺灣大學資訊工程學研究所碩士論文,2000年,pp1-69

[4]周蘇江,”「含時窗限制的動態車輛途程問題之研究」” ,中原大學工業工程學系碩士學位論文,2001年,pp1-96

[5]陳志明,”「應用群蟻演算法於動態車輛途程規劃研究」”,朝陽科技大學工業工程與管理系碩士論文,2004年,pp1-63

[6]陳隆熙 ,”「一個解決 TSP 問題最佳解的穩定方法—以 TA 演算法為例」”,大葉大學工業工程學系碩士論文,2002年,pp1-108

[7]陳致元 朱子豪”「以空間群聚分析探討 單一物流中心車輛途程問題」”,地理學報 第三十七期,2004年,pp123-137

[8]潘立登 黃小峰”「用啟發式貪心法求解商旅問題」”,北京化工大學學報 第2卷第二期,1998年,pp46-51

[9]李臻,雷定獻,”「多車場車輛優化調度模型及演算法」” ,中南大學交通運輸工程學院,交通運輸工程學報,2004年,pp83-86

[10]鄒鵬, 周智, 陳國良,顧鈞”「求解TSP問題的多級歸約演算法」”, 中國科學技術大學電腦科學技術系, Journal of Software,2003 年, PP1-4

[11]楊忠憲 鄧志堅 張春蘭 潘信允”「TSP 的位移探討及其對最佳化解答的影響」”,第一屆台灣作業研究學會學術研討會暨2004年科技與管理學術研討會,PP172-182

[12]吳泰熙 張欽智”「以禁忌搜尋法則求解推銷員旅行問題」” ,大葉學報 第六卷 第一期,1997年, pp.87-99

[13] 蘇純繒 翁瑞聰,”「以螞蟻群聚最佳化整合噪音擾動法求解 TSP問題」”, 商管科技季刊第四卷第四期,2003年,pp. 359 -375


英文部分
[14]Lin, S. & B.W. Kernighan,, “「An Effective Heuristic Algorithm for the Traveling Salesman Problem, 」” Operations Research, Vol. 21,1973, pp.498-516.

[15]Marco Dorigo and Gianni Di Caro ,“「Ant Algorithms for Discrete Optimization」”Artificial Life, MIT Press, 1999,pp1-36

[16] WeixiongZhang and Moshe Looks “「A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones」” Department of Computer Science and Engineering Washington University in Saint Louis Saint Louis, MO 63130, USA pp1-6

[17] Marco Dorigo, L.M. Gambardella “「Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem」” ,IEEE Transactions on Evolutionary Computation,Vol.1, No.1, 1997 pp 1-24

[18] Marco Dorigo, Vittorio Maniezzo, Alberto Colorni “「The Ant System: Optimization by a colony of cooperating agents」” IEEE Transactions on Systems, Man, and Cybernetics–Part B, Vol.26,No.1,1996, pp.1-13

[19]Dorigo, M. and Gambardella, L. M “「Ant colonies for the
traveling salesman problem, 」” ,BioSystems, Vol.43,1997, pp.73-81.

[20]Dorigo, M., Caro, G. D., Gambardella, L. M, “「Ant algorithms for distributed discrete optimization」” Artificial Life Vol.5(2),1999, pp.137–172.

[21] Dorigo M., Bonabeau E., theraulaz G., “「Ant algorithms and
stigmergy」”, Future Generation computer ystems 16 , 2000, pp.889-914..

[22] Gambardella L. M. and Dorigo M.,“「Solving symmetric and
asymmetric TSPs by ant colonies」”, in: Proceedings of the IEEE
International Conference on Evolutionary Computation (ICEC’96),
IEEE Press, Piscataway,1996,pp.622–627.


[23] Jenn-Long Liu ,Enhanced ant colony with rank-based state transition rule for combinatorial optimization problem,二十二屆組合數學與計算理論研討會,2005

[24] Stützle T., and Hoos H.H., 2000, “MAX-MIN Ant System,” Future
Generation computer Systems 16, pp.889-914.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔