Projects per year
Abstract
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 VariableDepth Search (VDS) on an artiﬁcial test function. We determine features of the ﬁtness 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 efﬁciently optimize a discretized Rastrigin function. Stochastic ﬁtness 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 efﬁcient 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 lowerorder 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 ﬁrst tight runtime analysis of a populationbased EA, up to lowerorder 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 ﬁnding an exact expression for the drift. We formalize an exact closedform expression for the drift and provide small error approximations that are very efﬁcient to compute. Selfadjusting mutation rates for the (1+λ) EA on ONEMAX. We propose a new mechanism to selfadjust the mutation rate in populationbased 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 bestpossible among all λparallel mutationbased unbiased blackbox algorithms.
Original language  English 

Publisher  DTU Compute 

Number of pages  156 
Publication status  Published  2018 
Series  DTU Compute PHD2017 

Volume  460 
ISSN  09093192 
Fingerprint
Dive into the research topics of 'The Impact of Parametrization on Randomized Search Heuristics'. Together they form a unique fingerprint.Projects
 1 Finished

Bridging the Gap Between Theory and Practice in Natureinspired algorithms
Gießen, C., Witt, C., Bille, P., Lehre, P. K. & Sudholt, D.
01/10/2014 → 11/04/2018
Project: PhD