Departamento de Computación

La complejidad de un problema es una medida que indica la dificultad inherente para poder resolverlo. Dos clases de complejidad que han sido ampliamente estudiadas son la clase P y la clase NP. A la clase de complejidad NP, pertenecen los problemas intratables entre los que se encuentran los problemas de optimizacion combinatoria cuyo espacio de soluciones crece exponencialmente. Dado que no se conocen algoritmos polinominales para resolver estos problemas de manera exacta y ya que es invíable hacer una busqueda exhaustiva para insatancias de tamaño moderado, se han propuesto diversas estrategias para obtener soluciones aproximadas. Los algoritmos geneticos los cuales su estrategia en las teorías de evolución de Darwin, han mostrado ser un método eficaz para obtener soluciones potenciales las cuales se combinan mediante operadores genéticos para obtener una nueva generación de soluciones. El método se itera hasta un número fijo de generaciones o hasta que se encuentra una solución razonablemente buena por lo anterior, los algoritmos genéticos requieren un alto consumo de recursos computacionales lo que representa una de sus mayores debilidades. Es posible, sin embargo, mejorar su desempeño usando técnicas de programación paralela las cuales reducen los tiempos de ejecución sin detrimento de la calidad de las soluciones obtenidas. En este trabajo de tesis se presentan tres modelos de paralelización, modelo global, modelo de islas y modelo celular, para la implementación paralela de algoritmos genéticos. Para evaluar los beneficios del uso de paralclismo comparado con la versión secuencial del algoritmo se eligio un problema de optimización combinatoria muy conocido y fácil de entender llamado TSP. Posteriormente se presentan las versiones paralelas de dicho algoritmo genético serial usando los tres modelos de paralelización, finalmente, se compara el rendimiento de cada uno de los modelos paralelos usando 4 y 8 procesadores contra la versión secuencial.

Abstract

The complexity of a problem is a measurement that indicates the inherent difficulty to solve it. Two classes of complexity that have been studied are the P and NP classes problems. Combinatorial optimization problems belong to the NP class whose space of solutions increases exponentially. Since there are not know polinomial algorithms available to solve these problems in an exact way and since is nonviable to make an exhaustive search for instances of moderate sizes, diverse strategies have been proposed to obtaining approximated solutions. The genetic algorithms, which beses its strategy on Darwin's theory of evolution, have show to be an effective method to obtain good solutions in some types of problems. There are based on the use of potential populations of solutions which are combined by means of genetic operators to obtain a new group of solutions. The method is repeated until reaching a fixed number of generations or until one reasonably good solutions is found. Therefore, genetic algorithm requires a high consumption of computing resources which represent one of their weaknesses. It is possible, nevertheless, to improve his performance by using methods of parallel programming which reduce the execution or running time without harming the quality of the solutions obtained. In this thesis we present three parallel models, global model, island model and cellular model, each of which was adopted for the parallel implementation of genetic algorithms. In order to evaluate the benefits of using parallelism compared with the secuential of the version algorithm, we chose a of solutions combinatorial optimization problem called TSP. Later, we show the parallel version of this serial genetic algorithm using three parallel models. Finally, the performance of each one on the parallel models is compared using 4 and 8 processors with the sequential version.