PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)

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 8x8 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.

• Autores: Poveda Chaves, Roberto Manuel
• Tipo de recurso: Doctoral thesis
• Fecha de publicación: 2019
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/76688
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/76688; http://bdigital.unal.edu.co/73360/
• Palabra clave: Quadratic Assignment Problem (QAP); Genetic Algorithm (GA); Parallel Genetic Algorithm (PGA); Graphics Processing Unit (GPU); Compute Unified Device Architecture (CUDA); Problema de Asignación Cuadrática; Algoritmos Genéticos Paralelos; Unidades de Procesamiento Gráfico; Arquitectura Unificada de Dispositivos de Cómputo
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional