Run Time Bounds for Integer-Valued OneMax Functions
share
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 L_1-metric) and the 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 ·log^2 (|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.
READ FULL TEXT