On the behavior of parallel island models

Abstract

Parallel island models have often been used not only to speeding up evolutionary algorithms but also to increase accuracy. For island model genetic algorithms, it has been argued that multiple islands preserve the genetic diversity since each island can follow a different search trajectory in the search space. In island models, each island evolves througha breeding cycle, and migration policies control the exchange of genetic material. The migration policies are restricted to a graph topology that specifies which pairs of islands are connected and can be static or dynamic. In static topologies, the communication between the islands remain unchanged, while in dynamic topologies communication may change before each migration process. This work explores such migration policies proposing different parallel island model for genetic algorithms. To analyze the proposed parallel island models from a general perspective, we used four case-studies related with NP -Hard problems from different fields including evolutionary distance, task mapping and scheduling and N -Queens completion. For each parallel island model the parameters for migration policies and breeding cycle were calibrated separately before performing experiments. The results obtained showed that there is neither a model which provides better speed-up nor accuracy in general. However, in general models with dynamic topologies provide better accuracy than those using static topologies, and models using few islands achieve the best speed-ups.