Evolutionary Computation (EC) is a class of algorithms
that can be applied to open-ended learning problems in Artificial
Intelligence. Traditionally, such algorithms evolve fixed-length genomes
under the assumption that the space of the genome is sufficient
to encode the solution. A genome containing genes
encodes a single point in an -dimensional search space.
In many cases, a solution is known to exist somewhere in that space.
For example, the global maximum of a function of three arguments
*must* exist in the three dimensional space defined by those
arguments. Thus, a genome of three genes can encode the
location of the maximum.

However, many common structures are defined by an
indefinite number of parameters. In particular, those
solution types that can contain a variable number of parts
can be represented by any number of
parameters above some minimum. For example, the number of parts in
neural networks, cellular automata, and electronic
circuits can vary .
In fact, theoretically two neural networks with different numbers of
connections and nodes can represent the same function .
Thus, it is not clear what number of
genes is appropriate for solving a particular problem.
Researchers evolving fixed-length genotypes must use heuristics
to estimate *a priori* the appropriate number of genes
to encode such structures.

A major obstacle to using fixed-length encodings is that heuristically determining the appropriate number of genes becomes impossible for very complex problems. For example, how many nodes and connections are necessary for a neural network that controls a ping-pong playing robot? Or, how many bits are needed in the neighborhood function of a cellular automaton that performs information compression? The answers to these questions can hardly be based on empirical experience or analytic methods, since little is known about the solutions. One possible approach is to simply make the genome extremely large, so that the space it encodes is extremely large and a solution is likely to lie somewhere within. Yet the larger the genome, the higher dimensional the space that evolution needs to search. Even if a ping-pong playing robot lies somewhere in the 10,000 dimensional space of a 10,000 gene genome, searching such a space may take prohibitively long.

Even more problematic are open-ended problems where phenotypes are meant
to improve indefinitely and there is no known final solution.
For example, in competitive games,
estimating the complexity of the ``best'' possible player is difficult
because such an estimate implicitly assumes that no better
player can exist, which we cannot always know.
Moreover, many artificial
life domains are aimed at evolving increasingly complex artificial
creatures for as long as possible .
Such continual evolution is difficult with a fixed
genome for two reasons:
(1) When a good strategy is found in a fixed-length genome, the entire
representational space of the genome is used to encode it.
Thus, the only way to improve it is to *alter* the
strategy, thereby sacrificing some of the functionality
learned over previous generations.
(2) Fixing the size of the genome in
such domains arbitrarily fixes the maximum complexity of evolved
creatures, defeating the purpose of the experiment.

In this paper, we argue that
structured phenotypes can be evolved effectively by starting evolution with a
population of small, simple genomes and systematically elaborating on them
over generations by adding new genes.
Each new gene expands the search space, adding a new dimension that
previously did not exist.
That way, evolution begins
searching in a small easily-optimized space, and adds new dimensions
as necessary. This approach is more likely to discover highly
complex phenotypes than an approach that begins searching directly
in the intractably large space of complete solutions. In fact,
natural evolution utilizes this strategy, occasionally
adding new genes that lead to increased phenotypic
complexity (Martin 1999; Section 2).
In biology, this process
of incremental elaboration
is called *complexification*, which is why
we use this term to describe our approach as well.

In evolutionary computation, complexification refers to
expanding the dimensionality of the search space
while preserving the values of the majority of dimensions.
In other words, complexification
*elaborates* on the existing strategy by adding new structure
without changing the existing representation.
Thus the strategy does not only become different, but
the number of possible
responses to situations it can generate increases (Figure 1).

In the EC domain of neuroevolution (i.e. evolving neural networks), complexification means adding nodes and connections to already-functioning neural networks. This is the main idea behind NEAT (NeuroEvolution of Augmenting Topologies; Stanley and Miikkulainen 2002b,c,d), the method described in this paper. NEAT begins by evolving networks without any hidden nodes. Over many generations, new hidden nodes and connections are added, complexifying the space of potential solutions. In this way, more complex strategies elaborate on simpler strategies, focusing search on solutions that are likely to maintain existing capabilities.

Expanding the length of the size of the genome has been found effective in previous work . NEAT advances this idea by making it possible to search a wide range of increasingly complex network topologies simultaneously. This process is based on three technical components: (1) Keeping track of which genes match up with which among differently sized genomes throughout evolution; (2) speciating the population so that solutions of differing complexity can exist independently; and (3) starting evolution with a uniform population of small networks. These components work together in complexifying solutions as part of the evolutionary process. In prior work, NEAT has been shown to solve challenging reinforcement learning problems more efficiently than other neuroevolution methods (Stanley and Miikkulainen 2002b,c,d). The focus of these studies was on optimizing a given fitness function through complexifying evolution.

In this paper, we focus on open-ended problems that have no explicit
fitness function; instead, fitness depends on comparisons with other
agents that are also evolving. The goal is to discover creative
solutions beyond a designer's ability to define a fitness function. It is
difficult to continually improve solutions in such
*coevolutionary* domains because evolution tends to oscillate
between idiosyncratic yet uninteresting solutions
. Complexification encourages continuing
innovation by elaborating on existing solutions.

In order to demonstrate the power of complexification in coevolution,
NEAT is applied to the competitive robot control domain of *Robot
Duel*. There is no known optimal strategy in the domain but there
is substantial room to come up with increasingly sophisticated
strategies. The main results were that (1) evolution did complexify
when possible, (2) complexification led to elaboration, and (3)
significantly more sophisticated and successful strategies were
evolved with complexification than without it. These results imply
that complexification allows establishing a coevolutionary arms race
that achieves a significantly higher level of sophistication than is
otherwise possible.

We begin by reviewing biological support for complexification, as well as past work in coevolution, followed by a description of the NEAT method, and experimental results.