Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19450
標題: 由較佳邊集合引導之基因區域搜尋法 及其應用於解旅行推銷員問題
Promising Edge Set Guided Genetic Local Search Algorithm for the Traveling Salesman Problem
作者: 余家華
Yu, Chia-Hua
關鍵字: Traveling salesman problem;旅行推銷者問題;genetic algorithm;promising edge set guided genetic local search algorithm;LKH algorithm;ANGEL algorithm;基因演算法;由較佳邊集合引導之基因區域搜尋法;LKH演算法;ANGEL演算法
出版社: 資訊科學系所
引用: (1) Books [1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. [2] J.H. Holland, Adaptation in Nature and Artificial Systems, University of Michigan Press. 1975. [3] D. S. Johnson, L. A. McGeoch, “The traveling salesman problem: A case study in local optimization,” in Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, Eds. , New York: Wiley: New York, 1997. [4] E. Lawler, J. K. Lenstra and D. B. Shmoys, The Traveling Salesman Problems: A Guided Tour of Combinatorial Optimization. Wiley, 1985. (2) Journal Articles [5] E. H. L. Aarts and H. P. Stehouwer, “Neural networks and the traveling salesman problem,” Proceedings of the International Conference on Artificial Neural Networks, Springer-Verlag, 1993, pp. 950-955. [6] J. R. A. Allwright, and D. B. Capenter, “A distributed implementation of simulated annealing for the traveling salesman problem,” Parallel Computing, vol. 10, pp. 335-338, 1989. [7] R. Baraglia, J. I. Hidalgo, and R. Perego, “A hybrid heuristic for the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 613-622, December 2001. [8] F. Bock, ‘‘An algorithm for solving traveling-salesman and related network optimization problems,'' unpublished manuscript associated with talk presented at the 14th ORSA National Meeting, 1958. [9] M. Barrie, Baker, and M.A. Ayechew, “A genetic algorithm for the vehicle rounting problem,” Computer and Operational Research., Vol. 30, pp. 787-800, 2003. [10] F. Croce, R. Tadei, And G. Volta, “A genetic algorithm for the job shop problem,” Computers and Operational Research., Vol. 22, pp. 15-24, 1995. [11] N. Christofides, ‘‘Worst-case analysis of a new heuristic for the traveling salesman problem,'' Report No. 388, GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1976. [12] G. Clarke AND J. W. Wright, ‘‘Scheduling of vehicles from a central depot to a number of delivery points,'' Operations Research, vol. 12, pp. 568-581, 1964. [13] G. A. Croes, ‘‘A method for solving traveling salesman problems,'' Operations Research , vol. 6, pp. 791-812, 1958. [14] M. 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, pp. 53-66, April 1997. [15] R. Durbin, R. Szeliski, and A. Yuille, “An analysis of the elastic net approach to the traveling salesman problem,” Neural Computation, vol. 1, pp. 348-358, 1989. [16] L. Fiechter, “A parallel Tabu search algorithm for large traveling salesman problems,” Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, vol. 51, pp. 243-267, 1994. [17] B. Freisleben and P. Merz, ‘‘A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems,'' Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, 1996. [18] B. Freisleben and M. Schulte. “Combinatorial optimization with parallel adaptive threshold accepting”. Proceedings of the 1992 European Workshop on Parallel Computing, Barcelona, IOS Press, 1992, pp. 176-179. [19] L. M. Gambardella and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem," Proceedings of the Twelfth International Conference on Machine Learning, 1995, pp. 252-260. [20] K. Helsgaun, “An effective implementation of the Lin-Kernighan traveling salesman heuristic,” European Journal of Operations Research, vol. 126, pp. 106-130, 2000. [21] L. Homaifar, C. Guan, and G. Liepins, “A new approach to the traveling salesman problem by genetic algorithms," Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, 1993, pp. 460-466. [22] O. Jellouli, E. Chatelet, “A dynamic programming approach to sequencing problems,” SLAM Review.10, pp.196-210, 2000. [23] S. Lin, ‘‘Computer solutions of the traveling salesman problem,'' Bell System Technical Journal, vol. 44, pp. 2245-2269, 1965. [24] S. Lin , B. W. Kernighan, ‘‘An effective heuristic algorithm for the traveling-salesman problem,'' Operations Research, vol. 21, pp. 498-516, 1973. [25] P. Merz and B. Freisleben, ‘‘Genetic local search for the TSP: New results,'' Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, 1997. [26] J. W. Pepper, B. L. Golden, and E. A. Wasil, “Solving the traveling salesman problem with annealing-based heuristics: a computational study,” IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol. 32, no. 1, pp. 72-77, January 2002. [27] J. Perttunen, “On the significance of the initial solution in traveling salesman heuristics,” Journal of the Operational Research Society, vol. 45, pp. 1131-1140, 1994. [28] G. Reinelt, “TSPLIB - A traveling salesman problem library,” ORSA Journal of Computing, vol. 3, no. 4, pp. 376-384, 1991. [29] T. Starkweather, D. Whitley, C. Whitley, K. Mathial, “A comparison of genetic sequencing operators,” Proceedings of the 4th International Conference on Genetic Algorithm, Morgan Kaufmann, 1991, pp. 69-76. [30] L. Y. Tseng and S. C. Liang, “A Hybrid Metaheuristic and Its Application to the Traveling Salesman Problem,” Submitted to IEEE Transactions on Evolutionary Computation. (Revised) (SCI), 2007. [31] T. Volgenant, R. Jonker , ”A branch and bound algorithm for the symmetric traveling salesmane problem based on the 1-tree relaxation,” European Journal of Operational Research.9, pp. 83-89,1982.
摘要: 
旅行推銷員問題(Traveling Salesman Problem ; TSP)為典型的組合最佳化(Combinatorial Optimization )問題之一。自西元1930年以來,它便吸引許多不同領域的學者投入研究,然而TSP問題已被證明是NP-hard問題,因此如何發展出在有限時間內能找出全域最佳解(global optimum)的方法,便是研究學者的最大挑戰。近年來的研究中,發現可利用TSP問題修正過之邊成本結合最小生成樹的規則來取得一些的較佳邊,稱為較佳邊集合,在過去研究中利用了較佳邊集合來加速求解過程中的有效收斂,但較為可惜的是,過去研究並無針對較佳邊集合的特性作進一步的利用。
因此本論文結合較佳邊集合與基因區域搜尋法以期能有效應用於求解TSP問題的研究上,且透過較佳邊集合能夠有效連結全域搜尋與區域搜尋的合作機制,使其兩者達到更完善的搜尋效果與求解品質。本論文採用TSPLIB[28]題庫之35題來測試本研究提出的基因區域搜尋法。在測試結果發現,本研究的基因區域搜尋法相較於目前表現較佳的LKH[20]演算法與ANGEL[30]演算法,有相當不錯的求解品質與效能表現。

The traveling salesman problem is an important combinatorial optimization problem. Since 1930, many researchers had been devoting their efforts in solving this problem. Being an NP-hard problem, the traveling salesman problem is unlikely to be solved in polynomial time. Hence a main research issue is to design efficient algorithms to find near optimal solutions for the TSP. In recent studies, the collection of promising edges by deriving the edges of the minimum spanning trees had been proposed. But the promising edges were not fully utilized in previous studies. In the thesis, we used the promising edge set to guide the search of a genetic local search algorithm. First, the promising edge set was generated by iteratively generating the minimum spanning trees.
Then, the promising edge set was used to guide the genetic local search algorithm in searching the promising areas. Furthermore, the promising edge set will evolve along the search. The proposed algorithm was tested on 35 instances taken from TSPLIB[28]. The experimental results revealed that the solution quality of the proposed algorithm is similar to that of the ANGEL[30] and is better than that of the LKH[20].
URI: http://hdl.handle.net/11455/19450
其他識別: U0005-1907200716185600
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.