Standard Steady State Genetic Algorithms Can Hillclimb Faster than Mutation-only Evolutionary Algorithms

摘要: Explaining to what extent the real power of genetic algorithms lies in ability crossover recombine individuals into higher quality solutions is an important problem evolutionary computation. In this paper we show how interplay between mutation and can make hillclimb faster than their mutation-only counterparts. We devise a Markov Chain framework that allows rigorously prove upper bound on runtime standard steady state OneMax function. The establishes steady-state are 25% all bit with static rate up lower order terms for moderate population sizes. analysis also suggests larger populations may be size 2. present greedy (2+1) GA matches 2, proving 2 cannot outperform sizes under selection terms. complementary experiments best greater ones, further suggesting derived holds GA.