Rescaled mutations have been proven to improve the convergence behavior of Evolution Strategies (ES) in noisy or highly multimodal fitness landscapes. The basic principle is "mutate large, but inherit small", meaning that the step toward the new parental centroid is reduced by a factor 1/κ. This paper investigates the impact of κ on the progress rate of a (μ/μI, λ)-ES in a highly multimodal and noisy scenario. For the second-order progress rate, the gain part scales inverse linearly and the loss part scales inverse quadratically with κ. This relationship is applied to the Rastrigin function in the limit of large dimensionality. Furthermore, a κ-dependent first-order progress rate for the noisy sphere is derived, yielding the aforementioned scaling behavior. The findings suggest that as κ increases, the interval of the normalized noise strength where positive progress is possible gets larger. Consequently, the search space can be explored with a larger mutation strength, leading to larger success rates in the Rastrigin landscape and to a smaller steady-state distance in the noisy sphere case.

Three state-of-the-art adaptive population control strategies (PCS) are theoretically and empirically investigated for a multi-recombinative, cumulative step-size adaptation Evolution Strategy μλ-CSA-ES. First, scaling properties for the generation number and mutation strength rescaling are derived on the sphere in the limit of large population sizes. Then, the adaptation properties of three standard CSA variants are studied for varying population size and dimensionality, and compared to the predicted scaling results. Thereafter, three PCS are implemented along the CSA-ES and studied on a test bed of sphere, random, and Rastrigin functions. The CSA properties significantly influence the performance and stability of PCS, which is shown in greater detail. Given the test bed, well-performing parameter sets (in terms of scaling, efficiency, and success rate) for both the CSA-and PCS-subroutines are identified.

This paper examines restart strategies for algorithms whose successful termination depends on a parameter λ. After each restart, λ is increased, until the algorithm terminates successfully. It is assumed that there is an unknown, optimal value for λ. For the algorithm to run successfully, this value must be surpassed. The key question is whether there exists an optimal strategy for selecting λ after each restart taking into account that the computational costs increase with λ. Potential restart strategies are classified into parameter-dependent strategy types. A loss function is introduced to quantify the wasted computational cost relative to the optimal strategy. A crucial requirement for any efficient restart strategy is that its loss, relative to the optimal λ, remains bounded. To this end, upper and lower bounds of the loss are derived. Using these bounds it will be shown that not all strategy types are bounded. However, for a particular strategy type, where λ is increased multiplicatively by a constant factor ρ, the relative loss function is bounded. Furthermore, it will be demonstrated that within this strategy type, there exists an optimal value ρ = 2 that minimizes the maximum relative loss. In the asymptotic limit, this optimal choice does not depend on the unknown optimal A. While the multiplicative strategy with ρ = 2 was already used in implementations of evolutionary algorithms to control the population size showing acceptable performance in applications, a formal proof of its optimality is presented and the underlying conditions are discussed in this paper the first time.

The self-adaptive, multi-recombinative (μ/μI,λ)-ES (Evolution Strategy) is investigated on the highly multimodal Rastrigin test function by theoretical and experimental means. The analysis is based on the established dynamical systems approach. To this end, the self-adaptation response function is derived in the limit of large populations, which are necessary to achieve high success rates. Furthermore, steady-state conditions on Rastrigin are discussed and compared to the sphere function. Then, a relation for the learning parameter τ is derived to tune the sampling process of the self-adaptive ES, improving its efficiency on Rastrigin. The obtained result is compared to default τ-values. Furthermore, expected runtime experiments are conducted varying τ and population parameters of the ES. Theoretical and experimental results regarding τ are compared in terms of efficiency and robustness showing good agreement.

This paper derives a population sizing model for standard Evolution Strategies (ES) in highly multimodal fitness landscapes with exponentially many local optima. The Rastrigin, Bohachevsky, and Ackley test functions are considered. Due to the highly non-convex structure of these functions a detailed analytical description of the behavior of the ES is a challenge. Therefore, a model is derived that simplifies the complex structure of the functions under consideration. The main idea of this model is the interpretation of local landscape oscillations as frozen noise. This allows for an estimation of the success probability of the ES converging to the global optimum and in turn an estimation of the population size required. It is shown that the population size scales usually sublinearly with the search space dimension N. For the Rastrigin and Bohachevsky function, the population size scales with O(√N ln(N)). As for Ackley, the scaling behavior depends strongly on the initial values. If the algorithm starts in a certain vicinity of the global optimizer, the dependence on the dimension N is rather weak. However, if the initial value exceeds a certain distance R to the optimizer, the population size scales exponentially with R.

The mutation strength$(\sigma)$adaptation of a multi-recombinative self-adapting Evolution Strategy is investigated on the Rastrigin test function by theoretical and experimental means. Sampling$\sigma$from a log-normal distribution reveals the occurrence of an undesired steady-state under high multimodal-ity, which halts the$\sigma$-adaptation and prevents convergence. It is shown that an inherent bias is the reason for this steady-state when sampling log-normal mutations. Therefore, sampling from a normal distribution is introduced as an alternative. Normal sampling does not exhibit the steady-state behavior and it is more stable optimizing functions under high multimodality.

The Griewank function is one of the widely used multimodal benchmark functions. The function is known for its counter intuitive behavior of getting simpler to be optimized with increasing dimension, although the number of local minima increases with the problem dimension. A frozen noise model is introduced that is able to partially explain the empirically observed behaviors. The influence of the different Evolution Strategies and their parameters on the success rate are analyzed. Empirical investigations are used to show the limitations of this model. These investigations reveal some unexpected behaviors regarding the influence of the population size on the success rate of the Evolution Strategies that cannot be explained by the current theory.

The highly multimodal Rastrigin test function is analyzed by deriving a new aggregated progress rate measure. It is derived as a function of the residual distance to the optimizer by assuming normally distributed positional coordinates around the global optimizer. This assumption is justified for successful ES-runs operating with sufficiently slow step-size adaptation. The measure enables the investigation of further convergence properties. For moderately large mutation strengths a characteristic distance-dependent Rastrigin noise floor is derived. For small mutation strengths local attraction is analyzed and an escape condition is established. Both mutation strength regimes combined pose a major challenge optimizing the Rastrigin function, which can be counteracted by increasing the population size. Hence, a population scaling relation to achieve high global convergence rates is derived which shows good agreement with experimental data.

A model is presented that allows for the calculation of the success probability by which a vanilla Evolution Strategy converges to the global optimizer of the Rastrigin test function. As a result a population size scaling formula will be derived that allows for an estimation of the population size needed to ensure a high convergence security depending on the search space dimensionality.

, λ)-ES with isotropic scale-invariant mutations on the highly multimodal Rastrigin test function. Closed-form analytic solutions for the progress rates are obtained in the limit of large dimensionality and large populations. The first order results are able to model the one-generation progress including local attraction phenomena. Furthermore, a second order progress rate is derived yielding additional correction terms and further improving the progress model. The obtained results are compared to simulations and show good agreement, even for moderately large populations and dimensionality. The progress rates are applied within a dynamical systems approach, which models the evolution using difference equations. The obtained dynamics are compared to real averaged optimization runs and yield good agreement. The results improve further when dimensionality and population size are increased. Local and global convergence is investigated within given model showing that large mutations are needed to maximize the probability of global convergence, which comes at the expense of efficiency. An outlook regarding future research goals is provided.

)-ES on the highly multimodal Rastrigin test function. The progress is derived within a linearized model applying the method of so-called noisy order statistics. To this end, the mutation-induced variance of the Rastrigin function is determined. The obtained progress approximation is compared to simulations and yields strengths and limitations depending on mutation strength and distance to the optimizer. Furthermore, the progress is iterated using the dynamical systems approach and compared to averaged optimization runs. The property of global convergence within given approximation is discussed. As an outlook, the need of an improved first order progress rate as well as the extension to higher order progress including positional fluctuations is explained.

An evolution strategy design is presented that allows for an evolution on general quadratic manifolds. That is, it covers elliptic, parabolic, and hyperbolic equality constraints. The peculiarity of the presented algorithm design is that it is an interior point method. It evaluates the objective function only for feasible search parameter vectors and it evolves itself on the nonlinear constraint manifold. Such a characteristic is particularly important in situations where it is not possible to evaluate infeasible parameter vectors, e.g., in simulation-based optimization. This is achieved by a closed form transformation of an individual’s parameter vector, which is in contrast to iterative repair mechanisms. This constraint handling approach is incorporated into a matrix adaptation evolution strategy making such algorithms capable of handling problems containing the constraints considered. Results of different experiments are presented. A test problem consisting of a spherical objective function and a single hyperbolic/parabolic equality constraint is used. It is designed to be scalable in the dimension. As a further benchmark, the Thomson problem is used. Both problems are used to compare the performance of the developed algorithm with other optimization methods supporting constraints. The experiments show the effectiveness of the proposed algorithm on the considered problems. Additionally, an idea for handling multiple constraints is discussed. And for a better understanding of the dynamical behavior of the proposed algorithm, single run dynamics are presented.

An evolution strategy design is presented that allows for an evolution on general quadratic manifolds. That is, it covers elliptic, parabolic, and hyperbolic equality constraints. The peculiarity of the presented algorithm design is that it is an interior point method. It evaluates the objective function only for feasible search parameter vectors and it evolves itself on the nonlinear constraint manifold. This is achieved by a closed form transformation of an individual's parameter vector, which is in contrast to iterative repair mechanisms. Results of different experiments are presented. A test problem consisting of a spherical objective function and a single hyperbolic/parabolic equality constraint is used. It is designed to be scalable in the dimension and it is used to compare the performance of the developed algorithm with other optimization methods supporting constraints. The experiments show the effectiveness of the proposed algorithm on the considered problems.

In combination with successful constraint handling techniques, a Matrix Adaptation Evolution Strategy (MA-ES) variant (the εMAg-ES) turned out to be a competitive algorithm on the constrained optimization problems proposed for the CEC 2018 competition on constrained single objective real-parameter optimization. A subsequent analysis points to additional potential in terms of robustness and solution quality. The consideration of a restart scheme and adjustments in the constraint handling techniques put this into effect and simplify the configuration. The resulting BP-εMAg-ES algorithm is applied to the constrained problems proposed for the IEEE CEC 2020 competition on Real-World Single-Objective Constrained optimization. The novel MA-ES variant realizes improvements over the original εMAg-ES in terms of feasibility and effectiveness on many of the real-world benchmarks. The BP-εMAg-ES realizes a feasibility rate of 100% on 44 out of 57 real-world problems and improves the best-known solution in 5 cases.

Theoretical analyses of evolution strategies are indispensable for gaining a deep understanding of their inner workings. For constrained problems, rather simple problems are of interest in the current research. This work presents a theoretical analysis of a multi-recombinative evolution strategy with cumulative step size adaptation applied to a conically constrained linear optimization problem. The state of the strategy is modeled by random variables and a stochastic iterative mapping is introduced. For the analytical treatment, fluctuations are neglected and the mean value iterative system is considered. Nonlinear difference equations are derived based on one-generation progress rates. Based on that, expressions for the steady state of the mean value iterative system are derived. By comparison with real algorithm runs, it is shown that for the considered assumptions, the theoretical derivations are able to predict the dynamics and the steady state values of the real runs.

A theoretical performance analysis of the (μ/μI, λ)σ-self-adaptation evolution strategy (σSA-ES) is presented considering a conically constrained problem. Infeasible offspring are repaired using projection onto the boundary of the feasibility region. Closed-form approximations are used for the one-generation progress of the evolution strategy. Approximate deterministic evolution equations are formulated for analyzing the strategy's dynamics. By iterating the evolution equations with the approximate one-generation expressions, the evolution strategy's dynamics can be predicted. The derived theoretical results are compared to experiments for assessing the approximation quality. It is shown that in the steady state the (μ/μI, λ)σSA-ES exhibits a performance as if the ES were optimizing a sphere model. Unlike the nonrecombinative (1, λ)-ES, the parental steady state behavior does not evolve on the cone boundary but stays away from the boundary to a certain extent.

This paper concerns the theoretical analysis of a multi-recombinative meta-ES with repair by projection applied to a conically constrained problem. Using theoretical results for the mean value dynamics and steady state considerations of the inner ES, approximate closed-form expressions for the mean value dynamics and the steady state behavior of the outer ES are derived. The approximation quality is shown by comparison with real meta-ES runs using isolation periods larger than one. The theoretical results are compared to known theoretical results of the multi-recombinative ES with σ-Self-Adaptation and Cumulative Step-Size adaptation. It is shown that the meta-ES achieves the largest steady state progress for the considered problem at the cost of twice the function evaluations compared to the other variants.

The paper presents the theoretical performance analysis of a hierarchical Evolution Strategy (meta-ES) variant for mutation strength control on a conically constrained problem. Infeasible offspring are repaired by projection onto the boundary of the feasibility region. Closed-form approximations are used for the one-generation progress of the lower-level evolution strategy. An interval that brackets the expected progress over a single isolation period of the meta-ES is derived. Approximate deterministic evolution equations are obtained that characterize the upper-level strategy dynamics. It is shown that the dynamical behavior of the meta-ES is determined by the choice of the mutation strength control parameter. The obtained theoretical results are compared to experiments for assessing the approximation quality.

The covariance matrix adaptation evolution strategy (CMA-ES) is a popular method to deal with nonconvex and/or stochastic optimization problems when gradient information is not available. Being based on the CMA-ES, the recently proposed matrix adaptation evolution strategy (MA-ES) establishes the rather surprising result that the covariance matrix and all associated operations (e.g., potentially unstable eigen decomposition) can be replaced by an iteratively updated transformation matrix without any loss of performance. In order to further simplify MAES and reduce its O(n2) time and storage complexity to O(mn) with m ≪ n such as m ∈ O(1) or m∈O(log(n)), we present the limited-memory MA-ES for efficient zeroth order large-scale optimization. The algorithm demonstrates state-of-the-art performance on a set of established large-scale benchmarks.

This paper addresses the development of a covariance matrix self-adaptation evolution strategy (CMSA-ES) for solving optimization problems with linear constraints. The proposed algorithm is referred to as linear constraint CMSA-ES (lcCMSA-ES). It uses a specially built mutation operator together with repair by projection to satisfy the constraints. The lcCMSA-ES evolves itself on a linear manifold defined by the constraints. The objective function is only evaluated at feasible search points (interior point method). This is a property often required in application domains, such as simulation optimization and finite element methods. The algorithm is tested on a variety of different test problems revealing considerable results.

By combination of successful constraint handling techniques known within the context of Differential Evolution with the recently suggested Matrix Adaptation Evolution Strategy (MA-ES), a new Evolution Strategy for constrained optimization is presented. The novel MA - ES variant is applied to the benchmark problems specified for the CEC 2018 competition on constrained single objective real-parameter optimization. The algorithm is able to find feasible solutions on more than 80 % of the benchmark problems with high accuracy.

This paper applies an evolution strategy (ES) that evolves rays to single-objective real-valued constrained optimization problems. The algorithm is called Ray-ES. It was proposed as an ad hoc optimization approach for dealing with the unconstrained real-parameter optimization problem class called HappyCat. To our knowledge, the application of the Ray-ES to constrained problems is new. It serves as a simple alternative to other approaches such as for example differential evolution (DE). This paper describes how the Ray-ES can be applied to a constrained setting. The algorithm is tested on a variety of different test problems. Additionally, it is compared to DE approaches.

Regarding the noisy ellipsoid model with additive Gaussian noise, the population control covariance matrix self-adaptation Evolution Strategy (pcCMSA-ES) by Hellwig and Beyer was empirically observed to exhibit a convergence rate (CR) close to the theoretical lower bound of - 1 for all comparison-based direct search algorithms. The present paper provides the corresponding theoretical analysis of the pcCMSA-ES long-term behavior. To this end, the analysis from the context of isotropic mutations is transferred to the pcCMSA-ES that uses covariance matrix adaptation until significant noise influence is detected. The results allow for the computation of an upper bound on the number of generations between two consecutive test decisions of the pcCMSA-ES that ensures the observed performance. Further, the empirically observed convergence rate of CR ∼ −1 is theoretically derived.

A steady state analysis of the optimization quality of a classical self-adaptive evolution strategy (ES) on a class of robust optimization problems is presented. A novel technique for calculating progress rates for nonquadratic noisy fitness landscapes is presented. This technique yields asymptotically exact results in the infinite population size limit. This technique is applied to a class of functions with noise-induced multimodality. The resulting progress rate formulas are compared with high-precision experiments. The influence of fitness resampling is considered and the steady state behavior of the ES is derived and compared with simulations. The questions whether one should sample and average fitness values and how to choose the truncation ratio are discussed giving rise to further research perspectives.

The standard covariance matrix adaptation evolution strategy (CMA-ES) comprises two evolution paths, one for the learning of the mutation strength and one for the rank-1 update of the covariance matrix. In this paper, it is shown that one can approximately transform this algorithm in such a manner that one of the evolution paths and the covariance matrix itself disappear. That is, the covariance update and the covariance matrix square root operations are no longer needed in this novel so-called matrix adaptation (MA) ES. The MA-ES performs nearly as well as the original CMA-ES. This is shown by empirical investigations considering the evolution dynamics and the empirical expected runtime on a set of standard test functions. Furthermore, it is shown that the MA-ES can be used as a search engine in a bi-population (BiPop) ES. The resulting BiPop-MA-ES is benchmarked using the BBOB comparing continuous optimizers (COCO) framework and compared with the performance of the CMA-ES-v3.61 production code. It is shown that this new BiPop-MA-ES-while algorithmically simpler-performs nearly equally well as the CMA-ES-v3.61 code.

The behavior of the [Formula: see text]-Evolution Strategy (ES) with cumulative step size adaptation (CSA) on the ellipsoid model is investigated using dynamic systems analysis. At first a nonlinear 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 dimensions. It is shown that the system exhibits linear convergence order. The steady state mutation strength is calculated, and it is shown that compared to standard settings in [Formula: see text] self-adaptive ESs, the CSA control rule allows for an approximately [Formula: see text]-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.

This paper analyzes the multi-recombinant self-adaptive evolution strategy (ES), denoted as(μ/μI, λ)-σSA-ES on the convex-quadratic function class under the influence of noise, which is referred to as noisy ellipsoid model. Asymptotically exact progress rate and self-adaptation response measures are derived (i.e., for N → ∞, N - search space dimensionality) for the considered objective function model and verified using experimental ES runs.

The convergence behaviors of so-called natural evolution strategies (NES) and of the information-geometric optimization (IGO) approach are considered. After a review of the NES/IGO ideas, which are based on information geometry, the implications of this philosophy w.r.t. optimization dynamics are investigated considering the optimization performance on the class of positive quadratic objective functions (the ellipsoid model). Exact differential equations describing the approach to the optimizer are derived and solved. It is rigorously shown that the original NES philosophy optimizing the expected value of the objective functions leads to very slow (i.e., sublinear) convergence toward the optimizer. This is the real reason why state of the art implementations of IGO algorithms optimize the expected value of transformed objective functions, for example, by utility functions based on ranking. It is shown that these utility functions are localized fitness functions that change during the IGO flow. The governing differential equations describing this flow are derived. In the case of convergence, the solutions to these equations exhibit an exponentially fast approach to the optimizer (i.e., linear convergence order). Furthermore, it is proven that the IGO philosophy leads to an adaptation of the covariance matrix that equals in the asymptotic limit-up to a scalar factor-the inverse of the Hessian of the objective function considered.

The optimization behavior of the self-adaptation (SA) evolution strategy (ES) with intermediate multi-recombination [(μ/μI, λ)-σSA-ES] using isotropic mutations is investigated on convex-quadratic functions (referred to as ellipsoid model). An asymptotically exact quadratic progress rate formula is derived. This is used to model the dynamical ES system by a set of difference equations. The solutions of this system are used to analytically calculate the optimal learning parameter τ. The theoretical results are compared and validated by comparison with real (μ/μI, λ)-σSA-ES runs on two ellipsoid test model cases. The theoretical results clearly indicate that using a model-independent learning parameter τ leads to suboptimal performance of the (μ/μI, λ)-σSA-ES on objective functions with changing local condition numbers as often encountered in practical problems with complex fitness landscapes.

This paper investigates strategy parameter control by Meta-ES using the noisy sphere model. The fitness noise considered is normally distributed with constant noise variance. An asymptotical analysis concerning the mutation strength and the population size is presented. It allows for the prediction of the Meta-ES dynamics. An expression describing the asymptotical growth of the normalized mutation strength is calculated. Finally, the theoretical results are evaluated empirically.

This paper investigates mutation strength control using Meta-ES on the sharp ridge. The asymptotical analysis presented allows for the prediction of the dynamics in ridge as well as in radial direction. Being based on this analysis the problem of the choice of population size λ and isolation parameter γ will be tackled. Remarkably, the qualitative convergence behavior is not determined by γ alone, but rather by the number of function evaluations λ γ devoted to the inner ES.

This paper describes the algorithm's engineering of a covariance matrix self-adaptation evolution strategy (CMSA-ES) for solving a mixed linear/nonlinear constrained optimization problem arising in portfolio optimization. While the feasible solution space is defined by the (probabilistic) simplex, the nonlinearity comes in by a cardinality constraint bounding the number of linear inequalities violated. This gives rise to a nonconvex optimization problem. The design is based on the CMSA-ES and relies on three specific techniques to fulfill the different constraints. The resulting algorithm is then thoroughly tested on a data set derived from time series data of the Dow Jones Index.

In the above-named article [ibid., vol 16, no 4, pp. 578-596, Aug. 2012] an error occurred during the print production process that resulted in the incorrect display of Greek characters within many of the figures in the printed publication. However, the electronic PDF version available on IEEEXplore was not affected and all of the articles' figures appear correctly. Please visit http://ieeexplore. ieee.org/xpl/tocresult.jsp?isnumber=6249762&punumber=4235 to access the correct article of record. The affected figures in print were as follows: Fig. 5(a) vertical axis label incomplete, Greek rho missing; Fig. 6(a) vertical axis label incomplete, Greek rho missing; Fig. 9(a) vertical axis label incomplete, Greek rho missing; Fig. 9(c) vertical axis label incomplete, Greek sigma missing; Fig. 10(a) vertical axis label incomplete, Greek rho missing; Fig. 10(b) vertical axis label incomplete, Greek rho missing; Fig. 11(a) vertical axis label incomplete, Greek rho missing; Fig. 11(c) vertical axis label incomplete, Greek sigma missing; Fig. 12(a) vertical axis label incomplete, Greek rho missing; Fig. 12(c) vertical axis label incomplete, Greek sigma missing; Fig. 13(a) vertical axis label incomplete, Greek rho missing; Fig. 13(c) vertical axis label incomplete, Greek sigma missing; Fig. 14(a) and (b) vertical axis labels incomplete, Greek rho overlined (bar) missing; Fig. 17(a) and (b) horizontal axis labels, Greek kappa missing; Fig. 18 horizontal axis label, Greek kappa missing; Fig. 19(b) vertical axis label incomplete, Greek lambda missing; Fig. 21(a) and (b) horizontal axis labels, Greek kappa missing; Fig. 22(b) Delta before "f" and "x" missing; Fig. 24(a) and (b) horizontal axis labels, Greek lambda missing.

This paper presents a performance comparison of 4 direct search strategies in continuous search spaces using the noisy sphere as test function. While the results of the Evolution Strategy (ES), Evolutionary Gradient Search (EGS), Simultaneous Perturbation Stochastic Approximation (SPSA) considered are already known from literature, Implicit Filtering (IF) as the fourth strategy is firstly analyzed in this paper. After a short review of ES, EGS, and SPSA, the derivation of the quality gain formula of IF is sketched. Using the results, a comparison of the strategies is performed that worked out the similarities and differences of the strategies.

In this paper, first results on the analysis of self-adaptive evolution strategies (ES) with intermediate multirecombination on the elliptic model are presented. Equations describing the ES behavior on the ellipsoid will be derived using a deterministic approach and experimentally verified. A relationship between newly obtained formulae for the elliptic model and previous theoretical results will be discussed.

This paper studies the performance of multi-recombinative evolution strategies using isotropically distributed mutations with cumulative step length adaptation when applied to optimising cigar functions. Cigar functions are convex-quadratic objective functions that are characterised by the presence of only two distinct eigenvalues of their Hessian, the smaller one of which occurs with multiplicity one. A simplified model of the strategy's behaviour is developed. Using it, expressions that approximately describe the stationary state that is attained when the mutation strength is adapted are derived. The performance achieved by cumulative step length adaptation is compared with that obtained when using optimally adapted step lengths.

December 01 2010 Editorial Introduction In Special Collection: CogNet Hans-Georg Beyer Hans-Georg Beyer Search for other works by this author on: This Site Google Scholar Author and Article Information Hans-Georg Beyer Online Issn: 1530-9304 Print Issn: 1063-6560 © 2010 by the Massachusetts Institute of Technology2010 Evolutionary Computation (2010) 18 (4): i. https://doi.org/10.1162/EVCO_a_00027 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Hans-Georg Beyer; Editorial Introduction. Evol Comput 2010; 18 (4): i. doi: https://doi.org/10.1162/EVCO_a_00027 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsEvolutionary Computation Search Advanced Search This content is only available as a PDF. © 2010 by the Massachusetts Institute of Technology2010 Article PDF first page preview Close Modal You do not currently have access to this content.

This paper investigates the behavior of$(\mu /\mu _{I},\lambda )\hbox{-}\sigma {\rm SA}$-ES on a class of positive definite quadratic forms. After introducing the fitness environment and the strategy, the self-adaptation mechanism is analyzed with the help of the self-adaptation response function. Afterward, the steady state of the strategy is analyzed. The dynamical equations for the expectation of the mutation strength$\sigma $and the localization parameter$\zeta $will be derived. Building on that, the progress rate$\varphi $is analyzed and tuned by means of the learning parameter$\tau $. An approximate formula for$\tau _{\rm opt}$, yielding locally maximal progress, is presented. Finally, the performance of the$\sigma {\rm SA}$-rule is compared with the performance of the cumulative step size adaptation rule, and a rough approximation for the expected runtime is presented.

Cigar functions are convex quadratic functions that are characterised by the presence of only two distinct eigenvalues of their Hessian, the smaller one of which occurs with multiplicity one. Their ridge-like topology makes them a useful test case for optimisation strategies. This paper extends previous work on modelling the behaviour of evolution strategies with isotropically distributed mutations optimising cigar functions by considering weighted recombination as well as the effects of noise on optimisation performance. It is found that the same weights that have previously been seen to be optimal for the sphere and parabolic ridge functions are optimal for cigar functions as well. The influence of the presence of noise on optimisation performance depends qualitatively on the trajectory of the search point, which in turn is determined by the strategy's mutation strength as well as its population size and recombination weights. Analytical results are obtained for the case of cumulative step length adaptation.

This paper introduces simple control rules for the mutation strength and the parental population size using the Meta-ES approach. An in-depth analysis is presented on the mutation strength control using the sphere model. A heuristic formula for the outer mutation parameter will be proposed based on the theoretical analysis. Finally, a new evolutionary control strategy for the parental population size is proposed and evaluated empirically.

This paper analyzes the behavior of the (mu/muI,lambda) ES on a class of noisy positive definite quadratic forms (PDQFs). First the equations for the normalized progress rates are derived and then analyzed for constant normalized noise strength and constant (non-normalized) noise strength. Since in the latter case the strategy is not able to reach the optimum, formulas for the final distances to the optimizer (steady state) are derived. The theoretical predictions are then compared with empirical results. In both noise cases the influence of the strategy parameters will be investigated. Further, the equipartition conjecture is used to provide an alternative derivation of the steady state distances in the case of vanishing mutation strength.

This paper proposes the σ-self-adaptive weighted multirecombination evolution strategy (ES) and presents a performance analysis of this newly engineered ES. The steady state behavior of this strategy is investigated on the sphere model and a formula for the optimal choice of the learning parameter is derived allowing the ES to reach maximal performance. A comparison between weighted multirecombination ES with σ-self-adaptation (σSA) and with cumulative step size adaptation (CSA) shows that the σ-self-adaptive ES can exhibit the same performance and can even outperform its CSA counterpart for a range of learning parameters.

This paper considers self-adaptive (mu/mu_I,lambda)-evolution strategies on the noisy sharp ridge. The evolution strategy (ES) is treated as a dynamical system using the so-called evolution equations to model the ES's behavior. The approach requires the determination of the one-generational expected changes of the state variables - the progress measures. For the analysis, the stationary state behavior of the ES on the sharp ridge is considered. Contrary to the usual perception of noise, it is shown that noise has a positive influence on the performance. An explanation for this astonishing behavior is given and conditions for the usefulness of noise in other fitness landscapes are discussed.

In this paper, we propose two evolutionary strategies for the optimization of problems with actuator noise as encountered in robust optimization, where the design or objective parameters are subject to noise: the ROSAES and the ROCSAES. Both algorithms use a control rule for increasing the population size when the residual error to the optimizer state has been reached. Theoretical analysis has previously shown that the residual error depends among other factors on the population size and on the variance of the noise. Furthermore, ROSAES exploits the similarity of the mutation term in evolutionary strategies and the additive noise term in the case of actuator noise. The population variance is controlled to guarantee that the realized noise level is adjusted correctly. Simulations are carried out on test functions and the results are analyzed with respect to the performance and the dependence of ROSAES and ROCSAES on newly introduced exogenous strategy parameters.

Evolutionary algorithms are frequently applied to dynamic optimization problems in which the objective varies with time. It is desirable to gain an improved understanding of the influence of different genetic operators and of the parameters of a strategy on its tracking performance. An approach that has proven useful in the past is to mathematically analyze the strategy's behavior in simple, idealized environments. The present paper investigates the performance of a multiparent evolution strategy that employs cumulative step length adaptation for an optimization task in which the target moves linearly with uniform speed. Scaling laws that quite accurately describe the behavior of the strategy and that greatly contribute to its understanding are derived. It is shown that in contrast to previously obtained results for a randomly moving target, cumulative step length adaptation fails to achieve optimal step lengths if the target moves in a linear fashion. Implications for the choice of population size parameters are discussed.

Most studies concerned with the effects of noise on the performance of optimization strategies, in general, and on evolutionary approaches, in particular, have assumed a Gaussian noise model. However, practical optimization strategies frequently face situations where the noise is not Gaussian. Noise distributions may be skew or biased, and outliers may be present. The effects of non-Gaussian noise are largely unexplored, and it is unclear whether the insights gained and the recommendations with regard to the sizing of strategy parameters that have been made under the assumption of Gaussian noise bear relevance to more general situations. In this paper, the behavior of a powerful class of recombinative evolution strategies is studied on the sphere model under the assumption of a very general noise model. A performance law is derived, its implications are studied both analytically and numerically, and comparisons with the case of Gaussian noise are drawn. It is seen that while overall, the assumption of Gaussian noise in previous studies is less severe than might have been expected, some significant differences do arise when considering noise that is of unbounded variance, skew, or biased

This paper proposes and analyzes a class of test functions for evolutionary robust optimization, the "functions with noise-induced multimodality" (FNIMs). After a motivational introduction gleaned from a real-world optimization problem, the robust optimizer properties of this test class are investigated with respect to different robustness measures. The steady-state behavior of evolution strategies on FNIMs will be investigated empirically. Being based on the empirical results, a subclass of FNIMs is identified which is amenable to an asymptotical performance analysis. The results of this analysis will be used to derive recommendations for the choice of strategy-specific parameters such as population size and truncation ratio

This paper presents first results on the analysis of self-adaptive (/spl mu///spl mu//sub I/, /spl lambda/)-evolution strategies (ES). Applying a deterministic approach to model the evolution of the ES, equations describing the stationary state behavior of the normalized mutation strength and of the progress rate is derived. The analysis provides a deeper insight as to why the performance of the ES exhibits a sensitive dependence on the learning parameter /spl tau/.

It is known that, in the absence of noise, no improvement in local performance can be gained from retaining candidate solutions other than the best one. Yet, it has been shown experimentally that, in the presence of noise, operating with a non-singular population of candidate solutions can have a marked and positive effect on the local performance of evolution strategies. So as to determine the reasons for the improved performance, we have studied the evolutionary dynamics of the (micro ,lambda)-ES in the presence of noise. Considering a simple, idealized environment, we have developed a moment-based approach that uses recent results involving concomitants of selected order statistics. This approach yields an intuitive explanation for the performance advantage of multi-parent strategies in the presence of noise. It is then shown that the idealized dynamic process considered does bear relevance to optimization problems in high-dimensional search spaces.

Cumulative step-size adaptation (CSA) based on path length control is regarded as a robust alternative to the standard mutative self-adaptation technique in evolution strategies (ES), guaranteeing an almost optimal control of the mutation operator. This paper shows that the underlying basic assumption in CSA--the perpendicularity of expected consecutive steps--does not necessarily guarantee optimal progress performance for (mu/mu(I), lambda) intermediate recombinative ES.

While noise is a phenomenon present in many real world optimization problems, the understanding of its potential effects on the performance of evolutionary algorithms is still incomplete. This paper investigates the effects of fitness proportionate Gaussian noise for a (1 + 1)-ES with isotropic normal mutations on the quadratic sphere in the limit of infinite search-space dimensionality. It is demonstrated experimentally that the results provide a good approximation for finite space dimensionality. It is shown that overvaluation as a result of failure to re-evaluate parental fitness leads to both reduced success probabilities and improved performance. Implications for mutation strength adaptation rules are discussed and optimal re-sampling rates are computed.

While in the absence of noise no improvement in local performance can be gained from retaining but the best candidate solution found so far, it has been shown experimentally that, in the presence of noise, operating with a non-trivial population of candidate solutions can have a marked and positive effect on the local performance of evolution strategies (ES). In this paper, we attempt to shed some light on the reasons for the potential performance improvement. In particular, we derive a progress law for the (/spl mu/, /spl lambda/)-ES on a noisy linear fitness function and both numerically and empirically study its implications. We then discuss the significance of the progress coefficients that have been obtained on the linear function for the quadratic sphere, Comparisons of the local performance of the (/spl mu/, /spl lambda/)-ES and of the (1+1)-ES and the (1, /spl lambda/)-ES are presented.

The starting point for the analysis and experiments presented in this paper is a simplified elevator control problem, called 'S-ring'. As in many other real-world optimization problems, the exact fitness function evaluation is disturbed by noise. Evolution strategies (ES) can generally cope with noisy fitness function values. It has been proposed that the 'plus'-strategy can find better solutions by keeping over-valued function values, thus preventing inferior offspring with fitness inflated by noise from being accepted. The 'plus'-strategy builds an implicit barrier around the current best population. We propose to make this barrier building process explicit and to employ a threshold value /spl tau/ to be used in a selection operator for noisy fitness functions. 'Thresholding' accepts a new individual if its apparent fitness is better than that of the parent by at least the margin /spl tau/. First analytical investigations and empirical results from tests on the sphere-model and 'S-ring' are presented.

Self-adaptation is an essential feature of natural evolution. However, in the context of function optimization, self-adaptation features of evolutionary search algorithms have been explored mainly with evolution strategy (ES) and evolutionary programming (EP). In this paper, we demonstrate the self-adaptive feature of real-parameter genetic algorithms (GAs) using a simulated binary crossover (SBX) operator and without any mutation operator. The connection between the working of self-adaptive ESs and real-parameter GAs with the SBX operator is also discussed. Thereafter, the self-adaptive behavior of real-parameter GAs is demonstrated on a number of test problems commonly used in the ES literature. The remarkable similarity in the working principle of real-parameter GAs and self-adaptive ESs shown in this study suggests the need for emphasizing further studies on self-adaptive GAs.

This paper presents the N-dependent analysis of the (1, /spl lambda/)-evolution strategy (ES) with isotropic mutations for the ridge functions including the special cases of sharp and parabolic ridges. The new approach presented allows for the prediction of the dynamics in ridge direction as well as in radial direction. The central quantities are the corresponding progress rates which are determined in terms of analytical expressions. Its predictive quality is evaluated by ES simulations and the steady-state behavior is discussed in detail.

Due to the flexibility in adapting to different fitness landscapes, self-adaptive evolutionary algorithms (SA-EAs) have been gaining popularity in the recent past. In this paper, we postulate the properties that SA-EA operators should have for successful applications in real-valued search spaces. Specifically, population mean and variance of a number of SA-EA operators such as various real-parameter crossover operators and self-adaptive evolution strategies are calculated for this purpose. Simulation results are shown to verify the theoretical calculations. The postulations and population variance calculations explain why self-adaptive genetic algorithms and evolution strategies have shown similar performance in the past and also suggest appropriate strategy parameter values, which must be chosen while applying and comparing different SA-EAs.

The progress behavior of evolution strategies (ES) using recombination is analyzed in this paper on the parabolic ridge. This test function represents landscapes far from the optimum. The ES algorithms with intermediate and dominant recombination are considered in the analysis. The derivations are presented for intermediate recombination. Thereafter, the formulae for dominant recombination are obtained using the so-called surrogate mutation model. In the analysis, the formulae are derived for the progress rate psi and for the stationary distance R(infinity) to the ridge axis. As a result, it will be shown that the progress rate psi can increase if recombination is applied. Simulations are used to show the appropriateness of the formulae derived.

The progress rate of the (1,+ lambda)-ES (Evolution Strategy) is analyzed on the parabolic ridge test function. A different progress behavior is observed for the (1, lambda)-ES than for the sphere model test function. The characteristics of the progress rate picture for the plus strategy differs little from the one obtained for the sphere model, but this strategy has drastically worse progress rate values than those obtained for the comma strategy. The dynamics of the distance to the progress axis is also investigated. A theoretical formula is derived to estimate the change in this distance over generations. This formula is used to derive the expected value of the problem-specific distance to the ridge axis. The correctness of the formulae is supported by simulation results.

The performance of the multirecombinant (/spl mu///spl mu/, /spl lambda/)-evolution strategy (ES) with /spl sigma/-self-adaptation (/spl sigma/SA) is investigated on the sphere model. The investigation includes the computation of the maximal performance of an ES using recombination can reach when the mutation strength is optimally adjusted during the whole evolution. The comparison between the strategies with and without /spl sigma/SA shows that SA (self-adaptation) is not always able to drive the ES in its optimal working regime, although it still guarantees linear convergence order. The static and dynamic aspects of SA are discussed and it is shown that the learning parameter has a sensible influence on the progress rate.

Most real-world search and optimization problems are faced with constraints, which must be satisfied by any acceptable solution. Although a plethora of research is spent on handling constraints in genetic algorithms (GAs), the same is not the case in evolution strategies (ESs). However, this does not say that ESs have not been applied to real-world problems. In fact, in the absence of an efficient constraint-handling technique, ES practitioners have mostly made sure that their ESs started from feasible solutions, a matter which allowed them to apply the commonly-used rejection scheme. In this paper, we borrow a constraint-handling scheme from the GA literature and implement it with standard ES paradigm. The resulting algorithm does not require initial feasible solutions and is found to yield a faster progress in the cylindrical corridor model and be efficient in solving a couple of complicated test problems. The results are interesting and suggest further use of the proposed technique in real-world search and optimization problems.

The multirecombinant (μ/μ, λ) evolution strategy (ES) is investigated for real-valued, N-dimensional parameter spaces. The analysis includes both intermediate recombination and dominant recombination, as well. These investigations are done for the spherical model first. The problem of the optimal population size depending on the parameter space dimension N is solved. A method extending the results obtained for the spherical model to nonspherical success domains is presented. The power of sexuality is discussed and it is shown that this power does not stem mainly from the “combination” of “good properties” of the mates (building block hypothesis) but rather from genetic repair diminishing the influence of harmful mutations. The dominant recombination is analyzed by introduction of surrogate mutations leading to the concept of species. Conclusions for evolutionary algorithms (EAs), including genetic algorithms (GAs), are drawn.

This paper analyzes the self-adaptation (SA) algorithm widely used to adapt strategy parameters of the evolution strategy (ES) in order to obtain maximal ES performance. The investigations are concentrated on the adaptation of one general mutation strength σ (called σSA) in (1, λ) ESs. The hypersphere serves as the fitness model. Starting from an introduction to the basic concept of self-adaptation, a framework for the analysis of σSA is developed on two levels: a microscopic level, concerning the description of the stochastic changes from one generation to the next, and a macroscopic level, describing the evolutionary dynamics of the σSA over time (generations). The σSA requires the fixing of a new strategy parameter, known as the learning parameter. The influence of this parameter on ES performance is investigated and rules for its tuning are presented and discussed. The results of the theoretical analysis are compared with ES experiments; it will be shown that applying Schwefel's τ-scaling rule guarantees the linear convergence order of the ES.

The effectiveness of intermediate recombination in evolution strategies is analyzed in light of the typical procedure of initializing trial solutions uniformly about the global optimum of benchmark functions. Analysis indicates that this procedure may predispose results in favor of intermediate recombination.

The multimembered evolution strategy (ES) acting on μ parents and λ offspring is analyzed for real-valued, N-dimensional parameter spaces (N ≳ 30). N-dependent progress rate formulas are derived for (1, λ) and (μ, λ) strategies on spherical models. The analytical results obtained are compared with simulation experiments for the (hyper)sphere and the inclined (hyper)plane.

A method for the determination of the progress rate and the probability of success for the Evolution Strategy (ES) is presented. The new method is based on the asymptotical behavior of the χ-distribution and yields exact results in the case of infinite-dimensional parameter spaces. The technique is demonstrated for the (l,+ λ) ES using a spherical model including noisy quality functions. The results are used to discuss the convergence behavior of the ES.