Competitive Coevolution through Evolutionary Complexification

By Kenneth O. Stanley, Risto Miikkulainen. 2011

520 citations recorded by the source corpus.

Two major goals in machine learning are the discovery and improvement of solutions to complex problems. In this paper, we argue that complexification, i.e. the incremental elaboration of solutions through adding new structure, achieves both these goals. We demonstrate the power of complexification through the NeuroEvolution of Augmenting Topologies (NEAT) method, which evolves increasingly complex neural network architectures. NEAT is applied to an open-ended coevolutionary robot duel domain where robot controllers compete head to head. Because the robot duel domain supports a wide range of strategies, and because coevolution benefits from an escalating arms race, it serves as a suitable testbed for studying complexification. When compared to the evolution of networks with fixed structure, complexifying evolution discovers significantly more sophisticated strategies. The results suggest that in order to discover and improve complex solutions, evolution, and search in general, should be allowed to complexify as well as optimize.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Kenneth O. Stanley
2. Shimon Whiteson
3. Sergey Levine
4. Sebastian Risi
5. J. Urgen Schmidhuber
6. Jeff Clune
7. Pieter Abbeel
8. Joel Lehman

Citations in the corpus

• Emergent Tool Use From Multi-Agent Autocurricula (2019, background): “Early work explored self-play using genetic algorithms [16, 17, 18, 19].”
• Emergent Complexity via Multi-Agent Competition (2017, background): “Stanley and Miikkulainen [2004] trained agents in a competitive 2D world, using evolutionary strategies to evolve both weights and structure of policies with competition as a fitness measure.”
• Growing Action Spaces (2019, background): “Stanley & Miikkulainen (2004) study continual complexification in the context of coevolution, growing the complexity of neural network architectures through the course of training.”
• Real-time neuroevolution in the NERO video game (2005, methodology): “Using such techniques, relatively simple ANN controllers can be trained in games and game-like environments to produce convincing purposeful and intelligent behavior [5], [11], [36], [40], [65]–[67].”
• Evolvability Search: Directly Selecting for Evolvability in order to Study and Produce It (2016, methodology): “Note that this section only briefly reviews NEAT; for further details see [32,33].”
• Discovering Gated Recurrent Neural Network Architectures (2018, methodology): “NEAT is a neuroevolution method that has been successful in solving sequential decision making tasks (Stanley and Miikkulainen (2002; 2004), Lehman and Miikkulainen (2014)).”
• Neuroevolution (2010, background): “Networks can also be evolved through coevolution [4, 18].”
• Generative NeuroEvolution for Deep Learning (2013, methodology): “…(NEAT) algorithm [17] is a popular neuroevolutionary approach that has been proven in a variety of challenging tasks, including particle physics [18, 19], simulated car racing [20], RoboCup Keep-away [21], function approximation [22], and real-time agent evolution [23], among others [17].”
• On the deleterious effects of a priori objectives on evolution and representation (2011, background): “Furthermore, although there may be better algorithms, NEAT generally has a good record in a variety of domains [24, 25, 27], diminishing the possible argument that it is a kind of straw man chosen for its weaknesses.”
• Ieee Transactions on Evolutionary Computation on the Performance of Indirect Encoding across the Continuum of Regularity (unknown): “The NEAT algorithm contains three major components [25], [26].”
• Evolving plastic neural networks with novelty search (2010, methodology): “Complete descriptions of the NEAT method, including experiments confirming the contributions of its components, are available in Stanley and Miikkulainen (2002, 2004) and Stanley et al. (2005).”
• Single-unit pattern generators for quadruped locomotion (2013, methodology): “A full description of NEAT is available in Stanley and Miikkulainen [31] or Stanley and Miikkulainen [33].”
• Evolution of Cartesian Genetic Programs for Development of Learning Neural Architecture (2011, background): “Stanley and Miikkulainen’s approach to achieve complexification is through the incremental elaboration of solutions by adding new neural structures (Stanley and Miikkulainen, 2002; Stanley and Miikkulainen, 2004).”