Algoritmos genéticos com chaves aleatórias

desempenho de duas variantes na resolução do problema do caixeiro viajante

Autores

DOI:

https://doi.org/10.26853/Refas_ISSN-2359-182X_v11n04_07

Palavras-chave:

Metaheurísticas, Algoritmos Evolucionários, Problemas de Roteamento

Resumo

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

Não há dados estatísticos.

Biografia do Autor

Eduardo Paz Putti, LABICON, Instituto Federal de Santa Catarina (IFSC)

Discente do curso de Bacharelado em Engenharia de Controle e Automação.

Nathan Batistelli de Oliveira, LABICON, Instituto Federal de Santa Catarina (IFSC)

Discente do curso de Bacharelado em Engenharia de Controle e Automação.

Carise Elisane Schmidt, LABICON, Instituto Federal de Santa Catarina (IFSC)

Doutora em Métodos Numéricos em Engenharia.

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

30/04/2025

Como Citar

Putti, E. P., Oliveira, N. B. de, & Schmidt, C. E. (2025). Algoritmos genéticos com chaves aleatórias: desempenho de duas variantes na resolução do problema do caixeiro viajante. Refas - Revista Fatec Zona Sul, 11(4), 38–49. https://doi.org/10.26853/Refas_ISSN-2359-182X_v11n04_07

Edição

Seção

Logística

Métricas

Artigos mais lidos pelo mesmo(s) autor(es)