Hierarchical BOA on random decomposable problems
11 July 2006Pelikan, M., Sastry, K., Butz, M.V., Goldberg, D.E. (2006). Proceedings of the 2006 Genetic and Evolutionary Computation Conference, 431—432. [Full paper - PDF] [Full paper - PS] [Poster slides].
Abstract:
The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems scalably and reliably. This paper describes a class of random additively decomposable problems with and without interactions between the subproblems and tests hBOA on a large number of random instances of the proposed class of problems. The performance of hBOA is compared to that of the simple genetic algorithm with standard crossover and mutation operators, the univariate marginal distribution algorithm, and the hill climbing with bit-flip mutation. The results confirm that hBOA achieves quadratic or subquadratic performance on the proposed class of random decomposable problems and that it significantly outperforms all other methods included in the comparison. The results also show that low-order polynomial scalability is retained even when only a small percentage of hardest problems are considered and that hBOA is a robust algorithm because its performance does not change much across the entire spectrum of random problem instances of the same structure. The proposed class of decomposable problems can be used to test other optimization algorithms that address nearly decomposable problems.
Related Posts:
- Empirical Analysis of ideal recombination on random decomposable problems
- Generator and interface for random decomposable problems in C
- Analysis of ideal recombination on random decomposable problems
- Analyzing probabilistic models in hierarchical BOA on traps and spin glasses
- Substructrual surrogates for learning decomposable classification problems: Implementation and first results
No comments yet
