%0 Generic
%A Córdoba González, Carmen
%A Pedraz Sánchez, Juan Carlos
%T Implementación de un algoritmo genético paralelo sobre HW gráfico de última generación
%J Trabajos de curso (Departamento de Arquitectura de Computadores y Automática)
%D 2005
%U https://hdl.handle.net/20.500.14352/54285
%X Los algoritmos genéticos (AGs) son procedimientos de búsqueda y optimizacióninspirados por la simplicidad y efectividad del proceso de la evolución natural de lasespecies. Al igual que ocurre en la naturaleza, basan su éxito en la supervivencia de losindividuos más aptos de una población. En este caso, un individuo es una soluciónpotencial del problema, y se implementa como una estructura de datos. Los AGstrabajan sobre poblaciones de soluciones que evolucionan mediante la aplicación deoperadores genéticos (selección, cruce y mutación) adecuados al problema específicoque intentan resolver. Uno de los rasgos esenciales de los AGs es su paralelismoimplí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, frecuentementeprogramables, que permanecen inactivas durante la ejecución de aplicaciones nográficas. Dichas tarjetas cuentan con un procesador de naturaleza paralela, que las haceespecialmente indicadas para la ejecución de AGs.Este trabajo es una propuesta para aprovechar un recurso hardware habitualmenteinactivo para implementar, en un sistema monoprocesador, algún tipo de topología deAGs paralelos. Obtenemos así mejoras -tanto en la calidad de las soluciones como en eltiempo 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 natureselects the best individuals (the best adaptation to the environment) to createdescendants which are more highly adapted. The first step is to generate a random initialpopulation, where each individual is represented by a character chain like achromosome and with the greatest diversity, so that this population has the widest rangeof characteristics. Each individual represents a solution for the targeted problem. Then,each individual is evaluated using a fitness function, which indicates the quality of eachindividual. Finally, the best-adapted individuals are selected to generate a newpopulation, whose average will be nearer to the desired solution. This new population iscreated making use of three operators: selection, crossover and mutation.One of themajor aspects of GA is their ability to be parallelised. Indeed, because natural evolutiondeals with an entire population and not only with particular individuals, it is aremarkably highly parallel process.Nowadays computer systems incorporate powerful graphic cards that are commonly idleduring a normal execution process of most of the optimization algorithms. Moderngraphic cards use a pipelined streaming architecture to perform a significant part of therendering process. Two stages in the pipelined process are programmable in currentgraphics hardware. The vertex engine is used to perform transformations on the vertexattributes (normal, position, color, texture, ...). On the other hand, the fragment engine isused to transform the fragments that form the different polygons. Both engines areextremely parallel, processing several elements in parallel and making extensive use ofSIMD units.In this work we have presented a parallel implementation of a GA using a GPU. Wehave implemented not only three well know benchmarks problems with excellentSpeed-up results, but also a novel implementation of an algorithm for solving defectivesproblems proposed in the literature.
%~