Neutrality and variability: two sides of evolvability in linear genetic programming

ABSTRACT

The notion of evolvability has been put forward to describe the "core mechanism" of natural and artificial evolution. Recently, studies have revealed the influence of the environment upon a system's evolvability. In this contribution, we study the evolvability of a system in various environmental situations. We consider neutrality and variability as two sides of evolvability. The former makes a system tolerant to mutations and provides a hidden staging ground for future phenotypic changes. The latter produces explorative variations yielding phenotypic improvements. Which of the two dominates is influenced by the environment. We adopt two tools for this study of evolvability: 1) the rate of adaptive evolution, which captures the observable adaptive variations driven by evolvability; and 2) the variability of individuals, which measures the potential of an individual to vary functionally. We apply these tools to a Linear Genetic Programming system and observe that evolvability is able to exploit its two sides in different environmental situations.

REFERENCES

• 1: Lee Altenberg, The evolution of evolvability in genetic programming, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 2: W. Banzhaf and A. Leier. Evolution on neutral networks in genetic programming. In Genetic Programming Theory and Practice III pages 207--221. Springer, 2006.
• 3: M. A. Bedau and N. H. Packard. Evolution of evolvability via adaptation of mutation rates. BioSystems 69(2):143--162, 2003.
• 4: Terry Van Belle , David H. Ackley, Code Factoring And The Evolution Of Evolvability, Proceedings of the Genetic and Evolutionary Computation Conference, p.1383-1390, July 09-13, 2002
• 5: Markus F. Brameier , Wolfgang Banzhaf, Linear Genetic Programming (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 6: S. Collins, J. de Meaux, and C. Acquisti. Adaptive walks toward a moving optimum. Genetics 176(2):1089--1099, 2007.
• 7: M. Conrad. The geometry of evolution. BioSystems 24(11):61--81, 1990.
• 8: R. Dawkins. The evolution of evolvability. In Artificial Life: The Quest for a New Creation pages 201--220. Addison-Wesley, Reading, MA, USA, 1989.
• 9: D. J. Earl and M. W. Deem. Evolvability is a selectable trait. Proceedings of the National Academy of Sciences 101(32):11531--11536, 2004.
• 10: Marc Ebner , Mark Shackleton , Rob Shipman, How neutral networks influence evolvability, Complexity, v.7 n.2, p.19-33, November/December 2001 [doi>10.1002/cplx.10021]
• 11: Ting Hu , Wolfgang Banzhaf, Nonsynonymous to Synonymous Substitution Ratio ka/ks: Measurement for Rate of Evolution in Evolutionary Computation, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_45]
• 12: Y. Jin, R. Gruna, I. Paenke, and B. Sendhoff. Multi-objective optimization of robustness and innovation in redundant genetic representations. In Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multicriteria Decision-Making pages 38--45. IEEE Press, 2009.
• 13: N. Kashtan, E. Noor, and U. Alon. Varying environments can speed up evolution. Proceedings of the National Academy of Sciences 104(34):13713--13716, 2007.
• 14: M. W. Kirschner and J. C. Gerhart. Evolvability. Proceedings of the National Academy of Sciences 95(15):8420--8427, 1998.
• 15: K. F. Liem. Key evolutionary innovations, differential diversity, and symecomorphosis. In Evolutioanry Innovations pages 147--170. University of Chicago Press, Chicago, IL, USA, 1990.
• 16: P. Marrow, M. Heath, and I. I. Re. Evolvability: Evolution, Computation, and Biology. In GECCO'99: Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop on Evolvability pages 30--33. Morgan Kaufmann, 1999.
• 17: L. A. Meyers, F. D. Ancel, and M. Lachmann. Evolution of genetic potential. PLoS Computational Biology 1(3):0236--0243, 2005.
• 18: C. L. Nehaniv. Measuring evolvability as the rate of complexity increase. In Proceedings of the Artificial Life VII Workshop pages 55--57. MIT Press, 2000.
• 19: H. A. Orr. The population genetics of adaptation:the distribution of factors fixed during adaptive evolution Evolution 52(4):935--949, 1998.
• 20: M. Parter, N. Kashtan, and U. Alon. Facilitated variation:How evolution learns from past environments to generalize to new environments. PLoS Computational Biology 4(11):e1000206, 2008.
• 21: R. A. Raff. The Shape of Life: Genes, Development, and the Evolution of Animal Form Universityof Chicago Press, Chicago, IL, USA, 1996.
• 22: Joseph Reisinger , Risto Miikkulainen, Selecting for evolvable representations, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144199]
• 23: A. Wagner. Robustness, evolvability, and neutrality. Federation of European Biochemical Societies Letters 579(8):1772--1778, 2005.
• 24: A. Wagner. Robustness and evolvability:A paradox resolved. Proceedings of The Royal Society B 275(1630):91--100, 2008.
• 25: G. P. Wagner and L. Altenberg. Complex adaptations and the evolution of evolvability. Evolution 50(3):967--976, 1996.
• 26: Z. Yang and J. P. Bielawski. Statistical methods for detecting molecular adaptation. Trends in Ecology and Evolution 15(12):496--503, 2000.
• 27: T. Yu. Program evolvability under environmental variations and neutrality. In Proceedings of the 9th European Conference on Advances in Artificial Life (ECAL07)pages 835--844. Springer, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Experimentation, Measurement, Performance

Keywords:
evolvability, neutrality, rate of evolution, variability