Cooperative network construction using digital germlines

ABSTRACT

This paper describes a study in the evolution of cooperative behavior, specifically the construction of communication networks, through digital evolution and multilevel selection. In digital evolution, a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. Multilevel selection links the survival of the individual to the survival of its group, thus encouraging cooperation. The results of experiments using the Avida digital evolution platform demonstrate that populations of digital organisms are capable of constructing communication networks, and that these networks can exhibit desired properties depending on the selective pressures used. We also show that the use of a digital germline can significantly improve evolvability of cooperation.

REFERENCES

• 1: C. Adami, C. Ofria, and T. C. Collier. Evolution of biological complexity. Proc Natl Acad Sci USA, 97:4463--4468, 2000.
• 2: R. M. Axelrod. The Evolution of Cooperation. Basic Books, 1984.
• 3: J. Clune, C. Ofria, and R. T. Pennock. Investigating the emergence of phenotypic plasticity in evolving digital organisms. In European Conference on Artificial Life (ECAL), pages 74--83, 2007.
• 4: M. E. Davey and G. A. O'Toole. Microbial biofilms: from ecology to molecular genetics. Microbiology and Molecular Biology Reviews, 64(4):847--867, 2000.
• 5: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 6: Marco Dorigo , Vito Trianni , Erol Şahin , Roderich Groß , Thomas H. Labella , Gianluca Baldassarre , Stefano Nolfi , Jean-Louis Deneubourg , Francesco Mondada , Dario Floreano , Luca M. Gambardella, Evolving Self-Organizing Behaviors for a Swarm-Bot, Autonomous Robots, v.17 n.2-3, p.223-245, September-November 2004 [doi>10.1023/B:AURO.0000033973.24945.f3]
• 7: E. Eddy. The germ line and development. Developmental Genetics, 19:287--289, 1996.
• 8: D. S. Wilson. Altruism and organism: Disentangling the themes of multilevel selection theory. The American Naturalist, 150:S122--S134, 1997.
• 9: Oliver Giel , Per Kristian Lehre, On the effect of populations in evolutionary multi-objective optimization, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144114]
• 10: H. J. Goldsby, B. H. C. Cheng, P. K. McKinley, D. B. Knoester, and C. Ofria. Digital evolution of behavioral models for autonomic systems. In Proceedings of the International Conference on Autonomic Computing (ICAC), 2008.
• 11: D. Grimaldi and M. S. Engel. Evolution of the Insects. Cambridge University Press, 2005.
• 12: M. Jelasity and O. Babaoglu. T-man: Gossip-based overlay topology management. In Proceedings of the Workshop on Engineering Self-Organising Applications (ESOA), 2005.
• 13: R. E. Lenski, C. Ofria, R. T. Pennock, and C. Adami. The evolutionary origin of complex features. Nature, 423:139--144, 2003.
• 14: Philip McKinley , Betty H. C. Cheng , Charles Ofria , David Knoester , Benjamin Beckmann , Heather Goldsby, Harnessing Digital Evolution, Computer, v.41 n.1, p.54-63, January 2008 [doi>10.1109/MC.2008.17]
• 15: R. Michod. On the transfer of fitness from the cell to the multicellular organism. Biology and Philosophy, 20(5):967--987, 2005.
• 16: M. A. Nowak. Five rules for the evolution of cooperation. Science, 314(5805):1560--1563, 2006.
• 17: C. Ofria and C. Adami. Evolution of genetic organization in digital organisms. In Proceedings of DIMACS Workshop on Evolution as Computation, 1999.
• 18: Charles Ofria , Claus O. Wilke, Avida: a software platform for research in computational evolutionary biology, Artificial Life, v.10 n.2, p.191-229, April 2004 [doi>10.1162/106454604773563612]
• 19: J. C. Scholz and M. O. W. Greiner. Topology control with IPD network creation games. New J. Phys., 9(185), 2007.
• 20: T. D. Seeley. Honey bee colonies are group-level adaptive units. The American Naturalist, 150:S22--S41, 1997.
• 21: G. Werner and M. Dyer. Evolution of communication in artificial organisms. In Artificial Life II, pages 659--687. Addison-Wesley Pub., 1992.
• 22: D. Floreano, S. Mitri, S. Magnenat, and L. Keller. Evolutionary conditions for the emergence of communication in robots. Current Biology, 17(6):514--519, 2007.
• 23: L. Yamamoto and C. F. Tschudin. Experiments on the automatic evolution of protocols using genetic programming. In Proceedings of the IFIP Workshop on Autonomic Communication (WAC), 2005.
• 24: Emily M. Zechman , S. Ranji Ranjithan, Multipopulation cooperative coevolutionary programming (MCCP) to enhance design innovation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068286]
• 25: M. G. Zimmermann and V. M. Eguiluz. Cooperation, social networks, and the emergence of leadership in a prisoner's dilemma with adaptive local interactions. Physical Review E, 72(5), 2005.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

General Terms:
Experimentation

Keywords:
biologically-inspired computing, cooperative behavior, digital evolution, germline, multilevel selection, mutation, natural selection