An Analysis of Synchronous and Asynchronous parallel Distributed Genetic Algorithms with Structured and panmictic Islands

摘要

In a paralle lgenetic algorithm several communicating nodel GAs evolve in parallel to solve the same problem. PGAs have been traditionally used to extend the power of serial GAs since they often can be tailored to provide a larger efficiency on compl search tasks. This has led to a considerable number of different models and implementations that preclude direct comparision and knowledge exchange. To fill this gap we begin by providinga common framework for studying PGAs. Ths allows us to analyze the importance of the synchronism in the migration step of parallel distributed GAs. We will show how this implementation issue affect the evaluation effort as well as the serach time and the speedup. In addition, we consider popular evolution schemes of pammictic and structred-popular evolution schemes of pammicitc and structured-population GAs for the islands. The evaluated PGAs demonstrate linear and even super-linear speedup when run in a cluster of workstations. They also show important numericla benefis when compared with their sequential counterparts. In addition, we always report lower search tiems for the asynchronous versions.