Each of the 33 evolution runs took between 5 and 10 days on a 1GHz Pentium III processor, depending on the progress of evolution and sizes of the networks involved. The NEAT algorithm itself used less than 1% of this computation: Most of the time was spent in evaluating networks in the robot duel task. Evolution of fully-connected topologies took about 90% longer than structure-growing NEAT because larger networks take longer to evaluate.
In order to analyze the results, we define complexity as the number of nodes and connections in a network: The more nodes and connections there are in the network, the more complex behavior it can potentially implement. The results were analyzed to answer three questions: (1) As evolution progresses does it also continually complexify? (2) Does such complexification lead to more sophisticated strategies? (3) Does complexification allow better strategies to be discovered than does evolving fixed-topology networks? Each question is answered in turn below.
NEAT was run thirteen times, each time from a different seed, to verify that the results were consistent. The highest levels of dominance achieved were 17, 14, 17, 16, 16, 18, 19, 15, 17, 12, 12, 11, and 13, averaging at 15.15 (sd = 2.54).
![]() ![]() |
At each generation where the dominance level increased in at least one of the thirteen runs, we averaged the number of connections and number of nodes in the current dominant strategy across all runs (Figure 5). Thus, the graphs represent a total of 197 dominance transitions spread over 500 generations. The rise in complexity is dramatic, with the average number of connections tripling and the average number of hidden nodes rising from 0 to almost six. In a smooth trend over the first 200 generations, the number of connections in the dominant strategy grows by 50%. During this early period, dominance transitions occur frequently (fewer prior strategies need to be beaten to achieve dominance). Over the next 300 generations, dominance transitions become more sparse, although they continue to occur.
Between the 200th and 500th generations a stepped pattern emerges: The complexity first rises dramatically, then settles, then abruptly increases again (This pattern is even more marked in individual complexifying runs; the averaging done in Figure 5 smooths it out somewhat). The cause for this pattern is speciation. While one species is adding a large amount of structure, other species are optimizing the weights of less complex networks. Initially, added complexity leads to better performance, but subsequent optimization takes longer in the new higher-dimensional space. Meanwhile, species with smaller topologies have a chance to temporarily catch up through optimizing their weights. Ultimately, however, more complex structures eventually win, since higher complexity is necessary for continued innovation.
Thus, there are two underlying forces of progress: The building of new structures, and the continual optimization of prior structures in the background. The product of these two trends is a gradual stepped progression towards increasing complexity.
An important question is: Because NEAT searches by adding structure only, not by removing it, does the complexity always increase whether it helps in finding good solutions or not? To demonstrate that NEAT indeed prefers simple solutions and complexifies only when it is useful, we ran five complexifying evolution runs with fitness assigned randomly (i.e. the winner of each game was chosen at random). As expected, NEAT kept a wide range of networks in its population, from very simple to highly complex (Figure 5). That is, the dominant networks did not have to become more complex; they only did so because it was beneficial. Not only is the minimum complexity in the random-fitness population much lower than that of the dominant strategies, but the maximum complexity is significantly greater. Thus, evolution complexifies sparingly, only when the complex species holds its own in comparison with the simpler ones.
To see how complexification
contributes to evolution, let us
observe how a sample
dominant strategy develops over time. While many complex
networks evolved in the experiments, we follow
the species
that produced
the winning network in the third run because its progress
is rather typical and easy to understand.
Let us use
for the best network
in species
at generation
, and
for the
th
hidden node to arise from a structural mutation over the course
of evolution.
We will track both strategic and structural innovations
in order to see how they correlate.
Let us begin with
(Figure 6a), when
had a mature
zero-hidden-node strategy:
The analysis above shows that in some cases, weight optimization alone can produce improved strategies. However, when those strategies need to be extended, adding new structure allows the new behaviors to coexist with old strategies. Also, in some cases it is necessary to add complexity to make the timing or execution of the behavior more accurate. These results show how complexification can be utilized to produce increasing sophistication.
In order to illustrate the level of sophistication
achieved in this process, we conclude this section
by describing the competition between two
sophisticated strategies, and
, from another run of
evolution.
At the beginning of the competition,
and
collected most of
the available food
until their energy levels were about equal.
Two pieces of food remained on the board in locations
distant from both
and
(Figure 7).
Because of the danger of colliding
with similar energy levels, the obvious strategy is to
rush for the last two pieces of food. In fact,
did exactly
that, consuming
the second-to-last piece, and then heading towards the
last one. In contrast,
forfeited the race for the
second-to-last piece, opting to sit still,
even though its energy temporarily dropped
below
's.
However,
was closer to the last piece and got there first.
It received a boost of energy while
wasted its energy running the long distance from
the second-to-last piece.
Thus,
's strategy ensured that it had
more energy when they finally met.
Robot
's behavior was surprisingly deceptive,
showing that high strategic sophistication had evolved.
Similar waiting behavior was observed against several
other opponents, and also evolved in several other runs,
suggesting that it was a robust result.
This analysis of individual evolved behaviors shows that complexification indeed elaborates on existing strategies, and allows highly sophisticated behaviors to develop that balance multiple goals and utilize weaknesses in the opponent. The last question is whether complexification indeed is necessary to achieve these behaviors.
Complexifying coevolution
was compared to two alternatives:
standard coevolution in a fixed search space,
and to simplifying coevolution
from a complex starting point.
Note that it is not possible to compare methods using the standard
crossvalidation
techniques because no external performance measure exists in this domain.
However, the
evolved neural networks can be compared directly
by playing a duel. Thus, for example, a run of fixed-topology coevolution can
be compared to a run of complexifying coevolution by playing
the highest dominant strategy from the fixed-topology run against
the entire dominance ranking of the complexifying run. The
highest level strategy in the ranking that the fixed-topology strategy
can defeat, normalized by the number of dominance levels,
is a measure of its quality against the complexifying
coevolution.
For example, if a strategy can defeat up to and including the 13th
dominant strategy out of 15, then its performance against that run
is .
By playing every fixed-topology champion,
every simplifying coevolution champion, and every complexifying
coevolution champion
against the dominance ranking
from every
complexifying run and averaging,
we can measure the
relative performance of each of these methods.
In this section, we will first establish the baseline performance by playing complexifying coevolution runs against themselves and demonstrating that a comparison with dominance levels is a meaningful measure of performance. We will then compare complexification with fixed-topology coevolution of networks of different architectures, including fully-connected small networks, fully-connected large networks, and networks with an optimal structure as determined by complexifying coevolution. Third, we will compare the performance of complexification with that of simplifying coevolution.
The highest dominant
strategy from each of the 13 complexifying runs
played the entire dominance ranking from every
other run.
Their average performance scores were ,
,
,
,
,
,
,
,
,
,
,
, and
,
with an overall average of
(sd=12.8%).
Above all, this result shows that
complexifying runs produce consistently good strategies:
On average, the highest dominant strategies
qualify for the top
of the other complexifying runs.
The best runs were the
sixth, seventh, and eighth, which were able to defeat almost the
entire dominance
ranking of every other run.
The highest dominant network from the best run
(
) is shown in Figure 8.
In order to understand what it means for a network to be one or more dominance levels above another, figure 9 shows how many more games the more dominant network can be expected to win on average over all its 288-game comparisons than the less dominant network. Even at the lowest difference (i.e. that of one dominance level), the more dominant network can be expected to win about 50 more games on average, showing that each difference in dominance level is important. The difference grows approximately linearly: A network 5 dominance levels higher will win 100 more games, while a network 10 levels higher will win 150 and 15 levels higher will win 200. These results suggest that dominance level comparisons indeed constitute a meaningful way to measure relative performance.
In fixed-topology coevolution,
the network architecture must be chosen by
the experimenter.
One sensible approach is to approximate the complexity of the
best complexifying network.
(Figure 8).
This network included 11 hidden units and 202
connections, with both recurrent connections and direct
connections from input to output.
As an idealization of this structure, we used
10-hidden-unit fully recurrent networks with direct connections
from inputs to outputs, with a total of
263 connections. A network of this type should be able
to approximate the
functionality of the most effective complexifying strategy.
Fixed-topology coevolution runs exactly as complexifying coevolution
in NEAT, except that no structural mutations can occur.
In particular,
the population is still speciated based on weight differences
(i.e. from equation 1), using
the usual speciation procedure.
Three runs of fixed-topology coevolution were performed with these
networks, and their highest dominant strategies were
compared to the entire dominance ranking of every complexifying
run. Their average performances were
,
, and
, for an overall average
of
. Compared to the
performance
of complexifying coevolution, it is clear that fixed-topology
coevolution produced consistently inferior solutions.
As a matter of fact, no fixed-topology
run could defeat any of the highest dominant
strategies from the 13 complexifying coevolution runs.
This difference in performance can be illustrated by computing the average generation of complexifying coevolution with the same performance as fixed-topology coevolution. This generation turns out to be 24 (sd = 8.8). In other words, 500 generations of fixed-topology coevolution reach on average the same level of dominance as only 24 generations of complexifying coevolution! In effect, the progress of the entire fixed-topology coevolution run is compressed into the first few generations of complexifying coevolution (Figure 10).
One of the arguments for using complexifying coevolution is that starting the search directly in the space of the final solution may be intractable. This argument may explain why the attempt to evolve fixed-topology solutions at a high level of complexity failed. Thus, in the next experiment we aimed at reducing the search space by evolving fully-connected, fully-recurrent networks with a small number of hidden nodes as well as direct connections from inputs to outputs. After considerable experimentation, we found out that five hidden nodes (144 connections) was appropriate, allowing fixed-topology evolution to find the best solutions it could. Five hidden nodes is also about the same number of hidden nodes as the highest dominant strategies had on average in the complexifying runs.
A total of seven runs were performed with the 5-hidden-node networks,
with average performances of ,
,
,
,
,
, and
.
The overall average was
(sd=18.4%), which is
better but still significantly below the
performance of
complexifying coevolution (
).
In particular, the two most effective complexifying runs were still never defeated by any of the fixed-topology runs. Also, because each dominance level is more difficult to achieve than the last, on average the fixed-topology evolution only reached the performance of the 159th complexifying generation (sd=72.0). Thus, even in the best case, fixed-topology coevolution on average only finds the level of sophistication that complexifying coevolution finds halfway through a run (Figure 11).
One problem with evolving fully-connected architectures is that they may not have an appropriate topology for this domain. Of course, it is very difficult to guess an appropriate topology a priori. However, it is still interesting to ask whether fixed-topology coevolution could succeed in the task assuming that the right topology was known? To answer this question, we evolved networks as in the other fixed-topology experiments, except this time using the topology of the best complexifying network (Figure 8). This topology may constrain the search space in such a way that finding a sophisticated solution is more likely than with a fully-connected architecture. If so, it is possible that seeding the population with a successful topology gives it an advantage even over complexifying coevolution, which must build the topology from a minimal starting point.
Five runs were performed, obtaining
average performance score ,
,
,
, and
, and an overall average
of
(sd=
). The
performance of complexifying
coevolution is significantly better than even this version of fixed-topology
coevolution (
). However, interestingly, the
average
performance of 10-hidden-unit fixed topology coevolution is
significantly below best-topology evolution, even though both
methods search in spaces of similar sizes. In fact, best-topology
evolution performs at about the same level as 5-hidden-unit
fixed-topology evolution (
), even though 5-hidden-unit
evolution optimizes half the number of hidden nodes.
Thus, the results
confirm the hypothesis that using a successful evolved topology
does help constrain the search. However, in comparison to
complexifying coevolution, the
advantage gained from starting this way is still not enough to
make up for the penalty of starting search directly
in a high-dimensional space.
As Figure 12 shows, best-topology evolution
on average only finds a strategy that performs as well
as those found by the 193rd generation of complexifying coevolution.
The results of the fixed-topology coevolution experiments can be summarized as follows: If this method is used to search directly in the high-dimensional space of the most effective solutions, it reaches only 40% of the performance of complexifying coevolution. It does better if it is allowed to optimize less complex networks; however, the most sophisticated solutions may not exist in that space. Even given a topology appropriate for the task, it does not reach the same level as complexifying coevolution. Thus, fixed-topology coevolution does not appear to be competitive with complexifying coevolution with any choice of topology.
The conclusion is that complexification is superior not only because it allows discovering the appropriate high-dimensional topology automatically, but also because it makes the optimization of that topology more efficient. This point will be discussed further in Section 7.
A possible remedy to having to search in high-dimensional spaces is to allow evolution to search for smaller structures by removing structure incrementally. This simplifying coevolution is the opposite of complexifying coevolution. The idea is that a mediocre complex solution can be refined by removing unnecessary dimensions from the search space, thereby accelerating the search.
Although simplifying coevolution is an alternative method to complexifying coevolution for finding topologies, it still requires a complex starting topology to be specified. This topology was chosen with two goals in mind: (1) Simplifying coevolution should start with sufficient complexity to at least potentially find solutions of equal or more complexity than the best solutions from complexifying coevolution, and (2) with a rate of structural removal equivalent to the rate of structural addition in complexifying NEAT, it should be possible to discover solutions significantly simpler than the best complexifying solutions. Thus, we chose to start search with a 12-hidden-unit, 339 connection fully-connected fully-recurrent network. Since 162 connections were added to the best complexifying network during evolution, a corresponding simplifying coevolution could discover solutions with 177 connections, or 25 less than the best complexifying network.
Thus, simplify coevolution was run just as complexifying coevolution, except that the initial topology contained 339 connections instead of 39, and structural mutations removed connections instead of adding nodes and connections. If all connections of a node were removed, the node itself was removed. Historical markings and speciation worked as in complexifying NEAT, except that all markings were assigned in the beginning of evolution. (because structure was only removed and never added). A diversity of species of varying complexity developed as before.
The five runs of simplifying coevolution performed at ,
,
,
, and
, with an overall
average of
(sd=19.8%). Again, such performance is
significantly below
the
performance of complexifying coevolution (
).
Interestingly, even though it started with 76 more connections
than fixed-topology coevolution with ten hidden units, simplifying
coevolution still performed significantly
better (
), suggesting that evolving structure through reducing
complexity is better than evolving large fixed structures.
Like Figures 10-12,
Figure 13 compares typical runs of
complexifying and simplifying coevolution.
On average, 500 generations of simplification
finds solutions equivalent to 56 generations
of complexification.
Simplifying coevolution also
tends to find more dominance levels than any other method tested.
It generated an average of dominance levels per run, once even
finding
in one run, whereas e.g. complexifying coevolution
on average finds
levels. In other words,
the difference between dominance levels is much smaller
in simplifying coevolution than complexifying coevolution.
Unlike in other methods, dominant strategies tend
to appear in spurts of a few at a time,
and usually after complexity has been decreasing for several
generations, as also shown in Figure 13.
Over a number of generations,
evolution removes several connections until
a smaller, more easily optimized space is discovered. Then,
a quick succession of minute improvements creates several
new levels of dominance, after which the space is further
refined, and so on. While
such a process makes sense, the inferior results
of simplifying coevolution suggest that
simplifying search is an ineffective way of discovering
useful structures compared to complexification.
Table 1 shows how the coevolution methods differ on number of dominance levels, generation of the highest dominance level, overall performance, and equivalent generation. The conclusion is that complexifying coevolution innovates longer and finds a higher level of sophistication than the other methods.