A tight runtime analysis for the cGA on jump functions
Benjamin Doerr · Proceedings of the Genetic and Evolutionary Computation Conference · 2019
We prove that the compact genetic algorithm (cGA) with hypothetical population size [MATH HERE] poly(n) with high probability finds the optimum of any n-dimensional jump function with jump size [MATH HERE] ln n in [MATH HERE] iterations. Since it is known that the cGA with high probability needs at least [MATH HERE] iterations to optimize the unimodal OneMax function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross mo derate-sized valleys of low fitness at no extra cost.