Evolutionary and Other Direct Search Methods under Noise

Noise is a common phenomenon in optimization tasks dealing with real-world applications. Typically one has to cope with measurement errors, actuator vibrations, production tolerances and/or one is searching for robust (i.e., insensitive) designs. As a consequence, one has to deal with noisy objective functions. The treatment of such optimization tasks can be accomplished by direct search techniques based on stochastic approximation, pattern search, response surface methods, and evolutionary computation, respectively. In the last decade, evolutionary algorithms such as evolution strategies and genetic algorithms appeared to exhibit promising performance properties on such optimization problems. While it is often argued that this is due to the use of a population of candidate solutions which is in contrast to most of the other direct search methods, the theory of evolutionary algorithms is not so much advanced up to now to provide a rigorous justification of the claims being made about these algorithms. Considering finite time performance estimates on objective function classes, this also holds more or less for all classes of direct search algorithms. Up to now only a few systematic performance evaluations of these algorithms in the presence of noise have been conducted. The goal of this project is to systematically push forward the frontiers of knowledge about the finite time properties of these direct search algorithms both the evolutionary and the other methods (with an 50% emphasis on evolutionary methods, especially evolution strategies). This research comprises both theoretical investigations concerning asymptotic scaling laws of the solution quality and empirical performance evaluations. It also compares the different direct search algorithms in order to determine their strengths and weaknesses on the objective function classes considered. Thus, providing algorithm application guidelines for users facing the problems of noisy optimization.

Noise is a common phenomenon in optimization tasks dealing with real-world applications. Typically one has to cope with measurement errors, actuator vibrations, production tolerances and/or one is searching for robust (i.e., insensitive) designs. As a consequence, one has to deal with noisy objective functions. The treatment of such optimization tasks can be accomplished by direct search techniques based on stochastic approximation, pattern search, response surface methods, and evolutionary computation, respectively. In the last decade, evolutionary algorithms such as evolution strategies and genetic algorithms appeared to exhibit promising performance properties on such optimization problems. While it is often argued that this is due to the use of a population of candidate solutions which is in contrast to most of the other direct search methods, the theory of evolutionary algorithms is not so much advanced up to now to provide a rigorous justification of the claims being made about these algorithms. Considering finite time performance estimates on objective function classes, this also holds more or less for all classes of direct search algorithms. Up to now only a few systematic performance evaluations of these algorithms in the presence of noise have been conducted. The goal of this project is to systematically push forward the frontiers of knowledge about the finite time properties of these direct search algorithms both the evolutionary and the other methods (with an 50% emphasis on evolutionary methods, especially evolution strategies). This research comprises both theoretical investigations concerning asymptotic scaling laws of the solution quality and empirical performance evaluations. It also compares the different direct search algorithms in order to determine their strengths and weaknesses on the objective function classes considered. Thus, providing algorithm application guidelines for users facing the problems of noisy optimization.