Beyer, Hans-Georg
Refine
Year of publication
Document Type
- Article (22)
- Conference Proceeding (22)
- Book (5)
- Part of a Book (2)
- Working Paper (2)
- Report (1)
Institute
Is part of the Bibliography
- yes (54)
Keywords
- Evolution strategy (7)
- Evolution Strategies (5)
- self-adaptation (4)
- Evolution strategies (3)
- Global optimization (3)
- Optimization (3)
- Rastrigin function (3)
- evolution strategies (3)
- global optimization (3)
- multi-modal objective function (3)
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 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.
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.