FWF Project Page P22649-N23


Project Title:  

"Evolutionary and Other Direct Search Methods in the Presence of Noise II: Analysis and Design"

Project Number: P22649-N23

Project Summary:

This research project was aiming at the analysis and design of so-called direct search algorithms under the condition of noise and uncertainties. Especially, Evolution Strategies have been analyzed, but also so-called pattern search and response surface based strategies have been considered. Aside from theoretical analyses that build the basis for a deeper understanding of the performance of these algorithms, techniques have been developed to improve the performance of these algorithms.

Noise and uncertainties do often occur in real-world optimization problems and cannot always be prevented. Typical examples are hardware-in-the-loop optimizations, optimization of Monte Carlo simulations and the increasingly important field of robust system design. Furthermore, the problems to be optimized are often too complex for a complete analysis such that a first approach is to treat the systems as black-boxes.

Direct search methods are the means of choice for the improvement and/or optimization of such systems arising in all fields of engineering, science, and economy. The main advantage of these direct search techniques is their ease of use and the general applicability that makes them especially well suited for black-box optimization. Direct search algorithm do directly manipulate the input variables of the black-box in order to tune the system in such a manner that the output of the box gets maximal or minimal according to predefined design goals.

However, in the case of noise the output of the black-box is randomly disturbed. That is, testing the system with the same input several times, the output changes randomly (e.g. observational or measurement errors). A seemingly good output may belong to a rather unsuitable input and vice versa. In order to apply direct search algorithms to such scenarios, countermeasures must be taken in order to ensure a finally good outcome of the optimization process. Furthermore and this was a main intent of this research the efforts needed to get closer to the optimal solution should be as low as possible. That is, it was the aim to design direct search algorithms that do need a minimum of black-box evaluations (because running the black-box, e.g. a simulation program, is costly and takes time). As a result, a variable population size Evolution Strategy has been developed that can even cope with strong noise.




1.1  Already published

1.  Finck, S. and Beyer, H.-G. and Melkozerov, A.: „Noisy Optimization: A Theoretical Strategy Comparison of ES, EGS, SPSA & IF on the Noisy Sphere“ in GECCO'11: Proceedings of the Genetic and Evolutionary Computation Conference; pp. 813-820; 2011; DOI: 10.1145/2001576.2001688; [pdf]

2.  Finck, S. and Beyer, H.-G.: „Performance Analysis of Simultaneous Perturbation Stochastic Approximation on the Noisy Sphere Model“ in Journal of Theoretical Computer Science, pp. 50-72, Vol. 419, 2012; DOI: 10.1016/j.tcs.2011.11.015; [pdf]

3.  Beyer, H.-G. and Finck, S.: „HappyCat - A Simple Function Class Where Well-Known Direct Search Algorithms Do Fail“ in Proceedings of Parallel Problem Solving from Nature XII, pp. 367-376, 2012; DOI: 10.1007/978-3-642-32937-1_37; [pdf]

4.  Beyer, H.-G. and Hellwig, M.: „Mutation Strength Control by Meta-ES on the Sharp Ridge“ in GECCO'12: Proceedings of the Genetic and Evolutionary Computation Conference; pp. 305-312, 2012; DOI: 10.1145/2330163.2330208; [pdf]

5.  Beyer, H.-G. and Hellwig, M.: „Controlling Population Size and Mutation Strength by Meta-ES under Fitness Noise“ in Foundations of Genetic Algorithms XII, pp. 11-24, 2013; DOI: 10.1145/2460239.2460242; [pdf]

6.  Beyer, H.-G. and Melkozerov, A.: „The Dynamics of Self-Adaptive Multi-Recombinant Evolution Strategies on the General Ellipsoid Model“ in IEEE Transactions on Evolutionary Computation 18(5), pp. 764-778, 2014; DOI: 10.1109/TEVC.2013.2283968; [pdf]

7.  Beyer, H.-G. and Finck, S. and Breuer, T.: „Evolution on Trees: On the Design of an Evolution Strategy for Scenario-Based Multi-Period Portfolio Optimization under Transaction Costs“ in Journal Swarm and Evolutionary Computation, 17, pp. 74-87, 2014; DOI: 10.1016/j.swevo.2014.03.002; [pdf]

8.  Beyer, H.-G.: „Convergence Analysis of Evolutionary Algorithms that are Based on the Paradigm of Information Geometry“ in Journal Evolutionary Computation 22(4), pp. 679-709, 2014; DOI: 10.1162/EVCO_a_00132; [pdf]


1.2 Publications accepted

1.  Hellwig, M. and Arnold, D.V.: “Comparison of Constraint Handling Mechanisms for the (1,l)-ES on a Simple Constrained Problem” in Journal Evolutionary Computation, 2015; DOI: 10.1162/EVCO_a_00139; [pdf]

2.  Beyer, H.-G. and Hellwig, M.: “The Dynamics of Cumulative Step-Size Adaptation on the Ellipsoid Model“ in Journal Evolutionary Computation, 2015; DOI: 10.1162/EVCO_a_00142; [pdf]

3.  Melkozerov, A. and Beyer, H.-G.: “Towards an Analysis of Self-Adaptive Evolution Strategies on the Noisy Ellipsoid Model: Progress Rate and Self-Adaptation Response“ in GECCO'15: Proceedings of the Genetic and Evolutionary Computation Conference; 2015; DOI: 10.1145/2739480.2754800; [pdf]


1.3 Publications in review

1.  Hellwig, M. and Beyer, H.-G.: “Mutation Strength Control via Meta-Evolution Strategies on the Ellipsoid Model“ IEEE Transactions on Evolutionary Computation, 2015; [pdf]


1.4 Technical Reports

1.  Hansen, N. and Finck, S. and Ros, R.: „COCO - COmparing Continuous Optimizers: The Documentation”, Rapport de recherche RT-0409, INRIA, 2011, URL: http://hal.inria.fr/inria-00597334

2.  Finck, S.: „Analysis of Simple Pattern Search on the Noisy Sphere Model“, Technical Report 2013/01,  Vorarlberg University of Applied Sciences, Research Center PPE, URL: PPE-Working Papers 2013/01

3.  Melkozerov, A. and Beyer, H.-G.: „On the Derivation of the Progress Rate and Self-Adaptation Response for the (m/m,l)-sSA-ES on the Noisy Ellipsoid Model“, Technical Report 2015/01,  Vorarlberg University of Applied Sciences, Research Center PPE, URL: PPE-Working Papers 2015/01

4.  Hellwig, M. and Beyer, H.-G.: „Population Size Control of CMSA-ES for Noisy Optimization Using Time Series Analysis“, Technical Report 2015/02,  Vorarlberg University of Applied Sciences, Research Center PPE, URL: PPE-Working Papers 2015/02



last change: 24.04.2015