Escaping hierarchical traps with competent genetic algorithms

TLDR

Solving hierarchical problems requires learning linkages, efficiently representing partial solutions, and ensuring effective niching. The authors aim to introduce a hierarchical Bayesian optimization algorithm and a new class of hierarchically decomposable deceptive problems, called hierarchical traps. The algorithm integrates Bayesian optimization with local Bayesian network structures and a powerful niching technique. The algorithm scales subquadratically on all test problems, and empirical results confirm recent theory.

Abstract

To solve hierarchical problems, one must be able to learn the linkage, represent partial solutions efficiently, and assure effective niching. We propose the hierarchical Bayesian optimization algorithm which combines the Bayesian optimization algorithm, local structures in Bayesian networks, and a powerful niching technique. Additionally, we propose a class of hierarchically decomposable problems, called hierarchical traps, which are deceptive on each level. The proposed algorithm is shown to scale up subquadratically on all test problems. Empirical results are in agreement with recent theory.