DOI:

https://doi.org/10.14483/22484728.11738

Publicado:

2016-12-20

Número:

Vol. 10 Núm. 2 (2016)

Sección:

Visión Investigadora

Problema 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

Autores/as

  • Julián Octavio Castellanos Millán
  • Víctor Hugo Amarillo Calvo
  • Roberto Manuel Poveda Chaves

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.

Cómo citar

APA

Castellanos Millán, J. O., Amarillo Calvo, V. H., & Poveda Chaves, R. M. (2016). Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo. Visión electrónica, 10(2), 179–183. https://doi.org/10.14483/22484728.11738

ACM

[1]
Castellanos Millán, J.O., Amarillo Calvo, V.H. y Poveda Chaves, R.M. 2016. Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo. Visión electrónica. 10, 2 (dic. 2016), 179–183. DOI:https://doi.org/10.14483/22484728.11738.

ACS

(1)
Castellanos Millán, J. O.; Amarillo Calvo, V. H.; Poveda Chaves, R. M. Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo. Vis. Electron. 2016, 10, 179-183.

ABNT

CASTELLANOS MILLÁN, J. O.; AMARILLO CALVO, V. H.; POVEDA CHAVES, R. M. Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo. Visión electrónica, [S. l.], v. 10, n. 2, p. 179–183, 2016. DOI: 10.14483/22484728.11738. Disponível em: https://revistas.udistrital.edu.co/index.php/visele/article/view/11738. Acesso em: 20 may. 2022.

Chicago

Castellanos Millán, Julián Octavio, Víctor Hugo Amarillo Calvo, y Roberto Manuel Poveda Chaves. 2016. «Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo». Visión electrónica 10 (2):179-83. https://doi.org/10.14483/22484728.11738.

Harvard

Castellanos Millán, J. O., Amarillo Calvo, V. H. y Poveda Chaves, R. M. (2016) «Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo», Visión electrónica, 10(2), pp. 179–183. doi: 10.14483/22484728.11738.

IEEE

[1]
J. O. Castellanos Millán, V. H. Amarillo Calvo, y R. M. Poveda Chaves, «Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo», Vis. Electron., vol. 10, n.º 2, pp. 179–183, dic. 2016.

MLA

Castellanos Millán, J. O., V. H. Amarillo Calvo, y R. M. Poveda Chaves. «Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo». Visión electrónica, vol. 10, n.º 2, diciembre de 2016, pp. 179-83, doi:10.14483/22484728.11738.

Turabian

Castellanos Millán, Julián Octavio, Víctor Hugo Amarillo Calvo, y Roberto Manuel Poveda Chaves. «Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo». Visión electrónica 10, no. 2 (diciembre 20, 2016): 179–183. Accedido mayo 20, 2022. https://revistas.udistrital.edu.co/index.php/visele/article/view/11738.

Vancouver

1.
Castellanos Millán JO, Amarillo Calvo VH, Poveda Chaves RM. Problema de asignación quadrática (pac) sobre gpu a través de una pga maestro-esclavo. Vis. Electron. [Internet]. 20 de diciembre de 2016 [citado 20 de mayo de 2022];10(2):179-83. Disponible en: https://revistas.udistrital.edu.co/index.php/visele/article/view/11738

Descargar cita

Visitas

323

Dimensions


PlumX


Descargas

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