An empirical investigation of how and why neutrality affects evolutionary search

ABSTRACT

The effects of neutrality on evolutionary search have been considered in a number of studies, the results of which, however, have been contradictory. Some have found neutrality to be beneficial to aid evolution whereas others have argued that neutrality in the evolutionary process is useless. We believe that this confusion is due to several reasons: many studies have based their conclusions on performance statistics rather than a more in-depth analysis of population dynamics, studies often consider problems, representations and search algorithms that are relatively complex and so results represent the compositions of multiple effects, there is not a single definition of neutrality and different studies have added neutrality to problems in radically different ways. In this paper, we try to shed some light on neutrality by addressing these problems. That is, we use the simplest possible definition of neutrality (a neutral network of constant fitness, identically distributed in the whole search space), we consider one of the simplest possible algorithms (a mutation based, binary genetic algorithm) applied to two simple problems (a unimodal landscape and a deceptive landscape), and analyse both performance figures and, critically, population flows from and to the neutral network and the basins of attraction of the optima.

REFERENCES

• 1: Wolfgang Banzhaf, Genotype-Phenotype-Mapping and Neutral Variation - A Case Study in Genetic Programming, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.322-332, October 09-14, 1994
• 2: R. Chow. Evolving genotype to phenotype mappings with a multiple-chromosome genetic algorithm. In K. D. et al. editor, GECCO 2004: Proceedings of the 2004 Conference on Genetic and Evolutionary Computation volume 1, pages 1006--1017, Seattle WA, USA, 26-30 June 2004. Springer-Verlag.
• 3: M. Collins, Finding needles in haystacks is harder with neutrality, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068282]
• 4: R. M. Downing. Evolving binary decision diagrams using implicit neutrality. In CEC 2005: IEEE Congress on Evolutionary Computation (CEC'2005) pages 5--11, Edinburgh, Scotland, 2005.
• 5: Inman Harvey , Adrian Thompson, Through the Labyrinth Evolution Finds a Way: A Silicon Ridge, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.406-422, October 07-08, 1996
• 6: R. E. Keller and W. Banzhaf. Genetic programming using genotype-phenotype mapping from linear genomes into linear phenotypes. In J. R. Koza, D. E. Goldberg, D. B. Fogel, andR. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference pages 116--122, Stanford University, CA, USA, 28--31 July 1996. MIT Press.
• 7: M. Kimura. Evolutionary rate at the molecular level. In Nature volume 217, pages 624--626, 1968.
• 8: Julian F. Miller , Peter Thomson, Cartesian Genetic Programming, Proceedings of the European Conference on Genetic Programming, p.121-132, April 15-16, 2000
• 9: R. Shipman , M. Shackleton , I. Harvey, The Use of Neutral Genotype-Phenotype Mappings for Improved Evolutionary Search, BT Technology Journal, v.18 n.4, p.103-111, October 2000 [doi>10.1023/A:1026714927227]
• 10: R. Shipman, M. Schakleton, M. Ebner, and R. Watson. Neutral search spaces for artificial evolution: A lesson from life. In M. Bedau, S. Rasmussen, J. McCaskill, and N. Packard, editors, Artificial Life: Proceedings of the Seventh International Conference on Artificial Evolution pages 162--169. MIT Press, 2000.
• 11: Tom Smith , Phil Husbands , Michael O'Shea, Neutral Networks and Evolvability with Complex Genotype-Phenotype Mapping, Proceedings of the 6th European Conference on Advances in Artificial Life, p.272-281, September 10-14, 2001
• 12: T. Smith, P. Husbands, and M. O'Shea. Neutral networks in an evolutionary robotics search space. In Congress on Evolutionary Computation: CEC 2001 pages 136--145. IEEE Press, 2001.
• 13: Tina Yu , Julian F. Miller, Neutrality and the Evolvability of Boolean Function Landscape, Proceedings of the 4th European Conference on Genetic Programming, p.204-217, April 18-20, 2001
• 14: Tina Yu , Julian F. Miller, Finding Needles in Haystacks Is Not Hard with Neutrality, Proceedings of the 5th European Conference on Genetic Programming, p.13-25, April 03-05, 2002
• 15: T. Yu and J. F. Miller. The role of neutral and adaptive mutation in an evolutionary search on the onemax problem. In E. Cantú-Paz, editor, Late Breaking Papers at the Genetic and Evolutionary Computation Conference (GECCO-2002) pages 512--519, New York, NY, July 2002. AAAI.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

General Terms:
Algorithms

Keywords:
genetic algorithms, neutrality, search space