Abstract: This work consists in implementing a fine-grained parallel genetic algorithm improved with a greedy 2-opt heuristic to find near-optimal solutions to the Quadratic Assignment Problem (QAP). The proposed algorithm was fully implemented on Graphics Processing Units (GPUs). A two-dimensional GPU grid of size 8_8 defines the population of the genetic algorithm (set of permutations of the QAP), and each GPU block consists of n GPU threads, where n is the size of the QAP. Each GPU block was used to represent the chromosome of a single individual, and each GPU thread represents a gene of such chromosome. The proposed algorithm was tested on a subset of the standard QAPLIB data set. Results show that this implementation is able to find good solutions for large QAP instances in few parallel iterations of the evolutionary process.

Resumen: Este trabajo consiste en implementar un algoritmo genético paralelo de grano fino mejorado con una heurística 2-opt voraz para encontrar soluciones cercanas al _optimo al problema de Asignación Cuadrática (QAP). El algoritmo propuesto fue completamente implementado sobre Unidades de Procesamiento Gráfico (GPUs). Una retícula GPU bidimensional de tamaño 8x8 define la población del algoritmo genético (conjunto de permutaciones del QAP) y cada bloque GPU consiste de n hilos GPU donde n es el tamaño del QAP. Cada bloque GPU fue utilizado para representar el cromosoma de un solo individuo y cada hilo GPU representa un gen de tal cromosoma. El algoritmo propuesto fue comprobado sobre un subconjunto de problemas de la librería estándar QAPLIB. Los resultados muestran que esta implementación es capaz de encontrar buenas soluciones para grandes instancias del QAP en pocas iteraciones del proceso evolutivo.

Keywords: Quadratic Assignment Problem (QAP), Genetic Algorithm (GA), Parallel Genetic Algorithm (PGA), Graphics Processing Unit (GPU), Compute Unified Device Architecture (CUDA).
Palabras clave: Problema de Asignación Cuadrática, Algoritmos Genéticos, Algoritmos Genéticos Paralelos, Unidades de Procesamiento Gráfico, Arquitectura Unificada de Dispositivos de Cómputo.

Socialización: miércoles 12 de junio 11 a.m. auditorio Sabio Caldas

Roberto Manuel Poveda Chaves.
Profesor TC. Facultad de Ingeniería.
Matemático. Universidad Nacional de Colombia.
MSc. Ingeniería de Sistemas. Universidad Nacional de Colombia
PhD. Ingeniería de Sistemas. Universidad Nacional de Colombia.