|Hierarchical BOA (hBOA)|
Hierarchical Bayesian optimization algorithm (hBOA)
To use decomposition on multiple levels, one must make sure that partial solutions from decomposition on each level are used as basic building blocks to construct solutions on the next level. It is also important to preserve several alternative partial solutions to each subproblem on the current level of decomposition so that combinations of these can be explored on higher levels. There are two primary reason for preservation of alternative partial solutions: (1) interactions that are ignored on the current level may reveal new information favoring either of noninferior partial solutions on the current level, and (2) several alternatives might look the same until higher levels reveal additional feedback for certain combinations of these alternatives. The hierarchical Bayesian optimization algorithm (hBOA) (Pelikan & Goldberg, 2001, 2003) can automatically discover and exploit hierarchical decomposition to ensure robust and scalable solution to nearly decomposable and hierarchical problems. hBOA consists of three components:
hBOA is capable of decomposing the problem over multiple levels of difficulty without any need for interaction with the user, and it can juxtapose solutions across the levels of a hierarchy to solve a broad class of nearly decomposable and hierarchical problems. Many hierarchical problems that are easily solved by hBOA in subquadratic number of function evaluations with respect to the number of decision variables, cannot be solved by any other method in less than exponential time. One example of such a challenging problem are hierarchical traps created by applying a hierarchy of a single trap function. Although there are practically no competitors who can scalably solve hierarchical traps, hBOA is capable of finding the optimum in less than a quadratic number of evaluations as shown in the following graph:
hBOA was patented with the U.S. Patent and Trademark Office.
Last update: Mon Aug 6 21:08:13 CDT 2012 by Martin Pelikan