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