Evolution strategies for constrained optimization

Abstract

Evolution strategies are population-based randomized optimization strategies derived from a simplified model of Darwinian evolution. Being based on that principle, they are well-suited for black-box optimization. In that area, it is assumed that the objective function(s) and/or constraint function(s) can only be evaluated for given points in the parameter space but nothing else is known about these functions. In such scenarios, evolutionary algorithms in general, and evolution strategies in particular for real-valued spaces, are naturally well-suited. The focus of their development and analysis has initially mainly been on unconstrained problems. As a step toward a better understanding of evolution strategies for constrained problems, this thesis is a combination of theoretically guided algorithm design and theoretical analyses of evolution strategies for constrained optimization.

In the first part, different algorithms are developed and empirically evaluated. Starting with linear constraints, an interior point evolution strategy with repair by projection is presented. For handling non-linear constraints, a second algorithm based on active covariance matrix adaptation is designed. The design of the algorithms is explained, they are empirically evaluated, and they are compared to other methods.

The second part deals with theoretical analyses. A conically constrained linear optimization problem is considered. Evolution strategies with sigma-self-adaptation and cumulative step-size adaptation are theoretically investigated. For the analyses, closed-form approximations for the microscopic aspects are derived. They are further used to investigate the macroscopic behavior of the algorithms (mean value dynamics and behavior in the steady state). The theoretically derived expressions are compared to real algorithm runs for showing the approximation quality.