On the complexity of hierarchical problem solving

• DOI: 10.1145/1068009.1068207
• Publication Date: 2005-08-03T08:31:47Z
• Authors: Edwin D. de Jong; Richard A. Watson; Dirk Thierens
• Keywords: 0102 computer and information sciences; 01 natural sciences

Competent Genetic Algorithms can efficiently address problems in which the linkage between variables is limited to a small order k. Problems with higher dependencies only be addressed if further problem properties exist that exploited. An important class of for this occurs hierarchical problems. Hierarchical contain all (k=n) while being solvable polynomial time.An open question so far what precise must possess efficiently. We study by investigating several features and determining their effect on computational complexity, both analytically empirically. The analyses are based Algorithm (HGA), developed as part work. HGA tested ranges problems, produced generator