Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19507
標題: 利用多軌跡搜尋法解最大完全子圖問題
Multiple Trajectory Search for the Maximum Clique Problem
作者: 陳柏宇
CHEN, PO-YU
關鍵字: Tabu Search;禁制搜尋法;metaheuristics;multiple trajectory search;maximum clique problem;超啟發式搜尋法;多軌跡搜尋法;最大完全子圖問題
出版社: 資訊科學與工程學系所
引用: [1]. R. Battiti, M. Protasi, “Reactive Local Search for the Maximum Clique Problem,” Algorithmica, vol.29, pp.610–637, 2001. [2]. R. Carraghan, P. M. Pardalos, “An exact algorithm for the maximum clique problem,” Operation Research Letters, vol.9, pp.375–382, 1990. [3]. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. [4]. M. Gendreau, P. Soriano, L. Salvail, “Solving the maximum clique problem using a tabu search approach,” Annals of Operations Research, vol.41, pp.385-403, 1993. [5]. X. Geng, J. Xu, J. Xiao, L. Pan “A Simple simulated annealing algorithm for maximum clique problem,” Information Sciences, pp.5064-5017, 2007. [6]. F. Glover, “Tabu search, Part 1”, ORSA Journal on Computing, pp.190-206, 1989. [7]. F. Glover, “Tabu search, Part 2”, ORSA Journal on Computing, pp.4-32, 1990. [8]. A. Grosso, M. Locatelli, “Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem,” Journal of Heuristics, vol.10, pp.135–152, 2004. [9]. P. Hansen, N. Mladenovic, “Two algorithms for maximum cliques in dense graphs”, Technical Report GERAD Research Report G-92-18, 1992. [10]. P. Hansen, N. Mladenovic, D. Urosevic, “Variable neighborhood search for the maximum clique,” Discrete Applied Mathematics, vol.145, pp.117-125, 2004. [11]. P. R. J. Ostergard, “A fast algorithm for the maximum clique problem,” Discrete Applied Mathematics, vol.120, pp.197-207, 2002. [12]. L. A. Sanchis, “Adaptive Restart Randomized Greedy Heuristics for Maximum Clique,” Journal of Heuristics, vol.7, pp.565–585, 2001. [13]. P. Soriano, M. Gendreau, “Diversification strategies in tabu search algorithms for the maximum clique problem,” Annals of Operations Research, vol.63, pp.189-207, 1996. [14]. X. Xu, J. Ma, J. Lei, “An Improves Ant Colony Optimization for the maximum clique problem,” Proceedings of the Third International Conference on Natural Computation, August 27-27,2007,China, pp.766-770 , IEEE, ICNC 2007. [15]. Q. Zhang, J. Sun, E. Tsang, “An Evolutionary Algorithm With Guided Mutation for the Maximum Clique Problem,” IEEE Transactions on Evolutionary Computation, vol.9, no.2, pp.192-200, 2005. [16]. 楊震禹(2005)。一個解最大完全子圖問題之超啟發式演算法。(碩士論文,中興大學,2005)。
摘要: 
本研究的目的是以多軌式搜尋法Multiple Trajectory Search ,以下簡稱為MTS,來解決最大完全子圖問題,最大完全子圖問題在圖論中是著名的NP-hard問題,並且長期以來受到許多學者的注意。並且最大完全子圖問題已被證明是個NP-hard問題,一般來說普通的演算法只能夠解決規模較小的題目。近幾年來,超啟發式演算法被用來解決NP問題,主要的目的就是在此類型的問題中找到最佳的或是接近最佳解的解,而我們提出的多軌式搜尋法演算法也是超啟發式演算法的一種。
我們所提出的多軌跡式搜尋法主要結構可以分為上層與底層。在上層的搜尋中,我們嘗試著在較大的鄰域結構中找出解,於上層的搜尋結構中將會包含底層的搜尋,而底層的搜尋是在較小的鄰域結構中找出解。
我們利用多軌式搜尋法來解DIMACS所公布的80個問題,並在論文中列出實驗的結果。利用多軌式搜尋法來解最大完全子圖問題,除了在 brock和C 題組之外,效能都相當的不錯。

The Multiple Trajectory Search (MTS) for solving the maximum clique problem is proposed in this thesis. The maximum clique problem is a famous NP-hard problem in the graph theory and has attracted much attention of researches for a very long period. Since this problem is NP-hard, exact algorithms in general can solve only small-sized instances. In recent years, metaheuristics were proposed to find optimal or near-optimal solutions of this problem. The multiple trajectory search is also a metaheuristic method. It is constituted by an upper level search and a lower level search. The upper level search tries to search a large neighborhood of a solution and this search of large neighborhood is based on the lower level search that searches a small neighborhood.
The experimental results of applying the multiple trajectory search to the eighty problems presented by DIMACS were reported. The performance of the multiple trajectory search for the maximum clique problem is good except the brock and C benchmarks.
URI: http://hdl.handle.net/11455/19507
其他識別: U0005-0701200910360000
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


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