Premium
Parallel genetic algorithm for N‐Queens problem based on message passing interface‐compute unified device architecture
Author(s) -
Jianli Cao,
Zhikui Chen,
Yuxin Wang,
He Guo
Publication year - 2020
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/coin.12300
Subject(s) - speedup , computer science , message passing interface , message passing , algorithm , simulated annealing , genetic algorithm , parallel algorithm , node (physics) , parallel computing , set (abstract data type) , interface (matter) , fitness function , structural engineering , bubble , machine learning , maximum bubble pressure method , engineering , programming language
N‐Queens problem derives three variants: obtaining a specific solution, obtaining a set of solutions and obtaining all solutions. The purpose of the variant I is to find a constructive solution, which has been solved. Variant III is aiming to find all solutions and the largest number of queens currently being resolved is 26. Variant II whose purpose is to obtain a set of solutions for larger‐scale problems relies on various intelligent algorithms. In this paper, we use a master‐slave model genetic algorithm that combines the idea of the evolutionary algorithm and simulated annealing algorithm to solve Variant III, and use a parallel fitness function based on compute unified device architecture. Experimental results show that our scheme achieved a maximum 60‐fold speedup over the single‐CPU counterpart. On this basis, a two‐level parallel genetic algorithm based on the island model and master‐slave model is implemented on the GPU cluster by using message passing interface technology. Using two‐node and three‐node GPU cluster, speedup of 1.46 and 2.01 are obtained on average over single‐node, respectively. Compared with the sequential genetic algorithm, the two‐level parallel genetic algorithm makes full use of the parallel computing power of GPU cluster in solving N‐Queen variant II and improves the performance by 99.19 times in the best case.