Analyzing synchronous and asynchronous parallel distributed genetic algorithms

Parallel genetic algorithms (PGAs) have been traditionally used to extend the power of serial genetic algorithms (GAs), since they often can be tailored to provide a larger efficiency on complex search problems. In a PGA several sub-algorithms cooperate in parallel to solve the problem. This high-level definition has led to a considerable number of different implementations that preclude direct comparisons and knowledge exchange. To fill this gap we begin by providing a common framework for studying PGAs. We then analyze the importance of the synchronism in the migration step of various parallel distributed GAs. This implementation issue could affect the evaluation effort as well as could provoke some differences in the search time and speedup. We cover in this study a set of popular evolution schemes relating panmictic (steady-state or generational) and structured-population (cellular) GAs for the islands. We aim at extending existing results to structured-population GAs, and also to new problems. The evaluated PGAs demonstrate linear and even super-linear speedup when run in a cluster of workstations. They also show important numerical benefits if compared with their sequential versions. In addition, we always report lower search times for the asynchronous versions. (C) 2001 Elsevier Science B.V. All rights reserved.