Analysis of mutation strength adaptation within evolution strategies on the ellipsoid model and methods for the treatment of fitness noise

This work addresses the theoretical and empirical analysis of Evolution Strategies (ESs) on quadratic functions, in particular on Positive Definite Quadratic Forms (PDQFs). Referring to this subset as the ellipsoid model, the analysis excludes such PDQFs with only a few dominating eigenvalues in the Hessian matrix diagonal. To perform the theoretical analysis, the so-called dynamical systems approach, which is known from the analysis of self-adaptive ES, is transferred to the specific problem formulations. In this context, the limit of large search space dimensions, N → ∞, is considered and the dynamics are based on expected values. The resulting description represents the exact asymptotic (long-term) behavior. The first part focuses on theoretical investigations concerning two common mutation strength adaptation mechanisms and the corresponding dynamical behavior of the evolutionary systems. In particular, cumulative step-size adaptation, as well as a specific hierarchically organized ES, are under consideration. Connecting these findings to existing results of σ self-adaptation, the analysis of the currently most common mutation strength adaptation methods in ES is completed. Regarding the behavior of the (μ/μ_I,λ)-ES with cumulative step size adaptation (CSA) a non-linear system of difference equations is derived that describes the mean-value evolution of the ES. This system is successively simplified to finally allow for deriving closed-form solutions of the steady state behavior in the asymptotic limit case of large search space dimensionality. It is shown that the system exhibits linear convergence order. The steady state mutation strength is calculated and it is demonstrated that compared to standard settings in σ self-adaptive ESs, the CSA control rule allows for an approximately μ-fold larger mutation strength. This explains the superior performance of the CSA in non-noisy environments. The results are used to derive a formula for the expected running time. Conclusions regarding the choice of the cumulation parameter c and the damping constant D are drawn. Further, the ability of a hierarchically organized evolution strategy (meta-Evolution Strategy) with isolation periods of length one to optimally control its mutation strength is investigated. By application of the dynamical systems analysis approach, a first step towards the analysis of the meta-Evolution Strategy behavior is conducted. A non-linear system of difference equations is derived to describe the mean-value evolution of the respective hierarchically organized strategy. In the asymptotic limit case of large search space dimensions, this system is suitable to derive closed-form solutions which describe the long-term behavior of the meta-Evolution Strategy. The steady state mutation strength is bracketed within an interval depending on the mutation strength control parameter. Compared to standard settings in cumulative step-length adaptation evolution strategies the meta evolution strategy realizes almost similar normalized mutation strengths. The performance of the meta-Evolution Strategy turns out to be very robust in terms of choosing its control parameters. The results allow for the derivation of the expected running time of the algorithm. Finally, the results are extended to meta-ES with longer isolation periods. While the respective strategies reveal the ability to reduce fluctuation in the upper level selection process for small control parameter choices, they do not indicate a potential for a long-term progress enhancement. The second part of this work expands the regarded optimization problem by the concept of fitness noise. To this end, the noisy ellipsoid model is motivated considering two contrasting noise models, i.e. additive noise of constant variance and noise of constant normalized variance. After transferring previous sphere model results to the noisy ellipsoid model two Evolution Strategies are examined that promise to successfully deal with the noise perturbations. The first attempt investigates the ability of meta-ES to simultaneously control mutation strength and the population size on the noise sphere model. The analysis of the strategy's long-term behavior is presented. An expression describing the asymptotical growth of the normalized mutation strength is calculated that allows for the prediction of the meta-ES dynamics. The theoretical results are empirically evaluated, indicating that the noise influence on the meta-ES selection process results in rather large deviations from the predicted long-term behavior. This suggests that the particular meta-ES variant is not well enough suited to deal with the noisy optimization problem. Adjustments of the selection decision are connected to additional expenses in terms of function evaluations and conclusively increase the optimization effort considerably. A second approach proposes the design of a noise detection technique which is able to identify noise related stagnation in the fitness dynamics of an ES on the noisy ellipsoid model. The noise detection is integrated into the well-known Covariance Matrix Self-Adaptation Evolution Strategy (CMSA-ES). It recognizes stagnations by use of a linear regression analysis of the observed fitness sequence in the evolutionary process and appropriately controls the population size of the CMSA-ES. The suggested strategy successfully deals with the regarded noise variants on the ellipsoid model. Additionally, the empirical proof-of-concept allows for a remarkable observation. That is, according to a theorem by Astete-Morales, Cauwet, and Teytaud, “Simple Evolution Strategies (ES)” that optimize quadratic functions disturbed by additive Gaussian noise of constant variance can only reach a simple regret log-log convergence slope ≥ -1/2 (lower bound). The population size controlled CMSA-ES (pcCMSA-ES) presented is able to perform better than the -1/2 limit. It is shown experimentally that the pcCMSA-ES is able to reach a slope of -1 being the theoretical lower bound of all comparison-based direct search algorithms