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 o...

Full description

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
id UNACIONAL2_b06d72c0bee0a8658ee3ac334ed28380
oai_identifier_str oai:repositorio.unal.edu.co:unal/76688
network_acronym_str UNACIONAL2
network_name_str Universidad Nacional de Colombia
repository_id_str
spelling Atribución-NoComercial 4.0 InternacionalDerechos reservados - Universidad Nacional de Colombiahttp://creativecommons.org/licenses/by-nc/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Gómez Perdomo, JonatanPoveda Chaves, Roberto Manuelacd4b536-428d-4054-b1e0-d7ed1c7bc45e3002020-03-30T06:26:13Z2020-03-30T06:26:13Z2019https://repositorio.unal.edu.co/handle/unal/76688http://bdigital.unal.edu.co/73360/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.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 óptimo 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 8×8 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.Doctoradoapplication/pdfspaUniversidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e IndustrialDepartamento de Ingeniería de Sistemas e Industrial5 Ciencias naturales y matemáticas / Science62 Ingeniería y operaciones afines / EngineeringPoveda Chaves, Roberto Manuel (2019) PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP). Doctorado thesis, Universidad Nacional de Colombia - Sede Bogotá.PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)Trabajo de grado - Doctoradoinfo:eu-repo/semantics/doctoralThesisinfo:eu-repo/semantics/acceptedVersionhttp://purl.org/coar/resource_type/c_db06Texthttp://purl.org/redcol/resource_type/TDQuadratic Assignment Problem (QAP)Genetic Algorithm (GA)Parallel Genetic Algorithm (PGA)Graphics Processing Unit (GPU)Compute Unified Device Architecture (CUDA)Problema de Asignación CuadráticaAlgoritmos Genéticos ParalelosUnidades de Procesamiento GráficoArquitectura Unificada de Dispositivos de CómputoORIGINALThesis_PGAGrid_on_GPU.pdfapplication/pdf943658https://repositorio.unal.edu.co/bitstream/unal/76688/1/Thesis_PGAGrid_on_GPU.pdf75806ab37773aee893d17fdfc2258764MD51THUMBNAILThesis_PGAGrid_on_GPU.pdf.jpgThesis_PGAGrid_on_GPU.pdf.jpgGenerated Thumbnailimage/jpeg5317https://repositorio.unal.edu.co/bitstream/unal/76688/2/Thesis_PGAGrid_on_GPU.pdf.jpg58f31512df4e67fccc079873b60d9375MD52unal/76688oai:repositorio.unal.edu.co:unal/766882023-07-15 23:03:47.901Repositorio Institucional Universidad Nacional de Colombiarepositorio_nal@unal.edu.co
dc.title.spa.fl_str_mv PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
title PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
spellingShingle PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
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
title_short PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
title_full PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
title_fullStr PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
title_full_unstemmed PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
title_sort PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP)
dc.creator.fl_str_mv Poveda Chaves, Roberto Manuel
dc.contributor.author.spa.fl_str_mv Poveda Chaves, Roberto Manuel
dc.contributor.spa.fl_str_mv Gómez Perdomo, Jonatan
dc.subject.proposal.spa.fl_str_mv 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
topic 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
description 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.
publishDate 2019
dc.date.issued.spa.fl_str_mv 2019
dc.date.accessioned.spa.fl_str_mv 2020-03-30T06:26:13Z
dc.date.available.spa.fl_str_mv 2020-03-30T06:26:13Z
dc.type.spa.fl_str_mv Trabajo de grado - Doctorado
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/doctoralThesis
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/acceptedVersion
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_db06
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TD
format http://purl.org/coar/resource_type/c_db06
status_str acceptedVersion
dc.identifier.uri.none.fl_str_mv https://repositorio.unal.edu.co/handle/unal/76688
dc.identifier.eprints.spa.fl_str_mv http://bdigital.unal.edu.co/73360/
url https://repositorio.unal.edu.co/handle/unal/76688
http://bdigital.unal.edu.co/73360/
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.ispartof.spa.fl_str_mv Universidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e Industrial
Departamento de Ingeniería de Sistemas e Industrial
dc.relation.haspart.spa.fl_str_mv 5 Ciencias naturales y matemáticas / Science
62 Ingeniería y operaciones afines / Engineering
dc.relation.references.spa.fl_str_mv Poveda Chaves, Roberto Manuel (2019) PGAGrid: A Parallel Genetic Algorithm of Fine-Grained implemented on GPU to find solutions near the optimum to the Quadratic Assignment Problem (QAP). Doctorado thesis, Universidad Nacional de Colombia - Sede Bogotá.
dc.rights.spa.fl_str_mv Derechos reservados - Universidad Nacional de Colombia
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.license.spa.fl_str_mv Atribución-NoComercial 4.0 Internacional
dc.rights.uri.spa.fl_str_mv http://creativecommons.org/licenses/by-nc/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
rights_invalid_str_mv Atribución-NoComercial 4.0 Internacional
Derechos reservados - Universidad Nacional de Colombia
http://creativecommons.org/licenses/by-nc/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.mimetype.spa.fl_str_mv application/pdf
institution Universidad Nacional de Colombia
bitstream.url.fl_str_mv https://repositorio.unal.edu.co/bitstream/unal/76688/1/Thesis_PGAGrid_on_GPU.pdf
https://repositorio.unal.edu.co/bitstream/unal/76688/2/Thesis_PGAGrid_on_GPU.pdf.jpg
bitstream.checksum.fl_str_mv 75806ab37773aee893d17fdfc2258764
58f31512df4e67fccc079873b60d9375
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad Nacional de Colombia
repository.mail.fl_str_mv repositorio_nal@unal.edu.co
_version_ 1814090190276263936