An addicted random key genetic algorithm applied to the maximum click problem
Abstract
The maximum clique problem consists of finding the largest subgraph within a given graph. This problem is well known in the field of Operational Research and has several applications in our daily life. In this work, we propose solving the maximum clique problem making use a mathematical solver and the well-known BRKGA metaheuristic. To validate our proposals, we used a set of test-problems that are available on-line in the literature. The BRKGA proved to be very efficient in solving the approached problems, and competitive with the mathematical solver used.
Keywords:
Click problem, genetic algorithm, random keys
References
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6:154–160.
Bomze, I. M., Budinich, M., Pardalos, P. M., and Pelillo, M. (1999). The maximum clique problem. In Handbook of combinatorial optimization, pages 1–74. Springer.
Chaves, A. A., Lorena, L. A. N., Senne, E. L. F., and Resende, M. G. (2016). Hybrid method with cs and brkga applied to the minimization of tool switches problem. Computers & Operations Research, 67:174–183.
Erd¨os, P. and Szekeres, G. (1935). A combinatorial problem in geometry. Compositio mathematica, 2:463–470.
Goldbarg, M. and Goldbarg, E. (2012). Grafos: Conceitos, algoritmos e aplicac¸ ˜oes. Elsevier.
Goldberg, D. E. and Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3:95–99.
Gonc¸alves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17:487–525.
Konc, J. and Janezic, D. (2007). An improved branch and bound algorithm for the maximum clique problem. proteins, 4(5).
Luce, R. D. and Perry, A. D. (1949). A method of matrix analysis of group structure. Psychometrika, 14(2):95–116.
Martinez, C., Loiseau, I., Resende, M. G. C., and Rodriguez, S. (2011). Brkga algorithm for the capacitated arc routing problem. Electronic Notes in Theoretical Computer Science, 281:69–83.
Spears, W. M. and De Jong, K. D. (1995). On the virtues of parameterized uniform crossover. Technical report, DTIC Document.
Toso, R. F. and Resende, M. G. C. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30:81–93.
Zudio, A., da Silva Costa, D. H., Masquio, B. P., Coelho, I. M., and Pinto, P. E. D. (2018).
Brkga/vnd hybrid algorithm for the classic three-dimensional bin packing problem. Electronic Notes in Discrete Mathematics, 66:175–182.
Bomze, I. M., Budinich, M., Pardalos, P. M., and Pelillo, M. (1999). The maximum clique problem. In Handbook of combinatorial optimization, pages 1–74. Springer.
Chaves, A. A., Lorena, L. A. N., Senne, E. L. F., and Resende, M. G. (2016). Hybrid method with cs and brkga applied to the minimization of tool switches problem. Computers & Operations Research, 67:174–183.
Erd¨os, P. and Szekeres, G. (1935). A combinatorial problem in geometry. Compositio mathematica, 2:463–470.
Goldbarg, M. and Goldbarg, E. (2012). Grafos: Conceitos, algoritmos e aplicac¸ ˜oes. Elsevier.
Goldberg, D. E. and Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3:95–99.
Gonc¸alves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17:487–525.
Konc, J. and Janezic, D. (2007). An improved branch and bound algorithm for the maximum clique problem. proteins, 4(5).
Luce, R. D. and Perry, A. D. (1949). A method of matrix analysis of group structure. Psychometrika, 14(2):95–116.
Martinez, C., Loiseau, I., Resende, M. G. C., and Rodriguez, S. (2011). Brkga algorithm for the capacitated arc routing problem. Electronic Notes in Theoretical Computer Science, 281:69–83.
Spears, W. M. and De Jong, K. D. (1995). On the virtues of parameterized uniform crossover. Technical report, DTIC Document.
Toso, R. F. and Resende, M. G. C. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30:81–93.
Zudio, A., da Silva Costa, D. H., Masquio, B. P., Coelho, I. M., and Pinto, P. E. D. (2018).
Brkga/vnd hybrid algorithm for the classic three-dimensional bin packing problem. Electronic Notes in Discrete Mathematics, 66:175–182.
Published
2019-09-25
How to Cite
PINTO, Antônio M.; ALMEIDA, Dayvson W. F.; LIMA, Christyellen S. C.; ESTRELA, Igor R. B.; CLÍMACO, Glaubos .
An addicted random key genetic algorithm applied to the maximum click problem. In: REGIONAL SCHOOL ON COMPUTING OF CEARÁ, MARANHÃO, AND PIAUÍ (ERCEMAPI), 7. , 2019, São Luís/MA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 40-46.
