| dc.description.abstract | RESUMEN: En esta tesis se resolvió el problema de múltiples agentes viajeros usando algoritmos genéticos en paralelo en un procesador de propósito general (CPU) y en un procesador gráfico (GPU). El problema del agente viajero es un problema de optimización combinatioria, que tiene una complejidad computacional de orden factorial, al considerar el problema con múltiples agentes viajeros (PMAV), la cantidad de posibles soluciones para encontrar la ruta óptima se incrementa. Es decir, la cantidad de posibles rutas en el PMAV es extremadamente grande, de tal manera que no es factible encontrar la ruta óptima mediante búsqueda exhaustiva, ni siquiera con el uso de cómputo de alto rendimiento. Por lo tanto, es importante buscr otras estrategias de solución, en este trabajo se aplica cómputo evolutivo, en particular algoritmos genéticos en paralelo, para aproximar la solución del PMAV. Para la solución del PMAV en CPU se usaron hilos POSIX y para el GPU funciones kernel. Para la implementación del algoritmo genético la población inicial se generó con el algoritmo greedy, la representación de los individuos en el CPU es multi-cromosoma y en el GPU es cromosomas de dos partes, donde la primera parte del cromosoma representa la ruta completa para todos los viajeros y la segunda parte indica la cantidad de ciudades que visitará cada viajero. Los problemas de prueba para el PMAV se tomaron de la base de datos de problemas del agente viajero TSPLIB. La solución óptima reportada en TSPLIB se usó como referencia para evaluar la aproximación de la solución del PMAV. Además, se presenta una representación gráfica de las rutas para el PMAV con dos, tres y cuatro agentes viajeros.
ABSTRACT: In this thesis the multiple traveling salesmen problem is solved using genetic algorithms in parallel in a general purpose processor (CPU) and in a graphic processor (GPU). The problem of the traveling salesman is a problem of combinatorial optimization, which has a computational complexity of factorial order, when considering the problem with multiple traveling salesperson (MTSP), the number of possible solutions to fi nd the optimal route increases. That is, the number of possible routes in the MTSP is extremely large so that it is not feasible to fi nd the optimal route through an exhaustive search, even with the use of high-performance computing. Therefore, it is important to look for other solution strategies, in this work we apply evolutionary computation, in particular, genetic algorithms in parallel, to approximate the solution of the MTSP. For the PMAV CPU solution, POSIX threads were used and for the GPU kernel functions. For the implementation of the genetic algorithm the initial population was generated with the
greedy algorithm, the representation of the individuals in the CPU is multi-chromosome and in the GPU is two-part chromosomes, where the rst part of the chromosome represents the complete path for all salesman and the second part indicates the number of cities that each salesman will visit. The test problems for the PMAV were taken from the TSPLIB library. The optimal solution reported in TSPLIB was used as a reference to evaluate the approximation of the PMAV solution. In addition, a graphic representation of the routes for the PMAV is presented with two, three and four salemen. | |
