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 (μ+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 μ, 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) J for duplicate elimination/minimisation, • O (n² 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 (μ+1) GA compared to the (1+1) EA, which requires Θ(n). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.