Solución de problemas de optimización mediante algoritmos genéticos aplicando computo de alto rendimiento

Abstract

RESUMEN: En este trabajo se resuelve un problema de optimización combinatoria usando Algoritmos Genéticos Paralelos en un procesador multi-hilos. Como problema de prueba se resuelve el problema del agente viajero (PAV), aplicándolo para encontrar la solución a problemas tomados de la biblioteca de problemas del agente viajero TSPLIB. La población inicial se obtiene empleando un algoritmo Greedy, la selección de los individuos para el cruzamiento se realiza por torneo, además se usa elitismo tanto en el cruce como en la mutación de los individuos, aplicando un 80 % de probabilidad para el cruce y un 30 % para la mutación. En los resultados numéricos se observa que el cruce por orden (OX) da una mejor aproximación al óptimo que el cruce de apareamiento parcial (PMX), también se nota que al aumentar el tamaño de la población no necesariamente se obtiene un mejor valor para la solución. En cuanto al tiempo de ejecución es mejor tener una población relativamente pequeña con muchas iteraciones que una población grande con pocas iteraciones. Se resuelve el problema para varias instancias del problema del agente viajero usando algoritmos genéticos paralelos, el porcentaje de error al obtener la mejor ruta es pequeño y se puede mejor haciendo ajustes en los parámetros, como número de iteraciones, tamaño de la población, métodos y porcentajes de cruce y mutación; uso de elitismo, etc. Se obtiene un buen speedup para menos de cinco hebras, por lo que no es conveniente usar más de cinco hebras. Palabras Clave: Algoritmos Genéticos, Problema del Agente Viajero, Cómputo Paralelo, NP-Completo.

ABSTRACT: In this work a combinatorial optimization problem is solved using Parallel Genetic Algorithms in a multithread processor. The Traveling Salesman Problems (TSP) are taken from the TSPLIB and used as test problem. The initial population is selected using a Greedy algorithm; the selection of the individuals for the crossing is by tournament. Moreover elitism is used in the crossover and mutation operators with a 80 % of probability for the crossing and 30 % for the mutation. The numerical results shown that the increase of the population size sometimes no generates a best solution. A relatively small population size with a large number of iterations is better than a large population size where the population is small. Several instances of the TSP are taken from TSPLIB and solved using parallel genetic algorithm; the error percent for the best route is small and can be improved with changes in the parameters, iterations number, population size, methods and percents of crossover and mutation, elitism, etc. A good speedup is achieved for less of five threads, and then is not recommended to use more than five threads. Keywords: Genetic Algorithms, Traveling Salesman Problem, Parallel Computing, NP-Complete.