Neuroevolution

evolutionary computationneuroevolutionneural networksNEAT

Evolving neural networks, from fixed-topology weight evolution to NEAT's growing topologies, speciation, CPPNs and HyperNEAT, and evolutionary architecture search, with a soft-robot project from the course.

Neuroevolution uses evolutionary algorithms to design neural networks. In its simplest form the network's structure is fixed and evolution searches only over its weights, which needs no gradient and works when the only feedback is a score at the end of an episode, as in many control and game-playing tasks. More ambitious methods evolve the structure as well: which neurons exist, how they connect, and what each computes. That raises problems a bit-string genetic algorithm never meets. Two networks can compute the same function with their hidden units in different orders, so crossing them can produce nonsense. New structure usually performs worse at first, before its weights are tuned, so selection tends to remove it before it can prove useful.

NeuroEvolution of Augmenting Topologies (NEAT), published by Kenneth Stanley and Risto Miikkulainen in 2002, answered both problems. It marks every new gene with a historical innovation number, so that crossover can line up matching parts of different networks. It divides the population into species, so that new structure competes mainly within its own niche. It also starts from minimal networks and adds structure by mutation, so that networks grow only as far as selection rewards. Later work extended the idea. Compositional pattern-producing networks and HyperNEAT encode a large network indirectly, as a function of the geometry of its neurons, and evolutionary architecture search has been used to design deep networks for image recognition. This topic covers these methods in order and ends with the course's final project, which used NEAT to evolve both the bodies and the controllers of simulated soft robots.

Articles

Evolving networks

  • Evolving neural network weights: weight evolution for a fixed network, the competing conventions problem, cooperative methods such as SANE and ESP, and where evolution competes with gradient-based training.
  • NEAT: NeuroEvolution of Augmenting Topologies: historical markings, crossover by innovation number, complexification from minimal networks, and the XOR experiment reproduced.
  • Speciation in NEAT: the compatibility distance, fitness sharing, offspring allocation, and stagnation, and what happens to NEAT without them.
  • CPPNs and HyperNEAT: compositional pattern-producing networks, substrates, and how a small evolved network can specify the connections of a much larger one.
  • Evolutionary neural architecture search: regularized evolution, its comparison with reinforcement-learning search and with random search, and population-based training.

From my course work

  • Coevolving soft robots with NEAT: the course's final project, a from-scratch NEAT that evolved voxel bodies and their controllers in the EvoGym simulator, presented as a single-run case study.

Neuroevolution relies on the selection and variation machinery of genetic algorithms, and its problem of evolving structure parallels that of genetic programming. Evolving bodies and controllers together is an instance of coevolution. Evolution strategies are often used for weight-only neuroevolution at scale, and evolutionary robotics continues the soft-robot line of work.

References

  • Stanley, K. O., and Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2), 99–127.
  • Yao, X. (1999). Evolving artificial neural networks. Proceedings of the IEEE, 87(9), 1423–1447.