Avaliando o desempenho de um algoritmo genético baseado em configurações de parâmetros no problema da mochila 0-1
DOI:
https://doi.org/10.35588/jyravv64Palavras-chave:
Algoritmo genético, Problema da mochila 0-1, Configuração de parâmetros, Otimização combinatóriaResumo
A experimentação com várias configurações do algoritmo genético revelou que a combinação específica de uma baixa probabilidade de mutação juntamente com um tamanho de torneio ajustado produz melhorias significativas de desempenho, evidenciadas tanto na redução do GAP médio quanto na maximização do valor objetivo alcançado, estabelecendo assim referências quantificáveis para implementações eficientes em problemas de mochila 0-1 de complexidade variável. A novidade está em fornecer diretrizes concretas para implementações práticas, estabelecendo relações claras entre parâmetros e desempenho. Embora os AGs sejam eficazes para explorar grandes espaços de busca em problemas NP-completos, o estudo confirma que eles exigem um ajuste cuidadoso para evitar convergência prematura. Propõe-se integrar técnicas avançadas como redes neurais profundas (DNN) e aprendizado por reforço (RL) para otimizar parâmetros de forma adaptativa, melhorando potencialmente sua aplicabilidade em cenários de maior escalabilidade.
Downloads
Referências
Ahmed, Z. y Younas, I. (2011). A Dynamic Programming based GA for 0-1 Modified
Knapsack Problem. International Journal of Computer Applications, 16(7), 1-6. https://doi.org/10.5120/2028-2668
Eiben, A. E. y Smit, S. K. (2011). Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation, 1(1), 19-31. https://doi.org/10.1016/j.swevo.2011.02.001
Ezziane, Z. (2002). Solving the 0/1 knapsack problem using an adaptive genetic algorithm. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 16(1), 23-30. https://doi.org/10.1017/s0890060401020030
He, J., He, F. y Dong, H. (2014). A Novel Genetic Algorithm using Helper Objectives for the 0-1 Knapsack Problem. arXiv:1404.0868 [cs.NE]. https://doi.org/10.48550/arXiv.1404.0868
Hinterding, R., Michalewicz, Z. y Eiben, A. E. (1997). Adaptation in evolutionary computation: a survey. IEEE International Conference on Evolutionary Computation (ICEC ’97), 65-69. https://doi.org/10.1109/icec.1997.592270
Hota, A. R. y Pat, A. (2010). An adaptive quantum‑inspired differential evolution algorithm for 0-1 knapsack problem. 2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC), 703-708. https://doi.org/10.1109/nabic.2010.5716320
Khuri, S., Bäck, T. y Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. ACM symposium on Applied computing - SAC ’94, 188-193. https://doi.org/10.1145/326619.326694
Krasnogor, N. y Smith, J. (2005). A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation, 9(5), 474-488. https://doi.org/10.1109/tevc.2005.850260
Malanthara, A. y Kale, I. R. (2025). Hybrid Firefly-Genetic Algorithm for Single and Multi-dimensional 0-1 Knapsack Problems (Versión 1). arXiv:2501.14775 [cs.NE]. https://doi.org/10.48550/ARXIV.2501.14775
Ortega, J. (s.f.). Instances of 0/1 Knapsack Problem. Universidad del Cauca. http://argotemisa.unicauca.edu.co/~johnyortega/instances_01_KP/
Owais, W. B., Alkhazendar, I. W. J. y Saleh, M. (2020). Evaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm. Computer Science & Information Technology (CS & IT), 01-16. https://doi.org/10.5121/csit.2020.101101
Pisinger, D. (2005). Where are the hard knapsack problems? Computers & Operations Research, 32(9), 2271-2284. https://doi.org/10.1016/j.cor.2004.03.002
Pradhan, T., Israni, A. y Sharma, M. (2014). Solving the 0–1 Knapsack problem using Genetic Algorithm and Rough Set Theory. IEEE International Conference on Advanced Communications, Control and Computing Technologies, 1120-1125. https://doi.org/10.1109/icaccct.2014.7019272
Raidl, G. R. (1998). An improved genetic algorithm for the multiconstrained 0-1 knapsack problem. IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360), 207-211. https://doi.org/10.1109/icec.1998.699502
Umbarkar, A. J. y Joshi, M. S. (2014). 0/1 Knapsack Problem using Diversity based Dual Population Genetic Algorithm. International Journal of Intelligent Systems and Applications, 6(10), 34-40. https://doi.org/10.5815/ijisa.2014.10.05
Yan, T. S., Guo, G. Q., Li, H. M. y He, W. (2013). A Genetic Algorithm for Solving Knapsack Problems Based on Adaptive Evolution in Dual Population. Advanced Materials Research, 756-759, 2799-2802. https://doi.org/10.4028/www.scientific.net/amr.756-759.2799
Yang, Y. (2024). An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem. arXiv:2403.11307 [cs.NE]. https://doi.org/10.48550/arXiv.2403.11307
Kim, Y., Kim, J.‑H. y Han, K.‑H. (2006). Quantum-inspired Multiobjective Evolutionary Algorithm for Multiobjective 0/1 Knapsack Problems. IEEE International Conference on Evolutionary Computation, 2601‑2606. https://doi.org/10.1109/cec.2006.1688633
Downloads
Submetido
2025-03-10Publicado
Edição
Secção
Licença
Direitos de Autor (c) 2025 Revista Electrónica Gestión de las Personas y Tecnología
Este trabalho encontra-se publicado com a Licença Internacional Creative Commons Atribuição 4.0.
