Abstract
Current Genetic Algorithms can efficiently address order-k separable problems, in which the order of the linkage is restricted to a low value k. Outside this class, there exist hierarchical problems that cannot be addressed by current genetic algorithms, yet can be addressed efficiently in principle by exploiting hierarchy. We delineate the class of hierarchical problems, and describe a framework for Hierarchical Genetic Algorithms. Based on this outline for algorithms, we investigate under what conditions hierarchical problems may be solved efficiently. Sufficient conditions are provided under which hierarchical problems can be addressed in polynomial time. The analysis points to the importance of efficient sampling techniques that assess the quality of module settings.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Goldberg, D.E.: The design of innovation. Lessons from and for competent genetic algorithms. Kluwer Academic Publishers, Dordrecht (2002)
Simon, H.A.: The Sciences of the Artificial. The MIT Press, Cambridge (1968)
Watson, R.A., Hornby, G.S., Pollack, J.B.: Modeling building-block interdependency. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 97–106. Springer, Heidelberg (1998)
Pelikan, M., Goldberg, D.E.: Escaping hierarchical traps with competent genetic algorithms. In: Spector, L., et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2001, pp. 511–518. Morgan Kaufmann, San Francisco (2001)
Pelikan, M., Goldberg, D.E.: Hierarchical problem solving by the bayesian optimization algorithm. In: Whitley, D., et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), Las Vegas, Nevada, USA, pp. 267–274. Morgan Kaufmann, San Francisco (2000)
Watson, R.A.: Compositional Evolution: Interdisciplinary Investigations in Evolvability, Modularity, and Symbiosis. PhD thesis, Brandeis University (2002)
Watson, R.A., Pollack, J.B.: A computational model of symbiotic composition in evolutionary transitions. Biosystems 69, 187–209 (2003); Special Issue on Evolvability, ed. Nehaniv
De Jong, E.D., Thierens, D.: Exploiting modularity, hierarchy, and repetition in variable-length problems. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 1030–1041. Springer, Heidelberg (2004)
Hu, J., Goodman, E.D.: The hierarchical fair competition (HFC) model for parallel evolutionary algorithms. In: Fogel, D.B., El-Sharkawi, M.A., Yao, X., Greenwood, G., Iba, H., Marrow, P., Shackleton, M. (eds.) Proceedings of the 2002 Congress on Evolutionary Computation CEC 2002, pp. 49–54. IEEE Press, Los Alamitos (2002)
Gulsen, M., Smith, A.E.: A hierarchical genetic algorithm for system identification and curve fitting with a supercomputer implementation. In: Davis, L.D., et al. (eds.) Evolutionary Algorithms, pp. 111–137. Springer, New York (1999)
Tang, K., Man, K., Istepanian, R.: Teleoperation controller design using hierarical genetic algorithms. In: Proceedings of the IEEE International conference on Industrial Technology, pp. 707–711 (2000)
Thierens, D., Goldberg, D.: Mixing in genetic algorithms. In: Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 38–45. Morgan Kaufmann, San Francisco (1993)
Thierens, D.: Scalability problems of simple genetic algorithms. Evolutionary Computation 7, 331–352 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Jong, E.D., Thierens, D., Watson, R.A. (2004). Hierarchical Genetic Algorithms. In: Yao, X., et al. Parallel Problem Solving from Nature - PPSN VIII. PPSN 2004. Lecture Notes in Computer Science, vol 3242. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30217-9_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-30217-9_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23092-2
Online ISBN: 978-3-540-30217-9
eBook Packages: Springer Book Archive