Análisis del comportamiento de un AG para GPUs

Abstract

Este trabajo presenta un algoritmo genético simple ejecutando-se sobre GPU y empleando la tecnología CUDA para resolver el problema MaxCut. Se realiza un estudio empírico del impacto en el rendimiento del algoritmo en la elección de distintos operadores de cruce para representaciones binarias. Las pruebas mostraron un buen desempeño de las distintas variantes planteadas, aunque una mejor calidad de resultados se obtuvo con la variante utilizando un cruce de dos puntos de corte. El paso siguiente fue contrastar el rendimiento de este algoritmo con una misma versión pero ahora ejecutándose en serie sobre CPU y así poder determinar la ganancia de tiempo, reflejada por el speedup. Los resultados obtenidos indican que la ganancia en tiempo está relacionada con la densidad del grafo que representa cada instancia del MaxCut.