2023/11/13 by Marc Kaufmann, Kaufmann, Marc, Maxime Larcher +5
Computer Science · #68W50 #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Probability (math.PR) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2311.07438
openalex publication_date 2023/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we revisit the question how hard it can be for the (1+1) Evolutionary Algorithm to optimize monotone pseudo-Boolean functions. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen first proved a runtime bound of O(n3/2). More recently, Lengler, Martinsson and Steger improved this upper bound to O(n log2 n) by an entropy compression argument. In this work, we analyze monotone functions that may adversarially vary at each step of the optimization, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the (1+1)-EA with any mutation rate p ∈ [0,1], SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the (1+1)-EA optimizes SDBV in Θ(n3/2) generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the \poea model. Our simulations demonstrate matching runtimes for both the static and the self-adjusting (1,λ)-EA and (1+λ)-EA. Moreover, devising an example for fixed dimension, we illustrate that drift minimization does not equal maximal runtime beyond asymptotic analysis.