Direct search mehtods under Nose II: Analysis and Design

The need for efficiently working direct search methods in the presence of noise is continuously growing, due to use of these strategies in simulation optimization and robust optimization. Analysis and design of these methods is still an almost uncharted field and offers plenty opportunities for research. First steps towards filling these gaps were done in the project "Evaluation of Evolutionary and Other Direct Search Methods in the Presence of Noise". The next step is now to push the design of improved efficient strategies. These strategies should be able to automatically detect noise and if necessary apply methods to reduce the influence of noise. The goal is to develop methods which need only a minimal number of additional function evaluations and are applicable to different strategies. In the case of noise reduction we will focus on Evolution Strategies (ES), where a reduction is possible by controlling the population sizes. This will be done by using a 2-level ES (Meta-ES), where the outer level controls the population sizes and the inner level solves the optimization task at hand. Existing research in this area showed that Meta-ES is quite promising to reach this goal. However, more research (especially in the field of noisy optimization) needs to be done before such strategies reach the status of practical use. On the other hand, the project will continue the analysis of direct search methods. Using the analysis methods developed by our group, more direct search strategies will be investigated. Especially, the pattern search methods and the response surface techniques are of interest. The focus will be on the analysis of the dynamic behavior on simple noisy functions. The anticipated results will improve the understanding of the behavior of these strategies and also allow for a direct comparison with other strategies. Furthermore, the analysis of strategies on more complex objective functions is part of the research goals. These include ridge functions and ellipsoidal functions. This will improve the understanding and might offer possibilities to improve the performance of these methods. Finally, one should be able to derive guidelines to assist the user in the field of noisy optimization.

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