Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning

By Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, Jeff Clune. 2017

759 citations recorded by the source corpus.

Deep artificial neural networks (DNNs) are typically trained via gradient-based learning algorithms, namely backpropagation. Evolution strategies (ES) can rival backprop-based algorithms such as Q-learning and policy gradients on challenging deep reinforcement learning (RL) problems. However, ES can be considered a gradient-based algorithm because it performs stochastic gradient descent via an operation similar to a finite-difference approximation of the gradient. That raises the question of whether non-gradient-based evolutionary algorithms can work at DNN scales. Here we demonstrate they can: we evolve the weights of a DNN with a simple, gradient-free, population-based genetic algorithm (GA) and it performs well on hard deep RL problems, including Atari and humanoid locomotion. The Deep GA successfully evolves networks with over four million free parameters, the largest neural networks ever evolved with a traditional evolutionary algorithm. These results (1) expand our sense of the scale at which GAs can operate, (2) suggest intriguingly that in some cases following the gradient is not the best choice for optimizing performance, and (3) make immediately available the multitude of techniques that have been developed in the neuroevolution community to improve performance on RL problems. To demonstrate the latter, we show that combining DNNs with novelty search, which was designed to encourage exploration on tasks with deceptive or sparse reward functions, can solve a high-dimensional problem on which reward-maximizing algorithms (e.g. DQN, A3C, ES, and the GA) fail. Additionally, the Deep GA parallelizes better than ES, A3C, and DQN, and enables a state-of-the-art compact encoding technique that can represent million-parameter DNNs in thousands of bytes.

Subfields: Artificial Intelligence, Mechanical Engineering, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Mechanical Engineering

In Reinforcement Learning

Citations in the corpus

Strike (With) a Pose: Neural Networks Are Easily Fooled by Strange Poses of Familiar Objects (2018, methodology): “In reinforcement learning problems, random search (RS) can be surprisingly effective compared to more sophisticated methods [41].”
Recurrent World Models Facilitate Policy Evolution (2018, background): “Recent works [14, 26, 73, 94] have demonstrated that ES is a viable alternative to traditional Deep RL methods on many strong baselines.”
Evolutionary-Neural Hybrid Agents for Architecture Search (2018, methodology): “[39] have applied genetic algorithms to evolve the weights of the model.”
MaskConnect: Connectivity Learning by Gradient Descent (2018, positive): “Evolutionary search has been proposed as an interesting framework to learn both the structure as well as the connections in a neural network [16,17,18,19,20,21,22,23,24].”
Transfer Learning with Neural AutoML (2018, background): “An emerging body of neuro-evolution research has adapted genetic algorithms for these complex optimization problems [20], including to set the parameters of existing deep networks [21], evolve image classifiers [5], and evolve generic deep neural networks [6].”
Evolving Deep Neural Networks (2017, background): “More recently, Such et al. (2017) demonstrated the power of this approach in reinforcement learning tasks, and Real et al. (2019) in image classiﬁcation.”
Diversity is All You Need: Learning Skills without a Reward Function (2018, background): “Prior work in neuroevolution and evolutionary algorithms has studied how complex behaviors can be learned by directly maximizing diversity (Lehman & Stanley, 2011a;b; Woolley & Stanley, 2011; Stanley & Miikkulainen, 2002; Such et al., 2017; Pugh et al., 2016; Mouret & Doncieux, 2009).”
Automatic differentiation in machine learning: a survey (2015, methodology): “Training of a neural network is an optimization problem with respect to its set of weights, which can in principle be addressed by using any method ranging from evolutionary algorithms (Such et al., 2017) to gradient-based methods such as BFGS (Apostolopoulou et al.”
The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities (2018, neutral): “Atari games are a common benchmark in deep reinforcement learning [94, 95, 117, 132].”
Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science (2017, background): “22,23 , it has been shown that evolution strategies and genetic algorithms, respectively, can train successfully ANNs with up to four million parameters as a viable alternative to DQN 2 for reinforcement learning tasks, but they need over 700 CPUs to do so.”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “Gradient-free evolutionary algorithms have also been employed for deep learning, where examples include Genetic Algorithms [199, 250], Neuro-Evolution [175, 243], and Particle-Swarm Optimization [168].”
Go-Explore: a New Approach for Hard-Exploration Problems (2019, methodology): “Comparing sample complexity for RL algorithms trained on Atari games can be tricky due to the common usage of frame skipping [31, 66], wherein a policy only sees and acts every nth (here, 4) frame, and that action is repeated for intervening frames to save the computation of running the policy.”
A survey and critique of multiagent deep reinforcement learning (2018, neutral): “It is therefore suggested to refer to “game frames” and “training frames” [310].”
An Atari Model Zoo for Analyzing, Visualizing, and Comparing Deep Reinforcement Learning Agents (2018, background): “, 2017] and Deep GA [Such et al., 2017]), and one value-function based algorithm (a high-performing DQN variant, Ape-X; [Horgan et al.”
Effective Diversity in Population-Based Reinforcement Learning (2020, background): “An alternative formulation is Evolution Strategies (ES, (Salimans et al., 2017)), which has recently shown to be effective (Such et al., 2017; Choromanski et al., 2018; Mania et al., 2018).”
Evolution-Guided Policy Gradient in Reinforcement Learning (2018, methodology): “These are benchmarks used widely in the ﬁeld [15, 27, 55, 49] and are hosted through the OpenAI gym [7].”
Autocurricula and the Emergence of Innovation from Social Interaction: A Manifesto for Multi-Agent Intelligence Research (2019, background): “Many of the principles remain the same regardless of whether evolution or learning dominate (Bloembergen et al., 2015; Börgers and Sarin, 1997; Such et al., 2017).”
AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence (2019, background): “There are pros and cons to us-ing evolutionary methods [176, 96, 146, 195, 167], and beneﬁts to hybrid approaches that combine evolutionary concepts (searching in the parameter space) with policy-gradient concepts (searching in the action space) [131, 46].”
Data-efficient neuroevolution with kernel-based surrogate models (2018, background): “With a body of existing NE research, on topics such as exploration and overcoming deception, already being leveraged on deep learning problems [7, 31], NE is poised for a surge in interest.”