Neuroevolution

Overview

Neuroevolution uses evolutionary search, not gradient descent, to shape a neural network. The variants below differ in what the search evolves. One evolves the wiring and never trains the weights during the search 1906.04358 §3. Another evolves the weights of a small controller and scores them with the real reward 1809.01999 §2 [arxiv:1809.01999 app. A.5]. A third evolves an agent's body, and each candidate's neural controller is trained with PPO before its fitness is known 2102.02202 §DERL. A fourth keeps a whole collection of different good solutions rather than one best, and its genotypes are parameter vectors, not described as networks 1708.09251 §3 1708.09251 §4. A position paper proposes an evolutionary update rule but gives no method and no results [arxiv:1706.01040 §3].

Every number on this page is author-reported and comes from the cited tables. The three lines of work use different tasks, inputs and metrics, so their scores are not directly comparable (see Contradictions). The two world-model papers by the same authors describe the same controller and report the same Car Racing and Take Cover scores 1803.10122 tab. 2 [arxiv:1803.10122 tab. 4] 1809.01999 tab. 1 1809.01999 tab. 2. Those numbers come from one line of work and are not independent replications.

Variants

Topology search with a shared weight

Every connection in a candidate takes the same value, so a candidate's score depends on its structure and on that one value 1906.04358 §3. The search starts from minimal networks 1906.04358 §3. Each generation it scores every candidate over six shared weight values, -2, -1, -0.5, 0.5, 1 and 2, and averages the rollouts at each value 1906.04358 §3. Parents are picked by tournament selection. Each child receives exactly one change from three operators: insert a node on a connection, add a feed-forward connection, or change a hidden node's activation 1906.04358 §3. Candidates are ranked by Pareto dominance, using mean reward against connection count in most generations and against maximum reward in the rest 1906.04358 §3. Card: Weight Agnostic Neural Networks.

Reported results, averaged over 100 trials of each champion [arxiv:1906.04358 tab. 1]:

The caption does not define the ± 1906.04358 tab. 1. Random shared weights are drawn from U(-2, 2), and the tuned value is the best in that range 1906.04358 §4. The introduction reports about 92% MNIST test accuracy with random weights 1906.04358 §1. The paper does not state the test protocol behind that figure.

The paper also says that its networks fail when their individual weights are drawn at random, so random-weight rows are not a measure of the method without training 1906.04358 §4.

Fine-tuning the champion's weights

After the search, the paper trains the champion's individual weights with population-based REINFORCE 1906.04358 app. A.6. For swing-up and biped it uses 384 agents with 16 rollouts each. For car racing it uses 64 agents with 4 rollouts each. Training runs for 3000 generations 1906.04358 app. A.6.

With trained weights the searched networks are close to the fixed baselines, and the order depends on the task. Swing-up gives 932 ± 6 against 918 ± 7, biped 332 ± 1 against 347 ± 1, and car racing 893 ± 74 against 906 ± 21 1906.04358 tab. 1. The authors read these as similar to state-of-the-art performance 1906.04358 §4.

Evolving a controller over a learned world model

A convolutional VAE encodes each frame into a latent z. An LSTM with a mixture-density output predicts the next z from the current z, the action and its hidden state 1809.01999 §2. Both are trained on frames from 10,000 random rollouts and never see the reward 1809.01999 §3 1809.01999 alg. 1. The controller is a single linear layer from z and the LSTM hidden state to the action. It has 867 parameters for car racing 1809.01999 §2 1809.01999 app. A.1 1803.10122 tab. 1. CMA-ES evolves those weights against the real episode reward, with a population of 64 and 16 rollouts per candidate 1809.01999 app. A.5 1803.10122 app. A.4. Cards: World Models (the original arXiv paper) and World Models Facilitate Policy Evolution.

On car racing the full model reaches 906 ± 21, against 838 ± 11 for the Gym Leader baseline and 591 ± 45 for A3C continuous. The controller on z alone reaches 632 ± 251 1809.01999 tab. 1 1809.01999 §3.1. The original paper reports the same full-model score and the same baselines 1803.10122 tab. 2. The best agent over 1024 rollouts reaches 900.46 after 1800 generations 1809.01999 app. A.5.

On DoomTakeCover the controller is trained only inside the learned model and then run in the real game. At sampling temperature τ = 1.15 it scores 1092 ± 556 on the real task, against 820 ± 58 for the Gym Leader baseline 1809.01999 tab. 2 1809.01999 §4.2 1803.10122 tab. 4. The temperature sweep shows the trade-off. At τ = 0.10 the same procedure scores 2086 ± 140 in the model but 193 ± 58 in the real game [arxiv:1809.01999 tab. 2] 1803.10122 tab. 4.

Evolving bodies with lifetime learning

Here the search changes an agent's body: a kinematic tree with a spherical head and motor-driven limbs, simulated in MuJoCo 2102.02202 §DERL. Mutations add or delete limbs and change limb size, density, joint axis, joint limits or motor gear 2102.02202 app. A. Each new body starts with a controller of random weights, which is trained with PPO for five million agent-environment steps. Its fitness is the final average reward [arxiv:2102.02202 §DERL] 2102.02202 app. A 2102.02202 tab. 2. The controller is trained by gradient-based PPO and is not evolved, so this variant is neuroevolution only in its outer loop.

The search is asynchronous. Four random agents are drawn, the fittest becomes the parent, and one mutation is applied to a copy of its body. The child is trained and added, and the oldest member leaves, so the population stays at 576 2102.02202 §DERL 2102.02202 app. A. Card: Embodied Intelligence via Learning and Evolution.

Reported results, from one simulator with three evolutionary runs per environment 2102.02202 app. D:

• Bodies evolved in manipulation on variable terrain beat bodies evolved on flat ground on most test tasks. Bodies evolved on variable terrain beat them on five of six agility and stability tasks [arxiv:2102.02202 §Environmental complexity] 2102.02202 fig. 4. The count of test tasks differs between text and figure (see Contradictions).
• For a flat-ground lineage, generation 8 reaches about twice the final reward of generation 1, and reaches generation 1's final reward in about a fifth of the time 2102.02202 §Baldwin effect 2102.02202 fig. 5.
• Learning time to a 75th-percentile starting fitness halves within 10 generations, although selection never rewards learning speed [arxiv:2102.02202 §Baldwin effect] 2102.02202 fig. 5.
• Bodies from manipulation on variable terrain have a lower cost of work than flat-ground bodies 2102.02202 §Environmental complexity [arxiv:2102.02202 fig. 4]. Across bodies, lower cost of work goes with higher reward and faster learning. This is a correlation 2102.02202 §Mechanistic underpinning 2102.02202 fig. 6.

Quality-diversity search over parameter vectors

This variant keeps a container of solutions and tries to fill it with solutions that behave differently, instead of returning one best [arxiv:1708.09251 §1]. The container is either a grid with one solution per cell, or an unstructured archive with an insertion rule based on exclusive epsilon-dominance 1708.09251 §3.1.1 1708.09251 §3.1.2. Parents are chosen with a curiosity score: a parent gains 1 when its offspring is added to the container and loses 0.5 when it is not 1708.09251 §3.2.3. The paper's genotypes are parameter vectors: eight real values for a planar arm, and 36 sampled values for a six-legged robot 1708.09251 tab. 2. The card does not describe them as neural networks. Card: Quality and Diversity Optimization.

Reported results, simulation only, with 10 to 20 replications per condition 1708.09251 §4:

• On the arm, curiosity selection over the whole collection beats population-based selection on all four collection metrics [arxiv:1708.09251 §4.2.2] 1708.09251 fig. 4.
• On hexapod turning, curiosity selection beats NSLC (p < 0.0047) 1708.09251 §4.3.2.
• On hexapod gaits, curiosity reaches the 20,000-batch quality of random selection at 11,000 batches with an archive and at 13,500 with a grid 1708.09251 §4.4.2 1708.09251 fig. 7.
• On the same gait task, population-based fitness selection gives the best maximal quality (p < 0.0017), so the curiosity result is about collection quality and speed, not peak score 1708.09251 §4.4.2.

Brain Intelligence (proposal only)

The position paper proposes a network of small neural sub-networks, updated by an "S-system" of reproduction, selection and mutation 1706.01040 §3. It gives no equations, algorithm, hyperparameters or experiments 1706.01040 §1–§4, and it does not define the S-system. Its claims that the design would solve four AI limitations are not tested [arxiv:1706.01040 §4]. Card: Brain Intelligence: Go Beyond Artificial Intelligence. Use it as background only, not as a method to implement.

When to use which

The search cost is high. The topology paper gives no wall-clock figures, so budget it by population and generation count 1906.04358 app. A.4. The world-model variant reaches about 1.8 million episodes at 1800 generations, derived from its population and rollout counts 1809.01999 app. A.5.

Implementation sketch

Language-agnostic pseudocode of the common core: score candidates, select, and vary. The variants differ in what a candidate is, how it is scored, and the update rule.

# Score one topology over the shared weights  [arxiv:1906.04358 §3]
# Input:  net, six shared weights W, rollouts per weight
# Output: (mean reward, best reward) over W

def score(net, W, reps):
    per_weight = []
    for w in W:
        # Every existing connection takes the value w; absent ones stay out
        # [arxiv:1906.04358 §3]
        rewards = [rollout(net, shared_weight=w) for _ in range(reps)]
        per_weight.append(mean(rewards))
    return mean(per_weight), max(per_weight)

# Search loop  [arxiv:1906.04358 §3]
# Input:  pop, generations, W, reps, k (tournament size)
# Output: final population of topologies

def wann_search(pop, generations, W, reps, k):
    # Start from minimal networks  [arxiv:1906.04358 §3]
    population = minimal_networks(pop)
    for _ in range(generations):
        scored = [(net, *score(net, W, reps)) for net in population]
        # Pareto ranking; the second objective is connection count in most
        # generations and maximum reward in the rest  [arxiv:1906.04358 §3]
        ranked = pareto_sort(scored)
        children = []
        while len(children) < pop:
            # Tournament selection picks the parent  [arxiv:1906.04358 §3]
            parent = tournament(ranked, k)
            # Exactly one change per child: insert node, add connection or
            # change activation  [arxiv:1906.04358 §3]
            children.append(one_change(parent))
        population = children
    return population

# Evolve controller weights with CMA-ES  [arxiv:1809.01999 app. A.5]
# Input:  num_params, generations, population, rollouts per candidate
# Output: mean of the search distribution (controller weights)

def evolve_controller(num_params, generations, population, rollouts):
    search = cma_init(num_params, popsize=population)
    for _ in range(generations):
        # Sample candidate weight vectors  [arxiv:1809.01999 app. A.5]
        candidates = search.ask()
        # Fitness is the mean real return over several seeds
        # [arxiv:1809.01999 app. A.5]
        returns = [mean_return(w, rollouts) for w in candidates]
        search.tell(returns)
    return search.current_mean()

# Asynchronous tournament over bodies  [arxiv:2102.02202 §DERL]
# Input:  population of evaluated agents, search budget
# Output: population after the budget is spent

def body_tournament(population, budget, pop_size=576, k=4):
    searched = 0
    while searched < budget:
        # Draw k agents; the fittest is the parent  [arxiv:2102.02202 app. A]
        parent = max(sample(population, k), key=fitness)
        # Mutate a copy of the parent body  [arxiv:2102.02202 app. A]
        child = Agent(mutate(parent.body), controller=random_weights())
        # Lifetime learning with PPO; fitness is the final reward
        # [arxiv:2102.02202 app. B] [arxiv:2102.02202 tab. 2]
        child.fitness = train_ppo(child, steps=5_000_000)
        # Add the child and keep the newest pop_size members
        # [arxiv:2102.02202 §DERL]
        population = (population + [child])[-pop_size:]
        searched += 1
    return population

Contradictions

Nothing in the sources directly disagrees, but the car racing numbers need care. The world-model papers report 906 ± 21 for the controller 1809.01999 tab. 1 1803.10122 tab. 2. The topology paper uses it as its fixed baseline for car racing 1906.04358 tab. 1. Its searched network scores 608 ± 161 with a tuned shared weight and 893 ± 74 with trained weights 1906.04358 tab. 1. These are not comparable as methods: the topology network sees only the 16-dimensional VAE latent, not the recurrent state 1906.04358 §4 1906.04358 app. A.4.

The world-model paper's own numbers disagree with its Doom setup. The paper trains the Doom controller at τ = 1.15 1809.01999 app. A.6, but the released code's default is 1.25. The code does not show which value produced the reported numbers 1809.01999 §4.2.

The DERL paper disagrees with itself on the number of test tasks. Its main comparison is described as using 7 test tasks, while the suite and the figure caption list 8 2102.02202 §Environmental complexity [arxiv:2102.02202 fig. 4]. Check the figure before quoting a count. Its scores come from MuJoCo locomotion and manipulation tasks, so they cannot be set against the car racing or swing-up numbers above.

The quality-diversity paper's code differs from its paper. Algorithm 1 credits each offspring's actual parent with the curiosity change. The released code pairs offspring with parents by index, so unless a random permutation is the identity, credit may go to a different individual [arxiv:1708.09251 alg. 1] 1708.09251 §Paper vs code. Its archive insertion test also differs from the paper's in the second-neighbour test and the tolerance term 1708.09251 §3.1.2 1708.09251 §Paper vs code. The card reads these from the code and does not run it, so check them before implementing either version.

Papers

• Quality and Diversity Optimization: one loop with a swappable container (grid or archive) and selection rule; adds an epsilon-dominance archive rule and curiosity selection, tested on simulated robot tasks.
• Weight Agnostic Neural Networks: evolves minimal topologies that are scored over shared weight values, with no weight training during search.
• World Models: the original three-part agent (VAE, MDN-RNN, linear controller) with the controller evolved by CMA-ES, plus training inside the learned model.
• World Models Facilitate Policy Evolution: evolves a linear controller with CMA-ES over a VAE and LSTM model, scored on the real reward.
• Embodied Intelligence via Learning and Evolution: co-evolves limb-tree bodies with PPO controllers trained from scratch for each candidate; reports that bodies evolved in harder terrain learn new tasks faster.
• Brain Intelligence: Go Beyond Artificial Intelligence: position paper proposing an evolutionary S-system update over sub-networks; no method or results.