Aplicando o Golden Ball ao Problema da Diversidade Máxima

• Carlos V. Dantas Araújo UFC
• Jailon W. B. Oliveira da Silva UFC
• Pablo L. Braga Soares UFC

DOI: https://doi.org/10.5753/etc.2025.9173

Resumo

Este trabalho adapta a meta-heurística Golden Ball ao Problema da Diversidade Máxima em grafos, modificando o algoritmo inspirado em esportes para selecionar subconjuntos de vértices que maximizam a soma de suas distâncias. Experimentos com 80 instâncias demonstraram um desempenho competitivo, alcançando soluções com desvio de 0,06% a 0,95% em relação aos melhores valores conhecidos, além de um tempo de execução consideravelmente menor em comparação ao método Scatter Search, referência na literatura. O algoritmo se destacou em instâncias geométricas, obtendo soluções equivalentes aos melhores valores conhecidos em 95% dos casos, e apresentou desempenho consistente nas demais instâncias.

Referências

Aringhieri, R., Bruglieri, M., Malucelli, F., and Nonato, M. (2015). Special issue on optimization in medicine and biology: Exact and heuristic approaches. European Journal of Operational Research, 244(3):647–648.

Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3):268–308.

Carrabs, F., Cerulli, R., and Toth, P. (2022). New approaches for solving the maximum diversity problem in large graphs. Journal of Heuristics, 28(3):231–256.

Duarte, A., Martí, R., Sánchez-Oro, J., and Glover, F. (2015). Metaheuristics for the maximum diversity problem. European Journal of Operational Research, 240(1):24–36.

Gallego, M., Duarte, A., Laguna, M., and Martí, R. (2009). Hybrid heuristics for the maximum diversity problem. Computational Optimization and Applications, 44(3):411–426.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.

Ghosh, J. B. (1996). Computational aspects of the maximum diversity problem.

Gonzalez, J. A., Hernández-Pérez, H., and Lozano, M. (2020). A review on maximum diversity problems. European Journal of Operational Research, 287(2):401–420.

Martí, R., Duarte, A., and Laguna, M. (2013). Advanced scatter search for the max-min diversity problem. INFORMS Journal on Computing, 25(2):245–260.

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(1):145–166.

Ruttanateerawichien, K., Kurutach, W., and Pichpibul, T. (2014). An improved golden ball algorithm for the capacitated vehicle routing problem. In Pan, L., Păun, G., Pérez-Jiménez, M. J., and Song, T., editors, Bio-Inspired Computing - Theories and Applications, pages 341–356, Berlin, Heidelberg. Springer Berlin Heidelberg.

Worawattawechai, T., Intiyot, B., Jeenanunta, C., and Ferrell, W. G. (2022). A learning enhanced golden ball algorithm for the vehicle routing problem with backhauls and time windows. Computers Industrial Engineering, 168:108044.