Selection for group-level efficiency leads to self-regulation of population size

ABSTRACT

In general, a population will grow until a limiting factor, such as resource availability, is reached. However, increased task efficiency can also regulate the size of a population during task development. Through the use of digital evolution, we demonstrate that the evolution of a group-level task, requiring a small number of individuals, can cause a population to self-regulate its size, even in the presence of abundant energy. We also show that as little as a 1% transfer of energy from a parent group to its offspring produces significantly better results than no energy transfer. A potential application of this result is the configuration and management of real-world distributed agent-based systems.

REFERENCES

• 1: Christoph Adami, Introduction to artificial life, Springer-Verlag New York, Inc., New York, NY, 1999
• 2: C. Adami, C. A. Ofria, and T. C. Collier. Evolution of biological complexity. Proceedings of the National Academy of Sciences, 97(9):4463--4468, April 2000.
• 3: J. Arabas, Z. Michalewicz, and J. J. Mulawka. Gavaps - a genetic algorithm with varying population size. In International Conference on Evolutionary Computation, pages 73--78, 1994.
• 4: M. Bakhouya , J. Gaber, Adaptive Approach for the Regulation of a Mobile Agent Population in a Distributed Network, Proceedings of the Proceedings of The Fifth International Symposium on Parallel and Distributed Computing, p.360-366, July 06-09, 2006 [doi>10.1109/ISPDC.2006.6]
• 5: A. Bieszczad, T. White, and B. Pagurek. Mobile agents for network management. IEEE Communications Surveys, 1998.
• 6: M. Dorigo. Swarmanoid project. http://www.swarmanoid.org, January 2008.
• 7: H. Eskandari, C. D. Geiger, and G. B. Lamont. FastPGA: A dynamic population sizing approach forsolving expensive multiob jective optimization problems. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization, volume 4403 of Lecture Notes in Computer Science, pages 141--155. Springer, 2006.
• 8: C. Fernandes and A. C. Rosa. Self-regulated population size in evolutionary algorithms. In PPSN, volume 4193 of Lecture Notes in Computer Science, pages 920--929. Springer, 2006.
• 9: D. Floreano, S. Mitri, S. Magnenat, and L. Keller. Evolutionary conditions for the emergence of communication in robots. Current Biology, 17:514--519, March 2007.
• 10: D. Floreano and F. Mondada. Evolution of Homing Navigation in a Real Mobile Robot. IEEE Transactions on Systems, Man and Cybernetics Part B : Cybernetics, 26(3):396--407, 1996.
• 11: Chien-Liang Fok , Gruia-Catalin Roman , Chenyang Lu, Rapid Development and Flexible Deployment of Adaptive Wireless Sensor Network Applications, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.653-662, June 06-10, 2005 [doi>10.1109/ICDCS.2005.63]
• 12: Matthew Glickman , Justin Balthrop , Stephanie Forrest, A Machine Learning Evaluation of an Artificial Immune System, Evolutionary Computation, v.13 n.2, p.179-212, June 2005 [doi>10.1162/1063656054088503]
• 13: Steven A. Hofmeyr , Stephanie A. Forrest, Architecture for an Artificial Immune System, Evolutionary Computation, v.8 n.4, p.443-473, December 2000 [doi>10.1162/106365600568257]
• 14: Jeffrey O. Kephart , David M. Chess, The Vision of Autonomic Computing, Computer, v.36 n.1, p.41-50, January 2003 [doi>10.1109/MC.2003.1160055]
• 15: R. E. Lenki, C. A. Ofria, T. C. Collier, and C. Adami. Genome complexity, robustness and genetic interactions in digital organisms. Nature, 400:661--664, 1999.
• 16: R. E. Lenski, C. Ofria, R. T. Pennock, and C. Adami. The evolutionary origin of complex features. Nature, 423:139--144, 2003.
• 17: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 18: Geoffrey Mainland , David C. Parkes , Matt Welsh, Decentralized, adaptive resource allocation for sensor networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.315-328, May 02-04, 2005
• 19: G. McHale and P. Husbands. Incorporating energy expenditure into evolutionary robotics fitness measures. In Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems, pages 206 -- 212, Cambridge, MA, USA, 2006. MIT Press.
• 20: 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]
• 21: 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]
• 22: Jim Pugh , Alcherio Martinoli, Multi-robot learning with particle swarm optimization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160715]
• 23: Transparent Self-Optimization in Existing CORBA Applications, Proceedings of the First International Conference on Autonomic Computing, p.88-95, May 17-18, 2004
• 24: Gyula Simon , Miklós Maróti , Ákos Lédeczi , György Balogh , Branislav Kusy , András Nádas , Gábor Pap , János Sallai , Ken Frampton, Sensor network-based countersniper system, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031497]
• 25: A. C. Society. Global cancer facts & figures, 2007.
• 26: Walt Truszkowski , Mike Hinchey , James Rash , Christopher Rouff, NASA's Swarm Missions: The Challenge of Building Autonomous Software, IT Professional, v.6 n.5, p.47-52, September 2004 [doi>10.1109/MITP.2004.66]
• 27: Elio Tuci , Roderich Groß , Vito Trianni , Francesco Mondada , Michael Bonani , Marco Dorigo, Cooperation through self-assembly in multi-robot systems, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.1 n.2, p.115-150, December 2006 [doi>10.1145/1186778.1186779]
• 28: Tony White , Bernard Pagurek , Dwight Deugo, Management of Mobile Agent Systems using Social Insect Metaphors, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.410, October 13-16, 2002
• 29: C. O. Wilke, J. Wang, C. A. Ofria, C. Adami, and R. E. Lenki. Evolution of digital organisms at high mutation rate leads to survival of the flattest. Nature, 412:331--333, 2001.
• 30: D. S. Wilson. Introduction: Multilevel selection theory comes of age. The American Naturalist, 150(S1-S4), July 1997.

INDEX TERMS

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

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

General Terms:
Experimentation

Keywords:
artificial life, cooperative behavior, digital evolution, multi-agent systems, selection, self-regulation