臺灣博碩士論文加值系統

旅行推銷員問題(Traveling Salesman Problem, TSP)以往用傳統整數規劃求解時，常遇到問題規模愈大其求解時間呈指數成長，求解時間變得毫無效率。因此，為了提升求解效率，啟發式演算法逐漸受到重視，而著名的啟發式演算法有基因演算法(Genetic Algorithm, GA)、禁忌搜尋法(Tabu Search, TS)、模擬退火法(Simulated Annealing, SA)與蟻群最適化(Ant Colony Optimization, ACO)等。
本研究提出權重型極大-極小螞蟻系統(Weighted Max-Min Ant System, WMMAS)主要以極大-極小螞蟻系統(Max-Min Ant System, MMAS)為基礎而重新建構一套費洛蒙更新機制，其使用全域最適解與疊代最適解兩種資訊，並加入權重的概念，依疊代次數增加而逐漸使權重產生變化，目的為使螞蟻初期以疊代最適解所產生之資訊為主，期望在初期螞蟻能在求解空間中有較寬廣的探索區域，後期則逐漸以全域最適解之資訊為主，繼以在較好的路徑上搜尋探索。
本研究進行8個國際例題測試，其中嘗試結合交換解法求解較大規模的國際例題；WMMAS與MMAS相較，分別在eil51、kroA100與d198減少0.38%、0.17%與0.24%，與其它螞蟻演算法相較，平均解之改善程度皆有提升。WMMAS+3-opt與MMAS+3-opt相較下，其求解績效在各國際例題中皆優於MMAS+3-opt且兩者求解時間上，僅在pcb442與att532例題上差異較大，其它例題則差異略小。

Solving traveling salesman problem (TSP) by integer programming we often spend a lot of time and inefficient when the problem scale to be large. For this reason, in order to improve efficiency the Meta-Heuristics become more important gradually such as Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), and Ant Colony Optimization (ACO), etc.
This study developed a new improved MMAS algorithm Weighted Max-Min Ant System (WMMAS), global best and iteration best are two information been used, and weight are used into pheromone mechanism, it was changed by iteration increasingly. In the initial stage, we expect more width search space, and global best are the major information that leads to a better search space in the final stage.
We uses eight international exemplars for testing in this study, and use exchange method solve large problems. Compare the results between WMMAS and MMAS, in each eil51, kroA100 and d198 reduce 0.38%, 0.17%, 0.24%, and result are compared with the results from other revised algorithms are improved. Compared result with WMMAS+3-opt and MMAS+3-opt, it’s gaps are better than MMAS+3-opt. At solving time, only at pcb442 and att532 difference are bigger, the other are small.

謝誌 I
摘要 II
Abstract III
目錄 IV
圖目錄 VI
表目錄 VII
第一章 緒論 1
1-1 研究動機 1
1-2 研究目的 2
1-3 研究範圍與限制 3
1-4 研究流程 4
第二章 文獻回顧 7
2-1 旅行推銷員問題(Traveling Salesman Problem, TSP) 7
2-2 正確解法(exact procedure) 8
2-3 螞蟻演算法的概念與演進 11
2-3.1 螞蟻系統(Ant System, AS) 13
2-3.2 精英螞蟻系統(Elitist ant system, ASe) 14
2-3.3 分等螞蟻系統(Rank Based Version of the Ant System, ASrank) 15
2-3.4 蟻群系統(Ant colony system) 16
2-3.5 極大-極小螞蟻系統(Max-Min Ant System) 17
2-3.6 小結 21
2-4 區域搜尋演算法(Local Search) 23
第三章 權重型極大-極小螞蟻系統 25
3-1 權重型極大-極小螞蟻系統之簡介 25
3-1.1 權重型極大-極小螞蟻系統變數定義 26
3-1.2 權重型極大-極小螞蟻系統演算流程與說明 27
3-1.3 費洛蒙更新之情境分析 30
3-2 系統環境設定 33
第四章 權重型極大-極小螞蟻系統參數設定 34
4-1 α、β、ρ之參數設定 34
4-2 螞蟻數量之設定 42
4-3 疊代次數之設定 43
第五章 測試結果與討論 46
5-1 權重型極大-極小螞蟻系統之測試 46
5-2 綜合比較分析其它螞蟻演算法之結果 48
5-3 討論 54
第六章 結論與建議 55
6-1 結論 55
6-2 建議 55
參考文獻 56
附錄一、費洛蒙濃度推導 60
附錄二、最大費洛蒙濃度推導 61

中文部份
[1]李泰琳、張靖、卓裕仁，「調適型螞蟻演算法應用於旅行推銷員問題之研究」，運輸學刊，第十九卷第一期，民國九十六年三月，pp.89-120。
[2]陳家和、丁慶榮，「應用螞蟻演算法於時窗限制車輛途程問題之研究」，運輸學刊，第十七卷第三期，民國九十四年九月，pp.261-280。
[3]陳冠樺，民94年，「螞蟻記憶系統應用於旅行推銷員問題」，私立逢甲大學交通工程與管理學系碩士論文。
[4]蕭再安，「作業研究」講義，國立台灣海洋大學。
[5]蘇純繒、翁瑞聰，「以螞蟻群聚最佳化整合噪音擾動法求解TSP問題」，商管科技季刊，第四卷第四期，民國九十二年，pp.359-375。

英文部份
[6]Bullnheimer B., Hartl R. F. and Strauss C., 1997, “A new rank-based version of the ant system: a computational study,” Technical Report POM-03/97, Institute of Management science, University of Vienna.
[7]Bektas T., 2006, “The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures,” Omega, Vol. 34, No. 33, pp.209–219.
[8]Colorni A., Dorigo M., and Maniezzo V., “Distributed optimization by ant colonies,” Proceedings of ECAL91 - European Conference on Artificial Life, Paris, France, 1991, F. Varela and P. Bourgine (Eds.), Elsevier Publishing, pp. 134–142.
[9]Concorde's TSP solver Web Page, http://www.tsp.gatech.edu/concorde/index.html
[10]Dorigo M., Maniezzo V. and Colorni A., 1991, “Positive feedback as a search strategy,” Technical Report 91-016, Dipartimento Elettronica, Politecnico di Milano, Italy.
[11]Dorigo M., Maniezzo V. and Colorni A., (1991a), Ant System: An Autocatalytic Optimizing Process, Dipartimento di Elettronica Informatica, Politecnico di Milano, Italy, Technical Report, No. 91016.
[12]Dorigo M., Maniezzo V. and Colorni A., 1996, “Ant system : Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 26(1), pp.29-41.
[13]Dorigo M. and Gambardella L. M., 1997, “Ant colony system：a cooperative learning approach to the traveling salesman problem, ”IEEE Transactions on Evolutionary Computation, Vol. 1(1), pp.53-66.
[14]Dorigo M. and Gambardella L. M., 1997, “Ant colonies for the traveling salesman problem,” BioSystems, Vol.43, pp.73-81.
[15]Dorigo M., Blum C., “Ant colony optimization theory: A survey,” Theoretical Computer Sicence 344(2005), pp.243–278.
[16]Gambardella L. M. and Dorigo M., 1996, “Solving symmetric and asymmetric TSPs by ant colonies,” in: Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC’96), IEEE Press, Piscataway, pp.622–627.
[17]Hamdy A. Taha (2003), “Operations Research,” Prentice Hall.
[18]Johnson D.S., McGeoch L.A., “The travelling salesman problem: a case study in local optimization,” in: E.H.L. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley, Chichester, UK, 1997, pp. 215–310.
[19]Stutzle T., Hoos H.H., 1997, “The MAX-MIN ant system and local search for the traveling salesman problem.” in Back, T., Michalewicz, Z., Yao, X.(editors), Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC’97), IEEE press, Piscataway, USA, pp.309-314.
[20]Stutzle T, Dorigo M., 1999, ACO Algorithms for the Traveling Salesman Problem, IRIDIA, Universit Libre de Bruxelles, Belgium.
[21]Stutzle T., Hoos H.H., “MAX–MIN ant system and local search for combinatorial optimization problems,” in: S. Voss, S. Martello, I.H. Osman, C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, MA, 1999, pp. 313–329.
[22]Stutzle T., Hoos H.H., 2000, “MAX-MIN Ant System,” Future Generation computer Systems 16, pp.889-914.
[23]Sean R. Eddy, “What is dynamic programming,” Nature Biotechnology 2004, 22, pp.909-910.
[24]TSPLIB Web Page, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/
[25]TSP Cutting-Plane Web Page, http://www.tsp.gatech.edu/methods/opt/cutting.htm