de Jong, Edwin D., Richard A. Watson, and Dirk Thierens. “On the complexity of hierarchical problem solving.” In Proceedings of the 7th annual conference on Genetic and evolutionary computation , pp. 1201-1208. 2005.
URL1 URL2
Competent Genetic Algorithms can efficiently address problems in which the linkage between variables is limited to a small order k . Problems with higher order dependencies can only be addressed efficiently if further problem properties exist that can be exploited. An important class of problems for which this occurs is that of hierarchical problems. Hierarchical problems can contain dependencies between all variables (k=n) while being solvable in polynomial time.An open question so far is what precise properties a hierarchical problem must possess in order to be solvable efficiently. We study this question by investigating several features of hierarchical problems and determining their effect on computational complexity, both analytically and empirically. The analyses are based on the Hierarchical Genetic Algorithm (HGA), which is developed as part of this work. The HGA is tested on ranges of hierarchical problems, produced by a generator for hierarchical problems.