Topologies, migration rates, and multi-population parallel genetic algorithms
Erick Cantú‐Paz · 1999
This paper presents a study of parallel genetic algorithms (GAs) with multiple populations (also called demes or islands). The study makes explicit the relation between the probability of reaching a desired solution with the deme size, the migration rate, and the degree of the connectivity graph. The paper considers arbitrary topologies with a fixed number of neighbors per deme. The demes evolve in isolation until each converges to a unique solution. Then, the demes exchange an arbitrary number of individuals and restart their execution. An accurate deme-sizing equation is derived, and it is used to determine the optimal configuration of an arbitrary number of demes that minimizes the execution time of the parallel GA. 1 INTRODUCTION Parallel genetic algorithms (GAs) with multiple populations are difficult to configure because they are controlled by many parameters that affect their efficiency and accuracy. Among other things, one must decide the number and the size of the populations...