Implementación de un algoritmo genético paralelo sobre HW gráfico de última generación

Abstract

Los algoritmos genéticos (AGs) son procedimientos de búsqueda y optimización inspirados por la simplicidad y efectividad del proceso de la evolución natural de las especies. Al igual que ocurre en la naturaleza, basan su éxito en la supervivencia de los individuos más aptos de una población. En este caso, un individuo es una solución potencial del problema, y se implementa como una estructura de datos. Los AGs trabajan sobre poblaciones de soluciones que evolucionan mediante la aplicación de operadores genéticos (selección, cruce y mutación) adecuados al problema específico que intentan resolver. Uno de los rasgos esenciales de los AGs es su paralelismo implícito puesto que, al igual que la evolución natural, trabajan con poblaciones enteras, no con sus individuos integrantes en particular. Los sistemas actuales cuentan con potentes tarjetas gráficas, frecuentemente programables, que permanecen inactivas durante la ejecución de aplicaciones no gráficas. Dichas tarjetas cuentan con un procesador de naturaleza paralela, que las hace especialmente indicadas para la ejecución de AGs. Este trabajo es una propuesta para aprovechar un recurso hardware habitualmente inactivo para implementar, en un sistema monoprocesador, algún tipo de topología de AGs paralelos. Obtenemos así mejoras -tanto en la calidad de las soluciones como en el tiempo de ejecución- con respecto a la ejecución secuencial del AG sobre la CPU. [ABSTRACT] Genetic algorithms (GAs) are optimization techniques which imitate the way that nature selects the best individuals (the best adaptation to the environment) to create descendants which are more highly adapted. The first step is to generate a random initial population, where each individual is represented by a character chain like a chromosome and with the greatest diversity, so that this population has the widest range of characteristics. Each individual represents a solution for the targeted problem. Then, each individual is evaluated using a fitness function, which indicates the quality of each individual. Finally, the best-adapted individuals are selected to generate a new population, whose average will be nearer to the desired solution. This new population is created making use of three operators: selection, crossover and mutation.One of the major aspects of GA is their ability to be parallelised. Indeed, because natural evolution deals with an entire population and not only with particular individuals, it is a remarkably highly parallel process. Nowadays computer systems incorporate powerful graphic cards that are commonly idle during a normal execution process of most of the optimization algorithms. Modern graphic cards use a pipelined streaming architecture to perform a significant part of the rendering process. Two stages in the pipelined process are programmable in current graphics hardware. The vertex engine is used to perform transformations on the vertex attributes (normal, position, color, texture, ...). On the other hand, the fragment engine is used to transform the fragments that form the different polygons. Both engines are extremely parallel, processing several elements in parallel and making extensive use of SIMD units. In this work we have presented a parallel implementation of a GA using a GPU. We have implemented not only three well know benchmarks problems with excellent Speed-up results, but also a novel implementation of an algorithm for solving defectives problems proposed in the literature.