DOI:
https://doi.org/10.14483/22484728.11738Publicado:
2016-12-20Número:
Vol. 10 Núm. 2 (2016)Sección:
Visión InvestigadoraProblema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo
Quadratic assignment problem (qap) on gpu through a master-slave pga
Palabras clave:
Algoritmos genéticos paralelos (AGP), Cálculo de Arquitectura Unificada de Dispositivos (CAUD), Problema de Asignación Cuadrática (PAC), Unidad de Procesamiento gráfico (UPG) (es).Palabras clave:
Parallel Genetic Algorithms (PGA), Compute Unified Device Architecture (CUDA), Quadratic Assignment Problem (QAP), Graphics Processing Unit (GPU) (en).Descargas
Resumen (es)
Este documento describe la implementación de un algoritmo genético paralelo maestroesclavo (AGP) en unidades de procesamiento gráfico (UPG) para encontrar soluciones o soluciones cercanas a soluciones óptimas para casos particulares del Problema de asignación Cuadrática (PAC). La eficiencia del algoritmo se prueba en un conjunto de problemas de la biblioteca estándar QAPLIB.
Resumen (en)
This document describes the implementation of a Master–Slave Parallel Genetic Algorithm (PGA) on Graphic Processing Units (GPU) to find solutions or solutions close to optimal solutions to particular instances of the Quadratic Assignment Problem (QAP). The efficiency of the algorithm is tested on a set of QAPLIB standard library problems.
Referencias
T. Koopmans and M. Beckman, "Assignment problems and the location of economic activities," Econometrica, vol. 25, pp. 53-76, 1957.
S. Sahni and T. Gonzalez, "P-complete approximation problems," Journal of the Association for Computing Machinery, vol. 23, pp. 555--565, 1976.
R. Burkard, E. Cela, P. Pardalos and L. Pitsoulis, "The quadratic assignment problem.," Handbook of Combinatorial Optimization, vol. 2, pp. 241-338, 1998.
E. Loiola, N. de Abreo, P. Boaventura-Nett, P. Hahn and T. Querido, "A survey for the quadratic assignment problem," European Journal of Operation Resarch, vol. 176, pp. 657-690, 2007.
R. Burkard, Ç. E., S. Karisch and R. F., "QAPLIB - "A Quadratic Assignment Problem Library," Septiembre 2015 [Online]. Available: http://www.opt.math.tu-graz.ac.at/qaplib/
R. Burkard, "The Quadratic Assignment Problem," Handbook of Combinatorial Optimization, pp.2741-2814, 2 nd Edition. Springer: New York, 2013.
Z. Michalewicz, "Genetic Algorithms + Data Structures = Evolution Programs," Springer- Verlag, 1994.
K. De Jong, W. Spears and D. Gordon, "Using genetic algorithms for concept learning.," Machine Learning, vol. 13, no. 2, pp. 161-188, 1993.
M. Tomassini, "A survey of genetic algorithms.," Annual Reviews of Computational Physics, World Scientific, vol. 3, pp. 87-118, 1995.
Nvidia, "CUDA GPUs" Agosto 2015 [Online]. Available:
https://developer.nvidia.com/cuda-gpus
T. Luong, N. Melab and E. Talbi, "Gpu-based island model for evolutionary algorithms," Genetic and Evolutionary Computation Conference, pp. 1089-1096, 2010.
N. Soca, J. Blengio, M. Pedemonte and P. Ezzatti, "Pugace, a cellular evolutionary algorithm framework on gpus," IEEE Congress on Evolutionary Computation, pp. 3891-3898, 2010.
M. Bashiri, "An analytical comparison to heuristic and meta-heuristic solution". Computers and Industrial Engineering (CIE), 2010 40th International Conference on
S. Tsutsui and N. Fujimoto, "An analytical study of gpu computation for solving qaps by parallel evolutionary computation with independent run," IEEE, 2010.
L. Thiele and T. Blickle, "A comparison of selection schemes used in genetic algorithms," TIK Report of Swiss Federal Insititute of Technology, 1995.
C. Kuijpers, P. Larrañaga, R. Murga, I. Inza and S. Dizdarevic, "Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators," Artificial Intelligence Review, vol. 13, no. 2, pp. 129-170, 1999.
E. León, J. Gómez and R. Poveda, "Grisland: A parallel genetic algorithm for finding near optimal," GECCO, 2009.
.png)
.jpg)
