NeuroEvolution

NeuroEvolution is a research field regrouping all techniques by which an Artificial Neural Network (ANN) can be made “better” via an Evolutionary approach with either direct or indirect encodings. Better, refers to the comparison, through a (multi-objective) fitness function, of performance between individuals, either on a population or species level.

The vagueness in the definition above stems from the variety of approaches taken by researcher in the field: from the evolution weights in fixed, fully-connected topologies to the indirect encoding of emerging structures in large-scale brains. In the context of my research, NeuroEvolution implies the evolution of at least the network’s topology and weights. To that end, I rely heavily on ES-HyperNEAT1 which is both a convoluted indirect encoding for neural networks and an evolutionary algorithm with built-in speciation features.

Field overview

ANNs are built upon the initial definition of the formal neuron2 and its subsequent use in perceptrons. Following the AI Winter3-6, they gained a renewed interest thanks to backpropagation7. However, ANNs again fell into disuse into mainstream Machine Learning (ML) until the beginning of the 90’s with the birth of the field of NeuroEvolution (e.g. Montana et al.) although it was not named as such right away.

In the following decade, multiple researchers led similar investigation leading to the field’s rapid growth with a multitude of approaches for both the encoding and evolution9-19. For an overview of early-stage works on NeuroEvolution refer to Branke et al. and Xin Yao et al..

In the early 2000’s a seminal contribution was made with NEAT22 (NeuroEvolution through Augmenting Topologies) which described an innovative evolutionary algorithm and a direct encoding for neural networks. To solve the common problem of competing conventions, the authors introduced historical markings in their genotypes which tracked mutations by assigning them with unique identifiers. This made it possible to implement a more robust crossover operator that used said markings to align genotypic elements before combining them. Another advantage was the built-in speciation capabilities which also leverage the historical markings to provide a genetic distance metrics between individuals, allowing the clustering of similar individuals into independent niches. As these individuals only compete inside their niches, innovation is more preserved than in open population where suboptimal candidates would be discarded despite their potential.

However, as NEAT uses a direct encoding, it is not scalable to even medium-sized input/output spaces (> 100 neurons) due to the combinatorial explosion of optimizing every neuron and connection through a practically infinite phenotypic space. A solution to that was brought on by HyperNEAT23 which uses a Composite Pattern-Producing Network24 (CPPN) to encode a pattern of connectivity, instead of each individual weight. This indirect encoding is made possible by the CPPN, an \(\mathbb{R}^{2n} \to \mathbb{R}\) function mapping two coordinates in \(\mathbb{R}^n\) to a connection weight. Through the combination of each internal nodes’ elementary function (\(sin(x), exp^x, |x|, ...\)) a CPPN is powerfully expressive, allowing the discovery of repetitions, symmetries or repetitions with variations. Furthermore, as it is independent on the number of neurons, it is well suited for used in large-scale networks where direct encodings would struggle to explore efficiently such a high dimensional space. In case of tasks where the geometry of e.g. a robot is relevant to solving more efficiently said task, the use of an indirect encoding that leverages such geometrical relationship has been found quite useful25.

In most cases the CPPN is more complex than in its initial definition. In my usual implementations it is more often \(\mathbb{R}^{2n+2} \to \mathbb{R}^3\), where the two additional inputs are the euclidian distance between the two coordinates, so that the CPPN does not have to discover it by itself, and a bias, to ensure potential activation for null coordinates. The two additional outputs are the Level Of Expression26 (LEO) which a binary flag stating whether a connection should be made and the per-neuron bias. In the former case, it has been traditionally assumed that under a specific connection weight threshold, the connection would be disabled and the weight scaled accordingly. While usable, in practice it is often useful to decouple both information (weight and connection). The latter is used to generate every neurons internal bias by querying the CPPN with the corresponding neuron’s position as a source and \(\vec 0\) as an output.

Finally, one major problem remained in HyperNEAT, namely that the hidden neurons had to be placed manually by the experimenter. The obvious issue caused by this limitation is that it drastically reduces the ANNs’ potential for growth as it can never have more computational power than that envisioned by the experimenter. Through the Evolvable Substrate1 extension to HyperNEAT, the hidden neurons are instead discovered by quantization of the CPPN’s patterns. In short, areas of high variance (read complex motif) are those where hidden neurons will be instantiated. This way, the experimenter only job is to place the input and output neurons at appropriate location, with respect to the robot’s geometry, and ES-HyperNEAT would generate a (potentially) complex ANN. One that would grow more complex as generations go by.

To conclude on this (brief) overview of the field, the inquisitive reader is referred to more recent literature reviews27,28.

In my research

NeuroEvolution is central to my research lines since early 2020, and has been a personal interest for much longer. As illustrated above, it is a subject I find fascinating by the opportunity it offers to create intelligent Artificial Life. Not Artificial Intelligence, mind. Autonomous, self-sufficient life forms made, not from biology, but from science.

While we quite far off that lovely objective, preliminary research into the mechanism of spontaneous self-organisation in ANNs already show promising results with respect to primitive mental states29, communication30 or coordination31. Thanks to their emerging properties, one can investigate a plethora of phenomenon, if these ANNs are faced with sufficiently complex environments and given enough evolutionqry budget32.

The following sections, highlight some prominent aspects of from my recent research.

ABrain

As mentioned in the projects page, ABrain is a C++ library with a Python API for the evolution of Artificial Neural Networks via indirect encoding. In practice, it is a mostly faithful implementation of ES-HyperNEAT and related algorithms.
Read more

VfMRI

Artificial Neural Networks take a lot of inspiration from biology although with much abstraction. Still even with such abstractions, it is not a trivial thing to understand exactly how anything but the simplest of perceptron operates. This makes ANNs, amongst others, a "black box" model because all we know is what comes in and what comes out with next to no knowledge about the internals.
Read more

Personal notes

Miconi et al. Differentiable indirect plasticity (useful?)

References

Risi, S. & Stanley, K. O. An Enhanced Hypercube-Based Encoding for Evolving the Placement, Density, and Connectivity of Neurons. Artificial Life 18, 331–363 (2012).
McCulloch, W. S. & Pitts, W. A Logical Calculus of the Ideas Immanent in Nervous Activity. The Bulletin of Mathematical Biophysics 5, 115–133 (1943).
Rosenblatt, F. The Perceptron - A Perceiving and Recognizing Automaton. Concours médical (1957).
Orbach, J. Principles of Neurodynamics. Perceptrons and the Theory of Brain Mechanisms. Archives of General Psychiatry 7, 218 (1962).
Minsky, M. & Papert, S. Perceptrons: An Introduction to Computational Geometry. (1969).
Lighthill, J. Artificial Intelligence: A General Survey. http://www.chilton-computing.org.uk/inf/literature/reports/lighthill_report/p001.htm (1972).
Rumelhart, D. E., Hinton, G. E. & Williams, R. J. Learning Representations by Back-Propagating Errors. Nature 323, 533–536 (1986).
Montana, D. J. & Davis, L. Training Feedforward Neural Networks Using Genetic Algorithms. Proceedings of the 11th International Joint Conference on Artificial intelligence - Volume 1 89, 762–767 (1989).
Dasgupta, D. & McGregor, D. R. Designing Application-Specific Neural Networks Using the Structured Genetic Algorithm. in [Proceedings] COGANN-92: International Workshop on Combinations of Genetic Algorithms and Neural Networks 87–96 (IEEE Comput. Soc. Press, 1992). doi:10.1109/COGANN.1992.273946.
Fullmer, B. & Miikkulainen, R. Using Marker-Based Genetic Encoding of Neural Networks to Evolve Finite-State Behaviour. Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life 255–262 (1992).
Braun, H. & Weisbrod, J. Evolving Neural Feedforward Networks. in Artificial Neural Nets and Genetic Algorithms 25–32 (Springer Vienna, Vienna, 1993). doi:10.1007/978-3-7091-7533-0_5.
Mandischer, M. Representation and Evolution of Neural Networks. in Artificial Neural Nets and Genetic Algorithms 643–649 (Springer Vienna, Vienna, 1993). doi:10.1007/978-3-7091-7533-0_93.
Zhang, B.-tak & Heinz, M. Evolving Optimal Neural Networks Using Genetic Algorithms with Occam ’ s Razor 1 Introduction. Complex Systems 7, 199–220 (1993).
Angeline, P. J., Saunders, G. M. & Pollack, J. B. An Evolutionary Algorithm That Constructs Recurrent Neural Networks. IEEE Transactions on Neural Networks 5, 54–65 (1994).
Maniezzo, V. Genetic Evolution of the Topology and Weight Distribution of Neural Networks. IEEE Transactions on Neural Networks 5, 39–53 (1994).
Gruau, F., Whitley, D. & Pyeatt, L. A Comparison between Cellular Encoding and Direct Encoding for Genetic Neural Networks. in Genetic Programming 1996 vol. 1 (The MIT Press, 1996).
Chi-Ho Lee & Jong-Hwan Kim. Evolutionary Ordered Neural Network with a Linked-List Encoding Scheme. in Proceedings of IEEE International Conference on Evolutionary Computation 665–669 (IEEE, 1996). doi:10.1109/ICEC.1996.542680.
Opitz, D. W. & Shavlik, J. W. Connectionist Theory Refinement: Genetically Searching the Space of Network Topologies. Journal of Artificial Intelligence Research 6, 177–209 (1997).
Figueira Pujol, J. C. & Poli, R. Evolving the Topology and the Weights of Neural Networks Using a Dual Representation. Applied Intelligence 8, 73–84 (1998).
Branke, J. Evolutionary Algorithms for Neural Network Design and Training. Workshop on Genetic Algorithms and its Applications 1–21 (1995).
Xin Yao. Evolving Artificial Neural Networks. Proceedings of the IEEE 87, 1423–1447 (1999).
Stanley, K. O. & Miikkulainen, R. Efficient Evolution of Neural Network Topologies. Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600) 2, 1757–1762 (2002).
Stanley, K. O., D’Ambrosio, D. B. & Gauci, J. A Hypercube-Based Encoding for Evolving Large-Scale Neural Networks. Artificial Life 15, 185–212 (2009).
Stanley, K. O. Compositional Pattern Producing Networks: A Novel Abstraction of Development. Genetic Programming and Evolvable Machines 8, 131–162 (2007).
Clune, J., Stanley, K. O., Pennock, R. T. & Ofria, C. On the Performance of Indirect Encoding across the Continuum of Regularity. IEEE Transactions on Evolutionary Computation 15, 346–367 (2011).
Verbancsics, P. & Stanley, K. O. Constraining Connectivity to Encourage Modularity in HyperNEAT. Genetic and Evolutionary Computation Conference, GECCO’11 1483–1490 (2011) doi:10.1145/2001576.2001776.
Stanley, K. O., Clune, J., Lehman, J. & Miikkulainen, R. Designing Neural Networks through Neuroevolution. Nature Machine Intelligence 1, 24–35 (2019).
Baldominos, A., Saez, Y. & Isasi, P. On the Automated, Evolutionary Design of Neural Networks: Past, Present, and Future. Neural Computing and Applications 32, 519–545 (2020).
Godin-Dubois, K., Cussat-Blanc, S. & Duthen, Y. Spontaneous Modular NeuroEvolution Arising from a Life/Dinner Paradox. in The 2021 Conference on Artificial Life 95 (MIT Press, Cambridge, MA, 2021). doi:10.1162/isal_a_00431.
Godin-Dubois, K., Cussat-Blanc, S. & Duthen, Y. On the Benefits of Emergent Communication for Threat Appraisal. in 3rd International Workshop on Agent-Based Modelling of Human Behaviour (Online, 2021).
Godin-Dubois, K., Cussat-Blanc, S. & Duthen, Y. Emergent Communication for Coordination in Teams of Embodied Agents. in 4th International Workshop on Agent-Based Modelling of Human Behaviour (ALife2022) (2022).
Godin-Dubois, K., Cussat-Blanc, S. & Duthen, Y. Explaining the Neuroevolution of Fighting Creatures Through Virtual fMRI. Artificial Life 29, 66–93 (2023).
Miconi, T., Clune, J. & Stanley, K. O. Differentiable Plasticity: Training Plastic Neural Networks with Backpropagation. 35th International Conference on Machine Learning, ICML 2018 8, 5728–5739 (2018).

3.	Rosenblatt, F. The Perceptron - A Perceiving and Recognizing Automaton. Concours médical (1957).
4.	Orbach, J. Principles of Neurodynamics. Perceptrons and the Theory of Brain Mechanisms. Archives of General Psychiatry 7, 218 (1962).
5.	Minsky, M. & Papert, S. Perceptrons: An Introduction to Computational Geometry. (1969).
6.	Lighthill, J. Artificial Intelligence: A General Survey. http://www.chilton-computing.org.uk/inf/literature/reports/lighthill_report/p001.htm (1972).

9.	Dasgupta, D. & McGregor, D. R. Designing Application-Specific Neural Networks Using the Structured Genetic Algorithm. in [Proceedings] COGANN-92: International Workshop on Combinations of Genetic Algorithms and Neural Networks 87–96 (IEEE Comput. Soc. Press, 1992). doi:10.1109/COGANN.1992.273946.
10.	Fullmer, B. & Miikkulainen, R. Using Marker-Based Genetic Encoding of Neural Networks to Evolve Finite-State Behaviour. Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life 255–262 (1992).
11.	Braun, H. & Weisbrod, J. Evolving Neural Feedforward Networks. in Artificial Neural Nets and Genetic Algorithms 25–32 (Springer Vienna, Vienna, 1993). doi:10.1007/978-3-7091-7533-0_5.
12.	Mandischer, M. Representation and Evolution of Neural Networks. in Artificial Neural Nets and Genetic Algorithms 643–649 (Springer Vienna, Vienna, 1993). doi:10.1007/978-3-7091-7533-0_93.
13.	Zhang, B.-tak & Heinz, M. Evolving Optimal Neural Networks Using Genetic Algorithms with Occam ’ s Razor 1 Introduction. Complex Systems 7, 199–220 (1993).
14.	Angeline, P. J., Saunders, G. M. & Pollack, J. B. An Evolutionary Algorithm That Constructs Recurrent Neural Networks. IEEE Transactions on Neural Networks 5, 54–65 (1994).
15.	Maniezzo, V. Genetic Evolution of the Topology and Weight Distribution of Neural Networks. IEEE Transactions on Neural Networks 5, 39–53 (1994).
16.	Gruau, F., Whitley, D. & Pyeatt, L. A Comparison between Cellular Encoding and Direct Encoding for Genetic Neural Networks. in Genetic Programming 1996 vol. 1 (The MIT Press, 1996).
17.	Chi-Ho Lee & Jong-Hwan Kim. Evolutionary Ordered Neural Network with a Linked-List Encoding Scheme. in Proceedings of IEEE International Conference on Evolutionary Computation 665–669 (IEEE, 1996). doi:10.1109/ICEC.1996.542680.
18.	Opitz, D. W. & Shavlik, J. W. Connectionist Theory Refinement: Genetically Searching the Space of Network Topologies. Journal of Artificial Intelligence Research 6, 177–209 (1997).
19.	Figueira Pujol, J. C. & Poli, R. Evolving the Topology and the Weights of Neural Networks Using a Dual Representation. Applied Intelligence 8, 73–84 (1998).

27.	Stanley, K. O., Clune, J., Lehman, J. & Miikkulainen, R. Designing Neural Networks through Neuroevolution. Nature Machine Intelligence 1, 24–35 (2019).
28.	Baldominos, A., Saez, Y. & Isasi, P. On the Automated, Evolutionary Design of Neural Networks: Past, Present, and Future. Neural Computing and Applications 32, 519–545 (2020).