Um algoritmo genético com chaves aleatórias viciadas aplicado ao problema da clique máxima
Resumo
O problema da clique maxima consiste em encontrar o maior sub-grafo completo dentro de um dado grafo. Esse problema e bem conhecido no ´ campo da Pesquisa Operacional e tem diversas aplicac¸oes em nosso cotidiano. ˜ Neste trabalho, propoe-se resolver o problema da clique m ˜ axima utilizando um ´ solver matematico e a bem conhecida metaheur ´ ´ıstica BRKGA. Para validar nossas propostas, utilizamos um conjunto de problemas-teste que estao dispon ˜ ´ıveis on-line na literatura. O BRKGA provou ser eficiente na resoluc¸ao dos proble- mas e competitivo com o resolvedor matematico utilizado
Palavras-chave:
Problema do Clique, algoritmo genético, chaves aleatórias
Referências
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.
Publicado
25/09/2019
Como Citar
PINTO, Antônio M.; ALMEIDA, Dayvson W. F.; LIMA, Christyellen S. C.; ESTRELA, Igor R. B.; CLÍMACO, Glaubos .
Um algoritmo genético com chaves aleatórias viciadas aplicado ao problema da clique máxima. In: ESCOLA REGIONAL DE COMPUTAÇÃO DO CEARÁ, MARANHÃO E PIAUÍ (ERCEMAPI), 7. , 2019, São Luís/MA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 40-46.
