Monotonic solution concepts in coevolution

ABSTRACT

Assume a coevolutionary algorithm capable of storing and utilizing all phenotypes discovered during its operation, for as long as it operates on a problem; that is, assume an algorithm with a monotonically increasing knowledge of the search space. We ask: If such an algorithm were to periodically report, over the course of its operation, the best solution found so far, would the quality of the solution reported by the algorithm improve monotonically over time? To answer this question, we construct a simple preference relation to reason about the goodness of different individual and composite phenotypic behaviors. We then show that whether the solutions reported by the coevolutionary algorithm improve monotonically with respect to this preference relation depends upon the solution concept implemented by the algorithm. We show that the solution concept implemented by the conventional coevolutionary algorithm does not guarantee monotonic improvement; in contrast, the game-theoretic solution concept of Nash equilibrium does guarantee monotonic improvement. Thus, this paper considers 1) whether global and objective metrics of goodness can be applied to coevolutionary problem domains (possibly with open-ended search spaces), and 2) whether coevolutionary algorithms can, in principle, optimize with respect to such metrics and find solutions to games of strategy.

REFERENCES

• 1: C. Adami. What is complexity? BioEssays, 24(12):1085--1094, 2002.
• 2: Peter J. Angeline , Jordan B. Pollack, Competitive Environments Evolve Better Solutions for Complex Tasks, Proceedings of the 5th International Conference on Genetic Algorithms, p.264-270, June 01, 1993
• 3: James P. Crutchfield, The calculi of emergence: computation, dynamics and induction, Physica D, v.75 n.1-3, p.11-54, Aug. 1, 1994
• 4: P. Darwen and X. Yao. Automatic modularization by speciation. In T. Fukuda et al., editors, Proc. of the 1996 IEEE International Conference on Evolutionary Computation, pages 88--93. IEEE Press, 1996.
• 5: E. D. de Jong. The incremental pareto-coevolution archive. In K. Deb et al., editors, Proc. 2004 Genetic and Evolutionary Computation Conference, LNCS 3102, pages 525--536. Springer, 2004.
• 6: Edwin de Jong, The MaxSolve algorithm for coevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068091]
• 7: K. A. De Jong. Are genetic algorithms function optimizers? In R. Männer and B. Manderick, editors, Parallel Problem Solving from Nature II, pages 3--13. Elsevier, 1992.
• 8: K. A. De Jong. Genetic algorithms are NOT function optimizers. In L. D. Whitely, editor, Foundations of Genetic Algorithms 2 (FOGA), pages 5--18. Morgan Kaufmann, 1993.
• 9: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, 2004
• 10: S. G. Ficici and J. B. Pollack. A game-theoretic memory mechanism for coevolution. In Cantú-Paz et al., editors, 2003 Genetic and Evolutionary Computation Conference, pages 286--297. Springer, 2003.
• 11: C. M. Fonseca and P. J. Fleming. An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3(1):1--16, 1995.
• 12: W. Fontana. Algorithmic chemistry. In Langton et al. {18}, pages 159--209.
• 13: H. Freund and R. Wolter. Evolution of bit strings: Some preliminary results. Complex Systems, 5:279--298, 1991.
• 14: Inman Harvey, Cognition is Not Computation; Evolution is Not Optimisation, Proceedings of the 7th International Conference on Artificial Neural Networks, p.685-690, October 08-10, 1997
• 15: T. Hashimoto and T. Ikegami. Emergence of net-grammar in communicating agents. BioSystems, 38(1):1--14, 1996.
• 16: Takashi Ikegami, From genetic evolution to emergence of game strategies, Physica D, v.75 n.1-3, p.310-327, Aug. 1, 1994
• 17: J. F. Kolen and J. B. Pollack. The observer's paradox: Apparent computational complexity in physical systems. Journal of Experimental and Theoretical Artificial Intelligence, 7:253--277, 1995.
• 18: Christopher G. Langton , Charles Taylor , Doyne Farmer , Steen Rasmussen, Artificial Life II, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 19: R. E. Lenski, C. Ofria, T. C. Collier, and C. Adami. Genome complexity, robustness and genetic interactions in digital organisms. Nature, 400:661--664, August 1999.
• 20: K. Lindgren. Evolutionary phenomena in simple dynamics. In Langton et al. {18}, pages 295--312.
• 21: S. Luke and R. P. Wiegand. When coevolutionary algorithms exhibit evolutionary dynamics. In A. Barry, editor, 2002 Genetic and Evolutionary Computation Conference Workshop Program, pages 236--241, 2002.
• 22: J. Maynard-Smith. Evolution and the Theory of Games. Cambridge University Press, 1982.
• 23: Stefano Nolfi , Dario Floreano, Coevolving Predator and Prey Robots: Do "Arms Races" Arise in Artificial Evolution?, Artificial Life, v.4 n.4, p.311-335, October 1998 [doi>10.1162/106454698568620]
• 24: 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]
• 25: Thomas S. Ray, Evolution, complexity, entropy and artificial reality, Physica D, v.75 n.1-3, p.239-263, Aug. 1, 1994
• 26: Christopher D. Rosin , Richard K. Belew, A competitive approach to game learning, Proceedings of the ninth annual conference on Computational learning theory, p.292-302, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238153]
• 27: L. M. Schmitt. Theory of coevolutionary genetic algorithms. In M. Guo and L. T. Yang, editors, Int. Symp. on Parallel and Distributed Processing and Applications, volume 2745 of LNCS, pages 285--293. Springer, 2003.
• 28: K. Sims. Evolving 3d morphology and behavior by competition. In R. A. Brooks and P. Maes, editors, Artificial Life IV, pages 28--39. MIT Press, 1994.
• 29: Tim Taylor, Creativity in evolution: individuals, interactions, and environments, Creative evolutionary systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 30: L. van Valen. A new evolutionary law. Evolutionary Theory, 1:1--30, 1973.
• 31: R. A. Watson and J. B. Pollack. Coevolutionary dynamics in a minimal substrate. In L. Spector et al., editors, Proc. of the 2001 Genetic and Evolutionary Computation Conference, pages 702--709, 2001.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Theory

Keywords:
coevolution, monotonic progress, solution concepts