Paper Info
Title
Solving The Quadratic Assignment Problem (Qap) Through A Fine-Grained Parallel Genetic Algorithm Implemented On Gpus
Abstract
This paper presents a fine-grained parallel genetic algorithm improved with a 2-opt heuristic for finding solutions near to the optimum to the Quadratic Assignment Problem (QAP). The proposed algorithm is fully implemented on Graphics Processing Units (GPUs). Unlike previous approaches reported in the literature our implementation a two-dimensional GPU grid of size 10x10 defines the population of the genetic algorithm (set of permutations of the QAP) and each GPU block consists of n GPU threads where n is the size of QAP. Each GPU block is used to represent the chromosome of a single individual and each GPU thread represents a gene of such chromosome. The proposed algorithm is tested on a subset of the standard QAPLIB data set. Our results show that our implementation is able to find good solutions for large QAP instances in few parallel iterations of the evolutionary process.
Year
DOI
Venue
2018
10.1007/978-3-319-98446-9_14
COMPUTATIONAL COLLECTIVE INTELLIGENCE, ICCCI 2018, PT II
Keywords
Field
DocType
Quadratic Assignment Problem, Parallel genetic algorithms, Graphics Processing Units
Graphics,Population,Data mining,Heuristic,Quadratic assignment problem,Computer science,Permutation,Parallel computing,Thread (computing),Genetic algorithm,Grid
Conference
Volume
ISSN
Citations 
11056
0302-9743
1
PageRank 
References 
Authors
0.36
2
2
Name
Order
Citations
PageRank
Roberto Poveda111.04
Jonatan Gómez224129.70