Paralelización de un algoritmo de optimización de colonia de hormigas aplicado al problema del viajante

Abstract

[Resumen]: Este Trabajo Fin de Grado tiene como objetivo estudiar la estructura básica del algoritmo de Optimización de Colonia de Hormigas (Ant Colony Optimization, ACO) para proponer y evaluar la efectividad y eficiencia de diferentes estrategias de parelización y su combinación. Como banco de pruebas para evaluar las distintas propuestas paralelas se utilizó el Problema del Viajante (Travel Salesman Problem, TSP). Se escogió este problema por ser uno de los más estudiados y con una gran cantidad de aplicaciones en el mundo real. Para la paralelización se han utilizado estrategias con memoria compartida, en las que se ha empleado la librería OpenMP, y estrategias con memoria distribuida, en las que se ha utilizado el paso de mensajes y la librería MPI. La evaluación experimental se realizó de manera exhaustiva con problemas de la conocida librería TSPLIB en un cluster de altas prestaciones.[Abstract]: The aim of this project is to study the basic structure of the Ant Colony Optimization (ACO) algorithm to propose and evaluate the effectiveness and efficiency of different parelization strategies and their combination. We used the Travel Salesman Problem (TSP) as a testbed to evaluate the different parallel proposals. This problem was chosen because it is is very popular and has a large number of applications in the real world. For the parallelization, shared memory strategies have been proposed, in which the OpenMP library has been used, along with memory distributed strategies, in which message passing and the MPI library have been employed. The experimental evaluation has been exhaustively carried out with problems of the well-known TSPLIB library in a high performance cluster.