Estudio Experimental con Diferentes Operadores de Cruce para la Resolución del Problema del Viajante

Abstract

El Problema del Viajante (TSP) es uno de los problemas NP más conocidos, fácil de comprender pero de difícil solución, y los algoritmos genéticos son utilizados en la resolución de los mismos. Este tipo de algoritmos simulan el proceso evolutivo de la naturaleza y nos permiten obtener resultados óptimos en tiempos razonables. Ante tales afirmaciones, el presente proyecto intentará realizar un análisis del comportamiento de este tipo de algoritmos ante diferentes situaciones, así como una comparativa con diferentes operadores de cruce, todo ello aplicado en la resolución del TSP. Para ello, primeramente se presentarán los conceptos fundamentales que nos permitirán desarrollar nuestra aplicación, para posteriormente pasar a detallar la implementación de nuestra herramienta con el lenguaje de programación MATLAB. Por último se presentarán los resultados y se analizarán, teniendo como criterios de comparación: el aumento del número de generaciones, el aumento del número de individuos de la población, los diferentes operadores de cruce implementados, los tiempos obtenidos etc.