跳到主要內容

臺灣博碩士論文加值系統

(44.200.140.218) 您好!臺灣時間:2024/07/14 19:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:胡裕宏
研究生(外文):Yu-Hung Hu
論文名稱:發展啟發式之蟻行演算法及其應用於旅行銷售員問題
論文名稱(外文):Development of Heuristic Ant Colony Optimization Applied to Traveling Salesman Problem
指導教授:劉振隆劉振隆引用關係
指導教授(外文):Jenn-Long Liu
學位類別:碩士
校院名稱:立德管理學院
系所名稱:應用資訊研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:78
中文關鍵詞:蟻行演算法旅行銷售員問題組合最佳化問題
外文關鍵詞:Traveling Salesman ProblemCombinatorial Optimization ProblemsAnt Colony Optimization(ACO)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:427
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
基於螞蟻族群系統(Ant Colony System Optimization, ACS)的設計原理,我們在本文中提出一個名為 NNPACS (Nearest Neighbor Procedure Ant Colony System) 的螞蟻族群系統優化方法。NNPACS 與ACS 二者之間最大的差異在於建構問題解的過程中所使用之方法有所不同。前者係以最鄰近法(Nearest Neighbor Procedure)路徑選擇策略為基礎,而後者則是以機率決策的方式產生問題解。以求解旅行銷售員問題 (Traveling Salesman Problem, TSP) 為效能評估的基準,實驗結果顯示 NNPACS 在效能上的表現優於傳統的螞蟻演算方法。
本研究主要之目的在於:對蟻群最佳化進行深入之研究,除了詳實探討蟻行演算法的特性外,也針對各項參數的組合問題提出了測試與分析。在本文中,將討論如何設計一個蟻行演算法(Ant Colony Optimization Algorithm, ACO Algorithm) 用來解決旅行推銷員問題(Traveling Salesman Problem)。設計蟻行演算法主要可分為下列四個部份討論: 1. 以最鄰近法(Nearest Neighbor Procedure)為基礎改善ACS建構路線的可行解,2. 計算啟發法權值的方法(Heuristic Value),3. 螞蟻搜尋解的方法(Solution Construction),4. 更新費洛蒙的方法(Pheromone Update)。
本研究希望利用蟻行演算法廣度搜尋的特點為基礎,結合最鄰近法(Nearest Neighbor Procedure)的啟發式方法,提出一套改良式的最鄰近蟻行演算法(Nearest Neighbor Procedure Ant Colony System, NNPACS),以提高其求解效率。此改良式蟻行演算法保留了蟻行演算法記錄歷史資訊的精神,嘗試將最鄰近法(Nearest Neighbor Procedure)導入到 ACS 的搜尋移動機制中,以取代原先的方法。此外,本研究也增加了鄰域搜尋(Neighborhood Search)的執行頻率,以強化蟻行演算法的深度搜尋弁遄C最後,在螞蟻搜尋過程,由於容易落入局部解當中,所以本研究利用隨機制度將每回第一隻螞蟻行走選擇制度作調整,避免蟻行演算法易掉入區域解的缺點。
On the basis of the Ant Colony System Optimization (ACS) theorem, this study has proposed an evolving method known as the NNPACS (Nearest Neighbor Procedure Ant Colony System). The most significant differences between NNPACS and ACS are the methods being adopted in the process of solving structural problems. The former has applied Nearest Neighbor Procedure as the foundation of its strategy selection, while the latter used probability decision theory to generate solutions. In seeking the solution on the Traveling Salesman Problem (TSP) as the criterion for effective evaluation, the findings have shown that NNPACS has better effectiveness than traditional ACS.
The objective of this study is to conduct further research into NNPACS to investigate the characteristics of ACO Algorithm, as well as to conduct test and analysis for each parameter in combinatorial problems. This study will discuss how to devise an Ant Colony Optimization Algorithm (ACO Algorithm) to solve the Traveling Salesman Problems. The ACO Algorithm can be categorized mainly into four aspects for discussion: (1) adopting the Nearest Neighbor Procedure as the basis to improve the feasible solution for ACS’ construction route; (2) the method for calculation of the Heuristic Value; (3) the method for searching of Solution Construction and (4) the method for Pheromone Update.
This study proposed an improved Nearest Neighbor Procedure Ant Colony System (NNPACS) to raise the efficiency for solution by combining the heuristic method of the Nearest Neighbor Procedure, by capitalizing on the ACO Algorithm’s characteristics of widespread search as foundation. While the NNPACS has preserved ACS’ spirit of recording historic data, it has tried to convert the Nearest Neighbor Procedure into a search mobility mechanism of ACS to replace the original method. Moreover, this study has also increased the frequency count of the Neighborhood Search to consolidate the depth search function of ACO Algorithm. Finally, owing to the tendency of being trapped into local solution during the search process, this study, therefore, has applied the random system to adjust the movement selection system of the first ant to prevent ACO Algorithm being trapped into the flaw of the local solution.
中文摘要.........................................I
英文摘要........................................II
誌謝...........................................III
目錄............................................IV
表目錄..........................................VI
圖目錄.........................................VII
第一章 緒論.....................................1
1.1 研究背景與動機...............................3
1.2 研究目的.....................................5
1.3 研究問題.....................................6
1.4 論文架構.....................................6
1.5 研究範圍與限制...............................8
1.6 研究流程....................................10
第二章 文獻探討................................11
2.1 旅行銷售員問題..............................11
2.1.1 TSP之定義.................................11
2.1.2 TSP之數學模式.............................12
2.1.3 TSP問題求解法.............................13
2.2 傳統啟發式解法..............................13
2.3 模擬退火法..................................17
2.4 門檻接受法..................................20
2.5 禁忌搜尋法..................................21
2.6 基因演算法..................................24
2.7 螞蟻演算法..................................27
2.7.1覓食原理...................................27
2.7.2螞蟻理論(Ant Theory).......................33
2.7.3螞蟻群體系統(Ant Colony System, ACS).......35
2.8 小結........................................38
第三章 研究方法與流程..............................................40
3.1 基本架構..............................................40
3.2 螞蟻系統..............................................41
3.3 最鄰近法蟻群系統..............................................43
3.4 設計方法....................................45
3.5 狀態轉換法則..............................................47
3.6 ACO的參數定義..............................................50
3.6.1 利用(Exploitation)和探索(Exploration)之間的平衡問題..............................................50
3.6.2 全域更新(Global Updating)與菁英策略(Elitist Strategy)......................................51
3.6.3 區域更新(Local Updating)......................................51
3.6.4 貪婪法則參數β的設定..............................................51
3.7 研究流程..............................................52
第四章 範例測試與結果分析..............................................53
4.1 測試例題..............................................53
4.2 測試結果..............................................54
4.3 效能分析....................................72
第五章 結論與建議...............................73
5.1 結論................................................73
5.2 後續研究建議................................74
參考文獻........................................75
[1] Holland, J.H., Adaptation in Natural and Artificial Systems, Univ. of Michigan Press,Ann Arbor, 1975.
[2] Aarts, E. and Korst, J., Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, John Wiley & Sons Ltd., New York, 1989.
[3] Hao Chen, Nicholas S. Flann, and Daniel W.Watson, "Paeallel Genetic Simulated Annealing: a Massively Parallel SIMD Algorithm," IEEE Trans. on Parallel and Distributed Systems, Vol. 9, No. 2, pp. 126-136, February 1998.
[4] Dorigo, M., and Stützle, T., ”The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” Technical Report IRIDIA, 2000.
[5] Karp, R., “Reducibility among Combinatorial Problem”,Complexity of Computer Computations, Plenum Press, pp. 85-104, 1972.
[6] Maniezzo, V. and Colorni, A., "The Ant System Applied to the Quadratic Assignment Problem," IEEE Trans. on Knowledge and Data Engineering, Vol. 11, No. 5, pp. 769-778, September/October 1999.
[7] Van Laarhoven, P.M.J., Aarts, E.H.L., Simulated Annealing: Theory and Applications. Reidel Publishing Company, 1987.
[8] Goldberg D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA, 1989.
[9] Glover F. and Laguna M., Tabu search. Boston: Kluwer Academic Publishers, 1997.
[10] Bonabeau, E., Dorigo, M. and Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems, Oxford, 1999.
[11] Dorigo, M., Maniezzo, V. and Colorni, A., Positive feedback as a search strategy. Technical Report No. 91-016, Politecnico di Milano, Italy, 1991.
[12] Maniezzo V., Colorni A., Dorigo M., The Ant System applied to the quadratic assignment problem, Technical Report IRIDIA/94-28, IRIDIA, Université Libre de Bruxelles, Belgium, 1994.
[13] Dorigo, M. and Gambardella, L. M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997.
[14] Araüjo, F., Ribeiro, B. and Rodrigues, L., “A Neural Network for Shortest Path Computation,” IEEE Transactions on Neural Network, Vol. 12, No. 5, pp.1067-1073, 2001.
[15] Dorigo, M., Maniezzo, V., and Colorni, A., “Ant System: Optimizatoin by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics - Part B, Vol.26-1, pp.29-41, 1996.
[16] Yoshiike, N. and Takefuji, Y., “Vehicle Routing Problem Using Clustering Algorithm by Maximum Neural Networks,” The Second International Conference on Intelligent Processing and Manufacturing of Materials, Vol. 2, pp.1109 –1113., 1999.
[17] Merkle, D., Middendorf, M. and Schmeck, H., "Ant Colony Optimization for Resource-Constrained Project Scheduling," IEEE Trans. on Evolutionary Computation, Vol. 6, No. 4, pp. 333-346, August 2000.
[18] Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. N., “An analysis of Several Heuristics for the Traveling Salesman Problem”, SLAM Journal on Computing, Vol. 6, pp. 563-581, 1977.
[19] Gutin, G. and Punnen, A. P., The Traveling Salesman Problem and Its Variations, Springer, 2002.
[20] Flood, M. M., “The Traveling Salesman Problem”, Operations Research, Vol. 4, pp. 61-75, 1956.
[21] Althofer, I. And Koschnick, K. U., “On the convergence of threshold accepting”, Applied Mathematics and Optimization, Vol. 24, pp. 183-195, 1991.
[22] Tian, P., Ma, J. and Zhang, D. M., “Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property : an investigation of generation mechanism”, European Journal of Operational Research, 118, pp. 81-94, 1999.
[23] 楊智凱,“以門檻接受法改善TSP 及VRP 網路成本之研究”, 交通大學土木工程研究所碩士論文, 1995。
[24] Abbound, N., Sakawa, M. and Inuiguchi, M., “School scheduling using threshold accepting”, Cybernetic and Systems, Vol. 29, pp. 593-611, 1998.
[25] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., “The Traveling Salesman Problem”, John Wiley & Sons Ltd., New York, 1985.
[26] Osman, I. H. and Kelly, J. P., “Meta-Heuristics: An Overview, ” In I. H. Osman and J. P. Kelly, editors, Meta-Heuristics: Theory and Applications, pp. 1-21, Kluwer, Boston, 1996.
[27] Norback, J. P. and Love, R. F., “Geometric approaches to solving the traveling salesman problem”, Management Science, Vol. 23, pp. 1208-1223, 1977.
[28] Norback, J. P. and Love, R. F., “Heuristic for the Hamiltonian path problem in Euclidean two space”, Journal of Operations Research Society, Vol. 30, pp. 363-368, 1979.
[29] Lin, S., “Computer solutions of the traveling salesman problem”, The Bell System Technical Journal, Vol. 44, pp. 2245-2269, 1965.
[30] Or, I., “Traveling salesman-type Combinatorial Problems and Their Realation on the Logistics of regional Blood Banking”, Ph. D. Dissertation, Northwestern University, 1976.
[31] Lin, S. and Kernighan, B. W., “An effective heuristic algorithm for the traveling salesman problem”, Operations Research, Vol. 21, pp. 498-516, 1973.
[32] Anily, S and Federgruen, A., “Ergodicity in parameter nonstationary markov chains: an application to simulated annealing methods”, Operations Search, Vol. 35, pp. 867-874, 1987.
[33] Aarts, E. H. L., De Bont, F. M. J., Habers, E. H. A. and Van Laarhoven, P. J. M., “Statistical cooling: a general approach to combinatorial optimizations”, Philips Journal of Research, Vol. 4, pp. 193-226, 1985.
[34] Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P., “Optimization by simulated annealing”, Science, 200(4956), pp.671-680, 1983.
[35] Lundy, M. and Mees, A., “Convergence of an annealing algorithm”, Mathematical Programming, Vol. 34, pp. 111,124, 1986.
[36] Penna, T. J. P., “Traveling salesman problem and Tsallis statistics”, Physical Review E, Vol. 51, pp. R1-R3, 1995.
[37] Kirkpatrick, S., “Optimization by simulated annealing: quantitative studies”, Journal of Statistical Physics, Vol. 34, pp. 975-986, 1984.
[38] Cerny, V., “Thermodynamical approach to the traveling salesman problem : an efficient simulated annealing”, Journal of Optimization Theory and Application, Vol. 45, pp. 41-51, 1985.
[39] Tasllis, C., “Possible generalization of Boltzmann-Gibbs statistics”, Journal of Statistical Physics, Vol. 52(1/2), pp. 479-487, 1988.
[40] Dueck, G. and Scheuer, T., “Threshold accepting : a general purpose optimizatiom algorithm appeared superior to simulated annealing”, Journal of Computational Physics, Vol. 90, pp. 161-175, 1990.
[41] 韓復華、楊智凱、卓裕仁, “應用門檻接受法求解車輛路線問題之研究”, 運輸計劃季刊, Vol. 26, No. 2, pp. 253-280, 1997。
[42] Glover, F., “Future Paths for Integer Programming and Links to Artificial Intelligence”, Computers and Operation Research, Vol. 13, No. 5, pp. 533-549, 1986.
[43] 徐俊能、宋明弘, “以遺傳基因演算法則解決多目標考量的推銷員旅行問題之研究”, 大葉大學事業經營研究所碩士論文, 1993。
[44] 曾國雄、王日昌、黃明居, “以基因演算法與樣板路徑求解旅行推銷員問題”, 運輸計劃季刊, Vol. 25, No. 3, pp. 493-516, 1996。
[45] Dorigo, M., Maniezzo, V. and Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No. 1, pp.1-13, 1996.
[46] Dorigo, M., and Gambardella, L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1,No. 1, pp.53-66, 1997.
[47] Dorigo, M., Maniezzo, V. and Colorni, A., “Positive feedback as a search stratey, ” Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top