A study of mutational robustness as the product of evolutionary computation

ABSTRACT

This paper investigates the ability of a tournament selection based genetic algorithm to find mutationally robust solutions to a simple combinatorial optimization problem. Two distinct algorithms (a stochastic hill climber and a tournament selection based GA) were used to search for optimal walks in several variants of the self avoiding walk problem. The robustness of the solutions obtained by the algorithms were compared, both with each other and with solutions obtained by a random sampling of the optimal solution space. The solutions found by the GA were, for most of the problem variants, significantly more robust than those found by either the hill climbing algorithm or random sampling. The solutions found by the hill climbing algorithm were often significantly less robust than those obtained through random sampling. .

REFERENCES

• 1: Thomas Back , David B. Fogel , Zbigniew Michalewicz, Handbook of Evolutionary Computation, IOP Publishing Ltd., Bristol, UK, 1997
• 2: K.M. Bryden, D. Ashlock, S. Corns, and S. Willson. Graph based evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 2006.
• 3: Seth Bullock, Will selection for mutational robustness significantly retard evolutionary innovation on neutral networks?, Proceedings of the eighth international conference on Artificial life, p.192-201, December 09-13, 2002
• 4: S. Corns, D. Ashlock, D. McCorkle, and K. Bryden. Improving design diversity using graph based evolutionary algorithms. In Proceedings of the 2006 Congress on Evolutionary Computation, pages 1037--1043. IEEE Press, 2006.
• 5: J. Edwards and B. O. Palsson. Robustness analysis of the escherichia coli metabolic netowrk. Biotechnology Progress, 16:927--939, 2000.
• 6: D. Keymeulen, R.Zebulum, Y.Jin, and A.Stoica. Fault-tolerant evolvable hardware using field-programmable transistor arrays. IEEE Transtractions on Reliability, 49:305--316, 2000.
• 7: M. A. Marra, B. E. Boling, and B. L. Walcott. Stability analysis of genetic algorithm controllers. In Conference Proceedings of IEEE Southeastcon 96, volume 1. IEEE Press, 1996.
• 8: J. Schonfeld and D. Ashlock. Comparison of robustness of solutions located by evolutionary computation and other search algorithms. Proceedings of the 2004 Congress on Evolutionary Computation, volume 1, pages 250--257. IEEE Press, 2004.
• 9: Justin Schonfeld , Daniel Ashlock, A study of evolutionary robustness in stochastically tiled polyominos, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068013]
• 10: D. Taverna and R.A. Goldstein. The distribution of structures in evolving protein populations. Biopolymers, 53:1--8, 2000.
• 11: G.L. Urban, K.M. Bryden, and D. A. Ashlock. Engineering optimization of an improved plancha stove. Energy for Sustainable Development, 6(2):9--19, 2001.
• 12: E. van Nimwegen, J. P. Crutchfeld, and M. Huynen. Neutral evolution of mutational robustness. In Proceedings of the National Academy of Sciences of the United States of America 1999, volume 96, pages 9716--9720, 1999.
• 13: A. Wagner. Robustness and Evolvability in Living Systems:(Princeton Studies in Complexity). Princeton University Press, 2005.
• 14: A.Wagner. Robustness, neutrality, and evolvability. FEBS Letters, 579:1772--1778, 2005.
• 15: C. O. Wilke, J. L. Wang, C. Ofria, R. E. Lenski, and C. Adami. Evolution of digital organisms at high mutation rate leads to survival of the flattest. Nature, 412: 331--333, 2001.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
genetic algorithms, robustness, self avoiding walk, tournament selection