Neuroevolution
Encyclopedia
Neuroevolution, or neuro-evolution, is a form of machine learning
that uses evolutionary algorithm
s to train artificial neural networks
. It is useful for applications such as games and robot
motor control, where it is easy to measure a network's performance at a task but difficult or impossible to create a syllabus of correct input-output pairs for use with a supervised learning algorithm
. In the classification scheme for neural network learning these methods usually belong in the reinforcement learning
category (needs reference).
A further distinction is made between methods that evolve the structure (topology) of the neural networks in parallel to the parameters (e.g. synaptic weights) and those that develop them separately.
s (in some algorithms these may be divided into species with differing genome
s), in neuroevolution a genotype is some representation of a neural network (a phenotype
).
In Direct encoding schemes the genotype is the same as the phenotype, every neuron and connection is specified directly and explicitly in the genotype. In contrast, in indirect encoding schemes the genotype specifies rules or some other structure for generating the network.
Indirect encodings are often used to achieve several aims:
(also known as artificial development
) have been categorised along the lines of a grammatical approach versus a cell chemistry approach. The former evolve sets of rules in the form of grammatical rewrite systems. The latter attempt to mimic how physical structures emerge in biology through gene expression. However, this distinction is largely superficial: although they often develop differently in a number of important ways, many of these differences only exist for historical reasons and not because of any intrinsic requirement of either approach. 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 and thus compared with others:
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
that uses evolutionary algorithm
Evolutionary algorithm
In artificial intelligence, an evolutionary algorithm is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection...
s to train artificial neural networks
Neural network
The term neural network was traditionally used to refer to a network or circuit of biological neurons. The modern usage of the term often refers to artificial neural networks, which are composed of artificial neurons or nodes...
. It is useful for applications such as games and robot
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
motor control, where it is easy to measure a network's performance at a task but difficult or impossible to create a syllabus of correct input-output pairs for use with a supervised learning algorithm
Supervised learning
Supervised learning is the machine learning task of inferring a function from supervised training data. The training data consist of a set of training examples. In supervised learning, each example is a pair consisting of an input object and a desired output value...
. In the classification scheme for neural network learning these methods usually belong in the reinforcement learning
Reinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
category (needs reference).
Features
There are many neuroevolutionary algorithms. A distinction is made between those that evolve the values of the connection weights for a network of pre-specified topology, vs. those that evolve the topology of the network in addition to the weights. Although there are no standardized terms for this distinction as a whole, adding or removing a network's connections during evolution may be referred to as complexification or simplification, respectively. Networks that have both their connection weights and topology evolved are referred to as TWEANNs (Topology & Weight Evolving Artificial Neural Networks).A further distinction is made between methods that evolve the structure (topology) of the neural networks in parallel to the parameters (e.g. synaptic weights) and those that develop them separately.
Direct and Indirect Encoding of Networks
Evolutionary algorithms operate on a population of genotypeGenotype
The genotype is the genetic makeup of a cell, an organism, or an individual usually with reference to a specific character under consideration...
s (in some algorithms these may be divided into species with differing genome
Genome
In modern molecular biology and genetics, the genome is the entirety of an organism's hereditary information. It is encoded either in DNA or, for many types of virus, in RNA. The genome includes both the genes and the non-coding sequences of the DNA/RNA....
s), in neuroevolution a genotype is some representation of a neural network (a phenotype
Phenotype
A phenotype is an organism's observable characteristics or traits: such as its morphology, development, biochemical or physiological properties, behavior, and products of behavior...
).
In Direct encoding schemes the genotype is the same as the phenotype, every neuron and connection is specified directly and explicitly in the genotype. In contrast, in indirect encoding schemes the genotype specifies rules or some other structure for generating the network.
Indirect encodings are often used to achieve several aims:
- Allow recurring structures or features in the network to form (modularity and other regularities);
- compression of phenotype to a smaller genotype, providing a smaller search space;
- mapping the search space (genome) to the problem domain.
Taxonomy of Embryogenic Systems for Indirect Encoding
Traditionally indirect encodings that employ artificial embryogenyEmbryology
Embryology is a science which is about the development of an embryo from the fertilization of the ovum to the fetus stage...
(also known as artificial development
Artificial development
Artificial development, also known as artificial embryogeny or computational development, is an area of computer science and engineering concerned with computational models motivated by genotype-phenotype mappings in biological systems...
) have been categorised along the lines of a grammatical approach versus a cell chemistry approach. The former evolve sets of rules in the form of grammatical rewrite systems. The latter attempt to mimic how physical structures emerge in biology through gene expression. However, this distinction is largely superficial: although they often develop differently in a number of important ways, many of these differences only exist for historical reasons and not because of any intrinsic requirement of either approach. 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 and thus compared with others:
- Cell (Neuron) Fate: the final characteristics and role of the cell in the mature phenotype. This dimension ranges from a single method for determining the fate of a cell to having many determination methods.
- Targeting: the method by which connections are directed from source cells to target cells. This ranges from specific targeting (source and target are explicitly identified) to only relative targeting (e.g. based on locations of cells relative to each other).
- Heterochrony: the timing and ordering of events during embryogeny. Ranges from no mechanisms for changing the timing of events to many mechanisms.
- Canalization: how tolerant the genome is to mutations (brittleness). Ranges from requiring precise genotypic instructions to a high tolerance of imprecision or mutation.
- Complexification: the ability of the system (including evolutionary algorithm and genotype to phenotype mapping) to allow complexification of the genome (and hence phenotype) over time. Ranges from allowing only fixed-size genomes to allowing highly variable length genomes.
Examples
Examples of Neuroevolution methods (those with direct encodings are necessarily non-embryogenic):| Method | Encoding | Evolutionary algorithm | Aspects evolved |
|---|---|---|---|
| Cellular Encoding (CE) by F. Gruau, 1994 | Indirect, embryogenic (grammar tree using S-expressions) | Genetic programming Genetic programming In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program... |
Structure and parameters (simultaneous, complexification) |
| GNARL by Angeline et al., 1994 | Direct | Evolutionary programming Evolutionary programming Evolutionary programming is one of the four major evolutionary algorithm paradigms. It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve.... |
Structure and parameters (simultaneous, complexification) |
| EPNet by Yao and Liu, 1997 | |||
| NeuroEvolution of Augmenting Topologies (NEAT) by Stanley and Miikkulainen, 2002 | Direct | Genetic algorithm Genetic algorithm A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems... . Tracks genes with historical markings to allow crossover between different topologies, protects innovation via speciation. |
Structure and parameters (simultaneous, complexification) |
| Hypercube-based NeuroEvolution of Augmenting Topologies HyperNEAT Hypercube-based NEAT, or HyperNEAT, is a generative encoding that evolves artificial neural networks with the principles of the widely used NeuroEvolution of Augmented Topologies algorithm. It is a novel technique for evolving large-scale neural networks utilizing the geometric regularities of... (HyperNEAT) by Stanley, D'Ambrosio, Gauci, 2008 |
Indirect, non-embryogenic (spatial patterns generated by a Compositional pattern-producing network Compositional pattern-producing network Compositional pattern-producing networks , are a variation of artificial neural networks which differ in their set of activation functions and how they are applied.... (CPPN) within a hypercube Hypercube In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An... are interpreted as connectivity patterns in a lower-dimensional space) |
Genetic algorithm Genetic algorithm A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems... . The NEAT algorithm (above) is used to evolve the CPPN. |
Parameters, structure fixed (functionally fully connected) |
| Evolutionary Acquisition of Neural Topologies Evolutionary Acquisition of Neural Topologies Evolutionary Acquisition of Neural Topologies is an evolutionary reinforcement learning method that evolves both the topology and weights of artificial neural networks. It is closely related to the works of Angeline et al. and Stanley and Miikkulainen... (EANT/EANT2) by Kassahun and Sommer, 2005 / Siebel and Sommer, 2007 |
Direct and indirect, potentially embryogenic (Common Genetic Encoding) | Evolutionary programming Evolutionary programming Evolutionary programming is one of the four major evolutionary algorithm paradigms. It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve.... /Evolution strategies |
Structure and parameters (separately, complexification) |
See also
- NeuroEvolution of Augmented TopologiesNeuroEvolution of Augmented TopologiesNeuroEvolution of Augmenting Topologies is a genetic algorithm for the generation of evolving artificial neural networks developed by Ken Stanley in 2002 while at The University of Texas at Austin...
(NEAT) - HyperNEATHyperNEATHypercube-based NEAT, or HyperNEAT, is a generative encoding that evolves artificial neural networks with the principles of the widely used NeuroEvolution of Augmented Topologies algorithm. It is a novel technique for evolving large-scale neural networks utilizing the geometric regularities of...
(A Generative version of NEAT) - Evolutionary Acquisition of Neural TopologiesEvolutionary Acquisition of Neural TopologiesEvolutionary Acquisition of Neural Topologies is an evolutionary reinforcement learning method that evolves both the topology and weights of artificial neural networks. It is closely related to the works of Angeline et al. and Stanley and Miikkulainen...
(EANT/EANT2)
External links
- University of Texas neuroevolution page (has downloadable papers on NEAT and applications)
- ANNEvolve is an Open Source AI Research Project (Has downloadable source code in C and Python for a variety of interesting problems. Also a tutorial & miscellaneous writings and illustrations)
- Web page on evolutionary learning with EANT/EANT2 (information and articles on EANT/EANT2 with applications to robot learning)