Neuroevolution


Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks, parameters, topology and rules. It is most commonly applied in artificial life, general game playing and evolutionary robotics. The main benefit is that neuroevolution can be applied more widely than supervised learning algorithms, which require a syllabus of correct input-output pairs. In contrast, neuroevolution requires only a measure of a network's performance at a task. For example, the outcome of a game can be easily measured without providing labeled examples of desired strategies. Neuroevolution is commonly used as part of the reinforcement learning paradigm, and it can be contrasted with conventional deep learning techniques that use gradient descent on a neural network with a fixed topology.

Features

Many neuroevolution algorithms have been defined. One common distinction is between algorithms that evolve only the strength of the connection weights for a fixed network topology, as opposed to those that evolve both the topology of the network and its weights.
A separate distinction can be made between methods that evolve the structure of ANNs in parallel to its parameters and those that develop them separately.

Comparison with gradient descent

Most neural networks use gradient descent rather than neuroevolution. However, around 2017 researchers at Uber stated they had found that simple structural neuroevolution algorithms were competitive with sophisticated modern industry-standard gradient-descent deep learning algorithms, in part because neuroevolution was found to be less likely to get stuck in local minima. In Science,
journalist Matthew Hutson speculated that part of the reason neuroevolution is succeeding where it had failed before is due to the increased computational power available in the 2010s.

Direct and indirect encoding

Evolutionary algorithms operate on a population of genotypes. In neuroevolution, a genotype is mapped to a neural network phenotype that is evaluated on some task to derive its fitness.
In direct encoding schemes the genotype directly maps to the phenotype. That is, every neuron and connection in the neural network is specified directly and explicitly in the genotype. In contrast, in indirect encoding schemes the genotype specifies indirectly how that network should be generated.
Indirect encodings are often used to achieve several aims:
Traditionally indirect encodings that employ artificial embryogeny have been categorised along the lines of a grammatical approach versus a cell chemistry approach. The former evolves sets of rules in the form of grammatical rewrite systems. The latter attempts to mimic how physical structures emerge in biology through gene expression. Indirect encoding systems often use aspects of both approaches.
Stanley and Miikkulainen propose a taxonomy for embryogenic systems that is intended to reflect their underlying properties. The taxonomy identifies five continuous dimensions, along which any embryogenic system can be placed:
Examples of neuroevolution methods :
MethodEncodingEvolutionary algorithmAspects evolved
Neuro-genetic evolution by E. Ronald, 1994DirectGenetic algorithmNetwork Weights
Cellular Encoding by F. Gruau, 1994Indirect, embryogenic Genetic programmingStructure and parameters
GNARL by Angeline et al., 1994DirectEvolutionary programmingStructure and parameters
EPNet by Yao and Liu, 1997DirectEvolutionary programming Structure and parameters
NeuroEvolution of Augmenting Topologies by Stanley and Miikkulainen, 2002DirectGenetic algorithm. Tracks genes with historical markings to allow crossover between different topologies, protects innovation via speciation.Structure and parameters
Hypercube-based NeuroEvolution of Augmenting Topologies by Stanley, D'Ambrosio, Gauci, 2008Indirect, non-embryogenic Genetic algorithm. The NEAT algorithm is used to evolve the CPPN.Parameters, structure fixed
Evolvable Substrate Hypercube-based NeuroEvolution of Augmenting Topologies by Risi, Stanley 2012Indirect, non-embryogenic Genetic algorithm. The NEAT algorithm is used to evolve the CPPN.Parameters and network structure
Evolutionary Acquisition of Neural Topologies by Kassahun and Sommer, 2005 / Siebel and Sommer, 2007Direct and indirect, potentially embryogenic Evolutionary programming/Evolution strategiesStructure and parameters
Interactively Constrained Neuro-Evolution by Rempis, 2012Direct, includes constraint masks to restrict the search to specific topology / parameter manifolds.Evolutionary algorithm. Uses constraint masks to drastically reduce the search space through exploiting domain knowledge.Structure and parameters
Deus Ex Neural Network by Gene Sher, 2012Direct/Indirect, includes constraints, local tuning, and allows for evolution to integrate new sensors and actuators.Memetic algorithm. Evolves network structure and parameters on different time-scales.Structure and parameters
Spectrum-diverse Unified Neuroevolution Architecture by Danilo Vasconcellos Vargas, Junichi Murata Direct, introduces the Unified Neural Representation.Genetic Algorithm with a diversity preserving mechanism called Spectrum-diversity that scales well with chromosome size, is problem independent and focus more on obtaining diversity of high level behaviours/approaches. To achieve this diversity the concept of chromosome Spectrum is introduced and used together with a Novelty Map Population.Structure and parameters
Modular Agent-Based Evolver by Clifford Bohm, Arend Hintze, and others. Direct or indirect encoding of Markov networks, Neural Networks, genetic programming, and other arbitrarily customizable controllers.Provides evolutionary algorithms, genetic programming algorithms, and allows customized algorithms, along with specification of arbitrary constraints.Evolvable aspects include the neural model and allows for the evolution of morphology and sexual selection among others.
Covariance Matrix Adaptation with Hypervolume Sorted Adaptive Grid Algorithm by Shahin Rostami, and others.,Direct, includes an atavism feature which enables traits to disappear and re-appear at different generations.Multi-Objective Evolution Strategy with Preference ArticulationStructure, weights, and biases.