Ring Migration Topology Helps Bypassing Local Optima
This provides theoretical insight for practitioners in evolutionary computation on maintaining diversity to bypass local optima, though it is incremental as it builds on prior analyses of migration topologies.
The paper tackles the problem of evolutionary algorithms getting stuck in local optima by analyzing island models with different migration topologies, showing that a ring topology achieves a run time of θ(n^r) on a fitness function, outperforming complete topologies at θ(n^{1.5r}) and avoiding bad optima.
Running several evolutionary algorithms in parallel and occasionally exchanging good solutions is referred to as island models. The idea is that the independence of the different islands leads to diversity, thus possibly exploring the search space better. Many theoretical analyses so far have found a complete (or sufficiently quickly expanding) topology as underlying migration graph most efficient for optimization, even though a quick dissemination of individuals leads to a loss of diversity. We suggest a simple fitness function FORK with two local optima parametrized by $r \geq 2$ and a scheme for composite fitness functions. We show that, while the (1+1) EA gets stuck in a bad local optimum and incurs a run time of $Θ(n^{2r})$ fitness evaluations on FORK, island models with a complete topology can achieve a run time of $Θ(n^{1.5r})$ by making use of rare migrations in order to explore the search space more effectively. Finally, the ring topology, making use of rare migrations and a large diameter, can achieve a run time of $\tildeΘ(n^r)$, the black box complexity of FORK. This shows that the ring topology can be preferable over the complete topology in order to maintain diversity.