The Impact of Parametrization on Randomized Search Heuristics

In this work we present runtime analyses of randomized search heuristics (RSH) in various settings that are determined by parameters of the problems, the algorithms and also exogenous parameters like noise. In the process we provide new techniques for the theoretical analysis of RSH as well as new optimization algorithms.

We consider the following topics. Escaping local optima using local search. We analyze memetic algorithms, i.e. evolutionary algorithms equipped with a local search after mutation. To this end we consider the (1+1) EA equipped with Standard Local Search (SLS) and Variable-Depth Search (VDS) on an artificial test function.

We determine features of the fitness landscape that lead to the (1+1) EA using SLS outperforming the (1+1) EA using VDS with an exponential performance gap. Moreover, we present a new local search operator, Opportunistic Local Search (OLS), that can deal with such features in the landscape and show that the (1+1) EA with OLS can efficiently optimize a discretized Rastrigin function.

Stochastic fitness functions. We analyze the role of populations in stochastic optimization. We assume that the objective function is subject to noise, introducing stochastic errors in its evaluation. On classical test functions, such noise makes optimization by the simple (1+1) EA hillclimber infeasible even in exponential time.

Interestingly, the use of parent and offspring populations of only logarithmic size turns the algorithm into an efficient one. The results are obtained by drift analysis. An asymptotic expansion of the expected runtime of the (1+λ) EA on ONEMAX. We consider the (1+λ) EA with mutation probability c/n, where c > 0 is a constant on ONEMAX.

We give an asymptotic expansion for the expected runtime depending on both c and λ. Our results show that c = 1 is the optimal mutation rate for λ = o(lognloglogn/logloglogn) and that c only has an impact on the lower-order terms of the expected runtime, i.e. c = 1 is no longer the only optimal mutation rate.

Our methods are strongly based on variable drift theorems for upper and lower bounds and a precise analysis of order statistics of the binomial distribution. To the best of our knowledge this is the first tight runtime analysis of a population-based EA, up to lower-order terms. Furthermore, we develop helpful stochastic tools for runtime analyses.

Optimal mutation rates for the (1+λ) EA on ONEMAX. We consider the (1+λ) EA with mutation probability c/n on ONEMAX, where c > 0 and λ are constant. We present an improved variable drift theorem that weakens the requirement that no large steps towards the optimum may occur in the process to a stochastic one, reducing the analysis of the expected optimization time to finding an exact expression for the drift.

We formalize an exact closed-form expression for the drift and provide small error approximations that are very efficient to compute. Self-adjusting mutation rates for the (1+λ) EA on ONEMAX. We propose a new mechanism to self-adjust the mutation rate in population-based evolutionary algorithms. It consists of creating half the offspring with a higher and the rest with a lower mutation rate.

The mutation rate is then adjusted, based on the success of the subpopulations. We show that the (1+λ) EA optimizes ONEMAX in an expected optimization time of O(nλ/logλ + nlogn) which has been shown to be best-possible among all λ-parallel mutation-based unbiased black-box algorithms.