Comparing genetic robustness in generational vs. steady state evolutionary algorithms

ABSTRACT

Previous research has shown that evolutionary systems not only try to develop solutions that satisfy a fitness requirement, but indirectly attempt to develop genetically robust solutions as well -solutions where average loss of fitness due to crossover and other genetic variation operators is minimized. It has been shown that in a simple "two peaks" problem, where the fitness landscape consists of a broad, low peak, and a narrow, high peak, individuals initially converge on the lower (less fit), but broader peak, and that increasing an individual's genetic robustness through growth is a necessary prerequisite for convergence on the higher, narrower peak 18. If growth is restricted, the population remains converged on the less fit solution. We tested whether this result holds true only for generational algorithms, or whether it applies to steady state algorithms as well. We conclude that although growth occurs with both algorithms, the steady state algorithm is able to converge on the higher peak without this growth. This result shows that the role of genetic robustness in the evolutionary process is significantly different in generational versus steady state algorithms.

REFERENCES

• 1: Blickle, T., and Thiele, L. Genetic Programming and Redundancy. In Genetic Algorithms within the Framework of Evolutionary Computation. Max-Planck-Institut fur Informatik, Saarbrucken, Germany, 1994, 33--38.
• 2: DeVisser, A. G. M., Hermission, J., Wager, G., Meyers, L. A., Bagheri-ChaiChain, H., Blanchard, J. L., Chao, L., Cheverud, J. M., Elena, S. F., Fontana, W., Gibson, G., Hansen, T. F., Krakauer, D., Lewontin, R. C., Ofria, C., Rice, S. H., von Dassow, G., and Wagner, A. Perspective: Evolution and Detection of Genetic Robustness. Evolution, 57, 2003, 1959--1972.
• 3: Jeffrey A. Edlund , Christoph Adami, Evolution of robustness in digital organisms, Artificial Life, v.10 n.2, p.167-179, April 2004 [doi>10.1162/106454604773563595]
• 4: Hogeweg, P., and Hesper, B. Evolutionary Dynamics and the Coding Structure of Sequences: Multiple Coding as a Consequence of Crossover and High Mutation Rates. Computers and Chemistry, 16, 1992, 171--182.
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: Krackauer, D. C., Plotkin, J. B. Redundnacy, antiredundancy, and the robustness of genomes. PNAS, 99 (2002), 1405--1409.
• 7: Langdon, W. Fitness Causes Bloat: Simulated Annealing, Hill Climbing and Populations. Technical Report CSRP-97-22, University of Birmingham, Birmingham, UK, 1997.
• 8: Langdon, W., and Poli, R. Fitness Causes Bloat. In Second On-line World Conference on Soft Computing in Engineering Design and Manufacturing, Springer-Verlag, London, 1997, 13--22.
• 9: William B. Langdon , Riccardo Poli, Fitness Causes Bloat: Mutation, Proceedings of the First European Workshop on Genetic Programming, p.37-48, April 14-15, 1998
• 10: William B. Langdon , Tery Soule , Riccardo Poli , James A. Foster, The evolution of size and shape, Advances in genetic programming: volume 3, MIT Press, Cambridge, MA, 1999
• 11: Nicholas Freitag McPhee , Justin Darwin Miller, Accurate Replication in Genetic Programming, Proceedings of the 6th International Conference on Genetic Algorithms, p.303-309, July 15-19, 1995
• 12: Peter Nordin , Wolfgang Banzhaf, Complexity Compression and Evolution, Proceedings of the 6th International Conference on Genetic Algorithms, p.310-317, July 15-19, 1995
• 13: Peter Norin , Wolfgang Banzahf , Frank D. Francone, Introns in Nature and in Simulated Structure Evolution, Biocomputing and emergent computation: Proceedings of BCEC97, p.22-35, January 1997
• 14: Smith, P., and Harries, K. Code Growth, Explicitly Defined Introns, and Alternative Selection Schemes. Evolutionary Computation, 6, 4 (1998), 339--360
• 15: Terence Soule, Exons and Code Growth in Genetic Programming, Proceedings of the 5th European Conference on Genetic Programming, p.142-151, April 03-05, 2002
• 16: Soule, T. Operator Choice and the Evolution of Robust Solutions. In Genetic Programming Theory and Practice, Riolo R., and Worzel, B., 2003, 257--270.
• 17: Terence Soule, Resilient Individuals Improve Evolutionary Search, Artificial Life, v.12 n.1, p.17-34, January 2006 [doi>10.1162/106454606775186437]
• 18: Soule, T., Foster, J., and Dickinson, J. Code Growth in Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference. MIT Press, Cambridge, MA, 1996, 215--223.
• 19: Soule, T., Heckendorn, R., and Shen, J. Solution Stability in Evolutonary Computation. In Proceedings of the 17th International Symposium on Computer and Information Systems, 2002, 237--241.
• 20: Wilke, C. Selection for Fitness versus Selection for Robustness in RNA Secondary Structure Folding. Evolution, 55 (2001), 2412--2420.
• 21: Wilke, C., Wang, J. L., Ofria, C, Lenski, R. E., and Adami, C. Evolution of digital organisms at high mutation rates leads to survival of the flattest. Nature, 412 (2001), 331--33.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
generational, genetic robustness, growth, resiliency, steady-state