
Project Title: "Evolutionary and Other Direct Search Methods in the
Presence of Noise II: Analysis and Design" Project Number: P22649N23
Project
Summary:
This research project was aiming at the
analysis and design of socalled direct search algorithms under the condition
of noise and uncertainties. Especially, Evolution Strategies have been
analyzed, but also socalled 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 realworld optimization problems and cannot always be prevented.
Typical examples are hardwareintheloop 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
blackboxes. 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 blackbox
optimization. Direct search algorithm do directly manipulate the input
variables of the blackbox 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 blackbox 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 blackbox evaluations
(because running the blackbox, 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. Publications 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.
813820; 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. 5072, 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 WellKnown Direct Search
Algorithms Do Fail in Proceedings of Parallel Problem Solving from
Nature XII, pp. 367376, 2012; DOI: 10.1007/9783642329371_37; [pdf]
4. Beyer, H.G. and Hellwig, M.: Mutation Strength Control by MetaES on the Sharp Ridge in
GECCO'12: Proceedings of the Genetic and Evolutionary Computation Conference;
pp. 305312, 2012; DOI: 10.1145/2330163.2330208; [pdf]
5. Beyer, H.G. and Hellwig, M.: Controlling Population Size and Mutation Strength by MetaES under
Fitness Noise in Foundations of Genetic Algorithms XII, pp. 1124, 2013;
DOI: 10.1145/2460239.2460242; [pdf]
6. Beyer, H.G. and Melkozerov, A.: The Dynamics of SelfAdaptive MultiRecombinant Evolution Strategies
on the General Ellipsoid Model in IEEE Transactions on Evolutionary
Computation 18(5), pp. 764778, 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 ScenarioBased MultiPeriod Portfolio Optimization
under Transaction Costs in Journal Swarm and Evolutionary Computation,
17, pp. 7487, 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.
679709, 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 StepSize 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 SelfAdaptive
Evolution Strategies on the Noisy Ellipsoid Model: Progress Rate and SelfAdaptation
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 MetaEvolution 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 RT0409, INRIA, 2011, URL: http://hal.inria.fr/inria00597334
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: PPEWorking Papers 2013/01
3. Melkozerov, A. and Beyer, H.G.: On the Derivation of the Progress Rate and SelfAdaptation Response
for the (m/m,l)sSAES on the
Noisy Ellipsoid Model, Technical
Report 2015/01, Vorarlberg University
of Applied Sciences, Research Center PPE, URL: PPEWorking Papers 2015/01
4. Hellwig, M. and Beyer, H.G.: Population Size Control of CMSAES for Noisy Optimization Using Time
Series Analysis, Technical Report 2015/02, Vorarlberg University of Applied Sciences,
Research Center PPE, URL: PPEWorking Papers 2015/02
