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

  • 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_US)
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_ES)

Resumen (en_US)

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

Descargas

La descarga de datos todavía no está disponible.

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
Cárdenas Gómez, E., Poveda Chaves, R., & García Hurtado, O. (2018). 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. Visión electrónica, 11(2), 146-151. https://doi.org/10.14483/22484728.14623
julio-diciembre de 2017
Publicado: 2018-10-27
Sección
Visión Investigadora

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