EL Problema del Viajante, heurísticas basadas en algoritmos genéticos

Abstract

Se consideran los algoritmos genéticos como una aproximación a la solución del Problema del Viajante. Se analiza la complejidad computacional del Problema del Viajante y se concluye que es un problema NP-Duro. Se sitúa históricamente el problema, describiendo los diferentes hitos que han sucedido, dando lugar a una variedad de métodos para resolver instancias cada vez mayores. Se examinan algunas de dichas aproximaciones, diferenciándose algoritmos exactos, heurísticas y metaheurísticas. Se estudia la metaheurística de los algoritmos genéticos en profundidad, presentando los operadores de selección, cruce y mutación clasificándolos en función de su contexto binario o permutacional. Se introduce la teoría de esquemas para justificar los operadores anteriores y se estudia el modelo de Markov que subyace en el proceso dinámico de optimización. Por último, se analiza la eficacia de los algoritmos genéticos sobre el Problema del Viajante en diferentes instancias del banco de ejemplos TSPLIB, comparando el rendimiento de las posibles opciones para cada operador, con unos parámetros fijados por el autor.

Genetic algorithms are considered to be an approximation to the solution of the Traveling Salesman Problem. The computational complexity of the Traveling Salesman Problem is analyzed and it is concluded that it is a a NP-Hard problem. The problem is historically set, describing the different milestones that have happened, leading to a variety of methods to solve increasingly bigger instances. Some of those approximations are examined, differentiating exact algorithms, heuristics and metaheuristics. The genetic algorithm metaheuristic is studied in depth, presenting the selection, crossover and mutation operators classifying them according to their binary or permutational context. The schema theory is introduced in order to justify the above operators and the Markov model underlying the dynamic optimization model is studied. Finally, the efficacy of genetic algorithms on the Traveling Salesman Problem is analyzed in different instances of the TSPLIB test bench, comparing the performance of the possible options for each operator, with parameters set by the author.