Implementación de algoritmos genéticos sobre la plataforma de desarrollo paralelo CUDA

Abstract

Los algoritmos genéticos (AGs) son técnicas de búsqueda y optimización inspiradas en la naturaleza que utilizan propiedades como la herencia, mutación, selección y cruce. Una de las cualidades principales de los algoritmos genéticos es su grado de paralelismo implícito, ya que se trabaja con un conjunto de soluciones de forma simultánea. Al igual que en la naturaleza, la evolución de los individuos no depende únicamente de ellos, si no también de la población a la que pertenece. Por otra parte, actualmente casi todos los computadores personales cuentan con una tarjeta gráfica destinada a la ejecución de aplicaciones gráficas (videojuegos). En la mayoría de las ocasiones estas tarjetas aparecen inactivas y se está desperdiciando su capacidad para realizar cálculos paralelos. Nuestro trabajo está destinado a utilizar ese hardware desaprovechado para implementar un conjunto de algoritmos que solucionen el problema del Viajante de Comercio y la función de Schwefel. Los principales objetivos de nuestro trabajo son estudiar la sobrecarga de comunicaciones en la comunicación CPU-GPU y evaluar distintos operadores genéticos utilizando las ventajas de programación que proporciona CUDA, el nuevo lenguaje de programación paralelo de Nvidia. [ABSTRACT] The genetic algorithms (GAs) are search and improvement technique inspired by evolutionary biology such as inheritance, mutation, selection and crossover. One of the most important features of the genetic algorithms is their high degree to be parallelised, because they use a group of solutions at the same time. As in the natural world, individual’s evolution depends not only the character, but also the environment. Nowadays, almost all the medium PC’s have a graphic card used to execute graphic applications (videogames). The most of the time, we are wasting all this capacity of parallel calculation. Our work is destined to use this wasted hardware to implement GA that solvent the Traveling Salesman Problem (TSP) and the Schwefel function as well. The project’s goals are to study the communication overload in the transfers between CPU and GPU and to evaluate different genetic operators using the CUDA’s advantages, the new language for parallel programming of NVIDIA.