Neuroevolution

Last updated

Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks (ANN), parameters, and rules. [1] It is most commonly applied in artificial life, general game playing [2] 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.

Contents

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). [3]

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. [4]

It can be shown that there is a correspondence between neuroevolution and gradient descent. [5]

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. [6]

Indirect encodings are often used to achieve several aims: [6] [7] [8] [9] [10]

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. [11] 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 [11] 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

Examples of neuroevolution methods (those with direct encodings are necessarily non-embryogenic):

MethodEncodingEvolutionary algorithmAspects evolved
Neuro-genetic evolution by E. Ronald, 1994 [12] Direct Genetic algorithm Network Weights
Cellular Encoding (CE) by F. Gruau, 1994 [8] Indirect, embryogenic (grammar tree using S-expressions) Genetic programming Structure and parameters (simultaneous, complexification)
GNARL by Angeline et al., 1994 [13] Direct Evolutionary programming Structure and parameters (simultaneous, complexification)
EPNet by Yao and Liu, 1997 [14] 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 [15] [16] 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 [7] 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 [10] 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 [17] / Siebel and Sommer, 2007 [18] Direct and indirect, potentially embryogenic (Common Genetic Encoding [6] ) Evolutionary programming/Evolution strategies Structure and parameters (separately, complexification)
Interactively Constrained Neuro-Evolution (ICONE) by Rempis, 2012 [19] 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 [20] 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 [21] (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. [22] (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. [23] [24] 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, [25] Direct Genetic algorithm, Single-Objective Evolution Strategy, specialized for Convolutional Neural NetworkStructure
Fast-DENSER by Assunção et al [26] and others [27] [28] Indirect Grammatical evolution (Dynamic Structured Grammar Evolution) [29] Structure and optimiser used for training

See also

Related Research Articles

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

NeuroEvolution of Augmenting Topologies (NEAT) is a genetic algorithm (GA) for the generation of evolving artificial neural networks developed by Kenneth Stanley and Risto Miikkulainen in 2002 while at The University of Texas at Austin. It alters both the weighting parameters and structures of networks, attempting to find a balance between the fitness of evolved solutions and their diversity. It is based on applying three key techniques: tracking genes with history markers to allow crossover among topologies, applying speciation to preserve innovations, and developing topologies incrementally from simple initial structures ("complexifying").

In genetic algorithms (GA), or more general, evolutionary algorithms (EA), a chromosome is a set of parameters which define a proposed solution of the problem that the evolutionary algorithm is trying to solve. The set of all solutions, also called individuals according to the biological model, is known as the population. The genome of an individual consists of one, more rarely of several, chromosomes and corresponds to the genetic representation of the task to be solved. A chromosome is composed of a set of genes, where a gene consists of one or more semantically connected parameters, which are often also called decision variables. They determine one or more phenotypic characteristics of the individual or at least have an influence on them. In the basic form of genetic algorithms, the chromosome is represented as a binary string, while in later variants and in EAs in general, a wide variety of other data structures are used.

In natural evolution and artificial evolution the fitness of a schema is rescaled to give its effective fitness which takes into account crossover and mutation.

In computer programming, genetic representation is a way of presenting solutions/individuals in evolutionary computation methods. The term encompasses both the concrete data structures and data types used to realize the genetic material of the candidate solutions in the form of a genome, and the relationships between search space and problem space. In the simplest case, the search space corresponds to the problem space. The choice of problem representation is tied to the choice of genetic operators, both of which have a decisive effect on the efficiency of the optimization. Genetic representation can encode appearance, behavior, physical qualities of individuals. Difference in genetic representations is one of the major criteria drawing a line between known classes of evolutionary computation.

A memetic algorithm (MA) in computer science and operations research, is an extension of the traditional genetic algorithm (GA) or more general evolutionary algorithm (EA). It may provide a sufficiently good solution to an optimization problem. It uses a suitable heuristic or local search technique to improve the quality of solutions generated by the EA and to reduce the likelihood of premature convergence.

Grammatical evolution (GE) is an evolutionary computation and, more specifically, a genetic programming (GP) technique (or approach) pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998 at the BDS Group in the University of Limerick.

Blondie24 is an artificial intelligence checkers-playing computer program named after the screen name used by a team led by David B. Fogel. The purpose was to determine the effectiveness of an artificial intelligence checkers-playing computer program.

Computational neurogenetic modeling (CNGM) is concerned with the study and development of dynamic neuronal models for modeling brain functions with respect to genes and dynamic interactions between genes. These include neural network models and their integration with gene network models. This area brings together knowledge from various scientific disciplines, such as computer and information science, neuroscience and cognitive science, genetics and molecular biology, as well as engineering.

<span class="mw-page-title-main">NEAT Particles</span>

NEAT Particles is an interactive evolutionary computation program that enables users to evolve particle systems intended for use as special effects in video games or movie graphics. Rather than being hand-coded like typical particle systems, the behaviors of NEAT Particle effects are evolved by user preference. Therefore, non-programmer, non-artist users may evolve complex and unique special effects in real time. NEAT Particles is meant to augment and assist the time-consuming computer graphics content generation process. NEAT is short for Neuroevolution of Augmenting Topologies.

Compositional pattern-producing networks (CPPNs) are a variation of artificial neural networks (ANNs) that have an architecture whose evolution is guided by genetic algorithms.

Evolutionary acquisition of neural topologies (EANT/EANT2) 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. Like the work of Angeline et al., the method uses a type of parametric mutation that comes from evolution strategies and evolutionary programming, in which adaptive step sizes are used for optimizing the weights of the neural networks. Similar to the work of Stanley (NEAT), the method starts with minimal structures which gain complexity along the evolution path.

Artificial development, also known as artificial embryogeny or machine intelligence or computational development, is an area of computer science and engineering concerned with computational models motivated by genotype–phenotype mappings in biological systems. Artificial development is often considered a sub-field of evolutionary computation, although the principles of artificial development have also been used within stand-alone computational models.

<span class="mw-page-title-main">HyperNEAT</span>

Hypercube-based NEAT, or HyperNEAT, is a generative encoding that evolves artificial neural networks (ANNs) with the principles of the widely used NeuroEvolution of Augmented Topologies (NEAT) algorithm developed by Kenneth Stanley. It is a novel technique for evolving large-scale neural networks using the geometric regularities of the task domain. It uses Compositional Pattern Producing Networks (CPPNs), which are used to generate the images for Picbreeder.orgArchived 2011-07-25 at the Wayback Machine and shapes for EndlessForms.comArchived 2018-11-14 at the Wayback Machine. HyperNEAT has recently been extended to also evolve plastic ANNs and to evolve the location of every neuron in the network.

The promoter based genetic algorithm (PBGA) is a genetic algorithm for neuroevolution developed by F. Bellas and R.J. Duro in the Integrated Group for Engineering Research (GII) at the University of Coruña, in Spain. It evolves variable size feedforward artificial neural networks (ANN) that are encoded into sequences of genes for constructing a basic ANN unit. Each of these blocks is preceded by a gene promoter acting as an on/off switch that determines if that particular unit will be expressed or not.

<span class="mw-page-title-main">Meta-optimization</span>

In numerical optimization, meta-optimization is the use of one optimization method to tune another optimization method. Meta-optimization is reported to have been used as early as in the late 1970s by Mercer and Sampson for finding optimal parameter settings of a genetic algorithm.

Lee Altenberg is an American theoretical biologist. He is on the faculty of the Departments of Information and Computer Sciences and of Mathematics at the University of Hawaiʻi at Mānoa. He is best known for his work that helped establish the evolution of evolvability and modularity in the genotype–phenotype map as areas of investigation in evolutionary biology, for moving theoretical concepts between the fields of evolutionary biology and evolutionary computation, and for his mathematical unification and generalization of modifier gene models for the evolution of biological information transmission, putting under a single mathematical framework the evolution of mutation rates, recombination rates, sexual reproduction rates, and dispersal rates.

Soft computing is an umbrella term used to describe types of algorithms that produce approximate solutions to unsolvable high-level problems in computer science. Typically, traditional hard-computing algorithms heavily rely on concrete data and mathematical models to produce solutions to problems. Soft computing was coined in the late 20th century. During this period, revolutionary research in three fields greatly impacted soft computing. Fuzzy logic is a computational paradigm that entertains the uncertainties in data by using levels of truth rather than rigid 0s and 1s in binary. Next, neural networks which are computational models influenced by human brain functions. Finally, evolutionary computation is a term to describe groups of algorithm that mimic natural processes such as evolution and natural selection.

Kenneth Owen Stanley is an artificial intelligence researcher, author, and former professor of computer science at the University of Central Florida known for creating the Neuroevolution of augmenting topologies (NEAT) algorithm. He coauthored Why Greatness Cannot Be Planned: The Myth of the Objective with Joel Lehman which argues for the existence of the "objective paradox", a paradox which states that "soon as you create an objective, you ruin your ability to reach it". While a professor at the University of Central Florida, he was the director of the Evolutionary Complexity Research Group (EPlex) which led the development of Galactic Arms Race. He also developed the HyperNEAT, CPPNs, and novelty search algorithms. He also co-founded Geometric Intelligence, an AI research firm, in 2015.

References

  1. ↑ Stanley, Kenneth O. (2017-07-13). "Neuroevolution: A different kind of deep learning". O'Reilly Media. Retrieved 2017-09-04.
  2. ↑ Risi, Sebastian; Togelius, Julian (2017). "Neuroevolution in Games: State of the Art and Open Challenges". IEEE Transactions on Computational Intelligence and AI in Games. 9: 25–41. arXiv: 1410.7326 . doi:10.1109/TCIAIG.2015.2494596. S2CID   11245845.
  3. ↑ Togelius, Julian; Schaul, Tom; Schmidhuber, Jürgen; Gomez, Faustino (2008). "Countering Poisonous Inputs with Memetic Neuroevolution". Parallel Problem Solving from Nature – PPSN X. Lecture Notes in Computer Science. Vol. 5199. pp. 610–619. doi:10.1007/978-3-540-87700-4_61. ISBN   978-3-540-87699-1.
  4. ↑ Hutson, Matthew (11 January 2018). "Artificial intelligence can 'evolve' to solve problems". Science. doi:10.1126/science.aas9715.
  5. ↑ Whitelam, Stephen; Selin, Viktor; Park, Sang-Won; Tamblyn, Isaac (2 November 2021). "Correspondence between neuroevolution and gradient descent". Nature Communications. 12 (1): 6317. arXiv: 2008.06643 . Bibcode:2021NatCo..12.6317W. doi:10.1038/s41467-021-26568-2. PMC   8563972 . PMID   34728632.
  6. 1 2 3 Kassahun, Yohannes; Sommer, Gerald; Edgington, Mark; Metzen, Jan Hendrik; Kirchner, Frank (2007), "Common genetic encoding for both direct and indirect encodings of networks", Genetic and Evolutionary Computation Conference, ACM Press, pp. 1029–1036, CiteSeerX   10.1.1.159.705
  7. 1 2 Gauci, Stanley (2007), "Generating Large-Scale Neural Networks Through Discovering Geometric Regularities" (PDF), Genetic and Evolutionary Computation Conference, New York, NY: ACM
  8. 1 2 Gruau, Frédéric; I, L'universite Claude Bernard-lyon; Doctorat, Of A. Diplome De; Demongeot, M. Jacques; Cosnard, Examinators M. Michel; Mazoyer, M. Jacques; Peretto, M. Pierre; Whitley, M. Darell (1994). Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm. CiteSeerX   10.1.1.29.5939 .
  9. ↑ Clune, J.; Stanley, Kenneth O.; Pennock, R. T.; Ofria, C. (June 2011). "On the Performance of Indirect Encoding Across the Continuum of Regularity". IEEE Transactions on Evolutionary Computation. 15 (3): 346–367. CiteSeerX   10.1.1.375.6731 . doi:10.1109/TEVC.2010.2104157. ISSN   1089-778X. S2CID   3008628.
  10. 1 2 Risi, Sebastian; Stanley, Kenneth O. (October 2012). "An Enhanced Hypercube-Based Encoding for Evolving the Placement, Density, and Connectivity of Neurons". Artificial Life. 18 (4): 331–363. doi: 10.1162/ARTL_a_00071 . PMID   22938563. S2CID   3256786.
  11. 1 2 Stanley, Kenneth O.; Miikkulainen, Risto (April 2003). "A Taxonomy for Artificial Embryogeny". Artificial Life. 9 (2): 93–130. doi:10.1162/106454603322221487. PMID   12906725. S2CID   2124332.
  12. ↑ Ronald, Edmund; Schoenauer, March (1994), "Genetic Lander: An experiment in accurate neuro-genetic control", PPSN III 1994 Parallel Programming Solving from Nature, pp. 452–461, CiteSeerX   10.1.1.56.3139
  13. ↑ Angeline, P.J.; Saunders, G.M.; Pollack, J.B. (January 1994). "An evolutionary algorithm that constructs recurrent neural networks". IEEE Transactions on Neural Networks. 5 (1): 54–65. CiteSeerX   10.1.1.64.1853 . doi:10.1109/72.265960. PMID   18267779. S2CID   44767.
  14. ↑ Yao, X.; Liu, Y. (May 1997). "A new evolutionary system for evolving artificial neural networks". IEEE Transactions on Neural Networks. 8 (3): 694–713. doi:10.1109/72.572107. PMID   18255671.
  15. ↑ Stanley, Kenneth O.; Bryant, Bobby D.; Miikkulainen, Risto (December 2005). "Real-Time Neuroevolution in the NERO Video Game" (PDF).
  16. ↑ Stanley, Kenneth O.; Miikkulainen, Risto (June 2002). "Evolving Neural Networks through Augmenting Topologies". Evolutionary Computation. 10 (2): 99–127. CiteSeerX   10.1.1.638.3910 . doi:10.1162/106365602320169811. PMID   12180173. S2CID   498161.
  17. ↑ Kassahun, Yohannes; Sommer, Gerald (April 2005), "Efficient reinforcement learning through evolutionary acquisition of neural topologies" (PDF), 13th European Symposium on Artificial Neural Networks, Bruges, Belgium, pp. 259–266{{citation}}: CS1 maint: location missing publisher (link)
  18. ↑ Siebel, Nils T.; Sommer, Gerald (17 October 2007). "Evolutionary reinforcement learning of artificial neural networks". International Journal of Hybrid Intelligent Systems. 4 (3): 171–183. doi:10.3233/his-2007-4304.
  19. ↑ Rempis, Christian Wilhelm (2012). Evolving Complex Neuro-Controllers with Interactively Constrained Neuro-Evolution (Thesis).
  20. ↑ Sher, Gene I. (2013). Handbook of Neuroevolution Through Erlang. doi:10.1007/978-1-4614-4463-3. ISBN   978-1-4614-4462-6. S2CID   21777855.
  21. ↑ Vargas, Danilo Vasconcellos; Murata, Junichi (2019). "Spectrum-Diverse Neuroevolution With Unified Neural Models". IEEE Transactions on Neural Networks and Learning Systems. 28 (8): 1759–1773. arXiv: 1902.06703 . Bibcode:2019arXiv190206703V. doi:10.1109/TNNLS.2016.2551748. PMID   28113564. S2CID   206757620.
  22. ↑ Edlund, Jeffrey; Chaumont, Nicolas; Hintze, Arend; Koch, Christof; Tononi, Giulio; Adami, Christoph (2011). "Integrated Information Increases with Fitness in the Evolution of Animats". PLOS Computational Biology. 7 (10): e1002236. arXiv: 1103.1791 . Bibcode:2011PLSCB...7E2236E. doi: 10.1371/journal.pcbi.1002236 . PMC   3197648 . PMID   22028639.
  23. ↑ Rostami, Shahin; Neri, Ferrante (June 2017). "A fast hypervolume driven selection mechanism for many-objective optimisation problems". Swarm and Evolutionary Computation. 34: 50–67. doi:10.1016/j.swevo.2016.12.002. hdl: 2086/13102 .
  24. ↑ Shenfield, Alex; Rostami, Shahin (2017). "Multi-objective evolution of artificial neural networks in multi-class medical diagnosis problems with class imbalance" (PDF). 2017 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB). pp. 1–8. doi:10.1109/CIBCB.2017.8058553. ISBN   978-1-4673-8988-4. S2CID   22674515.
  25. ↑ Di Biasi, Luigi; De Marco, Fabiola; Auriemma Citarella, Alessia; Barra, Paola; Piotto Piotto, Stefano; Tortora, Genoveffa (2023). "Hybrid Approach for the Design of CNNS Using Genetic Algorithms for Melanoma Classification". In Rousseau, Jean-Jacques; Kapralos, Bill (eds.). Pattern Recognition, Computer Vision, and Image Processing. ICPR 2022 International Workshops and Challenges. Lecture Notes in Computer Science. Vol. 13643. Cham: Springer Nature Switzerland. pp. 514–528. doi:10.1007/978-3-031-37660-3_36. ISBN   978-3-031-37660-3.
  26. ↑ Assunção, Filipe; Lourenço, Nuno; Ribeiro, Bernardete; Machado, Penousal (June 2021). "Fast-DENSER: Fast Deep Evolutionary Network Structured Representation". SoftwareX. 14: 100694. Bibcode:2021SoftX..1400694A. doi:10.1016/j.softx.2021.100694. hdl: 10316/100856 .
  27. ↑ Vinhas, Adriano; Correia, João; Machado, Penousal (2024-06-20), Towards evolution of Deep Neural Networks through contrastive Self-Supervised learning, arXiv: 2406.14525
  28. ↑ Cortês, Gabriel; Lourenço, Nuno; Machado, Penousal (2024), Smith, Stephen; Correia, João; Cintrano, Christian (eds.), "Towards Physical Plausibility in Neuroevolution Systems", Applications of Evolutionary Computation, vol. 14635, Cham: Springer Nature Switzerland, pp. 76–90, doi:10.1007/978-3-031-56855-8_5, ISBN   978-3-031-56854-1 , retrieved 2024-06-21
  29. ↑ Lourenço, Nuno; Assunção, Filipe; Pereira, Francisco B.; Costa, Ernesto; Machado, Penousal (2018), Ryan, Conor; O'Neill, Michael; Collins, JJ (eds.), "Structured Grammatical Evolution: A Dynamic Approach", Handbook of Grammatical Evolution, Cham: Springer International Publishing, pp. 137–161, doi:10.1007/978-3-319-78717-6_6, ISBN   978-3-319-78717-6 , retrieved 2024-06-21
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.