On solving hierarchical problems with top down control

ABSTRACT

We review recent work on the Hierarchical-If-And-Only-If problem and present a new hierarchical problem, HIFF-M that does not fit with previous explanations for evolutionary difficulty on hierarchical problems decomposed by levels for RMHC2. RMHC2 is a hill climbing algorithm augmented with a multi-level selection scheme. When used with the "ideal" sieve for a problem, as is done in this paper, RMHC2 exerts top-down control on the evolutionary dynamics, in the sense that adaptation of higher levels are given priority over adaptation of lower levels, and creates stabilizing selection pressure with potential to increase evolvability. Through HIFF-M, we discovered that the summary statistic, Fitness Distance Correlation by level, is not a reliable indicator of when a hierarchical problem is solvable by RMHC2, and that the two properties proposed to explain search easiness for RMHC2 are inadequate. Our investigation of this anomaly led us to propose an additional property for hierarchical evolution difficulty under RMHC2: inter-level conflict. We also discuss how hierarchical control can be subverted through the information transfer capacity of the transposition operation.

REFERENCES

• 1: Forrest, S. and Mitchell, M. Relative Building-block Fitness and the Building Block Hypothesis. In D. Whitley (editor) Foundations of Genetic Algorithms (FOGA) vol. 2, 1993, Morgan Kaufmann.
• 2: Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 1995
• 3: Khor, S. HIFF-II: A Hierarchically Decomposable problem with Inter-level Interdependency. IEEE Symposium on Artificial Life, 2007. ISBN: 1-4244-0698-6
• 4: Susan Khor, Hill climbing on discrete HIFF: exploring the role of DNA transposition in long-term artificial evolution, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277014]
• 5: Khor, S. Rethinking the adaptive capability of accretive evolution on Hierarchically Consistent problems. IEEE Symposium on Artificial Life, 2007. ISBN: 1-4244-0698-6
• 6: Joshua D. Knowles , Richard A. Watson , David Corne, Reducing Local Optima in Single-Objective Problems by Multi-objectivization, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.269-283, March 07-09, 2001
• 7: Mesot, B. and Teuscher, C. Deducing local rules for solving global tasks with random Boolean networks. Physica D 211, 2005, pp. 88--106.
• 8: Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA, 1998
• 9: Pelikan, M. and Goldberg, D. E. Escaping Hierarchical Traps with Competent Genetic Algorithms. In Genetic and Evolutionary Computation Conference (GECCO), 2001. Morgan Kaufmann.
• 10: Richard A. Watson, Compositional Evolution: The Impact of Sex, Symbiosis, and Modularity on the Gradualist Framework of Evolution (Vienna Series in Theoretical Biology), The MIT Press, 2006
• 11: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Design

Keywords:
hierarchical control, hierarchical test problems, level decomposition, transposition