Mejora del rendimiento del algoritmo colonia de hormiga para resolver el problema de TSP

Abstract

El presente trabajo de investigación, tiene por finalidad mejorar el rendimiento del Algoritmo Colonia de hormigas (ACO) buscando reducir el tiempo en encontrar la solución a problemas TSP mediante el algoritmo colonia de hormigas, para ello se ha realizado una revisión de las diferentes soluciones que hay del algoritmo Colonia de Hormigas aplicado al problema del agente viajero (TPS). El problema TSP es un problema de optimización combinatoria, muy complejo computacionalmente, se ha implementado el algoritmo ACO paralelizado para mejorar el tiempo en encontrar la solución al problemas TSP; se ha paralelizando las tareas recurrentes que realizan las hormigas al buscar su alimento y regresar al nido buscando la ruta más corta durante el trayecto las hormigas van dejando en el ambiente una sustancia química llamada feromona la cual permite a las demás hormigas seguir el rastro y encontrar la ruta de regreso al nido. En el trabajo de investigación se ha implementado el algoritmo ACO serial y el algoritmo ACO paralelizado, utilizando el lenguaje de programación Python y la librería de Numba. En una primera prueba se observa que el Algoritmo ACO paralelizado es más rápido comparado con el algoritmo ACO serial, encontrando un resultado alentador con un Speedup de 64.53, en una segunda prueba se muestra que el coeficiente de disipación y el coeficiente de aprendizaje no repercute en la labor que realizan las hormigas debido al modelo matemático.