2023/07/21 by Jonathan Gadea Harder, Timo Kötzing, Harder, Jonathan Gadea +5
Computer Science · #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2307.11855
openalex publication_date 2023/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
While most theoretical run time analyses of discrete randomized search heuristics focused on finite search spaces, we consider the search space ℤn. This is a further generalization of the search space of multi-valued decision variables \0,…,r-1\n. We consider as fitness functions the distance to the (unique) non-zero optimum a (based on the L1-metric) and the \ooea which mutates by applying a step-operator on each component that is determined to be varied. For changing by ± 1, we show that the expected optimization time is Θ(n ⋅ (|a|∞ + log(|a|H))). In particular, the time is linear in the maximum value of the optimum a. Employing a different step operator which chooses a step size from a distribution so heavy-tailed that the expectation is infinite, we get an optimization time of O(n ⋅ log2 (|a|1) ⋅ (log (log (|a|1)))1 + ε). Furthermore, we show that RLS with step size adaptation achieves an optimization time of Θ(n ⋅ log(|a|1)). We conclude with an empirical analysis, comparing the above algorithms also with a variant of CMA-ES for discrete search spaces.