factor because it determines the size of the solution, and hence the size of the space in which the
solution can be found. Searching in too large a space may be intractable; In fact, if the solution
contains many dimensions, even searching in the space of the actual solution may be intractable.
On the other hand, searching in too small a space may fail because the solution may not exist in that
space.
Determining the right topology is important also because many common structures that the
neural networks may need to represent and process are defined by an indefinite number of parame-
ters. For example, the number of parts in electronic circuits and robot controllers can vary (Miller
et al. 2000a; Stanley and Miikkulainen 2004). Moreover, although theoretically two neural net-
works with different numbers of connections and nodes can represent the same function (Cybenko
1989), they may not be equally efficient to run nor equally easy to discover. Thus, it is not clear
what network topology is appropriate for solving a particular problem. Methods that search in fixed
spaces must rely on heuristics to determine the appropriate topology a priori.
In neuroevolution, the topology is defined by the network’s genetic encoding, and the size
of the encoding, i.e. the number of genes, is a crucial factor determining the network topology. In
highly complex domains the heuristics for determining the appropriate size are not very useful, and
it becomes increasingly difficult to solve such domains with fixed-length encodings. For example,
how many nodes and connections are necessary for a neural network that controls a robotic maid?
The answers to such 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 genetic
encoding extremely large, so that the space it encodes is extremely large and a solution is likely to
lie somewhere within. Yet the larger the encoding, the higher dimensional the space that evolution
needs to search. Even if a robotic maid lies somewhere in the 10,000 dimensional space of a 10,000
gene encoding, searching such a space may take prohibitively long.
Even more problematic are open-ended problems where behaviors and strategies are meant
to increase in sophistication indefinitely and there is no known final solution. For example, in
competitive games, it is not possible to estimate the complexity of the “best” possible player in
order to decide the size of a fixed-length genome; Similarly, many artificial life domains are aimed
at evolving increasingly complex artificial creatures for as long as possible (Maley 1999), which is
difficult with a fixed encoding for two reasons: (1) When a good strategy is found in a fixed-length
encoding, the entire representational space 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 encoding in such domains arbitrarily limits how complex the evolved
controller can be, defeating the purpose of the experiment.
In order to discover solutions to difficult real-world problems and to open-ended problems,
a method is needed that can automatically estimate the right number of dimensions for the solution.
Even if that solution exists in high-dimensional space, search should spend the majority of time in
lower-dimensional space building up a foundation for the final solution. Such a method is developed
3