Implementación de un algoritmo genético modificado para la solución al problema del agente viajero

Abstract

El problema del agente viajero ha representado un reto a lo largo del tiempo,debido a suscaracterísticas se considera como un problema computacionalmente complejo. Debido a lo anterior, varios algoritmos estocásticos han sido desarrollados para proponer una solución factiblea este problema. Entre estas soluciones disponibles,los algoritmos evolutivos siempre han sido una buenaaproximación para encontrar un buen resultado paraeste problema, el óptimo en el mejor de los casos. En el presente trabajose explorauna alternativade solución al problemaplanteado, un algoritmo genéticomodificado. Sepresentala implementación de un algoritmo genético modificado para la solución al problema del agente viajero mediante la modificación de la función de cruce. Se realiza una comparativa con la implementación del algoritmo de optimización por colonia de hormigas, con la finalidad de explorar las fortalezas de cada implementación, así como la naturaleza de sus soluciones.La comparativa se presenta en términos de tiempo de ejecución y distancia entregada en la solución proporcionada por cada implementación. ABSTRACT The traveling salesman problem has represented a challenge over time, due to its characteristics it is considered a computationally complex problem. Due to the above, several stochastic algorithms have been developed to propose a feasible solution to this problem. Among these available solutions, evolutionary algorithms have always been agood approach to find a good result for this problem, the optimal in the best case. In the present work, an alternativesolution to the proposed problemis explored, a modified genetic algorithm. The implementation of a modified genetic algorithm for the solution of the traveling salesman problem by modifying the crossover functionis presented. A comparison is made with the implementation of the ant colony optimization algorithm, to explore the strengths of each implementation, as well as the nature of their solutions.The comparison is presented in terms of execution time and distance obtained in the solution provided by eachimplementation