Hierarchical BOA (hBOA)

External links:

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:

BOA.
Local Structures in Bayesian networks.
Niching.

BOA ensures that the problem is decomposed properly on each level of hierarchy. Local structures in Bayesian networks enable more efficient representation to ensure that accurate probabilistic models can be represented efficiently. Finally, a niching technique called the restricted tournament replacement (RTR) is incorporated to ensure preservation of useful diversity.

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:

There has been a patent filed for hBOA, and you can reach the accepted patent application using one of the links listed below.

Links

References

Pelikan, M., & Goldberg, D. E. (2001). Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), 511-518. Also IlliGAL Report No. 2000020.
Pelikan, M., & Goldberg, D. E. (2003). A hierarchy machine: Learning to optimize from nature and humans. Complexity, 8(5).

Last update: Wed Mar 19 23:28:23 CDT 2008 by Martin Pelikan