@Article{StanleyMiikkulaine2004,
author = {Stanley, Kenneth and Miikkulaine, Risto},
title = {Competitive Coevolution through Evolutionary
Complexification},
journal = {Journal of Artificial Intelligence Research},
year = {2004},
OPTvolume = {21},
OPTpages = {63--100},
}
INTRODUCTION
complexification (CFN hereafter): the incremental elaboration of solutions through adding new structure [63]
Traditionally, in evolutionary computing, researchers have set the number of genes neeeded for solving a specific problem, based on a heuristic. This is very difficult to do for large scale problems. [63]
Possibility: Make the genome extremely large. Problem: searching such a large space can be prohibitive. [64]
Suggested better solution: Start with small simple genomes and systematically elaboration them over generations by adding new genes. In biology, this process is called complexification (CFN), used in this paper to indicate a similar process. [64] In Evolutionary Computing, CFN adds new structure without changing existing representation.
In EC domain of neuroevolution, CFN means adding nodes and connections to already-functioning neural networks. NEAT (NeuroEvolution of Augmenting Topologies) takes this idea to heart. NEAT evoloves networks, creating more complex strategies to elaborate on simple ones. [64]
Elaboration, not Alternation: Existing strategies are supplemented, but original strategies can still be used at any time by neural net. [65]
Focus here is on open-ended problems. Goal: To discover creative solutions beyond a designer's ability to define a fitness function. To demonstrate power of CFN in coevolutionary situations, NEAT is applied to the competitive robot control domain of "Robot Duel". No known optimal strategies. [66]
RESULTS: [66]
DETAILS:
CFN in Nature: New genes added to genome sometimes, allows CFN beyond
current optimization. [66]
See section 2.1 for extended details on gene duplication, which is a
specical kind of mutation in which
one or more parental genes are copied into an offspring's genome more
than once. [66] This has been responsible
for key innovations in body morphology over many generations.
Gene duplication provides inspiration for adding new genes to AI genomes as well, in ANN's, this means adding more neurons and connections to the network.
COMPETITIVE COEVOLUTION (CCE for short)
Individual fitness evaluated through competition with other individuals in populaion. Competing solutions continually outdo each other, leading to an arms race of better solutions. CCE used to evolve interactive behaviours and to gain insight into the dynamics of game-theoretic problems. [68]
Interesting strategies in CCE only show up if arms race continues for significant # of generations. CFN is a natural technique for establishing this sort of arms race. CFN adds new dimensions to search space, allowing for continued improvement of strategy. [69]
NEUROEVOLUTION OF AUGMENTING TOPOLOGIES (NEAT)
NEAT combines usual search for appropriate network weights with CFN of network structure. Very effective.
GENETIC ENCODING
Mutation in NEAT can change both connection weights and network structures. New genes are added continually. [69]
Tracking Genes through Historical Markings:
Historical origin tracked with "global innovation number". Represents a chronology of every gene in the system. [70]
Protecting Innovation through Speciation
NEAT speciates population so individuals compete within their own niches rather than with population at large. Topological innovations are protected and have time to optimize. [73]
MINIMIZING DIMENSIONALITY THROUGH COMPLEXIFICATION
NEAT begins with uniform population of simple ntworks with no hidden nodes. NEAT protects innovation with speciation, and this allows network to start minimally and grow new structure over generations. [74] As new structure is added, only useful ones survive, via fitness evaluations. In short, NEAT uses CFN to find the optimal topology for any given problem. [74]
THE ROBOT DUEL DOMAIN
Robot Duel used as demonstration effectiveness of CFN process. Robot Duel is coevolutionary arms race, and leads to increasingly sopisticated solutions by agents. [74]
DESCRIPTION OF ROBOT DUEL: Two simulated robots try to overpower each other in a rectangular room. They lose energy as they move around, in proportion to the amount of force applied to their wheels. Robot with higher energy wins when it collides with its competitor. Robots have sensors to indicate energy level difference between itself and competitors. Food items can be consumed to keep energy high. [75]
Robots must become good at foraging, prey capture, and escaping predators. Robots controlled with ANN evolved with NEAT. [75]
EXPERIMENTS
33 500-generation runs of coevolution in robot duel domain ran. 13 based on full NEAT procedure. 20 without CFN. [77] Experiments tried to determine whether continual coevolution will take place. Diverse and high quality sample of opponents played to try and encourage sophisticated and interesting strategies.
Hard to monitor progress in competitive coevolution. Solution: Implement dominance tournament. This works by comparing champion networks on many (144 in this case) different configurations of the game space. The network which wins more games out of a set is called the generation champion. Dominant strategies are strategies that defeat all previous dominant strategies. [79] This allows us to identify a sequence of increasingly more sophisticated strategies.
COMPETITION RESULTS
197 dominanace transitions over 500 generations. Significant rise in complexity. Average # of connections tripling and average # of hidden nodes rising from 0 to almost 6. Two underlying forces of progress: building new structures and continual optimization of prior structures in the background.
CFN VS FIXED-TOPOLOGY (FT) EVOLUTION AND SIMPLIFICATION
CFN coevolution compared to two alternatives: standard coevolution in a fixed search space and to simplifying coevolution from a complex starting point. Evolved neural nets compared directly in a duel. [84]
Fixed-topology Evolution: Network architecture chosen by experimenter. [85] 10 hidden units. 263 connections. Approximate functionality of most effective complexifying strategy. When tested against CFN coevolution network, failed to defeat any of the highest dominant strategies from CFN coevolution network. Indicates that fixed-topology coevolution is no match for CFN network. [85] In 500 generations of fixed-topology coevolution, network reaches same level of dominance as only 24 generations of CFN coevolution network.
Testing of Fixed-Topology Coevolution of Small Networks
Smaller Fixed-Topology network tested in duel to test whether initial size of fixed-topology network is the main problem. FT network reduced to 5 hidden nodes, 144 connections. CFN coevolution networks best efforts remain undefeated by any FT network runs. FT evolution only reached performance of the 159th complexifying generation. [87]
Testing of Fixed-Topology of Best Complexifying Network
Tested CFN coevolution network against FT network with best CFN network topology. Still not as good as CFN coevolutionary network, but significantly better than FT topology evolutionary network. This version performs as well as the 193rd generation of CFN coevolution. [89]
Testing of simplifying coevolution network
Simplifying coevolution is the opposite of CFN coevolution...it removes structure to search for smaller structures, accelerating the search process. [89] Starts with a highly complex network. 12 hidden units, 339 connections. Over 500 generations, simplification finds solutions equivalent to 56 generations of complexificatoin. Better than FT coevolution, but not nearly as good as CFN covolution. [91]
CONCLUSION
In future, complexification may help with the general problem of finding the appropriate level of abstraction for difficult problems. [94] Start out at a high level description and then add low level details.
This research leads towards AI research into efficient space search, searching the correct space rather than large volumes of space. Attempt to build a program that can decide what level of abstraction is most appropriate for a given domain. [94]
Experiments in this paper show compexlification of genomes leads to continual coevolution of increasingly sophisticated strategies. Major trends: