A study of heuristic algorithms for diversity optimization
Resumo
O projeto de metaheurísticas envolve selecionar e combinar componentes heurísticos, bem como ajustar seus parâmetros para otimizar soluções. Portanto, é importante entender a contribuição dos componentes e parâmetros para o desempenho do algoritmo. Este trabalho analisa a metaheurística GRASP aplicada ao problema da diversidade máxima, propondo heurísticas construtivas e de busca local para criar diversas configurações do algoritmo. Além disso, é feita a configuração automática do GRASP para melhorar seu desempenho. Essas configurações são avaliadas experimentalmente e usando a técnica de ablation analysis, permitindo identificar os componentes mais importantes e suas contribuições para a qualidade das soluções.
Palavras-chave:
Problema da diversidade máxima, metaheurísticas, análise de componentes
Referências
Dang, N. e De Causmaecker, P. (2019). Analysis of algorithm components and parameters: some case studies. Em Learning and Intelligent Optimization: 12th International Conference, LION 12, Kalamata, Greece, June 10–15, 2018, Revised Selected Papers 12, páginas 288–303. Springer.
Dhir, K., Glover, F. e Kuo, C.-C. (1993). Optimizing diversity for engineering management. Em Proceedings of engineering management society conference on managing projects in a borderless world, páginas 23–26. IEEE.
Fawcett, C. e Hoos, H. H. (2016). Analysing differences between algorithm configurations through ablation. Journal of Heuristics, 22:431–458.
Feo, T. A. e Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6:109–133.
Ghosh, J. B. (1996). Computational aspects of the maximum diversity problem. Operations research letters, 19(4):175–181.
Glover, F., Ching-Chung, K. e Dhir, K. S. (1995). A discrete optimization model for preserving biological diversity. Applied mathematical modelling, 19(11):696–701.
Glover, F., Kuo, C.-C. e Dhir, K. S. (1998). Heuristic algorithms for the maximum diversity problem. Journal of information and Optimization Sciences, 19(1):109–132.
Hutter, F., Hoos, H. e Leyton-Brown, K. (2014). An efficient approach for assessing hyperparameter importance. Em International conference on machine learning, páginas 754–762. PMLR.
Hutter, F., Hoos, H. H. e Leyton-Brown, K. (2013). Identifying key algorithm parameters and instance features using forward selection. Em Learning and Intelligent Optimization: 7th International Conference, LION 7, Catania, Italy, January 7-11, 2013, Revised Selected Papers 7, páginas 364–381. Springer.
Kuby, M. J. (1987). Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems. Geographical Analysis, 19(4):315–329.
Kuo, C.-C., Glover, F. e Dhir, K. S. (1993). Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sciences, 24(6):1171–1185.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M. e Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.
Martí, R., Gallego, M. e Duarte, A. (2010). A branch and bound algorithm for the maximum diversity problem. European journal of operational research, 200(1):36–44.
Martí, R. e Martínez-Gavara, A. (2023). Discrete diversity and dispersion maximization: A tutorial on metaheuristic optimization.
Pessoa, L. F. D. A., Wagner, C., Hellingrath, B. e Neto, F. B. D. L. (2015). Component analysis based approach to support the design of meta-heuristics for mlclsp providing guidelines. Em 2015 IEEE Symposium Series on Computational Intelligence, páginas 1029–1038. IEEE.
Rosenkrantz, D. J., Tayi, G. K. e Ravi, S. (2000). Facility dispersion problems under capacity and cost constraints. Journal of combinatorial optimization, 4:7–33.
Silva, G. C., Ochi, L. S. e Martins, S. L. (2004). Experimental comparison of greedy randomized adaptive search procedures for the maximum diversity problem. Em International Workshop on Experimental and Efficient Algorithms, páginas 498–512. Springer.
Villagra, A., Leguizamón, G. e Alba, E. (2015). Active components of metaheuristics in cellular genetic algorithms. Soft Computing, 19:1295–1309.
Dhir, K., Glover, F. e Kuo, C.-C. (1993). Optimizing diversity for engineering management. Em Proceedings of engineering management society conference on managing projects in a borderless world, páginas 23–26. IEEE.
Fawcett, C. e Hoos, H. H. (2016). Analysing differences between algorithm configurations through ablation. Journal of Heuristics, 22:431–458.
Feo, T. A. e Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6:109–133.
Ghosh, J. B. (1996). Computational aspects of the maximum diversity problem. Operations research letters, 19(4):175–181.
Glover, F., Ching-Chung, K. e Dhir, K. S. (1995). A discrete optimization model for preserving biological diversity. Applied mathematical modelling, 19(11):696–701.
Glover, F., Kuo, C.-C. e Dhir, K. S. (1998). Heuristic algorithms for the maximum diversity problem. Journal of information and Optimization Sciences, 19(1):109–132.
Hutter, F., Hoos, H. e Leyton-Brown, K. (2014). An efficient approach for assessing hyperparameter importance. Em International conference on machine learning, páginas 754–762. PMLR.
Hutter, F., Hoos, H. H. e Leyton-Brown, K. (2013). Identifying key algorithm parameters and instance features using forward selection. Em Learning and Intelligent Optimization: 7th International Conference, LION 7, Catania, Italy, January 7-11, 2013, Revised Selected Papers 7, páginas 364–381. Springer.
Kuby, M. J. (1987). Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems. Geographical Analysis, 19(4):315–329.
Kuo, C.-C., Glover, F. e Dhir, K. S. (1993). Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sciences, 24(6):1171–1185.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M. e Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.
Martí, R., Gallego, M. e Duarte, A. (2010). A branch and bound algorithm for the maximum diversity problem. European journal of operational research, 200(1):36–44.
Martí, R. e Martínez-Gavara, A. (2023). Discrete diversity and dispersion maximization: A tutorial on metaheuristic optimization.
Pessoa, L. F. D. A., Wagner, C., Hellingrath, B. e Neto, F. B. D. L. (2015). Component analysis based approach to support the design of meta-heuristics for mlclsp providing guidelines. Em 2015 IEEE Symposium Series on Computational Intelligence, páginas 1029–1038. IEEE.
Rosenkrantz, D. J., Tayi, G. K. e Ravi, S. (2000). Facility dispersion problems under capacity and cost constraints. Journal of combinatorial optimization, 4:7–33.
Silva, G. C., Ochi, L. S. e Martins, S. L. (2004). Experimental comparison of greedy randomized adaptive search procedures for the maximum diversity problem. Em International Workshop on Experimental and Efficient Algorithms, páginas 498–512. Springer.
Villagra, A., Leguizamón, G. e Alba, E. (2015). Active components of metaheuristics in cellular genetic algorithms. Soft Computing, 19:1295–1309.
Publicado
17/11/2024
Como Citar
SCHULTZ, Tailini; BECKER, Clara dos Santos; SOUZA, Marcelo de.
A study of heuristic algorithms for diversity optimization. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 21. , 2024, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 799-810.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2024.245223.
