Login
Login

Neuroevolution

{{Short description|Form of artificial intelligence}}

{{Distinguish|Evolution of nervous systems|Neural development|Neural Darwinism}}

Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks (ANN), parameters, and rules.{{Cite news|url=https://oreilly.com/ideas/neuroevolution-a-different-kind-of-deep-learning|title=Neuroevolution: A different kind of deep learning|last=Stanley|first=Kenneth O.|date=2017-07-13|work=O'Reilly Media|access-date=2017-09-04|language=en}} It is most commonly applied in artificial life, general game playing{{cite journal|last1=Risi |first1=Sebastian|last2=Togelius|first2=Julian |title= Neuroevolution in Games: State of the Art and Open Challenges |journal=IEEE Transactions on Computational Intelligence and AI in Games |volume=9|pages=25–41|year= 2017 |arxiv=1410.7326|doi=10.1109/TCIAIG.2015.2494596|s2cid=11245845}} 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 (i.e., whether one player won or lost) 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 backpropagation (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 (sometimes called conventional neuroevolution), and algorithms that evolve both the topology of the network and its weights (called TWEANNs, for Topology and Weight Evolving Artificial Neural Network algorithms).

A separate distinction can be made between methods that evolve the structure of ANNs in parallel to its parameters (those applying standard evolutionary algorithms) and those that develop them separately (through memetic algorithms).{{cite book |doi=10.1007/978-3-540-87700-4_61 |chapter=Countering Poisonous Inputs with Memetic Neuroevolution |title=Parallel Problem Solving from Nature – PPSN X |series=Lecture Notes in Computer Science |year=2008 |last1=Togelius |first1=Julian |last2=Schaul |first2=Tom |last3=Schmidhuber |first3=Jürgen |last4=Gomez |first4=Faustino |volume=5199 |pages=610–619 |isbn=978-3-540-87699-1 }}

Comparison with gradient descent

{{further|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.{{cite journal |last1=Hutson |first1=Matthew |title=Artificial intelligence can 'evolve' to solve problems |journal=Science |date=11 January 2018 |doi=10.1126/science.aas9715 }}

It can be shown that there is a correspondence between neuroevolution and gradient descent.{{cite journal |last1=Whitelam |first1=Stephen |last2=Selin |first2=Viktor |last3=Park |first3=Sang-Won |last4=Tamblyn |first4=Isaac |title=Correspondence between neuroevolution and gradient descent |journal=Nature Communications |date=2 November 2021 |volume=12 |issue=1 |pages=6317 |doi=10.1038/s41467-021-26568-2 |pmid=34728632 |pmc=8563972 |arxiv=2008.06643 |bibcode=2021NatCo..12.6317W }}

Direct and indirect encoding

Evolutionary algorithms operate on a population of genotypes (also referred to as genomes). 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.{{Citation |last1=Kassahun|first1=Yohannes|last2=Sommer|first2=Gerald|last3=Edgington|first3=Mark|last4=Metzen|first4=Jan Hendrik|last5=Kirchner|first5=Frank|date=2007|contribution=Common genetic encoding for both direct and indirect encodings of networks|title=Genetic and Evolutionary Computation Conference |publisher=ACM Press|pages=1029–1036|citeseerx=10.1.1.159.705}}

Indirect encodings are often used to achieve several aims:{{citation|last=Gauci |first= Stanley |contribution=Generating Large-Scale Neural Networks Through Discovering Geometric Regularities |title=Genetic and Evolutionary Computation Conference|year=2007 |location=New York, NY |publisher=ACM |contribution-url=https://eplex.cs.ucf.edu/papers/gauci_gecco07.pdf}}{{Cite book|title=Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm.|last1=Gruau|first1=Frédéric|last2=I|first2=L'universite Claude Bernard-lyon|last3=Doctorat|first3=Of A. Diplome De|last4=Demongeot|first4=M. Jacques|last5=Cosnard|first5=Examinators M. Michel|last6=Mazoyer|first6=M. Jacques|last7=Peretto|first7=M. Pierre|last8=Whitley|first8=M. Darell|date=1994|citeseerx = 10.1.1.29.5939}}{{Cite journal|last1=Clune|first1=J.|last2=Stanley|first2=Kenneth O.|last3=Pennock|first3=R. T.|last4=Ofria|first4=C.|date=June 2011|title=On the Performance of Indirect Encoding Across the Continuum of Regularity|journal=IEEE Transactions on Evolutionary Computation|volume=15|issue=3|pages=346–367|doi=10.1109/TEVC.2010.2104157|issn=1089-778X|citeseerx=10.1.1.375.6731|s2cid=3008628}}{{cite journal |last1=Risi |first1=Sebastian |last2=Stanley |first2=Kenneth O. |title=An Enhanced Hypercube-Based Encoding for Evolving the Placement, Density, and Connectivity of Neurons |journal=Artificial Life |date=October 2012 |volume=18 |issue=4 |pages=331–363 |doi=10.1162/ARTL_a_00071 |pmid=22938563 |s2cid=3256786 |url=https://stars.library.ucf.edu/cgi/viewcontent.cgi?article=4196&context=facultybib2010 |doi-access=free }}

  • 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 embryogeny (also known as artificial development) have been categorised along the lines of a grammatical approach versus a cell chemistry approach.{{cite journal |last1=Stanley |first1=Kenneth O. |last2=Miikkulainen |first2=Risto |title=A Taxonomy for Artificial Embryogeny |journal=Artificial Life |date=April 2003 |volume=9 |issue=2 |pages=93–130 |doi=10.1162/106454603322221487 |pmid=12906725 |s2cid=2124332 }} 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:

  • Cell (neuron) fate: the final characteristics and role of the cell in the mature phenotype. This dimension counts the number of methods used for determining the fate of a cell.
  • 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 relative targeting (e.g., based on locations of cells relative to each other).
  • Heterochrony: the timing and ordering of events during embryogeny. Counts the number of mechanisms for changing the timing of events.
  • Canalization: how tolerant the genome is to mutations (brittleness). Ranges from requiring precise genotypic instructions to a high tolerance of imprecise 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):

class="wikitable" border="1"
Method

! Encoding

! Evolutionary algorithm

! Aspects evolved

Neuro-genetic evolution by E. Ronald, 1994{{citation |contribution=Genetic Lander: An experiment in accurate neuro-genetic control |first1=Edmund |last1=Ronald |first2= March |last2=Schoenauer |title=PPSN III 1994 Parallel Programming Solving from Nature |pages=452–461 |citeseerx=10.1.1.56.3139 |year=1994 }}

| Direct

| Genetic algorithm

| Network Weights

Cellular Encoding (CE) by F. Gruau, 1994

| Indirect, embryogenic (grammar tree using S-expressions)

| Genetic programming

| Structure and parameters (simultaneous, complexification)

GNARL by Angeline et al., 1994{{cite journal |last1=Angeline |first1=P.J. |last2=Saunders |first2=G.M. |last3=Pollack |first3=J.B. |title=An evolutionary algorithm that constructs recurrent neural networks |journal=IEEE Transactions on Neural Networks |date=January 1994 |volume=5 |issue=1 |pages=54–65 |doi=10.1109/72.265960 |pmid=18267779 |citeseerx=10.1.1.64.1853 |s2cid=44767 }}

| Direct

| Evolutionary programming

| Structure and parameters (simultaneous, complexification)

EPNet by Yao and Liu, 1997{{cite journal |last1=Yao |first1=X. |last2=Liu |first2=Y. |title=A new evolutionary system for evolving artificial neural networks |journal=IEEE Transactions on Neural Networks |date=May 1997 |volume=8 |issue=3 |pages=694–713 |doi=10.1109/72.572107 |pmid=18255671 }}

| Direct

| Evolutionary programming (combined with backpropagation and simulated annealing)

| Structure and parameters (mixed, complexification and simplification)

NeuroEvolution of Augmenting Topologies (NEAT) by Stanley and Miikkulainen, 2002{{cite web|title=Real-Time Neuroevolution in the NERO Video Game|first1=Kenneth O. |last1=Stanley |first2=Bobby D. |last2=Bryant |first3=Risto |last3=Miikkulainen|url=https://nn.cs.utexas.edu/downloads/papers/stanley.ieeetec05.pdf |date=December 2005 }}{{cite journal |last1=Stanley |first1=Kenneth O. |last2=Miikkulainen |first2=Risto |title=Evolving Neural Networks through Augmenting Topologies |journal=Evolutionary Computation |date=June 2002 |volume=10 |issue=2 |pages=99–127 |doi=10.1162/106365602320169811 |pmid=12180173 |citeseerx=10.1.1.638.3910 |s2cid=498161 }}

| Direct

| Genetic 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 (HyperNEAT) by Stanley, D'Ambrosio, Gauci, 2008

| Indirect, non-embryogenic (spatial patterns generated by a Compositional pattern-producing network (CPPN) within a hypercube are interpreted as connectivity patterns in a lower-dimensional space)

| Genetic algorithm. The NEAT algorithm (above) is used to evolve the CPPN.

| Parameters, structure fixed (functionally fully connected)

Evolvable Substrate Hypercube-based NeuroEvolution of Augmenting Topologies (ES-HyperNEAT) by Risi, Stanley 2012

| Indirect, non-embryogenic (spatial patterns generated by a Compositional pattern-producing network (CPPN) within a hypercube are interpreted as connectivity patterns in a lower-dimensional space)

| Genetic algorithm. The NEAT algorithm (above) is used to evolve the CPPN.

| Parameters and network structure

Evolutionary Acquisition of Neural Topologies (EANT/EANT2) by Kassahun and Sommer, 2005{{citation|first1=Yohannes |last1=Kassahun |first2=Gerald |last2=Sommer|contribution=Efficient reinforcement learning through evolutionary acquisition of neural topologies|title=13th European Symposium on Artificial Neural Networks |pages= 259–266|location= Bruges, Belgium |date=April 2005 |contribution-url=https://ks.informatik.uni-kiel.de/~yk/ESANN2005EANT.pdf}} / Siebel and Sommer, 2007{{cite journal |last1=Siebel |first1=Nils T. |last2=Sommer |first2=Gerald |title=Evolutionary reinforcement learning of artificial neural networks |journal=International Journal of Hybrid Intelligent Systems |date=17 October 2007 |volume=4 |issue=3 |pages=171–183 |doi=10.3233/his-2007-4304 }}

| Direct and indirect, potentially embryogenic (Common Genetic Encoding)

| Evolutionary programming/Evolution strategies

| Structure and parameters (separately, complexification)

Interactively Constrained Neuro-Evolution (ICONE) by Rempis, 2012{{cite thesis |last1=Rempis |first1=Christian Wilhelm |title=Evolving Complex Neuro-Controllers with Interactively Constrained Neuro-Evolution |date=2012 |url=https://osnadocs.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-2012101710370 }}

| Direct, 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 (separately, complexification, interactive)

Deus Ex Neural Network (DXNN) by Gene Sher, 2012{{cite book |doi=10.1007/978-1-4614-4463-3 |title=Handbook of Neuroevolution Through Erlang |year=2013 |last1=Sher |first1=Gene I. |isbn=978-1-4614-4462-6 |s2cid=21777855 }}

| Direct/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 (separately, complexification, interactive)

Spectrum-diverse Unified Neuroevolution Architecture (SUNA) by Danilo Vasconcellos Vargas, Junichi Murata{{cite journal|first1=Danilo Vasconcellos |last1=Vargas |first2=Junichi |last2=Murata |journal=IEEE Transactions on Neural Networks and Learning Systems |volume=28 |issue=8 |pages=1759–1773 |title=Spectrum-Diverse Neuroevolution With Unified Neural Models|doi=10.1109/TNNLS.2016.2551748 |pmid=28113564 |year=2019 |arxiv=1902.06703 |bibcode=2019arXiv190206703V |s2cid=206757620 }} ([https://github.com/zweifel/Physis-Shard Download code])

| Direct, introduces the Unified Neural Representation (representation integrating most of the neural network features from the literature).

| 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 (mixed, complexification and simplification)

Modular Agent-Based Evolver (MABE) by Clifford Bohm, Arend Hintze, and others.{{cite journal|first1=Jeffrey |last1=Edlund |first2=Nicolas |last2=Chaumont |first3=Arend |last3=Hintze |first4=Christof |last4=Koch |first5=Giulio

|last5=Tononi |first6=Christoph |last6=Adami |journal=PLOS Computational Biology |volume=7 |issue=10 |pages=e1002236 |title=Integrated Information Increases with Fitness in the Evolution of Animats|doi=10.1371/journal.pcbi.1002236 |pmid=22028639 |pmc=3197648 |year=2011 |arxiv=1103.1791 |bibcode=2011PLSCB...7E2236E |doi-access=free }} ([https://github.com/Hintzelab/MABE Download code])

| 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 (CMA-HAGA) by Shahin Rostami, and others.{{cite journal |last1=Rostami |first1=Shahin |last2=Neri |first2=Ferrante |title=A fast hypervolume driven selection mechanism for many-objective optimisation problems |journal=Swarm and Evolutionary Computation |date=June 2017 |volume=34 |pages=50–67 |doi=10.1016/j.swevo.2016.12.002 |hdl=2086/13102 |hdl-access=free }}{{cite book |doi=10.1109/CIBCB.2017.8058553 |chapter=Multi-objective evolution of artificial neural networks in multi-class medical diagnosis problems with class imbalance |title=2017 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) |year=2017 |last1=Shenfield |first1=Alex |last2=Rostami |first2=Shahin |pages=1–8 |isbn=978-1-4673-8988-4 |s2cid=22674515 |chapter-url=https://eprints.bournemouth.ac.uk/29999/1/CIBCB2017_fetal.pdf }}

|Direct, includes an atavism feature which enables traits to disappear and re-appear at different generations.

|Multi-Objective Evolution Strategy with Preference Articulation (Computational Steering)

|Structure, weights, and biases.

GACNN evolutionary pressure-driven by Di Biasi et al, {{Cite book |last1=Di Biasi |first1=Luigi |last2=De Marco |first2=Fabiola |last3=Auriemma Citarella |first3=Alessia |last4=Barra |first4=Paola |last5=Piotto Piotto |first5=Stefano |last6=Tortora |first6=Genoveffa |chapter=Hybrid Approach for the Design of CNNS Using Genetic Algorithms for Melanoma Classification |series=Lecture Notes in Computer Science |date=2023 |volume=13643 |editor-last=Rousseau |editor-first=Jean-Jacques |editor2-last=Kapralos |editor2-first=Bill |title=Pattern Recognition, Computer Vision, and Image Processing. ICPR 2022 International Workshops and Challenges |chapter-url=https://link.springer.com/chapter/10.1007/978-3-031-37660-3_36 |language=en |location=Cham |publisher=Springer Nature Switzerland |pages=514–528 |doi=10.1007/978-3-031-37660-3_36 |isbn=978-3-031-37660-3}}

|Direct

|Genetic algorithm, Single-Objective Evolution Strategy, specialized for Convolutional Neural Network

|Structure

Fast-DENSER by Assunção et al{{Cite journal |last1=Assunção |first1=Filipe |last2=Lourenço |first2=Nuno |last3=Ribeiro |first3=Bernardete |last4=Machado |first4=Penousal |date=June 2021 |title=Fast-DENSER: Fast Deep Evolutionary Network Structured Representation |url=https://linkinghub.elsevier.com/retrieve/pii/S235271102100039X |journal=SoftwareX |language=en |volume=14 |pages=100694 |doi=10.1016/j.softx.2021.100694|bibcode=2021SoftX..1400694A |hdl=10316/100856 |hdl-access=free }} and others{{Citation |last1=Vinhas |first1=Adriano |title=Towards evolution of Deep Neural Networks through contrastive Self-Supervised learning |date=2024-06-20 |arxiv=2406.14525 |last2=Correia |first2=João |last3=Machado |first3=Penousal}}{{Citation |last1=Cortês |first1=Gabriel |title=Towards Physical Plausibility in Neuroevolution Systems |date=2024 |work=Applications of Evolutionary Computation |volume=14635 |pages=76–90 |editor-last=Smith |editor-first=Stephen |url=https://link.springer.com/10.1007/978-3-031-56855-8_5 |access-date=2024-06-21 |place=Cham |publisher=Springer Nature Switzerland |language=en |doi=10.1007/978-3-031-56855-8_5 |isbn=978-3-031-56854-1 |last2=Lourenço |first2=Nuno |last3=Machado |first3=Penousal |editor2-last=Correia |editor2-first=João |editor3-last=Cintrano |editor3-first=Christian|url-access=subscription }}

|Indirect

|Grammatical evolution (Dynamic Structured Grammar Evolution){{Citation |last1=Lourenço |first1=Nuno |title=Structured Grammatical Evolution: A Dynamic Approach |date=2018 |work=Handbook of Grammatical Evolution |pages=137–161 |editor-last=Ryan |editor-first=Conor |url=https://doi.org/10.1007/978-3-319-78717-6_6 |access-date=2024-06-21 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-78717-6_6 |isbn=978-3-319-78717-6 |last2=Assunção |first2=Filipe |last3=Pereira |first3=Francisco B. |last4=Costa |first4=Ernesto |last5=Machado |first5=Penousal |editor2-last=O'Neill |editor2-first=Michael |editor3-last=Collins |editor3-first=JJ|url-access=subscription }}

|Structure and optimiser used for training

See also

References

{{reflist|30em}}

External links

  • {{Cite web|url=https://beacon-center.org/blog/2012/08/13/evolution-101-neuroevolution/|title=Evolution 101: Neuroevolution {{!}} BEACON|website=beacon-center.org|language=en-US|access-date=2018-01-14}}
  • {{Cite web|url=https://nn.cs.utexas.edu/keyword?neuroevolution|title=NNRG Areas - Neuroevolution|website=nn.cs.utexas.edu|publisher=University of Texas |access-date=2018-01-14}} (has downloadable papers on NEAT and applications)
  • {{Cite web|url=https://sharpneat.sourceforge.net/|title=SharpNEAT Neuroevolution Framework|website=sharpneat.sourceforge.net|language=en|access-date=2018-01-14}} mature open source neuroevolution project implemented in C#/.Net.
  • [https://ANNEvolve.sourceforge.net ANNEvolve is an Open Source AI Research Project] (Downloadable source code in C and Python with a tutorial & miscellaneous writings and illustrations
  • {{Cite web|url=https://siebel-research.de/evolutionary_learning/|title=Nils T Siebel – EANT2 – Evolutionary Reinforcement Learning of Neural Networks|website=siebel-research.de|access-date=2018-01-14}} Web page on evolutionary learning with EANT/EANT2] (information and articles on EANT/EANT2 with applications to robot learning)
  • [https://nerd.x-bot.org/ NERD Toolkit.] The Neurodynamics and Evolutionary Robotics Development Toolkit. A free, open source software collection for various experiments on neurocontrol and neuroevolution. Includes a scriptable simulator, several neuro-evolution algorithms (e.g. ICONE), cluster support, visual network design and analysis tools.
  • {{Cite web|url=https://github.com/CorticalComputer|title=CorticalComputer (Gene)|website=GitHub|access-date=2018-01-14}} Source code for the DXNN Neuroevolutionary system.
  • {{Cite web|url=https://eplex.cs.ucf.edu/ESHyperNEAT|title=ES-HyperNEAT Users Page|website=eplex.cs.ucf.edu|language=en|access-date=2018-01-14}}

{{Evolutionary computation}}

{{Neuroscience}}

Category:Evolutionary algorithms and artificial neuronal networks