Effects of Parameters of an Island Model Parallel Genetic Algorithm for the Quadratic Assignment Problem

摘要

Quadratic Assignment Problem (QAP) is one of the most difficult combinatorial problems in the literature and has a diverse field of applications. This paper presents the results of experiments on the impact of parallelization of a sequential GA using island model. Both of the genetic algorithms are applied to the QAP. For the island model parallel GA, we systematically change the number of islands and investigate the effects of dividing the same global population into a number of subpopulations. The number of islands is gradually increased to observe the effects on solution quality and speedup in total execution time using different problem instances. The results clearly indicate that, while parallelized version outperforms sequential counterpart in both solution quality and total execution time, an increasing number of subpopulations also positively effects the results until a critical point where every subpopulation has a certain number of individuals to be able to evolve independently. Beyond that point, the performance of the algorithm begins to decrease.