Author/Authors :
özçetin, erdener anadolu üniversitesi - mühendislik fakültesi - endüstri mühendisliği bölümü, turkey , öztürk, gürkan anadolu üniversitesi - mühendislik fakültesi - endüstri mühendisliği bölümü, Turkey
Title Of Article :
A HYBRID GENETIC ALGORITHM FOR THE QUADRATIC ASSIGNMENT PROBLEM ON GRAPHICS PROCESSING UNITS
Abstract :
In this paper, a hybrid genetic algorithm is proposed for the quadratic assignment problem. The most time-consuming parts of the proposed algorithm are the calculation of objective function values and the local search operator. Therefore, the parallelization and implementation on graphics processing units of these parts was addressed. This parallel algorithm and its sequential version have been tested and compared for 49 instances in the literature. The best-known solutions were obtained for 34 of these instances. Computational experiments show that the proposed algorithm is capable of providing good quality solutions in a short time. Indeed, it can be observed that the parallel algorithm works up to 51 times faster --17 times faster on average-- than the sequential algorithm.
NaturalLanguageKeyword :
Quadratic assignment problem (QAP) , parallel programming , graphics processing units (GPU) , CUDA
JournalTitle :
Anadolu University Journal of Science and Technology. A : Applied Sciences and Engineering
