Combining Distributed Populations and Periodic Centralized Selections in Coarse-Grain Parallel Genetic Algorithms

In this paper we demonstrate that parallel genetic algorithms can profit from performing periodic centralized selections of distributed populations. With this combination, implementations can benefit from the variety of environments provided by distributed approaches, while periodically being able to consider the population as a whole and disregard very unfit individuals. We study four different parallel genetic algorithm implementation strategies; each of them striking a different balance between centralization and distribution. These strategies are applied to several well-known benchmark problems. Our results show that the implementations using periodic centralized selections exhibit remarkable robustness in terms of their search quality, while keeping running time overheads under control. Our main conclusion is that performing centralized selections represents an improvement to the traditional population distribution approaches, which are susceptible to somewhat inefficient search.