Pelikan M. Hierarchical Bayesian Optimization Algorithm. Toward a New Generation of Evolutionary Algorithms

Springer, 2005. — 181 p.A black-box optimization problem may be defined by specifying (1) a set of all potential solutions to the problem and (2) a measure for evaluating the quality of each candidate solution. The task is to find a solution or a set of solutions that perform best with respect to the specified measure. An important feature of black-box optimization is that a black-box optimizer does not know anything about the semantics of potential solutions or the relationship between potential solutions and the evaluation procedure. Potential solutions can represent anything from aircraft wings, to chess strategies, to musical compositions, to job schedules, or to configurations of a molecule. The evaluation procedure can be based on an experiment in a wind tunnel, a traffic simulation, or a computer procedure. The only way how a black-box optimizer can learn something about the problem is to sample new solutions, evaluate them, and process the results of the evaluation. Since many challenging realworld problems can be formulated as black-box optimization problems, the design of automated, robust, and scalable black-box optimization methods is one of the most important challenges in computational optimization.
The primary goal of this book is to design an advanced black-box optimization algorithm for automated, robust, and scalable solution of a broad class of real-world problems without the need for interaction with the user or problem-specific knowledge in addition to the set of potential solutions and the performance measure. Despite that the book tries to alleviate the need for expensive manual problem analysis, the methods presented here enable the use of prior problem-specific knowledge of various forms. Consequently, if the practitioner has additional knowledge about the problem, this can likely be used for further efficiency enhancement.
To meet this difficult challenge, the book derives inspiration from the way the best problem solvers – humans – solve their problems. To simplify problems and to develop tractable models of complex systems, humans often break up the problem or system into several subproblems or subsystems. This can be done on a single or multiple levels, but the basic idea remains the same – decompose the big problem into smaller subproblems, solve the subproblems (either directly or via yet another level of decomposition), and combine the results to form the solution to the entire problem. Although the basic idea of using decomposition in problem solving is simple, decomposition can be used across an enormously diverse spectrum of areas from mathematical theorem proving to engineering design, to computation of magnetic properties of complex physical systems, to development of models of complex ecological systems, and to music composition.
The algorithms developed in this book borrow ideas from genetic and evolutionary computation, machine learning, and statistics. The work is most closely related to genetic and evolutionary computation, which provides us with the concepts of population-based search, directed exploration by combining features of promising solutions, diversity preservation techniques, and facetwise theory and design. New operators are designed for exploration of the space of all potential solutions based on methods adopted from machine learning and statistics to ensure automatic discovery and exploitation of single-level and hierarchical decomposition in genetic and evolutionary algorithms. The combination of genetic and evolutionary computation with the methods of machine learning and statistics enables quick, accurate, and reliable solution of a large class of nearly decomposable and hierarchical problems, many of which are intractable by other common optimization techniques.
This book is intended for a wide audience and it does not require the reader to be an expert in genetic and evolutionary computation, machine learning, or statistics. Basics in mathematics and statistics should provide sufficient background to understand most material in this book. Basic knowledge of genetic and evolutionary computation and machine learning is not necessary, but it can allow the reader to proceed faster.From Genetic Variation to Probabilistic Modeling
Probabilistic Model-Building Genetic Algorithms
Bayesian Optimization Algorithm
Scalability Analysis
The Challenge of Hierarchical Difficulty
Hierarchical Bayesian Optimization Algorithm
Hierarchical BOA in the Real World
Summary and Conclusions