Parallelism and evolutionary algorithms

TLDR

This paper surveys modern parallelization techniques for evolutionary algorithms, noting that while EA families have converged, parallel EAs lack unified studies and many recent improvements necessitate a comprehensive review. The authors aim to clarify the distinctions between EA models and their parallel implementations, evaluate the advantages and drawbacks of parallel EAs, and highlight applications, open problems, and potential solutions. They classify recent theoretical and practical results that address identified problems, propose solutions, and provide a structured background to inform researchers about decentralizing and parallelizing EAs.

Abstract

This paper contains a modern vision of the parallelization techniques used for evolutionary algorithms (EAs). The work is motivated by two fundamental facts: 1) the different families of EAs have naturally converged in the last decade while parallel EAs (PEAs) are still lack of unified studies; and 2) there is a large number of improvements in these algorithms and in their parallelization that raise the need for a comprehensive survey. We stress the differences between the EA model and its parallel implementation throughout the paper. We discuss the advantages and drawbacks of PEAs. Also, successful applications are mentioned and open problems are identified. We propose potential solutions to these problems and classify the different ways in which recent results in theory and practice are helping to solve them. Finally, we provide a highly structured background relating to PEAs in order to make researchers aware of the benefits of decentralizing and parallelizing an EA.