2010/11/15 by Carola Doerr, Benjamin Doerr, Daniel Johannsen +4
Computer Science · Mathematics · #Advanced Multi-Objective Optimization Algorithms #F.2 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Probability (math.PR) #cs.NE #math.PR
paper · pdf · doi:10.48550/arxiv.1011.3466
19 pages; This work contains parts of the GECCO 2010 and CEC 2010 papers of the same authors
arxiv created 2010/11/15 · openalex publication_date 2010/11/15 · arxiv updated 2015/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Drift analysis has become a powerful tool to prove bounds on the runtime of randomized search heuristics. It allows, for example, fairly simple proofs for the classical problem how the (1+1) Evolutionary Algorithm (EA) optimizes an arbitrary pseudo-Boolean linear function. The key idea of drift analysis is to measure the progress via another pseudo-Boolean function (called drift function) and use deeper results from probability theory to derive from this a good bound for the runtime of the EA. Surprisingly, all these results manage to use the same drift function for all linear objective functions. In this work, we show that such universal drift functions only exist if the mutation probability is close to the standard value of 1/n.