  Surrogate-assistance approaches have long been used in computationally
expensive domains to improve the data-efficiency of optimization algorithms.
Neuroevolution, however, has so far resisted the application of these
techniques because it requires the surrogate model to make fitness predictions
based on variable topologies, instead of a vector of parameters. Our main
insight is that we can sidestep this problem by using kernel-based surrogate
models, which require only the definition of a distance measure between
individuals. Our second insight is that the well-established Neuroevolution of
Augmenting Topologies (NEAT) algorithm provides a computationally efficient
distance measure between dissimilar networks in the form of "compatibility
distance", initially designed to maintain topological diversity. Combining
these two ideas, we introduce a surrogate-assisted neuroevolution algorithm
that combines NEAT and a surrogate model built using a compatibility distance
kernel. We demonstrate the data-efficiency of this new algorithm on the low
dimensional cart-pole swing-up problem, as well as the higher dimensional
half-cheetah running task. In both tasks the surrogate-assisted variant
achieves the same or better results with several times fewer function
evaluations as the original NEAT.
