Efficient parallel genetic algorithms: theory and practice

Parallel genetic algorithms (GAs) are complex programs that are controlled by many parameters, which affect their search quality and their efficiency. The goal of this paper is to provide guidelines to choose those parameters rationally. The investigation centers on the sizing of populations, becaus e previous studies show that there is a crucial relation between solution q uality and population size. As a first step, the paper shows how to size a simple GA to reach a solution of a desired quality. The simple GA is then p arallelized, and its execution time is optimized. The rest of the paper dea ls with parallel GAs with multiple populations. Two bounding cases of the m igration rate and topology are analyzed, and the case that yields good spee dups is optimized. Later, the models are specialized to consider sparse top ologies and migration rates that are more likely to be used by practitioner s. The paper also presents the additional advantages of combining multi- an d single-population parallel GAs. The results of this work are simple model s that practitioners may use to design efficient and competent parallel GAs . (C) 2000 Elsevier Science S.A. All rights reserved.