40,81 €
Mehr erfahren.
- Herausgeber: Packt Publishing
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Increase the performance of various neural network architectures using NEAT, HyperNEAT, ES-HyperNEAT, Novelty Search, SAFE, and deep neuroevolution
Key Features
- Implement neuroevolution algorithms to improve the performance of neural network architectures
- Understand evolutionary algorithms and neuroevolution methods with real-world examples
- Learn essential neuroevolution concepts and how they are used in domains including games, robotics, and simulations
Book Description
Neuroevolution is a form of artificial intelligence learning that uses evolutionary algorithms to simplify the process of solving complex tasks in domains such as games, robotics, and the simulation of natural processes. This book will give you comprehensive insights into essential neuroevolution concepts and equip you with the skills you need to apply neuroevolution-based algorithms to solve practical, real-world problems.
You'll start with learning the key neuroevolution concepts and methods by writing code with Python. You'll also get hands-on experience with popular Python libraries and cover examples of classical reinforcement learning, path planning for autonomous agents, and developing agents to autonomously play Atari games. Next, you'll learn to solve common and not-so-common challenges in natural computing using neuroevolution-based algorithms. Later, you'll understand how to apply neuroevolution strategies to existing neural network designs to improve training and inference performance. Finally, you'll gain clear insights into the topology of neural networks and how neuroevolution allows you to develop complex networks, starting with simple ones.
By the end of this book, you will not only have explored existing neuroevolution-based algorithms, but also have the skills you need to apply them in your research and work assignments.
What you will learn
- Discover the most popular neuroevolution algorithms – NEAT, HyperNEAT, and ES-HyperNEAT
- Explore how to implement neuroevolution-based algorithms in Python
- Get up to speed with advanced visualization tools to examine evolved neural network graphs
- Understand how to examine the results of experiments and analyze algorithm performance
- Delve into neuroevolution techniques to improve the performance of existing methods
- Apply deep neuroevolution to develop agents for playing Atari games
Who this book is for
This book is for machine learning practitioners, deep learning researchers, and AI enthusiasts who are looking to implement neuroevolution algorithms from scratch. Working knowledge of the Python programming language and basic knowledge of deep learning and neural networks are mandatory.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 427
Veröffentlichungsjahr: 2019
Ähnliche
Hands-On Neuroevolution with Python
Copyright © 2019 Packt Publishing
All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.
Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book.
Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.
Commissioning Editor: Sunith ShettyAcquisition Editor: Nelson MorrisContent Development Editor: Pratik AndradeSenior Editor: Ayaan HodaTechnical Editor: Prachi SawantCopy Editor: Safis EditingLanguage Support Editor: Safis EditingProject Coordinator: Anish DanielProofreader: Safis EditingIndexer: Priyanka DhadkeProduction Designer: Nilesh Mohite
First published: December 2019
Production reference: 1231219
Published by Packt Publishing Ltd. Livery Place 35 Livery Street Birmingham B3 2PB, UK.
ISBN 978-1-83882-491-4
www.packt.com
Packt.com
Subscribe to our online digital library for full access to over 7,000 books and videos, as well as industry leading tools to help you plan your personal development and advance your career. For more information, please visit our website.
Why subscribe?
Spend less time learning and more time coding with practical eBooks and Videos from over 4,000 industry professionals
Improve your learning with Skill Plans built especially for you
Get a free eBook or video every month
Fully searchable for easy access to vital information
Copy and paste, print, and bookmark content
Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.packt.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at [email protected] for more details.
At www.packt.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on Packt books and eBooks.
Contributors
About the author
Iaroslav Omelianenko occupied the position of CTO and research director for more than a decade. He is an active member of the research community and has published several research papers at arXiv, ResearchGate, Preprints, and more. He started working with applied machine learning by developing autonomous agents for mobile games more than a decade ago. For the last 5 years, he has actively participated in research related to applying deep machine learning methods for authentication, personal traits recognition, cooperative robotics, synthetic intelligence, and more. He is an active software developer and creates open source neuroevolution algorithm implementations in the Go language.
About the reviewers
Alan McIntyre is a principal software architect at CodeReclaimers, LLC, where he provides custom software design and development services for technical computing applications, including computational geometry, computer vision, and machine learning. He has previously worked as a software engineer at General Electric, Microsoft, and multiple start-ups.
Unsal Gokdag has been working full time as a senior data scientist in logistics since 2017, and had previously worked as a research and development engineer in 2013.
He is currently doing his PhD in a comparison of machine learning algorithms for image despeckling and the classification of polarimetric SAR images. His past experience includes work in machine learning, computer vision, and bioinformatics. He was introduced to the NEAT algorithm in this bachelor's thesis and has been interested in evolutionary algorithms since. He is currently residing in Germany.
Packt is searching for authors like you
If you're interested in becoming an author for Packt, please visit authors.packtpub.com and apply today. We have worked with thousands of developers and tech professionals, just like you, to help them share their insight with the global tech community. You can make a general application, apply for a specific hot topic that we are recruiting an author for, or submit your own idea.
Table of Contents
Title Page
Copyright and Credits
Hands-On Neuroevolution with Python
Dedication
About Packt
Why subscribe?
Contributors
About the author
About the reviewers
Packt is searching for authors like you
Preface
Who this book is for
What this book covers
To get the most out of this book
Download the example code files
Download the color images
Conventions used
Get in touch
Reviews
Section 1: Fundamentals of Evolutionary Computation Algorithms and Neuroevolution Methods
Overview of Neuroevolution Methods
Evolutionary algorithms and neuroevolution-based methods
Genetic operators
Mutation operator
Crossover operator
Genome encoding schemes
Direct genome encoding
Indirect genome encoding
Coevolution
Modularity and hierarchy
NEAT algorithm overview
NEAT encoding scheme
Structural mutations
Crossover with an innovation number
Speciation
Hypercube-based NEAT
Compositional Pattern Producing Networks
Substrate configuration
Evolving connective CPPNs and the HyperNEAT algorithm
Evolvable-Substrate HyperNEAT
Information patterns in the hypercube
Quadtree as an effective information extractor
ES-HyperNEAT algorithm
Novelty Search optimization method
Novelty Search and natural evolution
Novelty metric
Summary
Further reading
Python Libraries and Environment Setup
Suitable Python libraries for neuroevolution experiments
NEAT-Python
NEAT-Python usage example
PyTorch NEAT
PyTorch NEAT usage example
MultiNEAT
MultiNEAT usage example
Deep Neuroevolution
Comparing Python neuroevolution libraries
Environment setup
Pipenv
Virtualenv
Anaconda
Summary
Section 2: Applying Neuroevolution Methods to Solve Classic Computer Science Problems
Using NEAT for XOR Solver Optimization
Technical requirements
XOR problem basics
The objective function for the XOR experiment
Hyperparameter selection
NEAT section
DefaultStagnation section
DefaultReproduction section
DefaultSpeciesSet section
DefaultGenome section
XOR experiment hyperparameters
Running the XOR experiment
Environment setup
XOR experiment source code
Running the experiment and analyzing the results
Exercises
Summary
Pole-Balancing Experiments
Technical requirements
The single-pole balancing problem
The equations of motion of the single-pole balancer
State equations and control actions
The interactions between the solver and the simulator
Objective function for a single-pole balancing experiment
Cart-pole apparatus simulation
The simulation cycle
Genome fitness evaluation
The single-pole balancing experiment
Hyperparameter selection
Working environment setup
The experiment runner implementation
Function to evaluate the fitness of all genomes in the population
The experiment runner function
Running the single-pole balancing experiment
Exercises
The double-pole balancing problem
The system state and equations of motion
Reinforcement signal
Initial conditions and state update
Control actions
Interactions between the solver and the simulator
Objective function for a double-pole balancing experiment
Double-pole balancing experiment
Hyperparameter selection
Working environment setup
The experiment runner implementation
Running the double-pole balancing experiment
Exercises
Summary
Autonomous Maze Navigation
Technical requirements
Maze navigation problem
Maze simulation environment
Maze-navigating agent
Maze simulation environment implementation
Sensor data generation
Agent position update
Agents records store
The agent record visualization
Objective function definition using the fitness score
Running the experiment with a simple maze configuration
Hyperparameter selection
Maze configuration file
Working environment setup
The experiment runner implementation
Genome fitness evaluation
Running the simple maze navigation experiment
Agent record visualization
Exercises
Running the experiment with a hard-to-solve maze configuration
Hyperparameter selection
Working environment setup and experiment runner implementation
Running the hard-to-solve maze navigation experiment
Exercises
Summary
Novelty Search Optimization Method
Technical requirements
The NS optimization method
NS implementation basics
NoveltyItem
NoveltyArchive
The fitness function with the novelty score
The novelty score
The novelty metric
Fitness function
The population fitness evaluation function
The individual fitness evaluation function
Experimenting with a simple maze configuration
Hyperparameter selection
Working environment setup
The experiment runner implementation
The trials cycle
The experiment runner function
Running the simple maze navigation experiment with NS optimization
Agent record visualization
Exercise 1
Experimenting with a hard-to-solve maze configuration
Hyperparameter selection and working environment setup
Running the hard-to-solve maze navigation experiment
Exercise 2
Summary
Section 3: Advanced Neuroevolution Methods
Hypercube-Based NEAT for Visual Discrimination
Technical requirements
Indirect encoding of ANNs with CPPNs
CPPN encoding
Hypercube-based NeuroEvolution of Augmenting Topologies
Visual discrimination experiment basics
Objective function definition
Visual discrimination experiment setup
Visual discriminator test environment
Visual field definition
Visual discriminator environment
Experiment runner
The experiment runner function
Initializing the first CPPN genome population
Running the neuroevolution over the specified number of generations
Saving the results of the experiment
The substrate builder function
Fitness evaluation
Visual discrimination experiment
Hyperparameter selection
Working environment setup
Running the visual discrimination experiment
Exercises
Summary
ES-HyperNEAT and the Retina Problem
Technical requirements
Manual versus evolution-based configuration of the topography of neural nodes
Quadtree information extraction and ES-HyperNEAT basics
Modular retina problem basics
Objective function definition
Modular retina experiment setup
The initial substrate configuration
Test environment for the modular retina problem
The visual object definition
The retina environment definition
The function to create a dataset with all the possible visual objects
The function to evaluate the detector ANN against two specific visual objects
Experiment runner
The experiment runner function
The substrate builder function
Fitness evaluation
The eval_genomes function
The eval_individual function
Modular retina experiment
Hyperparameter selection
Working environment setup
Running the modular retina experiment
Exercises
Summary
Co-Evolution and the SAFE Method
Technical requirements
Common co-evolution strategies
SAFE method
Modified maze experiment
The maze-solving agent
The maze environment
Fitness function definition
Fitness function for maze solvers
Fitness function for the objective function candidates
Modified Novelty Search
The _add_novelty_item function
The evaluate_novelty_score function
Modified maze experiment implementation
Creation of co-evolving populations
Creation of the population of the objective function candidates
Creating the population of maze solvers
The fitness evaluation of the co-evolving populations
Fitness evaluation of objective function candidates
The evaluate_obj_functions function implementation
The evaluate_individ_obj_function function implementation
Fitness evaluation of the maze-solver agents
The evaluate_solutions function implementation
The evaluate_individual_solution function implementation
The evaluate_solution_fitness function implementation
The modified maze experiment runner
Modified maze experiment
Hyperparameters for the maze-solver population
Hyperparameters for the objective function candidates population
Working environment setup
Running the modified maze experiment
Exercises
Summary
Deep Neuroevolution
Technical requirements
Deep neuroevolution for deep reinforcement learning
Evolving an agent to play the Frostbite Atari game using deep neuroevolution
The Frostbite Atari game
Game screen mapping into actions
Convolutional layers
The CNN architecture to train the Atari playing agent
The RL training of the game agent
The genome encoding scheme
Genome encoding scheme definition
Genome encoding scheme implementation
The simple genetic algorithm
Training an agent to play the Frostbite game
Atari Learning Environment
The game step function
The game observation function
The reset Atari environment function
RL evaluation on GPU cores
The RLEvalutionWorker class
Creating the network graph
The graph evaluation loop
The asynchronous task runner
The ConcurrentWorkers class
Creating the evaluation workers
Running work tasks and monitoring results
Experiment runner
Experiment configuration file
Experiment runner implementation
Running the Frostbite Atari experiment
Setting up the work environment 
Running the experiment
Frostbite visualization
Visual inspector for neuroevolution
Setting up the work environment
Using VINE for experiment visualization
Exercises
Summary
Section 4: Discussion and Concluding Remarks
Best Practices, Tips, and Tricks
Starting with problem analysis
Preprocessing data
Data standardization
Scaling inputs to a range
Data normalization
Understanding the problem domain
Writing good simulators
Selecting the optimal search optimization method
Goal-oriented search optimization
Mean squared error
Euclidean distance
Novelty Search optimization
Advanced visualization
Tuning hyperparameters
Performance metrics
Precision score
Recall score
F1 score
ROC AUC
Accuracy
Python coding tips and tricks
Coding tips and tricks
Working environment and programming tools
Summary
Concluding Remarks
What we learned in this book
Overview of the neuroevolution methods
Python libraries and environment setup
Using NEAT for XOR solver optimization
Pole-balancing experiments
Autonomous maze navigation
Novelty Search optimization method
Hypercube-based NEAT for visual discrimination
ES-HyperNEAT and the retina problem
Co-evolution and the SAFE method
Deep Neuroevolution
Where to go from here 
Uber AI Labs
alife.org
Open-ended evolution at Reddit
The NEAT Software Catalog
arXiv.org
The NEAT algorithm paper
Summary
Other Books You May Enjoy
Leave a review - let other readers know what you think
Preface
With conventional deep learning methods almost hitting a wall in terms of their capability, more and more researchers have started looking for alternative approaches to train artificial neural networks.
Deep machine learning is extremely effective for pattern recognition, but fails in tasks that require an understanding of context or previously unseen data. Many researchers, including Geoff Hinton, the father of the modern incarnation of deep machine learning, agree that the current approach to designing artificial intelligence systems is no longer able to cope with the challenges currently being faced.
In this book, we discuss a viable alternative to traditional deep machine learning methods—neuroevolution algorithms. Neuroevolution is a family of machine learning methods that use evolutionary algorithms to ease the solving of complex tasks such as games, robotics, and the simulation of natural processes. Neuroevolution algorithms are inspired by the process of natural selection. Very simple artificial neural networks can evolve to become very complex. The ultimate result of neuroevolution is the optimal topology of a network, which makes the model more energy-efficient and more convenient to analyze.
Throughout this book, you will learn about various neuroevolution algorithms and get practical skills in using them to solve different computer science problems—from classic reinforcement learning to building agents for autonomous navigation through a labyrinth. Also, you will learn how neuroevolution can be used to train deep neural networks to create an agent that can play classic Atari games.
This book aims to give you a solid understanding of neuroevolution methods by implementing various experiments using step-by-step guidance. It covers practical examples in areas such as games, robotics, and the simulation of natural processes, using real-world examples and datasets to help you better understand the concepts explored. After reading this book, you will have everything you need to apply neuroevolution methods to other tasks similar to the experiments presented.
In writing this book, my goal is to provide you with knowledge of cutting-edge technology that is a vital alternative to traditional deep learning. I hope that the application of neuroevolution algorithms in your projects will allow you to solve your currently intractable problems in an elegant and energy-efficient way.
Who this book is for
This book is for machine learning practitioners, deep learning researchers, and AI enthusiasts who are looking to implement neuroevolution algorithms from scratch. You will learn how to apply these algorithms to various sets of real-world problems. You will learn how neuroevolution methods can optimize the process of training artificial neural networks. You will become familiar with the core concepts of neuroevolution and get the necessary practical skills to use it in your work and experiments. A working knowledge of Python and deep learning and neural network basics is mandatory.
What this book covers
Chapter 1, Overview of Neuroevolution Methods, introduces the core concepts of genetic algorithms, such as genetic operators and genome encoding schemes.
Chapter 2, Python Libraries and Environment Setup, discusses the practical aspects of neuroevolution methods. This chapter provides the pros and cons of popular Python libraries that provide implementations of the NEAT algorithm and its extensions.
Chapter 3, Using NEAT for XOR Solver Optimization, is where you start experimenting with the NEAT algorithm by implementing a solver for a classical computer science problem.
Chapter 4, Pole-Balancing Experiments, is where you continue with experiments related to the classic problems of computer science in the field of reinforcement learning.
Chapter 5, Autonomous Maze Navigation, is where you continue your experiments with neuroevolution through an attempt to create a solver that can find an exit from a maze. You will learn how to implement a simulation of a robot that has an array of sensors to detect obstacles and monitor its position within the maze.
Chapter 6, Novelty Search Optimization Method, is where you use the practical experience gained during the creation of a maze solver in the previous chapter to embark on the path of creating a more advanced solver.
Chapter 7, Hypercube-Based NEAT for Visual Discrimination, introduces you to advanced neuroevolution methods. You'll learn about the indirect genome encoding scheme, which uses Compositional Pattern Producing Networks (CPPNs) to aid with the encoding of large-phenotype ANN topologies.
Chapter 8, ES-HyperNEAT and the Retina Problem, is where you will learn how to select the substrate configuration that is best suited for a specific problem space.
Chapter 9, Co-Evolution and the SAFE Method, is where we discuss how a co-evolution strategy is widely found in nature and could be transferred into the realm of the neuroevolution.
Chapter 10, Deep Neuroevolution, presents you with the concept of Deep Neuroevolution, which can be used to train Deep Artificial Neural Networks (DNNs).
Chapter 11, Best Practices, Tips, and Tricks, teaches you how to start working with whatever problem is at hand, how to tune the hyperparameters of a neuroevolution algorithm, how to use advanced visualization tools, and what metrics can be used for the analysis of algorithm performance.
Chapter 12, Concluding Remarks, summarizes everything you have learned in this book and provides further directions for you to continue your self-education.
To get the most out of this book
A practical knowledge of the Python programming language is essential to work with the examples presented in this book. For better source code understanding, it is preferable to use an IDE that supports Python syntax highlighting and code reference location. If you don't have one installed, you can use Microsoft Visual Studio Code. It is free and cross-platform, and you can download it here: https://code.visualstudio.com.
Python and most of the libraries we discuss in this book are cross-platform, and compatible with Windows, Linux, and macOS. All experiments described in the book are executed from the command line, so make yourself familiar with the terminal console application installed on the OS of your choice.
To complete the experiment described in Chapter 10, Deep Neuroevolution, you need to have access to a modern PC with Nvidia graphics accelerator GeForce GTX 1080Ti or better. This experiment is also better to run in an Ubuntu Linux environment. Ubuntu is a modern Linux-based OS that is free and powerful. Making yourself familiar with it will help you a lot.
Download the example code files
You can download the example code files for this book from your account at www.packt.com. If you purchased this book elsewhere, you can visit www.packtpub.com/support and register to have the files emailed directly to you.
You can download the code files by following these steps:
Log in or register at
www.packt.com
.
Select the
Support
tab.
Click on
Code Downloads
.
Enter the name of the book in the
Search
box and follow the onscreen instructions.
Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:
WinRAR/7-Zip for Windows
Zipeg/iZip/UnRarX for Mac
7-Zip/PeaZip for Linux
The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/Hands-on-Neuroevolution-with-Python. In case there's an update to the code, it will be updated on the existing GitHub repository.
We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!
Download the color images
We also provide a PDF file that has color images of the screenshots/diagrams used in this book. You can download it here: https://static.packt-cdn.com/downloads/9781838824914_ColorImages.pdf.
Get in touch
Feedback from our readers is always welcome.
General feedback: If you have questions about any aspect of this book, mention the book title in the subject of your message and email us at [email protected].
Errata: Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you have found a mistake in this book, we would be grateful if you would report this to us. Please visit www.packtpub.com/support/errata, selecting your book, clicking on the Errata Submission Form link, and entering the details.
Piracy: If you come across any illegal copies of our works in any form on the Internet, we would be grateful if you would provide us with the location address or website name. Please contact us at [email protected] with a link to the material.
If you are interested in becoming an author: If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, please visit authors.packtpub.com.
Reviews
Please leave a review. Once you have read and used this book, why not leave a review on the site that you purchased it from? Potential readers can then see and use your unbiased opinion to make purchase decisions, we at Packt can understand what you think about our products, and our authors can see your feedback on their book. Thank you!
For more information about Packt, please visit packt.com.
Section 1: Fundamentals of Evolutionary Computation Algorithms and Neuroevolution Methods
This section introduces core concepts of evolutionary computation and discusses particulars of neuroevolution-based algorithms and which Python libraries can be used to implement them. You will become familiar with the fundamentals of neuroevolution methods and will get practical recommendations on how to start your experiments. This section provides a basic introduction to the Anaconda package manager for Python as part of your environment setup. This section comprises the following chapters:
Chapter 1
,
Overview of Neuroevolution Methods
Chapter 2
,
Python Libraries and Environment Setup
Overview of Neuroevolution Methods
The concept of artificial neural networks (ANN) was inspired by the structure of the human brain. There was a strong belief that, if we were able to imitate this intricate structure in a very similar way, we would be able to create artificial intelligence. We are still on the road to achieving this. Although we can implement Narrow AI agents, we are still far from creating a Generic AI agent.
This chapter introduces you to the concept of ANNs and the two methods that we can use to train them (the gradient descent with error backpropagation and neuroevolution) so that they learn how to approximate the objective function. However, we will mainly focus on discussing the neuroevolution-based family of algorithms. You will learn about the implementation of the evolutionary process that's inspired by natural evolution and become familiar with the most popular neuroevolution algorithms: NEAT, HyperNEAT, and ES-HyperNEAT. We will also discuss the methods of optimization that we can use to search for final solutions and make a comparison between objective-based search and Novelty Search algorithms. By the end of this chapter, you will have a complete understanding of the internals of neuroevolution algorithms and be ready to apply this knowledge in practice.
In this chapter, we will cover the following topics:
Evolutionary algorithms and neuroevolution-based methods
NEAT algorithm overview
Hypercube-based NEAT
Evolvable-Substrate HyperNEAT
Novelty Search optimization method
Evolutionary algorithms and neuroevolution-based methods
The term artificial neural networks stands for a graph of nodes connected by links where each of the links has a particular weight. The neural node defines a kind of threshold operator that allows the signal to pass only after a specific activation function has been applied. It remotely resembles the way in which neurons in the brain are organized. Typically, the ANN training process consists of selecting the appropriate weight values for all the links within the network. Thus, ANN can approximate any function and can be considered as a universal approximator,which is established by the Universal Approximation Theorem.
For more information on the proof of the Universal Approximation Theorem, take a look at the following papers:
Cybenko, G. (1989)
Approximations by Superpositions of Sigmoidal Functions
,
Mathematics of Control, Signals, and Systems
, 2(4), 303–314.
Leshno, Moshe; Lin, Vladimir Ya.; Pinkus, Allan; Schocken, Shimon (January 1993).
Multilayer feedforward networks with a nonpolynomial activation function can approximate any function
.
Neural Networks
.
6
(6): 861–867.
doi
:
10.1016/S0893-6080(05)80131-5
. (
https://www.sciencedirect.com/science/article/abs/pii/S0893608005801315?via%3Dihub
)
Kurt Hornik (1991)
Approximation Capabilities of Multilayer Feedforward Networks
, Neural Networks, 4(2), 251–257. doi:10.1016/0893-6080(91)90009-T (
https://www.sciencedirect.com/science/article/abs/pii/089360809190009T?via%3Dihub
)
Hanin, B. (2018).
Approximating Continuous Functions by ReLU Nets of Minimal Width
. arXiv preprint arXiv:1710.11278. (
https://arxiv.org/abs/1710.11278
)
Over the past 70 years, many ANN training methods have been proposed. However, the most popular technique that gained fame in this decade was proposed by Jeffrey Hinton. It is based on the backpropagation of prediction error through the network, with various optimization techniques built around the gradient descent of the loss function with respect to connection weights between the network nodes. It demonstrates the outstanding performance of training deep neural networks for tasks related mainly to pattern recognition. However, despite its inherent powers, it has significant drawbacks. One of these drawbacks is that a vast amount of training samples are required to learn something useful from a specific dataset. Another significant disadvantage is the fixed network architecture that's created manually by the experimenter, which results in inefficient use of computational resources. This is due to a significant amount of network nodes not participating in the inference process. Also, backpropagation-based methods have problems with transferring the acquired knowledge to other similar domains.
Alongside backpropagation methods, there are very promising evolutionary algorithms that can address the aforementioned problems. These bio-inspired techniques draw inspiration from Darwin's theory of evolution and use natural evolution abstractions to create artificial neural networks. The basic idea behind neuroevolution is to produce the ANNs by using stochastic, population-based search methods. It is possible to evolve optimal architectures of neural networks, which accurately address the specific tasks using the evolutionary process. As a result, compact and energy-efficient networks with moderate computing power requirements can be created. The evolutionary process is executed by applying genetic operators (mutation, crossover) to the population of chromosomes (genetically encoded representations of ANNs/solutions) over many generations. The central belief is that since this is in biological systems, subsequent generations will be suited to withstand the generational pressure that's expressed by the objective function, that is, they will become better approximators of the objective function.
Next, we will discuss the basic concepts of genetic algorithms. You will need to have a moderate level of understanding of genetic algorithms.
Genetic operators
Genetic operators are at the very heart of every evolutionary algorithm, and the performance of any neuroevolutionary algorithm depends on them. There are two major genetic operators: mutation and crossover (recombination).
In this chapter, you will learn about the basics of genetic algorithms and how they differ from conventional algorithms, which use error backpropagation-based methods for training the ANN.
Mutation operator
The mutation operator serves the essential role of preserving the genetic diversity of the population during evolution and prevents stalling in the local minima when the chromosomes of organisms in a population become too similar. This mutation alters one or more genes in the chromosome, according to the mutation probability defined by the experimenter. By introducing random changes to the solver's chromosome, mutation allows the evolutionary process to explore new areas in the search space of possible solutions and find better and better solutions over generations.
The following diagram shows the common types of mutation operators:
The exact type of mutation operator depends on the kind of genetic encoding that's used by a specific genetic algorithm. Among the various mutation types we come across, we can distinguish the following:
Bit inversion
: The randomly selected bit, which is inverted (
binary encoding
).
Order change
: Two genes are randomly selected and their position is flipped in the genome (
permutation encoding
).
Value change
:
A small value is added to the expressed gene at a random position (
value encoding
).
Gene expression change
: A random gene is selected and added/removed from the genotype (
structural encoding
).
Genotypes can be encoded using genetic encoding schemes with fixed and variable chromosomal lengths. The first three mutations can be applied to both types of encoding schemes. The last mutation can only be expressed in genotypes that have been encoded using a variable-length encoding.
Crossover operator
The crossover (recombination) operator allows us to stochastically generate new generations (solutions) from existing populations by recombining genetic information from two parents to generate offspring. Thus, the portions of good solutions from parent organisms can be combined and can potentially lead to better offspring. Typically, after a crossover, the produced offspring are mutated before being added to the population of the next generation.
The following diagram shows the various crossover operators:
The different types of crossover operators also depend on the genetic encoding that's used by particular algorithms, but the following are the most common:
Single-point crossover
: The random crossover point is selected, the genome part from the beginning to the crossover point
is
copied to the offspring from one parent, and the rest are copied from another parent.
Two-point crossover
: The two crossover points are chosen randomly, the part of the genome from the beginning to the first point is copied from the first parent, the part between the first and second crossover point is copied from the second parent, and the rest are copied from the first parent.
Uniform crossover
: The genes are copied from the first or second parent randomly.
Genome encoding schemes
One of the most crucial choices when designing the neuroevolution algorithm is to determine the genetic representation of the neural network, which can be evolved in the following ways
Standard mutation (see the preceding
Mutation operator
subsection)
Combination operators (see the preceding
Crossover operator
subsection)
At the moment, two major schemes for genome encoding exist: direct and indirect. Let's consider each schema in more detail.
Direct genome encoding
Direct genome encoding attempts were used in neuroevolution methods to create ANNs that were related to neural networks with a fixed topology; that is, the network topology was determined solely by the experimenter. Here, genetic encoding (genotype) is implemented as a vector of real numbers, representing the strength (weights) of the connections between the network nodes.
The evolutionary operators modify the values of the weights vector with the mutation operator and combine the vectors of the parent organisms with the recombination (crossover) operator to produce offspring. While allowing evolutionary operators to be applied with ease, the described encoding method has some significant drawbacks. One of its main drawbacks is that the network topology is determined by the experimenter from the very beginning and fixed through all the generations during the execution of the algorithm. This approach contradicts the natural evolutionary process, in which not only the properties but also the physical structure of the organisms change during the evolutionary process. This allows us to explore the broadest possible search space and find optimal solutions.
The following diagram shows the evolutionary process:
To address the drawbacks of the fixed topology methods, Kenneth O. Stanley proposed the NeuroEvolution of Augmenting Topologies (NEAT) method. The primary idea behind this algorithm is that the evolutionary operators are applied not only to the vector with the weights of all the connections but also to the topology of the created neural network. Thus, through generating the populations of the organisms, various topologies with a variety of connection weights are tested. We will discuss the particulars of the NEAT algorithm later in this chapter.
The NEAT algorithm demonstrates outstanding performance in a variety of tasks – from traditional reinforcement learning to the control of sophisticated non-player characters in computer games – and has become one of the most popular neuroevolution algorithms ever. However, it belongs to the family of direct encoding algorithms, which limits its use to evolving only modest-sized ANNs, where parameter space is limited to a maximum of thousands of connections. This is because each connection is directly encoded in the genotype, and with a large number of encoded connections, the computational requirements increase significantly. This makes it impossible to use the algorithm to evolve large neural networks.
Indirect genome encoding
To overcome size issues with direct encoding, Kenneth O. Stanley proposed an indirect encoding method, which is inspired by how the phenotype is encoded by the genome in the DNA. It is based on the fact that the physical world is built around geometry and regularities (structural patterns), where natural symmetries are found everywhere. Thus, the encoding size of any physical process can be significantly reduced through the reuse of a specific set of encoding blocks for the same structure that repeats many times. The proposed method, called Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT), is designed to build large-scale neural networks by exploiting geometrical regularities. HyperNEAT employs a connective Compositional Pattern Producing Network (CPPN) to represent node connections as a function of Cartesian space. We will discuss HyperNEAT in more detail later in this chapter.
Coevolution
In nature, populations of different species often simultaneously evolve in mutual interaction with each other. This type of inter-species relationship is called coevolution. Coevolution is a powerful tool of natural evolution, and it is no surprise that it attracted the attention of the neuroevolution community. There are three main types of coevolution:
Mutualism
, which is when two or more species coexist and mutually benefit from each other.
Competitive coevolution
:
Predation
, which is when one organism kills another and consumes its resources.
Parasitism
, which is when one organism exploits the resources of another but does not kill it.
Commensalism
, which is when the members of one species gain benefits without causing harm or gaining benefits from other species.
The preceding coevolution strategies were explored by researchers and their pros and cons were revealed. In this book, we will introduce a neuroevolution algorithm that employs the commensalistic principle to maintain two coevolving populations: the population of candidate solutions and the population of candidate objective functions. We will discuss the Solution and Fitness Evolution (SAFE) algorithm later in Chapter 9, Co-Evolution and the SAFE Method.
Modularity and hierarchy
Another crucial aspect of how natural cognitive systems are organized is modularity and hierarchy. While studying the human brain, neuroscientists have found that it is not a monolithic system with a uniform structure, but rather a complex hierarchy of modular structures. Also, due to the speed limitations of signal propagation in the biological tissues, the structure of the brain enforces the principle of locality when related tasks are processed by geometrically adjacent structures in the brain. This aspect of natural systems did not escape the attention of researchers of neuroevolution and they are implemented in many evolutionary algorithms. We will discuss how modular ANNs can be created using a neuroevolution-based algorithm in Chapter 8, ES-HyperNEAT and the Retina Problems.
NEAT algorithm overview
The method of NEAT for evolving complex ANNs was designed to reduce the dimensionality of the parameter search space through the gradual elaboration of the ANN's structure during evolution. The evolutionary process starts with a population of small, simple genomes (seeds) and gradually increases their complexity over generations.
The seed genomes have a very simple topology: only input, output, and bias neurons are expressed. No hidden nodes are introduced into the seed from the beginning to guarantee that the search for a solution starts in the lowest-dimensional parameter space (connection weights) possible. With each new generation, additional genes are introduced, expanding the solution search space by presenting a new dimension that previously did not exist. Thus, evolution begins by searching in a small space that can be easily optimized and adds new dimensions when necessary. With this approach, complex phenotypes (solutions) can be discovered gradually, step by step, which is much more efficient than launching the search directly in the vast space of the final solutions. Natural evolution utilizes a similar strategy by occasionally adding new genes that make phenotypes more complex. In biology, this process of incremental elaboration is called complexification.
The primary goal of the NEAT method is to minimize the complexity of the genome structure – not only the final product, but of all the intermediate generations of the organisms as well. Thus, the evolution of the network topology results in a significant performance advantage by reducing the overall solutions for the search space. For example, the high-dimensional space of the final solution is only encountered at the end of the evolutionary process. Another essential feature of the algorithm is that each structure that's introduced to the genome is the subject of subsequent fitness evaluations in the future generations. Also, only useful structures will survive during the evolutionary process. In other words, the structural complexity of the genome is always goal-justified.
NEAT encoding scheme
The genetic encoding scheme of NEAT is designed to allow easy matching between corresponding genes during the mating process when a crossover operator is applied to the two parent genomes. The NEAT genome is a linear representation of the connectivity pattern of the encoded neural network, as shown in the following NEAT genome scheme:
Each genome is represented as a list of connection genes that encode connections between the nodes of the neural network. Also, there are node genes that encode information about network nodes, such as the node identifier, node type, and type of activation function. The connection gene encodes the following connection parameters of the network link:
The identifier of the input network node
The identifier of the output network node
The strength (weight) of the connection
A bit, which indicates whether the connection is enabled (expressed) or not
An innovation number, which allows matching genes during recombination
The bottom part of the preceding diagram represents a scheme of the same genome in the form of a directed graph.
Structural mutations
The mutation operator that's specific to NEAT can change a connection's strength (weight) and the network's structure. There are two main types of structural mutations:
Adding a new connection between nodes
Adding a new node to the network
The following diagram shows the structural mutations of the NEAT algorithm:
When the mutation operator is applied to the NEAT genome, the newly added gene (connection gene or node gene) is assigned with an increasingly incremented innovation number. During the evolutionary process, the genomes of organisms within the population gradually get larger and genomes of varying sizes are produced. This process results in different connection genes being in the same positions within a genome, making the matching process between same-origin genes extremely complicated.
Crossover with an innovation number
There is a piece of unexploited information in the evolutionary process that tells us exactly which genes to match between the genomes of any organism in the topologically diverse population. This is where each gene tells us which ancestor that gene was derived from. The connection genes with the same historical origin represent the same structure, despite possibly having different connection weight values. The historical origins of genes in the NEAT algorithm are represented by incrementally assigned innovation numbers, which allow us to track the chronology of structural mutations.
At the same time, during the crossover, the offspring inherit the innovation numbers of genes from parent genomes. Thus, the innovation number of specific genes never change, allowing similar genes from different genomes to be matched during the crossover. The innovation numbers of matched genes are the same. If the innovation numbers do not match, the gene belongs to the disjoint or excess part of the genome, depending on whether its innovation number lies inside of, or outside of, the range of other parent innovation numbers. The disjoint or excess genes represent structures that are not present in the genome of the other parent and require special handling during the crossover phase. Thus, the offspring inherits genes that have the same innovation number. These are randomly chosen from one of the parents. The offspring always inherit the disjoint or excess genes from the parent with the highest fitness. This feature allows a NEAT algorithm to efficiently perform gene recombination using linear genome encoding, without the need for complex topological analysis.
The following diagram shows the crossover (recombination) in the NEAT algorithm:
The preceding diagram shows an example of a crossover between two parents using the NEAT algorithm. The genomes of both parents are aligned using the innovation numbers (the number at the top of the connection gene cell). After that, the offspring is produced by randomly choosing connection genes from either of parents when the innovation numbers are the same: the genes with innovation numbers from one to five. Finally, the disjoint and excess genes are added from either of the parents unconditionally and ordered by innovation number.
Speciation
In the evolutionary process, organisms can create diverse topologies through generations, but they fail to produce and maintain topological innovations of their own. The smaller network structures optimize faster than larger ones, which artificially reduces the chances of survival of a descendant genome after adding a new node or connection to it. Thus, the freshly augmented topologies experience negative evolutionary pressure due to the temporary decrease of fitness of the organisms within the population. At the same time, novel topologies can introduce innovations that lead to a winning solution in the long run. To address the temporal drop of fitness, the concept of speciation was introduced in the NEAT algorithm. The speciation limits the range of organisms that can mate by introducing narrow niches where only organisms that belong to the same niche compete with each other during the crossover, instead of competing with all the organisms in the population. Speciation is implemented by dividing the population so that organisms with a similar topology belong to the same species.
Let's refer to the following speciation algorithm:
The NEAT method permits the creation of complex ANNs that are capable of solving a variety of control optimization problems, as well as other unsupervised learning problems. Due to the introduced specifics of ANN topology augmentation through complexification and speciation, the solutions tend to optimize the performance of training and inference. The resulting ANN topology grows to match the problem that needs to be solved, without any excess layers of hidden units being introduced by the conventional methods of ANN's topology design for backpropagation-based training.
Hypercube-based NEAT
Intelligence is a product of the brain, and the human brain as a structure is itself a product of natural evolution. Such an intricate structure has evolved over millions of years, under pressure from harsh environments, and while competing with other living beings for survival. As a result, an extremely complex structure has evolved, with many layers, modules, and trillions of connections between neurons. The structure of the human brain is our guiding star and is aiding our efforts in creating artificial intelligence systems. However, how can we address all the complexity of the human brain with our imperfect instruments?
By studying the human brain, neuroscientists have found that its spatial structure plays an essential role in all perceiving and cognitive tasks – from vision to abstract thinking. Many intricate geometric structures have been found, such as the grid cells that help us with inertial navigation, and the cortical columns that are connected to the eye's retina to process visual stimuli. It has been demonstrated that the structure of the brain allows us to effectively respond to the patterns in signals that are received from the sensorium by using designated neural structures that are activated by specific patterns in the inputs. This feature of the brain allows it to use an extremely efficient way of representing and processing the entire diversity of the input data that's obtained from the environment. Our brains have evolved to be effective pattern recognition and pattern processing engines that actively reuse specific neural modules to process particular patterns, thus dramatically reducing the number of different neural structures required. This only became possible due to the complex modular hierarchy and the spatial integration of its various parts.
As we mentioned previously, the biological brain incorporates complex hierarchical and spatially-aware data processing routines. This has inspired the researchers of neuroevolution to introduce similar data processing methods in the field of artificial neural networks. When designing such systems, it is necessary to address the following problems:
The vast number of input features and training parameters that require large-scale ANNs
The effective representation of natural geometrical regularities and symmetries that are observed in the physical world
The effective processing of input data through the introduction of the locality principle, that is, when spatially/semantically adjacent data structures are processed by the modules of interconnected neural units, which occupy the same compact area of the entire network structure
In this section, you learned about the Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT) method, which was proposed by Kenneth O. Stanley to solve various problems by exploiting geometrical regularities. In the next section, we will look at Compositional Pattern Producing Networks (CPPNs).
Compositional Pattern Producing Networks
HyperNEAT extends the original NEAT algorithm by introducing a new type of indirect genome encoding scheme called CPPNs. This type of encoding makes it possible to represent the connectivity patterns of a phenotype's ANN as a function of its geometry.
HyperNEAT stores the connectivity pattern of the phenotype neural network as a four-dimensional hypercube, where each point encodes the connection between two nodes (that is, the coordinates of the source and target neurons) and the connective CPPN paints various patterns within it. In other words, CPPN computes the four-dimensional function, which is defined as follows:
Here, the source node is at (x1, y1) and the target node is at (x2, y2). At this stage, CPPN returns a weight for every connection between every node in the phenotype network, which is represented as a grid. By convention, the connection between the two nodes is not expressed if the magnitude of the connection weight that's computed by CPPN is less than a minimum threshold (wmin). That way, the connectivity pattern that's produced by CPPN can represent any network topology. The connectivity pattern can be used to encode large-scale ANNs by discovering regularities in the training data and can reuse the same set of genes to encode repetitions. By convention, the connectivity pattern that's produced by CPPN is called the substrate.
The following diagram shows the interpretation of the Hypercube-based Geometric Connectivity Pattern:
Unlike traditional ANN architectures, CPPN employs a set of various activation functions for its hidden nodes to explore a variety of geometrical regularities. For example, the trigonometric sine can be used to represent repetitions, while Gaussian can be used to enforce locality at a specific part of the network (that is, symmetry along the coordinate axis). Thus, the CPPN encoding scheme can represent patterns with different geometrical regularities such as symmetry, repetition, repetition with regularities, and so on in a compact manner.
