On the runtime dynamics of the compact genetic algorithm on jump functions
Václav Hasenöhrl, Andrew M. Sutton · Proceedings of the Genetic and Evolutionary Computation Conference · 2018
Jump functions were originally introduced as benchmarks on which recombinant evolutionary algorithms can provably outperform those that use mutation alone. To optimize a jump function, an algorithm must be able to execute an initial hill-climbing phase, after which a point across a large gap must be generated. Standard GAs mix mutation and crossover to achieve both behaviors. It seems likely that other techniques, such as estimation of distribution algorithms (EDAs) may exhibit such behavior, but an analysis is so far missing.