2011/09/07 by Dirk Sudholt, Sudholt, Dirk · 3 citations
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.1109.1504
openalex publication_date 2011/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new method for proving lower bounds on the expected running time\nof evolutionary algorithms. It is based on fitness-level partitions and an\nadditional condition on transition probabilities between fitness levels. The\nmethod is versatile, intuitive, elegant, and very powerful. It yields exact or\nnear-exact lower bounds for LO, OneMax, long k-paths, and all functions with a\nunique optimum. Most lower bounds are very general: they hold for all\nevolutionary algorithms that only use bit-flip mutation as variation\noperator---i.e. for all selection operators and population models. The lower\nbounds are stated with their dependence on the mutation rate.\n These results have very strong implications. They allow to determine the\noptimal mutation-based algorithm for LO and OneMax, i.e., which algorithm\nminimizes the expected number of fitness evaluations. This includes the choice\nof the optimal mutation rate.\n