Combinatorial optimization NP-Hard problem solved by usingthe quadratic assignment problem (QAP) solution through aparallel genetic algorithm on GPU
Document title: Combinatorial optimization NP-Hard problem solved by usingthe quadratic assignment problem (QAP) solution through aparallel genetic algorithm on GPU
Journal: Visión electrónica
Database: PERIÓDICA
System number: 000461344
ISSN: 1909-9746
Authors: 1
2
2
Institutions: 1Universidad Nacional de Colombia, Bogotá. Colombia
2Universidad Distrital Francisco José de Caldas, Bogotá. Colombia
Year:
Season: Jul-Dic
Volumen: 11
Number: 2
Pages: 146-151
Country: Colombia
Language: Inglés
Document type: Artículo
Approach: Aplicado
Spanish abstract En este documento se resuelven algunas instancias de problemas bien conocidos de optimización combinatorial de tipo NP-Hard a partir de la formulaci ́on deKoopmans y Beckmann del problema de Asignaci ́on Cuadr ́atica (QAP). Dichasinstancias son solucionadas mediante un Algoritmo Gen ́etico EmbarasosamenteParalelo o mediante un Algoritmo Gen ́etico Paralelo de Islas, en ambos casos, laimplementaci ́on se hace sobre unidades de procesamiento gr ́afico (GPU’s)
English abstract In this article, some instances of well known combinatorial optimization NP-Hardproblems are solved by using Koopmans and Beckmann formulation of the quadraticassignment problem (QAP). These instances are solved by using an EmbarrassinglyParallel Genetic Algorithm or by using an Island Parallel Genetic Algorithm;in both cases, the implementation is carried out on Graphics Processing Units(GPUs)
Disciplines: Ciencias de la computación
Keyword: Algoritmos genéticos,
Problema de asignación cuadrática,
Problemas de optimización combinatorial,
Unidades de procesamiento gráfico
Keyword: Genetic algorithms,
Graphics processing units,
NP-hard problems,
Quadratic assignment problem
Full text: https://revistas.udistrital.edu.co/index.php/visele/article/view/14623/14650