Problem decomposition using indirect reciprocity in evolved populations

ABSTRACT

Evolutionary problem decomposition techniques divide a complex problem into simpler subproblems, evolve individuals to produce subcomponents that solve the subproblems, and then assemble the subcomponents to produce an overall solution. Ideally, these techniques would automatically decompose the problem and dynamically assemble the subcomponents to form the solution. However, although significant progress in automated problem decomposition has been made, most techniques explicitly assemble the complete solution as part of the fitness function. In this paper, we propose a digital-evolution technique that lays the groundwork for enabling individuals within the population to dynamically decompose a problem and assemble a solution. Specifically, our approach evolves specialists that produce some subcomponents of a problem, cooperate with others to receive different subcomponents, and then assemble the subcomponents to produce an overall solution. We first establish that this technique is able to evolve specialists that cooperate. We then demonstrate that it is more effective to use a generalist strategy, wherein organisms solve the entire problem themselves, on simple problems, but that a specialist strategy is better on complex problems. Finally, we show that our technique automatically selects a generalist or specialist strategy based on the complexity of the problem.

REFERENCES

• 1: J. Clune, H. J. Goldsby, C. Ofria, and R. T. Pennock. Digital evolution confirms and informs the inclusive fitness theory prediction that selection favors increasingly accurate altruism targeting mechanisms. In preparation.
• 2: Tim F. Cooper , Charles Ofria, Evolution of stable ecosystems in populations of digital organisms, Proceedings of the eighth international conference on Artificial life, p.227-232, December 09-13, 2002
• 3: D. Cornforth and M. Kirley. Cooperative problem solving using an agent-based market. In Genetic and evolutionary computation conference (GECCO), pages 60--71, Seattle, Washington, 2004.
• 4: Marco Dorigo , Marco Colombetti, Robot Shaping: An Experiment in Behavior Engineering, MIT Press, Cambridge, MA, 1997
• 5: S. Goings, J. Clune, C. Ofria, and R. T. Pennock. Kin-selection: The rise and fall of kin-cheaters. In Ninth International Conference on Artificial Life, pages 303--308, Boston, MA, 2004.
• 6: S. Goings and C. Ofria. Ecological approaches to diversity maintenance in evolutionary algorithms. In IEEE Symposium on Artificial Life, Nashville, TN, 2009.
• 7: Faustino J. Gomez , Risto Miikkulainen, Solving Non-Markovian Control Tasks with Neuro-Evolution, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1356-1361, July 31-August 06, 1999
• 8: R. E. Lenski, C. Ofria, T. C. Collier, and C. Adami. Genome complexity, robustness, and genetic interactions in digital organisms. In Nature, volume 400, pages 661--664, 1999.
• 9: R. E. Lenski, C. Ofria, R. T. Pennock, and C. Adami. The evolutionary origin of complex features. In Nature, volume 423, pages 139--144, 2003.
• 10: Peter Lichodzijewski , Malcolm I. Heywood, Managing team-based problem solving with symbiotic bid-based genetic programming, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389162]
• 11: M. A. Nowak. Five rules for the evolution of cooperation. Science, 314(5805):1560--1563, December 2006.
• 12: C. Ofria and C. Adami. Evolution of genetic organization in digital organisms. In Proc. of DIMACS workshop Evolution as Computation, pages 167--175, Princeton, NJ, 1999.
• 13: C. Ofria, C. Adami, and T. C. Collier. Design of evolvable computer languages. IEEE Transactions in Evolutionary Computation, 6:420--424, 2002.
• 14: 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]
• 15: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 16: R. Sugden. The economics of rights, co-operation and welfare. Oxford: Basil Blackwell, 1986.
• 17: R. Sun and D. Qi. Marlbs: Team cooperation through bidding. In International Journal of Computational Intelligence Research, 2005.
• 18: C. O. Wilke, J. L. Wang, C. Ofria, C. Adami, and R. E. Lenski. Evolution of digital organisms at high mutation rate leads to survival of the flattest. In Nature, volume 412, pages 331--333, 2001.
• 19: Chern H Yong , Risto Miikkulainen, COOPERATIVE COEVOLUTION OF MULTI-AGENT SYSTEMS, University of Texas at Austin, Austin, TX, 2001

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)

General Terms:
Experimentation

Keywords:
altruism, binary string cover problem, digital evolution, evolution of cooperation