最大完全子圖問題是一個經典且眾所皆知的組合最佳化問題，其已被證實為NP-hard難題。完全子圖為圖G={V,E}中的一個子圖，在此完全子圖中的每點之間均相鄰。最大完全子圖問題的目標即是在一個任意圖形中尋找頂點數最多的完全子圖。在本篇論文中，我們提出一個基於基因演算法概念的演算法，解決任意圖形中找尋最大完全子圖問題，稱為MCGA演算法。在MCGA演算法中，我們改進Sakamoto等人提出的解碼方法使其能更有效率地解碼染色體，並且設計一個合適的交配運算子來擴大解的搜尋範圍。此外，為了更進一步提升解的多樣性，本文採用多基因池的概念獨立執行MCGA演算法。最後，我們所提出的演算法成功的解決了大部分DIMACS benchmark和BHOSLIB benchmark的基準圖。經由實驗結果數據顯示，我們提出的演算法在所有測試的基準圖上都能找到最佳解，且平均解集合的大小比其他有效的演算法來的好。

The maximum clique set problem is a classical and well-known combinatorial optimization problem, and it has been proved to be NP-hard. A clique of a graph G= (V,E) is a subset S⊆V such that every two vertices in S are connected by an edge. The purpose of the maximum clique set problem is to find a clique of G with the largest cardinality of vertices. In this thesis, we propose a genetic algorithm for the maximum clique problem, called MCGA. In MCGA, we improve the method by Sakamoto et al. to efficiently decode chromosomes and design a suitable crossover to expand the search space of solutions. Furthermore, to further increase the diversity of solutions, we adopt the idea of many gene pools to execute MCGA independently. Finally, our algorithm successfully solves most instances from the DIMACS benchmark graphs and the BHOSLIB benchmark graphs. The results of our empirical tests show that our algorithm can find the optimal solution in all test benchmark graphs and the average size of solutions is better than other efficient algorithms in most cases.

[1]E. Aarts and J. Korst, Simulated annealing and boltzmann machines, Chichester, UK: J. Wiley and Sons (1989).
[2]D.V. Andrade, M.G.C Resende and R.F. Werneck, “Fast local search for the maximum independent problem”, Journal of Heuristics, 18, 4 (2012), pp. 525-547.
[3]BHOSLIB benchmark set, http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-be
nchmarks.htm
[4]T. Back and S. Khuri, “An evolutionary heuristic for the maximum independent set problem”, Proceedings of the First IEEE Conference on Evolutionary Computation , 2 (1994), pp.531-535.
[5]T. Back, Evolutionary algorithms in theory and practice, Oxford University Press, New York (1996).
[6]E. Balus and C.S. Yu, “Finding a maximum clique in an arbitrary graph”, SIAM Journal of Computing, 15, 4 (1986), pp.1054-1068.
[7]R. Battiti and G. Tecchiolli, “The reactive tabu search”, ORSA Journal on Computing, 6, 2 (1994), pp.126-140.
[8]R. Battiti and M. Protasi, “Reactive local search for the maximum clique problem”, Algorithmica, 29, 4 (2001), pp. 610-637.
[9]R. Battiti and F. Mascia, “Reactive and dynamic local search for the max-clique: engineering effective building blocks”, Computers and Operations Research, 37, 3 (2010), pp.534-542.
[10]P. Berman and A. Pelc, “Distributed probabilistic fault diagnosis for multiprocessor systems”, Proceeding of the 20th International Symposium on Fault-Tolerant Computing, Newcastle, UK (1990), pp.340-346.
[11]S. Busygin, “A new trust region technique for the maximum weight clique problem”, Discrete Applied Mathematics, 154 (2006), pp.2080-2096.
[12]R. Carter and K. Park, “How good are genetic algorithms at finding large cliques: an experimental study”, Computer Science Department, Boston University, Tec. Rep. BU-CS-93-015 (1993).
[13]P.C. Chang, W.S. Huang and C.J. Ting, “Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems”, Expert Systems with Application, 37, 3 (2010), pp.1863-1878.
[14]DIMACS benchmark set, http://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-
benchmark.
[15]D.-C. Dang and A. Moukrim, “Subgraph extraction and metaheuristics for the maximum clique problem”, Journal of Heuristics, 18 (2012), pp. 767-794.
[16]T.A. Feo, M.G.C. Resende and S.H. Smith, “A greedy randomized adaptive search procedure for maximum independent set”, Operations Reacher, 42, 5 (1994), pp.860-878.
[17]M.R. Garey and D.S. Johnson, Computers and intractability, Freeman, San Francisco, CA (1979).
[18]M. Gen and R. Cheng, Genetic algorithms and engineering design, New York: Wiley (1997).
[19]X. Geng, J. Xu, J. Xiao and L. Pan, “A simple simulated annealing algorithm for the maximum clique problem”, Information Sciences, 177 (2007), pp.5064-5071.
[20]D. Goldberg and R. Lingle, “Alleles, loci and the traveling salesman problem”, Proceedings of the First International Conference on Genetic Algorithms (1985), pp.154-159.
[21]D.E. Goldberg, Genetic algorithms in search, optimization and machine learning, Addison Wesley, New York (1989).
[22]F. Harary and I.C. Ross, “A procedure for clique detection using the group matrix”, Sociometry , 20, 5 (1957), pp. 205-215.
[23]J.H. Holland, Adaptation in natural and artificial systems, The University Michigan Press, Ann Arbor (1975).
[24]B. Haung, “Finding maximum clique with a genetic algorithm”, Penn State Harrisburg Master’s Thesis in Computer Science (2002).
[25]A. Jagota and L.A. Sanchis, “Adaptive, restart, randomized greedy heuristics for maximum clique”, Journal of Heuristics, 7 (2001), pp. 565-585.
[26]M.M. Javidi and S. Mehrabi, “On evolutionary algorithms for maximum independent set problem”, Journal of Artificial Intelligence : Theory and Application, 1, 2 (2010), pp.54-59.
[27]K. Katayama, A. Hamamoto and H. Narihisa, “An effective local search for the maximum clique problem”, Information Processing Letters, 95, 5 (2005), pp.503-511.
[28]S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, “Optimization by simulated annealing”, Science, 220 (1983), pp.671-680.
[29]J. Konc and D. Janezic, “An improved branch and bound algorithm for the maximum clique problem”, MATCH Communications in Mathematical and in Computer Chemistry, 58 (2007), pp. 569-590.
[30]R. Kopf and G. Ruhe, “A computational study of the weighted independent set problem for general graphs”, Foundations of Control Engineering, 12, 4 (1987), pp. 167-180.
[31]F.J. MacWilliams and N.J.A. Sloane, The theory of error correcting codes, North-Holland, Amsterdam (1979).
[32]K.F. Man, K.S. Tang and S. Kwong, “Genetic algorithms: concepts and applications”, IEEE Transactions on Industrial Electronics, 43, 5 (1996), pp.519-534.
[33]E. Marchiori, “A simple heuristic based genetic algorithm for the maximum clique problem”, Procedings of the ACM Symposium on Applied Computing (1998), pp.366-373.
[34]N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, “Equation of state calculations by fast computing machines”, Journal of Chemical Physics, 21, 6 (1953), pp.1087-1092.
[35]P.M. Pardalos and G.P. Rodgers, “A branch and bound algorithm for the maximum clique problem”, Computer & Operations Research, 19, 5 (1992), pp. 363-375.
[36]P.M. Pardalos and J. Xue, “The maximum clique problem”, Journal of Global Optimization, 4, 3 (1994), pp. 301-328.
[37]P.A. Pevzner and S.H. Sze, “Combinatorial approaches to finding subtle signals in DNA sequences”, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology (2000), pp.269-278.
[38]W. Pullan and H.H. Hoos, “Dynamic local search for the maximum clique problem”, Journal of Artificial Intelligence Research, 25, 1 (2006), pp.159-185.
[39]S. Ronald, “Distance functions for order-based encoding”, IEEE International Conference on Evolutionary Computation, Adelaide, SA (1997), pp.49-54.
[40]A. Sakamoto, X. Liu and T. Shimamoto, “A genetic algorithm for maximum independent set problems”, IEEE International Conference on Systems, Man, and Cybernetics, 3 (1996), pp.1916-1921.
[41]A. Singh and A.K. Gupta, “A hybrid heuristic for the maximum clique problem”, Journal of Heuristics, 12 (2006), pp. 5-22.
[42]A. Taranenko and A. Vesel, “An elitist genetic algorithm for the maximum independent set problem”, Proceedings of the 23rd International Conference on Information Technology Interfaces, 1 (2001), pp.373-378.
[43]E. Tomita and T. Seki, “An efficient branch-and-bound algorithm for finding a maximum clique”, Discrete Mathematics and Theoretical Computer Science, 2731 (2003), pp. 278-289.
[44]E. Tomita, Y. Sutani, T. Higashi, S. Takahashi and M. Wakatsuki, “A simple and faster branch-and-bound algorithm for finding a maximum clique”, WALCOM: Algorithms and Computation, 5942 (2010), pp. 191-203.
[45]N. Wang and L. Shi, “A discrete particle swarm optimizer for finding a maximum clique”, Journal of Dalian Nationalities University (2005).
[46]Q. Wu and J.K. Hao, “An adaptive multistart tabu search approach to solve the maximum clique problem”, Journal of Combinatorial Optimization, 26, 1 (2013), pp.86-108.
[47]X.S. Xu and J. Ma, “An efficient simulated annealing algorithm for the minimum vertex cover problem”, Neurocomputing, 69 (2006), pp.913-916.
[48]X. Xu, J. Ma and J. Lei, “An improved ant colony optimization for the maximum clique problem”, Proceedings of the Third International Conference on Natural Computation, 4 (2007).
[49]Q. Zhang, J. Sun and E. Tsang, “An evolutionary algorithm with guided mutation for the maximum clique problem”, IEEE Transactions on Evolutionary Computation, 9, 2 (2005), pp.192-200.