Search

A theoretical performance analysis of the $(\mu /\mu _{I},\lambda) - \sigma $ -self-adaptation evolution strategy ($\sigma $ 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 $(\mu /\mu _{I},\lambda) - \sigma $ SA-ES exhibits a performance as if the ES were optimizing a sphere model. Unlike the nonrecombinative $(1,\lambda)$ -ES, the parental steady state behavior does not evolve on the cone boundary but stays away from the boundary to a certain extent. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 MA-ES and reduce its $\boldsymbol {\mathcal {O}}({n}^{ { {2}}})$ time and storage complexity to $\boldsymbol {\mathcal {O}}({{mn}})$ with $\boldsymbol {m}~{\boldsymbol \ll }~{n}$ such as $\boldsymbol {m}~{\boldsymbol \in }~\boldsymbol {\mathcal {O}}{(1)}$ or ${m} {\in } \boldsymbol {\mathcal {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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

The optimization behavior of the self-adaptation (SA) evolution strategy (ES) with intermediate multirecombination [\left(\mu/\muI,\lambda\right)\-\sigmaSA\-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 $\tau$ . The theoretical results are compared and validated by comparison with real \left(\mu/\muI,\lambda\right)\-\sigmaSA\-ES runs on two ellipsoid test model cases. The theoretical results clearly indicate that using a model-independent learning parameter \tau$ leads to suboptimal performance of the \left(\mu/\muI,\lambda\right)\-\sigmaSA\-ES on objective functions with changing local condition numbers as often encountered in practical problems with complex fitness landscapes. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper investigates the behavior of (μ/μI, λ)-σ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 σ and the localization parameter ζ will be derived. Building on that, the progress rate φ is analyzed and tuned by means of the learning parameter τ. An approximate formula for τopt, yielding locally maximal progress, is presented. Finally, the performance of the σSA-rule is compared with the performance of the cumulative step size adaptation rule, and a rough approximation for the expected runtime is presented. [ABSTRACT FROM AUTHOR]

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 FN1Ms 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 reevaluate parental fitness leads to both reduced success probabilities and improved performance. Implications for mutation strength adaptation rules are discussed and optimal resampling rates are computed. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper presents the N-dependent analysis of the (1,λ)-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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]