PaperlayerView exact revision on arXiv

Source-linked AI summary

Competitive Coevolution through Evolutionary Complexification

R. Miikkulainen, K. O. Stanley

arXiv:1107.0037v1cs.AI

TL;DR

Discovering and improving solutions to complex problems requires search methods that can handle evolving structure. The paper evaluates NEAT’s complexifying evolution in coevolutionary robot duels and finds it produces more sophisticated strategies than fixed-topology evolution.

  • Problem

    The paper addresses how evolutionary search can discover and improve solutions whose useful structures may require an indefinite number of parameters.

  • Method

    NEAT evolves increasingly complex neural-network topologies by retaining useful structural innovations identified through fitness evaluation.

  • Results

    91.4% performance for complexifying coevolution exceeded the 40.4% average for fixed-topology coevolution.

  • Takeaways & Limitations

    Evolutionary search should be allowed to complexify as well as optimize when seeking complex solutions.

  • Takeaways & Limitations

    Complexification depends on the desired behavior existing within the chosen network size.

Abstract

from arXiv · show

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.

1. In tro du tion

Fixed-length encodings struggle with variable and open-ended solution complexity. The paper argues that complexification—incrementally adding structure while preserving existing functionality—enables more sophisticated coevolutionary strategies through NEAT.

  • 1. Introduction: Fixed-length genomes require heuristics to choose an appropriate number of genes, but this becomes impractical for complex or open-ended problems.Larger genomes expand the search space, while fixed sizes also impose an arbitrary maximum complexity.
  • 1. Introduction: Elaboration through complexification preserves earlier abilities while adding new ones, enabling a coevolutionary arms race.The paper contrasts this with altering a strategy, which can discard functionality learned by previous generations.
  • 1. Introduction: Complexification starts with small genomes and adds genes over generations, expanding the search space while preserving most existing dimensions.Each added gene creates a new search dimension, allowing evolution to begin in a smaller, more easily optimized space.
  • 1. Introduction: NEAT complexifies functioning neural networks by adding nodes and connections, beginning without hidden nodes and elaborating potential solutions over generations.Its technical components include tracking gene matches, speciation by complexity, and starting with a uniform population of small networks.
  • 1. Introduction: Complexification evolved when possible, led to elaboration, and produced significantly more sophisticated and successful strategies than evolution without it.The results indicate that complexification enabled a coevolutionary arms race reaching a significantly higher level of sophistication.

2. Ba kground

Natural evolution complexifies by adding and protecting new genetic structure, and NEAT computationally abstracts these mechanisms to elaborate solutions. Competitive coevolution is especially suited to complexification because competing strategies can form an escalating arms race.

  • Biological Complexification: Natural mutation can add new genes, allowing evolution to complexify beyond optimizing existing structures.Gene duplication provides a biological example of adding genetic material that can later acquire novel roles.
  • Challenges for Artificial Evolution: Complexifying artificial evolution must address crossover misalignment and the difficulty of optimizing variable-length genomes before innovations are eliminated.Different network topologies can misalign genes during crossover, while larger genomes require more optimization.
  • Biological Mechanisms: Nature protects innovations through gene alignment during crossover and speciation, allowing initially lower-fitness novel organisms to reproduce within their species.Speciation prevents more complex organisms from competing directly with simpler counterparts for mates.
  • NEAT: NEAT implements abstractions of synapsis and speciation so genomes can complexify by adding genes that encode new phenotype structure.The method applies biological mechanisms computationally to support complexifying evolution.
  • Competitive Coevolution: Competitive coevolution evaluates solutions by relative performance against one another, making it a natural setting for an escalating arms race.Complexification elaborates strategies by adding new dimensions, while open-ended domains reward increasingly sophisticated strategies.

3. NeuroEv olution of Augmen ting T op ologies (NEA T)

NEAT combines weight optimization with incremental network complexification to evolve increasingly elaborate neural-network solutions. Its design addresses crossover between differing topologies, protection of structural innovations, and efficient discovery through minimal starting structures.

  • NEAT design: NEAT combines conventional connection-weight search with incremental complexification of network structure.The method starts from a minimal structure and adds nodes and connections incrementally.
  • NEAT design: Historical markings align genes with the same origin, allowing NEAT to recombine genomes with different topologies without expensive evolutionary comparison.New structural genes receive innovation numbers that preserve their ancestry and identify matching genes during crossover.
  • NEAT design: Speciating the population protects structural innovations while they are optimized, preventing new topological changes from disappearing prematurely.The method separates each innovation into a different species, allowing useful structures to survive fitness evaluation.
  • NEAT design: NEAT uses an expandable genome in which mutations can alter connection weights or add structure through new connections and node-splitting.Adding a node disables an existing connection, inserts the node, and adds two new connections, preserving prior behavior while enabling elaboration.
  • NEAT design: An ablation study found that NEAT’s three components are interdependent and necessary for the method to work.The components are historical markings, speciation, and incremental complexification.

4. The Rob ot Duel Domain

The paper introduces a simulated robot-duel domain designed to support and reveal increasingly sophisticated strategies through competitive coevolution. Robots forage, evade, pursue, and collide while managing energy, making opponent prediction and memory important.

  • Domain design: The domain pits two simulated robots against each other in a duel where the higher-energy robot wins upon collision.Robots begin on opposite sides of a rectangular room, and the objective is to attain more energy before colliding.
  • Domain design: Robots gain energy by consuming symmetrically arranged food while losing energy through movement, creating strategic tradeoffs among foraging, pursuit, and evasion.The task supports strategies ranging from forage-then-attack to luring an opponent into wasting energy before attacking.
  • Strategic complexity: The task supports a broad range of observable strategies that vary in sophistication and require robots to switch rapidly among behaviors.Competitors must become proficient at foraging, prey capture, and escaping predators.
  • Controller implementation: NEAT evolves neural-network controllers that receive robot sensors and a bias input, then produce three motor outputs controlling rotation and forward motion.The sensor suite includes food, opponent, wall, and energy-difference sensing.
  • Observability and control: Because the duel is a partially-observable Markov decision process, successful robots must predict opponents from past behavior and use memory through recurrent connections.The opponent’s internal state is not directly observed, so recurrent connections are described as crucial for success.

5. Exp erimen ts

The experiments test whether complexification improves competitive coevolution in robot duels, using an efficient host/parasite methodology and dominance tournaments to track increasingly sophisticated strategies.

  • Experimental design: Thirteen 500-generation runs used full NEAT, while 20 disabled complexification but retained speciation based on weight differences.The comparison tests whether complexification contributes to sophisticated strategy evolution.
  • Competitive coevolution methodology: Speciation, fitness sharing, and Hall of Fame comprise an effective competitive coevolution methodology.These mechanisms support opponent selection that is more efficient and reliable than random or round-robin tournaments.
  • Competitive coevolution methodology: Each network was evaluated in 24 games against 12 opponents: four highest-species champions and eight random Hall of Fame champions.The opponent set combined quality, diversity, and preservation of previously evolved abilities.
  • Progress measurement: Networks were compared across 288 games spanning varied food configurations, allowing superiority to reflect performance across many scenarios and starting disadvantages.The comparison used 144 configurations from each side of the board.
  • Progress measurement: Dominance tournaments identify a sequence of increasingly sophisticated strategies while requiring significantly fewer comparisons than master tournaments.A candidate becomes dominant by winning every 288-game comparison against previous dominant strategies.

6. Results

The results show that dominant networks became more complex as dominance increased, with significant differences between initial and final dominant strategies. Complexity was not inevitable across the population, and structure-growing NEAT evaluated networks faster than fully connected evolution.

  • Complexification: Dominant networks increased in complexity as dominance increased, measured by their numbers of connections and hidden nodes.Complexity was defined as the number of nodes and connections in a network.
  • Complexification: The differences between average final and first dominant strategies were statistically significant for both connections and nodes (p < 0:001).
  • Complexification: Complexity was not inevitable: very simple and very complex species coexisted throughout the run, while dominant networks complexified when it was beneficial.
  • Evaluation cost: 90% longer was the evaluation time for fully connected topologies compared with structure-growing NEAT.Larger fully connected networks took longer to evaluate.

6.1 Ev olution of Complexit y

Across thirteen NEAT runs, dominant strategies became substantially more complex through a stepped pattern driven by structural innovation and background weight optimization. Random-fitness controls showed that NEAT retains simple and complex networks, complexifying dominant strategies only when added structure is beneficial.

  • Evolution of Complexity: 15.15 (sd = 2.54) was the average highest dominance level across thirteen NEAT runs, with values ranging from 11 to 19.The runs produced 197 dominance transitions over 500 generations.
  • Evolution of Complexity: The average number of connections tripled, while average hidden nodes rose from 0 to almost six.During the first 200 generations, connections in dominant strategies grew by 50%.
  • Evolution of Complexity: Between generations 200 and 500, complexity followed a stepped pattern of sharp rises, plateaus, and renewed increases, caused by speciation.Species adding structure initially gained performance, while species with simpler topologies temporarily caught up by optimizing weights.
  • Evolution of Complexity: Progress resulted from two forces: building new structures and continually optimizing prior structures, producing gradual stepped growth toward greater complexity.More complex structures eventually won because higher complexity was necessary for continued progress.
  • Evolution of Complexity: Random-fitness populations retained networks from very simple to highly complex, showing that dominant networks complexified only when added complexity was beneficial.Their minimum complexity was much lower and maximum complexity significantly greater than those of dominant strategies.

6.2 Sophisti ation through Complexi ation

Complexification progressively elaborated an evolving robot’s strategies, allowing new behaviors to coexist with and improve existing ones. The resulting controllers developed sophisticated behaviors that balanced multiple goals and exploited opponents’ weaknesses.

  • The initial strategy followed opponents and attempted collisions, but it failed to switch clearly between foraging and chasing, missing food-gathering opportunities.
  • Weight optimization alone produced a resting strategy that conserved energy when disadvantaged, causing opponents to waste energy before becoming vulnerable to attack.This improvement increased inhibition from the energy-difference sensor, slightly modifying an existing behavior.
  • Adding a hidden node enabled an immediate all-out attack while preserving the resting behavior, allowing the robot to switch between resting when disadvantaged and attacking when energetic.The new structure elaborated the strategy without interfering with the already existing resting behavior.
  • A further structural addition improved attack timing and role-switching accuracy by replacing a direct connection with a sigmoid-mediated computation.The resulting behavior emphasized resting and foraging, then attacking only when victory was certain.
  • Complexification enabled sophisticated behaviors that elaborated existing strategies, balanced multiple goals, and exploited opponents’ weaknesses.A deceptive waiting behavior appeared against several opponents and in several runs, suggesting robustness.

6.3 Complexi ation vs. Fixed-top ology Ev olution and Simpli ation

Complexifying evolution consistently produced more sophisticated strategies and substantially higher performance than fixed-topology or simplifying evolution. It also searched for appropriate network structure more effectively, making optimization more efficient even when fixed-topology methods were given a suitable architecture.

  • Complexification vs. Simplification: 57.3% overall average performance (sd=19.8%) was achieved by simplifying evolution, significantly below complexifying evolution’s 91.4% (p < 0.001).Across 500 generations, simplification found solutions equivalent to 56 generations of complexification, despite averaging 23.2 dominance levels per run versus 15.2 for complexification.

7. Dis ussion and F uture W ork

The discussion argues that complexification makes high-dimensional search more tractable by elaborating previously optimized structures, while supporting increasingly sophisticated behavior and serving as a general principle for AI.

  • Why Complexification Helps: Complexifying evolution searches high-dimensional structures as elaborations of known, optimized lower-dimensional structures rather than starting blindly in the larger space.After new genetic material is added, the genome begins in a promising region of the expanded search space.
  • Why Complexification Helps: In robot duels, adding new nodes and connections enabled sophisticated strategy elaborations that established an evolutionary arms race.Fixed genomes can optimize existing strategies but cannot add functionality without sacrificing existing knowledge.
  • Limits of Fixed Representations: Fixed-size genomes can produce increasingly complex behavior, but choosing a neighborhood that is too small can make the desired behavior unreachable.Cellular automata evolved complex global patterns while their genome remained unchanged, yet success depended critically on selecting an adequate neighborhood size.
  • Limits of Fixed Representations: Starting in a small search space and incrementally adding dimensions can find solutions more efficiently than searching an unnecessarily large space from the outset.If the target function exists in a smaller neighborhood, it can be found with significantly fewer evaluations.

8. Con lusion

The experiments show that genome complexification supports continual coevolution of increasingly sophisticated strategies. Complexifying coevolution is more successful than non-complexifying coevolution at finding highly sophisticated strategies, making complexification crucial for searching for complex solutions.

  • Genome complexification leads to continual coevolution of increasingly sophisticated strategies.
  • As evolution progresses, solution complexity increases.
  • Evolution uses complexification to elaborate on existing strategies.
  • Complexifying coevolution is significantly more successful than non-complexifying coevolution at finding highly sophisticated strategies.
  • Complexification is a crucial component of a successful search for complex solutions.

A kno wledgmen ts

The appendices document NEAT’s population, evolutionary, and mutation settings, along with calibrated robot-motion equations. They also report that performance is robust to moderate parameter variations and acknowledge grant support and reviewer feedback.

  • Acknowledgments: The research received support from the National Science Foundation and Texas Higher Education Coordinating Board, with thanks to an anonymous reviewer.
  • Appendix A. NEAT System Parameters: Each population contained 256 NEAT networks, for a total of 512 networks.
  • Appendix A. NEAT System Parameters: The system targeted 10 species, adjusting the compatibility threshold by 0.3 when species counts deviated from that target.
  • Appendix A. NEAT System Parameters: Mutation and reproduction used an 80% connection-weight mutation chance, 75% inheritance-based disabling chance, 40% averaged-weight crossover rate, and 25% mutation-only offspring.
  • Appendix A. NEAT System Parameters: Performance was robust to moderate variations in experimentally selected parameters, whose pattern favored adding links more often than nodes.
  • Appendix B. Robot Duel Domain Coefficients of Motion: Robot motion was calibrated experimentally: turn angle depended on left and right turn outputs, while forward movement used a 1.33f distance coefficient on a 600 by 600 board.

Referen es

This section lists prior work spanning evolutionary computation, coevolution, neural-network topology evolution, robotics, and biological complexification.

  • Biological and artificial complexification: References also address gene duplication, genome evolution, complexification, and evolutionary design in biological and artificial systems.Cited topics include vertebrate genome evolution, gene duplication, open-ended evolution, and evolutionary design of digital circuits.
  • Neural-network evolution: The bibliography includes methods for evolving or incrementally constructing neural-network architectures and topologies.Examples include recurrent-network construction, incremental grid-growing networks, growing neural gas, and neural-network topology optimization.
Loading 1107.0037v1…