On the complexity of hierarchical problem solving

ABSTRACT

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.

REFERENCES

• 1: De Jong, E. D., Thierens, D., & Watson, W. (2004). Hierarchical genetic algorithms. In Yao, X., Burke, E., Lozano, J. A., Smith, J., Merelo-Guervos, J. J., Bullinaria, J. A., Rowe, J., Tino, P., Kaban, A., & Schwefel, H.-P. (Eds.), Parallel Problem Solving from Nature - PPSN VIII, Vol. 3242 of LNCS, pp. 232--241, Birmingham, UK. Springer-Verlag.
• 2: Edwin D. de Jong , Richard A. Watson , Dirk Thierens, A generator for hierarchical problems, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102328]
• 3: Etxeberria, R., & Larra~ naga, P. (1999). Global optimization using bayesian networks. In Rodriguez, A. O., Ortiz, M. S., & Hermida, R. S. (Eds.), Proceedings of the Second Symposium on Artificial Intelligence CIMAF.
• 4: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: David E. Goldberg , Kalyanmoy Deb , Hillol Kargupta , Georges Harik, RapidAccurate Optimization of Difficult Problems Using Fast Messy Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.56-64, June 01, 1993
• 6: Georges Raif Harik, Learning gene linkage to efficiently solve problems of bounded difficulty using genetic algorithms, University of Michigan, Ann Arbor, MI, 1997
• 7: Harik, G. (1999). Linkage learning via probabilistic modeling in the ECGA. Tech. rep. Illigal report no. 99010, University of Illinois at Urbana-Champain, Urbana, IL.
• 8: Kargupta, H. (1996). SEARCH, evolution, and the gene expression messy genetic algorithm. Tech. rep. LA-UR 96-60, Los Alamos National Laboratory.
• 9: Mühlenbein, H., & Mahnig, T. (1999). FDA - A scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation, 7(4), 353--376.
• 10: Pelikan, M., & Goldberg, D. E. (2001a). Escaping hierarchical traps with competent genetic algorithms. In Spector et al., L. (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-01, pp. 511--518. Morgan Kaufmann.
• 11: Pelikan, M., & Goldberg, D. E. (2001b). Hierarchical bayesian optimization algorithm = bayesian optimization algorithm + niching + local structures. In Optimization by Building and Using Probabilistic Models (OBUPM) 2001, pp. 217--221, San Francisco, California, USA.
• 12: Martin Pelikan , David E. Goldberg, A hierarchy machine: learning to optimize from nature and humans, Complexity, v.8 n.5, p.36-45, May/June 2003 [doi>10.1002/cplx.10103]
• 13: Pelikan, M., Goldberg, D. E., & Cantu-Paz, E. (1999). BOA: The bayesian optimization algorithm. In Banzhaf, W., Daida, J., Eiben, A. E., Garzon, M. H., Honavar, V., Jakiela, M., & Smith, R. E. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 1, pp. 525--532, San Francisco, CA. Morgan Kaufmann.
• 14: Toussaint, M. (2005). Foundations of Genetic Algorithms 8 (FOGA 2005), chap. Compact genetic codes as a search strategy of evolutionary processes. Morgan Kauffman.
• 15: Richard A. Watson , Jordan B. Pollack, Compositional evolution: interdisciplinary investigations in evolvability, modularity, and symbiosis, 2002
• 16: Richard A. Watson , Greg Hornby , Jordan B. Pollack, Modeling Building-Block Interdependency, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.97-108, September 27-30, 1998
• 17: Watson, R. A., & Pollack, J. B. (2003). A computational model of symbiotic composition in evolutionary transitions. Biosystems, 69(2-3), 187--209. Special Issue on Evolvability, ed. Nehaniv.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
hierarchy, modularity, representation development, scalability