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, because previous studies show that there is a crucial relation between solution quality 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 parallelized, and its execution time is optimized. The rest of the paper deals with parallel GAs with multiple populations. Two bounding cases of the migration rate and topology are analyzed, and the case that yields good speedups is optimized. Later, the models are specialized to consider sparse topologies and migration rates that are more likely to be used by practitioners. The paper also presents the additional advantages of combining multi- and single-population parallel GAs. The results of this work are simple models that practitioners may use to design efficient and competent parallel GAs. (C) 2000 Elsevier Science S.A. All rights reserved.