How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys.

The benefits of using crossover in crossing fitness gaps have been studied extensively in evolutionary computation. Recent runtime results show that majority-vote crossover is particularly efficient at optimizing the well-known Jump benchmark function that includes a fitness gap next to the global optimum. Also estimation-of-distribution algorithms (EDAs), which use an implicit crossover, are much more efficient on Jump than typical mutation-based algorithms. However, the allowed gap size for polynomial runtimes with EDAs is at most logarithmic in the problem dimension n. In this paper, we investigate variants of the Jump function where the gap is shifted and appears in the middle of the typical search trajectory. Such gaps can still be overcome efficiently in time O (n log ⁡ n) by majority-vote crossover and an estimation-of-distribution algorithm, even for gap sizes almost n. However, if the global optimum is located in the gap instead of the usual all-ones string, majority-vote crossover would nevertheless approach the all-ones string and be highly inefficient. In sharp contrast, an EDA can still find such a shifted optimum efficiently. Thanks to a general property called fair sampling , the EDA will with high probability sample from almost every fitness level of the function, including levels in the gap, and sample the global optimum even though the overall search trajectory points towards the all-ones string. Finally, we derive limits on the gap size allowing efficient runtimes for the EDA. • We study 2 algorithms using majority-vote crossover and an estimation-of-distribution algorithm on modified jump functions. • We derive theorems on the algorithms' runtime using rigorous mathematical analyses. • All 3 algorithms can overcome the fitness gap of the jump functions efficiently for moderate sizes of the gap. • All but the estimation-of-distribution algorithm usually fail to find an optimum located within the gap. • The estimation-of-distribution is efficient since it samples fairly on all fitness levels towards the optimum. [ABSTRACT FROM AUTHOR]