Hill climbing on discrete HIFF: exploring the role of DNA transposition in long-term artificial evolution

ABSTRACT

We show how a random mutation hill climber that does multi-level selection utilizes transposition to escape local optima on the discrete Hierarchical-If-And-Only-If (HIFF) problem. Although transposition is often deleterious to an individual, we outline two population models where recently transposed individuals can survive. In these models, transposed individuals survive selection through cooperation with other individuals. In the multi-population model, individuals were allowed a maturation stage to realize their potential fitness. In the genetic algorithm model, transposition helped maintain genetic diversity even within small populations. However, the results for transposition on the discrete Hierarchical-Exclusive-Or (HXOR) problem were less positive. Unlike HIFF, HXOR does not benefit from random drift. This led us to hypothesize that two conditions necessary for transposition to enhance evolvability are (i) the presence of local optima and (ii) susceptibility to random drift. This hypothesis is supported by further experiments. The findings of this paper suggest that epistasis and large mutations can sustain artificial evolution in the long-term by providing a way for individuals and populations to escape evolutionary dead ends. Paradoxically, epistasis creates local optima and holds a key to its resolution, while deleterious mutations such as transposition enhance evolvability. However, not all large mutations are equal.

REFERENCES

• 1: Alberts, B. (Editor) Molecular Biology of the Cell. Fourth edition, 2002. Garland Press. Available online at NCBI.
• 2: Lee Altenberg, Evolvability Suppression to Stabilize Far-Sighted Adaptations, Artificial Life, v.11 n.4, p.427-444, December 2005 [doi>10.1162/106454605774270633]
• 3: Culberson, J. C. Mutation-crossover isomorphisms and the construction of discriminating functions. Evolutionary Computation vol. 2, 1994, pages 279--311.
• 4: de Jong, E. D., Thierens, D. and Watson, R. A.allHierarchical genetic algorithms. In X. Yao, et al. (Editors) Parallel Problem Solving from Nature (PPSN) vol. VIII, 2004, pages 232 -- 241, Springer, Berlin.
• 5: 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.
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 8: 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
• 9: Kauffman, S. A. The Origins of Order. Oxford University Press, 1993.
• 10: Khor, S. Rethinking the adaptive capability of accretive evolution on hierarchically consistent problems. IEEE Symposium on Artificial Life, 2007.
• 11: 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
• 12: Pelikan, M. and Goldberg, D. E. Escaping hierarchical traps with competent genetic algorithms. In L.E Spector, et al. (editors), Genetic and Evolutionary Computation Conference, 2001, pages 511 -- 518, Morgan Kaufmann.
• 13: Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
• 14: James Alfred Walker , Julian Francis Miller, Embedded cartesian genetic programming and the lawnmower and hierarchical-if-and-only-if problems, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144154]
• 15: Watson, R. A. Analysis of recombinative algorithms on a non-separable building-block problem. In W. N. Martin and W. M. Spears (Editors) Foundations of Genetic Algorithms (FOGA), vol. 6, 2001, pages 69--90. Morgan Kaufman.
• 16: Watson, R. A. and Pollack, J. B. A computational model of symbiotic composition in evolutionary transitions. BioSystems, vol. 69, 2003, pages 187 -- 209, Elsevier.
• 17: Watson, R. A. and Pollack, J. B. Hierarchically consistent test problems for genetic algorithms. In P. J. Angeline, et al. (Editors), Congress on Evolutionary Computation (CEC), 1999, pages 1406--1413. IEEE Press.
• 18: 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
• 19: 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:
crossing fitness saddles, evolvability, hierarchical test problems, hill climbing