DSpace Repository

Cómputo de alto rendimiento para resolver grandes instancias del problema del agente viajero con un modelo de islas de algoritmos genéticos híbridos

Show simple item record

dc.contributor.author Cardenas Piñuelas, Jesus Carlos
dc.date.accessioned 2021-08-11T00:49:25Z
dc.date.available 2021-08-11T00:49:25Z
dc.date.created 2020-07-20
dc.date.issued 2021-08-09
dc.identifier.citation Cardenas Piñuelas Jesus. (2020). Cómputo de alto rendimiento para resolver grandes instancias del problema del agente viajero con un modelo de islas de algoritmos genéticos híbridos. (Maestría en Ciencias en Sistemas Digitales). Instituto Politécnico Nacional, Centro de Investigación y Desarrollo de Tecnología Digital, México. es
dc.identifier.uri http://tesis.ipn.mx/handle/123456789/29140
dc.description Tesis (Maestría en Ciencias en Sistemas Digitales), Instituto Politécnico Nacional, CITEDI, 2020, 1 archivo PDF, (72 páginas). tesis.ipn.mx es
dc.description.abstract RESUMEN: En esta investigación se presenta el desarrollo de un algoritmo genético paralelo para resolver el problema del agente viajero. Las principales características del algoritmo son la implementación del operador de cruce con ensamble de aristas (EAX) combinado con un método de búsqueda local (2-opt) y la aplicación del algoritmo genético paralelo con un modelo de islas. Además, la población inicial se genera con un algoritmo de búsqueda local muy eficiente. El algoritmo obtenido se paralelizó en un procesador multinúcleo con memoria compartida utilizando el estándar de hilos POSIX en lenguaje C. En la paralelización desarrollada se implementó un hilo de ejecución para cada isla. Los principales pasos del algoritmo se desarrollaron en paralelo, y después de cada paso se hizo la sincronización correspondiente. En cada generación se calcula una cantidad de descendientes previamente definida para cada uno de los individuos, después se selecciona al descendiente de mejor calidad para reemplazar al individuo padre en caso de ser mejor. Para la migración de individuos se escoge el mejor individuo de una isla que sustituye al peor individuo de otra isla, mediante una topología de anillo. El algoritmo se ejecutó para instancias del problema del agente viajero en la escala de decenas de miles de ciudades, obtenidas de la biblioteca TSPLIB, las mejores soluciones obtenidas están muy cercanas a los valores óptimos reportados en dicha biblioteca. Los resultados indican que el utilizar un modelo de isla acelera la convergencia. ABSTRACT: This research presents the development of a parallel genetic algorithm to solve the traveling salesman problem. The main features of the algorithm are the implementation of the edge assembling crossover operator (EAX) combined with a local search method (2-opt) and the application of the parallel genetic algorithm with an island model. Furthermore, the initial population is generated with a very efficient local search algorithm. The algorithm obtained was parallelized in a multicore processor with shared memory using the POSIX threads standard in C language. In the developed parallelization, an execution thread was implemented for each island. The main steps of the algorithm were developed in parallel, and after each step the corresponding synchronization was made. In each generation, a predefined quantity of descendants is calculated for each of the individuals, then the best quality descendant is selected to replace the parent individual if better. For the migration of individuals, the best individual from one island is chosen to replace the worst individual from another island, using a ring topology. The algorithm was executed for instances of the traveling salesman problem on the scale of tens of thousands of cities, obtained from the TSPLIB library, the best solutions obtained are very close to the optimal values reported in said library. The results indicate that using an island model accelerates convergence. es
dc.language.iso es es
dc.subject Problema del agente viajero es
dc.subject Algoritmo genético paralelo es
dc.subject Operador EAX es
dc.title Cómputo de alto rendimiento para resolver grandes instancias del problema del agente viajero con un modelo de islas de algoritmos genéticos híbridos es
dc.type TESIS es
dc.contributor.advisor Tapia Armenta, Juan José


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account