Active Sets for Explicitly Constrained Evolutionary Optimization.

Active-set approaches are commonly used in algorithms for constrained numerical optimization. We propose that active-set techniques can beneficially be employed for evolutionary black-box optimization with explicit constraints and present an active-set evolution strategy. We experimentally evaluate its performance relative to those of several algorithms for constrained optimization and find that the active-set evolution strategy compares favourably for the problem set under consideration.

Comparison of Constraint-Handling Mechanisms for the (1,λ)-ES on a Simple Constrained Problem.

This paper investigates constraint-handling techniques used in nonelitist single-parent evolution strategies for the problem of maximizing a linear function with a single linear constraint. Two repair mechanisms are considered, and the analytical results are compared to those of earlier repair approaches in the same fitness environment. The first algorithm variant applies reflection to initially infeasible candidate solutions, and the second repair method uses truncation to generate feasible solutions from infeasible ones. The distributions describing the strategies' one-generation behavior are calculated and used in a zeroth-order model for the steady state attained when operating with fixed step size. Considering cumulative step size adaptation, the qualitative differences in the behavior of the algorithm variants can be explained. The approach extends the theoretical knowledge of constraint-handling methods in the field of evolutionary computation and has implications for the design of constraint-handling techniques in connection with cumulative step size adaptation.

On the behaviour of the (1, λ)-ES for conically constrained linear problems.

We study the behaviour of a [Formula: see text]-ES that handles constraints by resampling infeasible candidate solutions for linear optimization problems with a conically constrained feasible region. The analysis generalizes prior work in that no particular orientation of the cone relative to the gradient of the objective function is assumed. Expressions that describe the strategy's single-step behaviour are derived. Assuming that the mutation strength is adapted in a scale-invariant manner, a simple zeroth-order model is used to determine the speed of convergence of the strategy. We then derive expressions that approximately characterize the average step size and convergence rate attained when using cumulative step size adaptation and compare the values with optimal ones.

Resampling versus repair in evolution strategies applied to a constrained linear problem.

We study the behaviour of multi-recombination evolution strategies for the problem of maximising a linear function with a single linear constraint. Two variants of the algorithm are considered: a strategy that resamples infeasible candidate solutions and one that applies a simple repair mechanism. Integral expressions that describe the strategies' one-generation behaviour are derived and used in a simple zeroth order model for the steady state attained when operating with constant step size. Applied to the analysis of cumulative step size adaptation, the approach provides an intuitive explanation for the qualitative difference in the algorithm variants' behaviour. The findings have implications for the design of constraint handling techniques to be used in connection with cumulative step size adaptation.

On the behaviour of evolution strategies optimising cigar functions.

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.

Step length adaptation on ridge functions.

Step length adaptation is central to evolutionary algorithms in real-valued search spaces. This paper contrasts several step length adaptation algorithms for evolution strategies on a family of ridge functions. The algorithms considered are cumulative step length adaptation, a variant of mutative self-adaptation, two-point adaptation, and hierarchically organized strategies. In all cases, analytical results are derived that yield insights into scaling properties of the algorithms. The influence of noise on adaptation behavior is investigated. Similarities and differences between the adaptation strategies are discussed.

Optimum tracking with evolution strategies.

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.

On the benefits of populations for noisy optimization.

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.

Qualms regarding the optimality of cumulative path length control in CSA/CMA-evolution strategies.

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.