Escaping Local Optima with Diversity Mechanisms and Crossover

Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (mu+1) GA using uniform crossover on the fitness function Jump(k). All previous results in this context only hold for unrealistically low crossover probability p(c) = O(k/n), while we give analyses for the setting of constant p(c) 1 in all but one case. Our bounds show a dependence on the problem size n, the jump length k, the population size mu, and the crossover probability p(c). For the typical case of constant k > 2 and constant p(c), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of O(n(k-1)) for duplicate elimination/minimisation, O(n(2) log n) for maximising the convex hull, O(n log n) for det. crowding (assuming p(c) = k/n), O(n log n) for maximising the Hamming distance, O(n log n) for fitness sharing, O(n log n) for the single-receiver island model. This proves a sizeable advantage of all variants of the (mu+1) GA compared to the (1+1) EA, which requires Theta(n(k)). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.