DOI:

https://doi.org/10.14483/22484728.14623

Publicado:

2017-12-31

Número:

Vol. 11 Núm. 2 (2017)

Sección:

Visión Investigadora

Combinatorial 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

Autores/as

  • Eduardo Cárdenas Gómez
  • Roberto Poveda Chaves
  • Orlando García Hurtado

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.

Cómo citar

APA

Cárdenas Gómez, E., Poveda Chaves, R., & 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., 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 (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, 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. 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: 26 nov. 2022.

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, E., 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». 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 noviembre 26, 2022. 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 26 de noviembre de 2022];11(2):146-51. Disponible en: https://revistas.udistrital.edu.co/index.php/visele/article/view/14623

Descargar cita

Visitas

555

Dimensions


PlumX


Descargas

Los datos de descargas todavía no están disponibles.

Artículos más leídos del mismo autor/a