Aplicação do Golden Ball para o Problema do Corte Máximo
Resumo
Este trabalho aplica a meta-heurística Golden Ball ao Problema do Corte Máximo em grafos, modelando soluções como jogadores organizados em times que evoluem, visando identificar partições dos vértices que maximizem a soma dos pesos das arestas cortadas. Foram avaliadas 120 instâncias da Biq Mac Library, e os experimentos mostraram que o Golden Ball gera soluções satisfatórias, com desvio médio de 37% no conjunto Be em 10 segundos e apenas 1.4% em 1200 segundos. Como método evolutivo, seus resultados melhoram com mais tempo de execução. A abordagem foi comparada ao solver Biq Mac Library, referência na área, que operou por até 10800 segundos.Referências
Agrawal, R., Rajagopalan, S., Srikant, R., and Xu, Y. (2003). Mining newsgroups using networks arising from social behavior. In Proceedings of the 12th international conference on World Wide Web, pages 529–535.
Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM computing surveys (CSUR), 35(3):268–308.
Boros, E. and Hammer, P. L. (1991). The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Annals of Operations Research, 33(3):151–180.
de Sousa, S., Haxhimusa, Y., and Kropatsch, W. G. (2013). Estimation of distribution algorithm for the max-cut problem. In Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 International Workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings 9, pages 244–253. Springer.
Karp, R. M. (1972). Reducibility among combinatorial problems. complexity of computer computations (the ibm research symposia series).
Liers, F., Nieberg, T., and Pardella, G. (2011). Via minimization in vlsi chip design-application of a planar max-cut algorithm.
Miyazawa, F. K. and de Souza, C. C. (2015). Introdução à otimização combinatória. Sociedade Brasileira de Computação.
Osaba, E., Diaz, F., and Onieva, E. (2014). Golden ball: a novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Applied intelligence, 41:145–166.
Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. S., Hong, S., et al. (2017). Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771.
Rendl, F., Rinaldi, G., and Wiegele, A. (2010). Solving Max-Cut to optimality by inter-secting semidefinite and polyhedral relaxations. Math. Programming, 121(2):307.
Wiegele, A. (2007). Biq mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Preprint, 51.
Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM computing surveys (CSUR), 35(3):268–308.
Boros, E. and Hammer, P. L. (1991). The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Annals of Operations Research, 33(3):151–180.
de Sousa, S., Haxhimusa, Y., and Kropatsch, W. G. (2013). Estimation of distribution algorithm for the max-cut problem. In Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 International Workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings 9, pages 244–253. Springer.
Karp, R. M. (1972). Reducibility among combinatorial problems. complexity of computer computations (the ibm research symposia series).
Liers, F., Nieberg, T., and Pardella, G. (2011). Via minimization in vlsi chip design-application of a planar max-cut algorithm.
Miyazawa, F. K. and de Souza, C. C. (2015). Introdução à otimização combinatória. Sociedade Brasileira de Computação.
Osaba, E., Diaz, F., and Onieva, E. (2014). Golden ball: a novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Applied intelligence, 41:145–166.
Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. S., Hong, S., et al. (2017). Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771.
Rendl, F., Rinaldi, G., and Wiegele, A. (2010). Solving Max-Cut to optimality by inter-secting semidefinite and polyhedral relaxations. Math. Programming, 121(2):307.
Wiegele, A. (2007). Biq mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Preprint, 51.
Publicado
20/07/2025
Como Citar
SILVA, Jailon W. B. Oliveira da; ARAÚJO, Carlos V. Dantas; SOARES, Pablo L. Braga.
Aplicação do Golden Ball para o Problema do Corte Máximo. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 114-118.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.9186.
