DOI:
https://doi.org/10.14483/22484728.14623Publicado:
2017-12-31Número:
Vol. 11 Núm. 2 (2017)Sección:
Visión InvestigadoraCombinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU
Problemas de optimización combinatorial np-hard solucionados a partir del problema de asignación cuadrática solución a través de un algoritmo genético paralelo sobre GPU
Palabras clave:
Combinatorial Optimization NP-Hard Problem, Compute Unified Device Architecture (CUDA), Graphics Processing Unit (GPU), Parallel Genetic Algorithms (PGA), Quadratic Assignment Problem (QAP) (en).Palabras clave:
Problemas de Optimización Combinatorial NP–Difíciles, Arquitectura Unificada de Dispositivos de Cómputo (CUDA), Unidades de Procesamiento Gráfico (GPU), Algoritmos Genéticos Paralelos, Problema de Asignación Cuadrática (QAP) (es).Descargas
Resumen (en)
In this article, some instances of well known combinatorial optimization NP-Hard problems are solved by using Koopmans and Beckmann formulation of the quadratic assignment problem (QAP). These instances are solved by using an Embarrassingly Parallel Genetic Algorithm or by using an Island Parallel Genetic Algorithm; in both cases, the implementation is carried out on Graphics Processing Units (GPUs).
Resumen (es)
En este documento se resuelven algunas instancias de problemas bien conocidos de optimización combinatorial de tipo NP-Hard a partir de la formulación de Koopmans y Beckmann del problema de Asignación Cuadrática (QAP). Dichas instancias son solucionadas mediante un Algoritmo Genético Embarasosamente Paralelo o mediante un Algoritmo Genético Paralelo de Islas, en ambos casos, la implementación se hace sobre unidades de procesamiento gráfico (GPU’s).
Referencias
[1] T Koopmans and M Beckman, "Assignment problems and the location of economic activities.," Econométrica, vol 25, no. 1, pp. 53-76, 1957. pp. 53-76.
[2] N Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem," Technical Report 338, 1976.
[3] R.E. Burkard, "The Quadratic Assignment Problem," Pardalos P.M. Handbook of Combinatorial Optimization, 2013, https://doi.org/10.1007/978-1-4419-7997-1_22
[4] E Lawler and J Lenstra, "The Traveling Salesman Problem," Wiley, Chichester, 1985.
[5] M Garey and D Johnson, "Computers and Intractability: A Gude to the Theory of NP-Completeness," W.H.Freeman and Company, New York, 1979.
[6] P Pardalos and J Xue, "The maximum clique problem.," J. Global Optim 4, pp. 301-328, 1994, https://doi.org/10.1007/BF01098364
[7] K. De Jong, W. Spears, and D. Gordon, "Using genetic algorithms for concept learning.," Machine Learning, vol. 13, no. 2, pp. 161-188, 1993, https://doi.org/10.1007/BF00993042
[8] M Tomassini., "A Survey of Genetic Algorithms," Volume III of Annual Reviews of Computational Physics, World Scientific., vol. 3, pp. 87-118, 1995, https://doi.org/10.1142/9789812830647_0003
[9] Nvidia CUDA. May 12th 2016 [Online]. Available : https://developer.nvidia.com/cuda-gpus
[10] University, Heidelberg. May 12th 2016 [Online]. Available: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[11] University of Florida The Harn Museum. “The SuiteSparse Matrix Collection” May 12th 2016 [Online]. Available: http://www.cise.ufl.edu/research/sparse/matrices/
[12] University of Glasgow School of Computing Science. (2012) DIMACS. May 12th 2016 [Online]. Available: http://www.dcs.gla.ac.uk/~pat/maxClique/distribution/DIMACS_cliques/
[13] E. León, J. Gómez, and R. Poveda, "Grisland: A parallel genetic algorithm for finding near optimal," GECCO, Montreal, Canada, pp. 2035-2040, 2009.
[2] N Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem," Technical Report 338, 1976.
[3] R.E. Burkard, "The Quadratic Assignment Problem," Pardalos P.M. Handbook of Combinatorial Optimization, 2013, https://doi.org/10.1007/978-1-4419-7997-1_22
[4] E Lawler and J Lenstra, "The Traveling Salesman Problem," Wiley, Chichester, 1985.
[5] M Garey and D Johnson, "Computers and Intractability: A Gude to the Theory of NP-Completeness," W.H.Freeman and Company, New York, 1979.
[6] P Pardalos and J Xue, "The maximum clique problem.," J. Global Optim 4, pp. 301-328, 1994, https://doi.org/10.1007/BF01098364
[7] K. De Jong, W. Spears, and D. Gordon, "Using genetic algorithms for concept learning.," Machine Learning, vol. 13, no. 2, pp. 161-188, 1993, https://doi.org/10.1007/BF00993042
[8] M Tomassini., "A Survey of Genetic Algorithms," Volume III of Annual Reviews of Computational Physics, World Scientific., vol. 3, pp. 87-118, 1995, https://doi.org/10.1142/9789812830647_0003
[9] Nvidia CUDA. May 12th 2016 [Online]. Available : https://developer.nvidia.com/cuda-gpus
[10] University, Heidelberg. May 12th 2016 [Online]. Available: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[11] University of Florida The Harn Museum. “The SuiteSparse Matrix Collection” May 12th 2016 [Online]. Available: http://www.cise.ufl.edu/research/sparse/matrices/
[12] University of Glasgow School of Computing Science. (2012) DIMACS. May 12th 2016 [Online]. Available: http://www.dcs.gla.ac.uk/~pat/maxClique/distribution/DIMACS_cliques/
[13] E. León, J. Gómez, and R. Poveda, "Grisland: A parallel genetic algorithm for finding near optimal," GECCO, Montreal, Canada, pp. 2035-2040, 2009.
Cómo citar
APA
Cárdenas Gómez, E., Poveda Chaves, R., y García Hurtado, O. (2017). Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU. Visión electrónica, 11(2), 146–151. https://doi.org/10.14483/22484728.14623
ACM
[1]
Cárdenas Gómez, E. et al. 2017. Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU. Visión electrónica. 11, 2 (dic. 2017), 146–151. DOI:https://doi.org/10.14483/22484728.14623.
ACS
(1)
Cárdenas Gómez, E.; Poveda Chaves, R.; García Hurtado, O. Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU. Vis. Electron. 2017, 11, 146-151.
ABNT
CÁRDENAS GÓMEZ, Eduardo; POVEDA CHAVES, Roberto; GARCÍA HURTADO, Orlando. Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU. Visión electrónica, [S. l.], v. 11, n. 2, p. 146–151, 2017. DOI: 10.14483/22484728.14623. Disponível em: https://revistas.udistrital.edu.co/index.php/visele/article/view/14623. Acesso em: 19 abr. 2024.
Chicago
Cárdenas Gómez, Eduardo, Roberto Poveda Chaves, y Orlando García Hurtado. 2017. «Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU». Visión electrónica 11 (2):146-51. https://doi.org/10.14483/22484728.14623.
Harvard
Cárdenas Gómez, E., Poveda Chaves, R. y García Hurtado, O. (2017) «Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU», Visión electrónica, 11(2), pp. 146–151. doi: 10.14483/22484728.14623.
IEEE
[1]
E. Cárdenas Gómez, R. Poveda Chaves, y O. García Hurtado, «Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU», Vis. Electron., vol. 11, n.º 2, pp. 146–151, dic. 2017.
MLA
Cárdenas Gómez, Eduardo, et al. «Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU». Visión electrónica, vol. 11, n.º 2, diciembre de 2017, pp. 146-51, doi:10.14483/22484728.14623.
Turabian
Cárdenas Gómez, Eduardo, Roberto Poveda Chaves, y Orlando García Hurtado. «Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU». Visión electrónica 11, no. 2 (diciembre 31, 2017): 146–151. Accedido abril 19, 2024. https://revistas.udistrital.edu.co/index.php/visele/article/view/14623.
Vancouver
1.
Cárdenas Gómez E, Poveda Chaves R, García Hurtado O. Combinatorial optimization np-hard problem solved by using the quadratic assignment problem (QAP) solution through a parallel genetic algorithm on GPU. Vis. Electron. [Internet]. 31 de diciembre de 2017 [citado 19 de abril de 2024];11(2):146-51. Disponible en: https://revistas.udistrital.edu.co/index.php/visele/article/view/14623
.png)
.jpg)
