Algoritmos genéticos com chaves aleatórias
desempenho de duas variantes na resolução do problema do caixeiro viajante
DOI:
https://doi.org/10.26853/Refas_ISSN-2359-182X_v11n04_07Palavras-chave:
Metaheurísticas, Algoritmos Evolucionários, Problemas de RoteamentoResumo
O Problema do Caixeiro Viajante é um clássico problema de otimização combinatória, que está entre os mais estudados na literatura. Neste problema, contrastam a simplicidade da definição e a complexidade computacional da resolução. Por conta dessa complexidade, algoritmos heurísticos e metaheurísticos têm sido amplamente estudados para a resolução do problema. Este trabalho tem por objetivo avaliar o desempenho de duas variantes do algoritmo genético com chaves aleatórias: o RKGA e o BRKGA. Para isso, os dois algoritmos foram implementados computacionalmente e um conjunto de 20 instâncias da literatura foi selecionado para a execução de testes computacionais. Foram selecionadas instâncias simétricas que possuem entre 70 e 1748 pontos. Nos testes computacionais, foram analisados e comparados a qualidade da solução obtida e o tempo de processamento de cada algoritmo ao longo de três execuções. Os resultados indicaram que o BRKGA é mais eficiente na busca por soluções que o RKGA, considerando o conjunto de instâncias avaliado. A melhoria na qualidade da solução produzida foi, em média, superior a 20%.
Downloads
Referências
ANDRADE, C. E.; SILVA, T.; PESSOA, L. S. Minimizing flowtime in a flowshop scheduling problem with a biased random-key genetic algorithm. Expert Systems with Applications, n. 128, p. 67–80, 2019.
BEAN, J. C. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, v. 6, p. 154–160, 1994.
BERNARDINO, R.; PAIAS, A. Heuristic approaches for the family traveling salesman problem. International Transactions in Operational Research, v. 28, n. 1, p., 262–295, 2021.
BIAJOLI, F. L.; CHAVES, A. A.; LORENA, L. A. N., A biased radom-key genetic algorithm for the two stages capacitated facility location problem. Expert Systems and Applications, v. 115, p. 418–426, 2019.
CHAVES, A. A.; GONÇALVES, J. F.; LORENA, L. A. N. Adaptive biased random-key genetic algorithm with local search for the capacitated centered clustering problem. Computers & Industrial Engineering, v. 124, p. 331–346, 2018.
CHAVES; A. A.; VIANNA, B. L.; SILVA; T. T.; SCHENEKEMBERG, C. M. A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem. Expert Systems with Applications, v. 228, Part A, 2024.
DAHIYA, C.; SANGWAN, S. Literature Review on Travelling Salesman Problem. International Journal of Research, v. 5, n. 16, p. 1152–1155, 2018.
DANTZIG, G.; FULKERSON, R.; JOHNSON, S. Solution of a large-scale traveling - salesman problem. Journal of the Operations Research Society of America, v. 2, n. 4, p. 393–410, 1954.
FERNANDES, D. R. M; ROCHA, C.; ALOISE, D.; RIBEIRO, G. M.; SANTOS, E. M.; SILVA, A. A simple and effective genetic algorithm for the two-stage capacitated facility location problem. Computers & Industrial Engineering, v. 75, p. 200–208, 2014.
GEN, M., LIN, L. Genetic Algorithms and Their Applications. In: Pham, H. (Eds). Handbook of Engineering Statistics. London: Springer, 2023.
GOLBARG, M. C.; LUNA, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. 2. ed. Rio de Janeiro: Campus, 2005.
GOLDBERG, D.E.; HOLLAND, J. H. Genetic Algorithms and Machine Learning. Machine Learning, v. 3, p. 95–99, 1988.
GONÇALVES, J. F.; RESENDE, M. G. C. Biased random-key genetic algorithm for combinatorial optimization. Journal Heuristics, v. 17, p. 487–525, 2011a.
GONÇALVES, J. F.; RESENDE, M. G. C. A. A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. Journal of Combinatorial Optimization, v. 22, n. 2, p. 180–201, 2011b.
GONÇALVES, J. F.; RESENDE, M. G. C. Random-Key Genetic Algorithms. In: MART, R.; PARDALOS, P. M.; RESENDE, M. G. C. (Org.) Handbook of Heuristics, Springer International Publishing, p. 1–13, 2016.
GU, Y.; RYU, S.; XU, Y.; CHEN, A.; CHAN, H. -Y.; XU, X. A random-key genetic algorithm-based method for transportation network vulnerability envelope analysis under simultaneous multi-link disruptions. Expert Systems with Applications, v. 248, 123401, 2024.
IZDEBSKI, M.; JACYNA-GOŁDA, I.; WASIAK, M.; JACHIMOWSKI, R., KŁODAWSKI, M.; PYZA, D.; ŻAK, J., The application of the genetic algorithm to multi-criteria warehouses location problems on the logistics network. Transport, v. 33, n. 3, p.741–750, 2018.
LONDE, M. A.; PESSOA, L. S.; ANDRADE, C. E.; RESENDE, M. G. C. Biased random-key genetic algorithms: a review. European Journal of Operational Research, v. 321, n.1, 2025.
LOPES, M. C.; ANDRADE, C. E.; QUEIROZ, T. A.; RESENDE, M. G. C.; MIYAZAWA, F. K., Heuristics for a hub location-routing problem. Networks, v. 68, n. 1, p. 54–90, 2016.
MAGALHÃES, M. T.; MIRANDA, G. B.; GONÇALVES, L. B.; MORENO, L. L. O.; SOARES, S. S. R. F.; OLIVEIRA, L. W. A Random Keys Genetic Algorithm Approach for Reconfiguration Problem in Distribution Power Networks. In: 2019 8th Brazilian Conference on Intelligent Systems (BRACIS), p. 866–871, 2019.
MATAI, R; SINGH, S. P.; MITALL, M. L. Traveling salesman problem: an overview of applications, formulations, and solution approaches. In: DAVENDRA D. (Ed.). Traveling salesman problema, theory and applications. InTech Press, London, p. 1–26, 2010.
MAZIERO, L. P. Exact and heuristic algorithms for covering routing problems. 2023. 106 f. Tese (Doutorado em Ciência da Computação) – Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2023.
PARK, H.; SON, D.; KOO, B.; JEONG, B. Waiting strategy for the vehicle routing problem with simultaneous pick-up and delivery using genetic algorithm. Expert System with Applications, v. 165, 113959, 2021.
PINHEIRO, P. R.; AMARO JÚNIOR, B.; SARAIVA, R. D. A random-key genetic algorithm for solving the nesting problem. International Journal of Computer Integrated Manufacturing, v. 29, n.11, p. 1159–1165, 2015.
POP, P. C; COSMA, O.; SABO, C.; SITAR, C. P. A comprehensive survey on the generalized traveling salesman problem. European Journal of Operational Research, v. 314, n. 3, p. 819–835, 2024.
ROCHMAN, A.N.; PRASETYO, H.; NUGROHO, M.T. Biased random key genetic algorithm with insertion and gender selection for capacitated vehicle routing problem with time windows. In: AIP Conference Proceedings, v. 1855, n. 1, article 020025, 2017.
SARKER, T. K.; TANG, M. A Random Key Genetic Algorithm for Live Migration of Multiple Virtual Machines in Data Centers. In: International Conference of Neural Information Processing - ICONIP. Neural Information Processing, Lecture Notes in Computer Science, v. 8835, p. 212–220, 2014.
SNYDER, L. V.; DASKIN, M. S., A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, v. 174, n. 1, p. 38–53, 2006.
SPEARS, W. M.; DEJONG, K. A. On the virtues of parameterized uniform crossover. In: Fourth International Conference on Genetic Algorithms. Proceedings of the Fourth International Conference on Genetic Algorithms, p. 230–236, 1991.
TOAZA, B.; ESZTERGÁR-KISS, D. A review of metaheuristic algorithms for solving TSP - based scheduling optimization problems. Applied Soft Computing, v. 148, n. 110908, 2023.
TSPLIB. Traveling Salesman Problem Library. Disponível em: <http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/>. Acesso em: 11 mar. 2024.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Refas - Revista Fatec Zona Sul
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
1 - As fontes dos dados, as autorizações pertinentes e os textos publicados na revista são de inteira responsabilidade de seus autores.
2 - É permitida a reprodução, desde que citada a fonte e o autor.
3 - Após o artigo aprovado, o autor principal deverá enviar declaração, conforme o modelo:
Refas - Revista Fatec Zona Sul
Autorização par publicação
(Nome do autor), (no caso de vários autores citar todos), autorizo (ou autorizam, no caso de diversos autores) a publicação do artigo (nome do artigo), com exclusividade para a primeira publicação pela Revista Fatec Zona Sul, em meio eletrônico.
A contribuição é original e inédita, e não está sendo avaliada para publicação por outra revista; caso contrário, deve-se justificar em "Comentários ao editor".
Dados de todos os autores:
Nome completo:
Instituição:
E-mail:
Telefone:
Obs.: Informar os códigos dos serviços DDD e DDI.
Assinatura do autor principal: ____________________________________
Aviso de Direito Autoral
Autores que publicam nesta revista concordam com os seguintes termos:
a) Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
b) Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.
c)Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons CC Attribution-NonCommercial-NoDerivatives 4.0, acessável em Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.