|
|
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. 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.
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
|
