On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms

摘要: It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence evolving via crossover and mutation may also benefit time hillclimbing unimodal functions. particular, prove bounds on expected runtime standard ($\mu$+1)~GA OneMax lower than its unary black box complexity decrease in leading constant with population size up to $\mu=O(\sqrt{\log n})$. Our analysis suggests optimal strategy flip two bits most time. To achieve interesting contributions theory randomised heuristics: 1) A novel application drift which compares absorption times different Markov chains without defining an explicit potential function. 2) The inversion fundamental matrices calculate chains. latter was previously proposed literature but best our knowledge first has been used show non-trivial runtimes.