Hardest Monotone Functions for Evolutionary Algorithms
METADATA ONLY
Author / Producer
Date
2024
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The hardness of optimizing monotone functions using the (1 + 1)-EA has been an open problem for a long time. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen proved a runtime bound of O(n(³/²)). In 2019, Lengler, Martinsson and Steger improved this upper bound to O(n log² n) leveraging an entropy compression argument. We continue this line of research by analyzing monotone functions that may vary at each step, 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, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the (1 + 1)-EA optimizes SDBV in Theta(n(³/²)) generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the PO-EA model. Our simulations demonstrate matching runtimes for both static and self-adjusting (1,lambda) and (1 +lambda)-EA. We additionally demonstrate, devising an example of fixed dimension, that drift minimization does not equal maximal runtime.
Permanent link
Publication status
published
External links
Book title
Evolutionary Computation in Combinatorial Optimization
Journal / series
Volume
14632
Pages / Article No.
146 - 161
Publisher
Springer
Event
24th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
hardest functions; fitness landscape; precise runtime analysis; drift minimization; (1+1)-EA; Switching Dynamic Binary Value; dynamic environments; evolutionary algorithm
Organisational unit
08738 - Lengler, Johannes (Tit.-Prof.) / Lengler, Johannes (Tit.-Prof.)
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)