Uma abordagem do algoritmo genético com foco na inicialização para o problema do caixeiro viajante

Abstract

Genetic Algorithms are heuristic search methods that replicate the evolutionary process as explained in Charles Darwin’s Theory of Evolution. According to this theory, individuals with more advantageous adaptations to their environment are more likely to survive. This search method is particularly eective in solving a classic problem in the literature known as the Traveling Salesman Problem, which falls into the NP-Complete category. This problem has broad applications in scenarios involving routing, logistics, and resource optimization. In this work, we introduce an innovative approach based on Genetic Algorithms. The primary goal is to present a new initialization method specic to the discussed problem while simultaneously conducting a simulation addressing a logistics distribution scenario with predened stock in the state of Alagoas. To evaluate the proposed algorithm, we will compare its results with another simple implementation of the Traveling Salesman Problem, using the same metrics and dataset. An assessment will be conducted considering the performance of each algorithm, taking into account their score per generation, the number of generations in which they found the best solution, and the execution time required for each algorithm to reach that solution. The study at hand yielded favorable results in the rst two evaluation metrics, with only a relatively lower performance in terms of execution time.