Coevolution of neural networks using a layered pareto archive

ABSTRACT

The Layered Pareto Coevolution Archive (LAPCA) was recently proposed as an effective Coevolutionary Memory (CM) which, under certain assumptions, approximates monotonic progress in coevolution. In this paper, a technique is developed that interfaces the LAPCA algorithm with NeuroEvolution of Augmenting Topologies (NEAT), a method to evolve neural networks with demonstrated efficiency in game playing domains. In addition, the behavior of LAPCA is analyzed for the first time in a complex game-playing domain: evolving neural network controllers for the game Pong. The technique is shown to keep the total number of evaluations in the order of those required by NEAT, making it applicable to complex domains. Pong players evolved with a LAPCA and with the Hall of Fame (HOF) perform equally well, but the LAPCA is shown to require significantly less space than the HOF. Therefore, combining NEAT and LAPCA is found to be an effective approach to coevolution.

REFERENCES

• 1: Bucci, A. & Pollack, J. B. (2002). A mathematical framework for the study of coevolution. Foundations of Genetic Algorithms 7, Proceedings of FOGA VII, 221--236.
• 2: Dave Cliff , Geoffrey F. Miller, Tracking the Red Queen: Measurements of Adaptive Progress in Co-Evolutionary Simulations, Proceedings of the Third European Conference on Advances in Artificial Life, p.200-218, June 04-06, 1995
• 3: Paul R. Cohen, Empirical methods for artificial intelligence, MIT Press, Cambridge, MA, 1995
• 4: De Jong, E. D. (2004). The incremental Pareto-coevolution archive. Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-04, 525--536.
• 5: De Jong, E. D. (2004). Towards a bounded Pareto-coevolution archive. Proceedings of the Congress on Evolutionary Computation CEC-04, 2341--2348.
• 6: De Jong, E. D., & Pollack, J. B. (2003). Learning the ideal evaluation function. Proceedings of the 2003 Genetic and Evolutionary Computation Conference, 277--288.
• 7: Edwin D. De Jong , Jordan B. Pollack, Ideal Evaluation from Coevolution, Evolutionary Computation, v.12 n.2, p.159-192, June 2004 [doi>10.1162/106365604773955139]
• 8: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, 2004
• 9: Sevan G. Ficici , Jordan B. Pollack, A Game-Theoretic Approach to the Simple Coevolutionary Algorithm, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.467-476, September 18-20, 2000
• 10: Ficici, S. G., & Pollack, J. B. (2003). A game-theoretic memory mechanism for coevolution. Proceedings of the 2003 Genetic and Evolutionary Computation Conference, 286--297.
• 11: Floreano, D., & Nolfi, S. (1997). God save the Red Queen! Competition in co-evolutionary robotics. Genetic Programming 1997: Proceedings of the Second Annual Conference, 398--406.
• 12: Noble, J., & Watson, R. A. (2001). Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for Pareto selection. Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, 493--500.
• 13: Poppleton, T. (2002). Can co-evolution play ball? Competitive co-evolution in a Pong game. Unpublished master's thesis, University of Sussex, UK. Retrieved August 6, 2005, from http://www.informatics.susx.ac.uk/easy/Publications/Online/MSc2002/ajp25.pdf
• 14: Rosin, C. D., & Belew, R. K. (1997). New methods for competitive evolution. Evolutionary Computation, 5, 1--29.
• 15: Stanley, K., Bryant, B. D., & Miikkulainen, R. (2005). Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation, 9(6), 653--668.
• 16: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 17: Stanley, K. O., & Miikkulainen, R. (2002). Efficient evolution of neural network topologies. Proceedings of the 2002 Congress on Evolutionary Computation (CEC '02), 2, 1757--1762.
• 18: Kenneth O. Stanley , Risto Miikkulainen, Efficient Reinforcement Learning Through Evolving Neural Network Topologies, Proceedings of the Genetic and Evolutionary Computation Conference, p.569-577, July 09-13, 2002
• 19: Kenneth O. Stanley , Risto Miikkulainen, Continual Coevolution Through Complexification, Proceedings of the Genetic and Evolutionary Computation Conference, p.113-120, July 09-13, 2002
• 20: Stanley, K. O., & Miikkulainen, R. (2003). Achieving high-level functionality through Complexification. Proceedings of the AAAI-2003 Spring Symposium on Computational Synthesis, 226--232.
• 21: Stanley, K. O., & Miikkulainen, R. (2004). Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21, 63--100.
• 22: Richard A. Watson , Jordan B. Pollack, Symbiotic Combination as an Alternative to Sexual Recombination in Genetic Algorithms, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.425-434, September 18-20, 2000
• 23: Winter, D. (2005). Magnavox Odyssey: First home video game console. Retrieved August 6, 2005, from http://www.pong-story.com/odyssey.htm

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

General Terms:
Algorithms, Experimentation, Theory

Keywords:
coevolution, hall of fame, layered pareto coevolution archive, neural networks, neuroevolution of augmenting topologies, pong