PaDe: A Parallel Algorithm Based on the MOEA/D Framework and the Island Model

Abstract. We study a coarse grained parallelization scheme (thread based) aimed at solving complex multi-objective problems by means of decomposition. Our scheme is loosely based on the MOEA/D framework. The resulting algorithm, called Parallel Decomposition (PaDe), makes use of the asynchronous generalized island model to solve the various decomposed problems. Efficient exchange of chromosomic material among islands happens via a fixed migration topology defined by the proximity of the decomposed problem weights. Each decomposed problem is solved using a generic single objective evolutionary algorithm (in this paper we experiment with self-adaptive differential evolution (jDE)). Comparing our algorithm to MOEA/D-DE we find that it is attractive in terms of performances and, most of all, in terms of computing time. Experiments with increasing numbers of threads show that PaDe scales well, being able to fully exploit the number of underlying available cores