XOR by NEAT

The problem

Find a neural network that computes XOR: an output of 1 when exactly one of its two inputs is 1, and 0 otherwise. XOR isn't linearly separable, so a network without hidden nodes can't compute it; the fixed network tab gives the network two hidden units and evolves only its weights. Here the structure evolves too, by NEAT (NeuroEvolution of Augmenting Topologies, Stanley and Miikkulainen 2002), starting from networks with no hidden nodes at all: the two inputs and a bias connected straight to the output. XOR is the paper's first experiment, a check that NEAT finds the structure a problem needs.

The fitness is the paper's, (4 − Σ|error|)², the error summed over the four cases: 16 for a perfect network. The problem is solved at the paper's criterion: every output on the right side of 0.5.

The Python version runs the same NEAT with gx.Neat, its networks evaluated in Rust (gx.neat.Network.feed_forward): it prints the same output and writes the same trace.

What makes it hard

The search has to add a hidden node and connect it before the fitness can reward it: a new node first changes the network's function little (it splits a connection, with a weight of 1 in and the old weight out), and a network with a new node is usually worse until its weights are tuned. NEAT protects such networks by speciation: networks are grouped by how different their genes are, and compete mainly within their species, whose offspring depend on its members' mean fitness.

Representation

A network (neat::Network): node genes (the inputs, the bias, the output and hidden nodes, each with the paper's steepened sigmoid 1 / (1 + e^(−4.9x)) on the output and the hidden nodes) and connection genes, each with an innovation number that records when that connection first appeared in the run. Crossover aligns two networks' genes by these numbers. Networks stay feed-forward; each is evaluated through Network::feed_forward, compiled once into the order of its nodes, with genoxide's math functions, so the outputs are the same bits on every platform.

Algorithm

NEAT (neat::Neat) with the paper's settings: 150 networks, speciated by the compatibility distance δ = E/N + D/N + 0.4 W̄ (excess and disjoint genes, and the mean weight difference of the matching ones) with a threshold of 3. Each species gets offspring in proportion to its members' shared fitness (the paper's: the raw fitness divided by the species' size). A quarter of the offspring come from mutation alone, the rest from crossover within the species (between species with probability 0.001); weights are mutated in 80% of the offspring, a new node is added with probability 0.03 and a new connection with 0.05. The champion of each species of more than five networks is kept, and a species that doesn't improve for 15 generations stops reproducing.

Where the paper gives no value: new weights are normal with deviation 1 and the parents of each species are its best 20%, as in neat-python, and weight perturbations are normal with deviation 1 (with neat-python's 0.5, 3 of 100 runs failed within 1000 generations).

Output

The first line gives the setting, then the generation in which a network solved XOR and the evaluations it took, the network (its hidden nodes and its enabled connections, from node to node with their weights: in0 and in1 the inputs, h the hidden nodes by id) and its outputs on the four cases.

The project page plays the run back: the best network's output over [0, 1]² in each generation.

Good results

The run of output.txt solved XOR in generation 68, after 9,539 evaluations, with a network of 3 hidden nodes and 12 enabled connections. Its outputs are on the right side of 0.5, two of them barely: the criterion is the paper's, and later generations push them apart.

Over 100 runs (seeds 1 to 100), all 100 solved it, in 39 generations in the median and 47 on average (245 at most), after 6,719 evaluations on average, with 2.95 hidden nodes and 10.7 enabled connections on average. The paper reports 32 generations and 4,755 evaluations on average, no failure in 100 runs, and 2.35 hidden nodes: genoxide's runs take about 1.4 times as long and grow slightly larger networks. The details the paper leaves out, such as the size of weight perturbations and which members breed, can account for the difference.

Reference: Stanley, K. O. and Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation 10(2): 99-127.

Known optimum: Every output on the right side of 0.5 (the paper's success criterion); a fitness of 16 is a perfect network

Source: examples/xor_neat

Interactive run: tachsin.gr/projects/genoxide/examples/xor-neat

RustPython

cargo run --release --example xor_neat

//! XOR by NEAT: evolve a network's structure and weights until it computes XOR, from networks
//! without hidden nodes.
//!
//! The NEAT paper's first experiment (Stanley and Miikkulainen 2002): XOR isn't linearly
//! separable, so a network needs at least one hidden node, which NEAT has to discover. The
//! initial networks connect the two inputs and the bias straight to the output; mutations add
//! nodes and connections, speciation protects the new structure while its weights are tuned. The
//! fitness is the paper's, (4 − Σ|error|)², maximized, with its fitness sharing, and the run stops
//! at the paper's success criterion: every output on the right side of 0.5.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example xor_neat
//! ```

mod trace;

use genoxide::neat::{Neat, Network, NodeKind, Sharing};
use genoxide::prelude::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};

// the inputs and the expected output
const CASES: [([f64; 2], f64); 4] = [
    ([0.0, 0.0], 0.0),
    ([0.0, 1.0], 1.0),
    ([1.0, 0.0], 1.0),
    ([1.0, 1.0], 0.0),
];

// the network's outputs for the four cases
fn outputs(network: &Network) -> [f64; 4] {
    let mut evaluator = network.feed_forward().expect("feed-forward networks");
    let mut values = [0.0; 4];
    for (value, (input, _)) in values.iter_mut().zip(&CASES) {
        let mut output = [0.0];
        evaluator.activate(input, &mut output);
        *value = output[0];
    }
    values
}

// the paper's fitness: (4 − Σ|error|)², 16 for a perfect network
fn fitness(network: &Network) -> f64 {
    let error: f64 = outputs(network)
        .iter()
        .zip(&CASES)
        .map(|(output, (_, target))| (output - target).abs())
        .sum();
    (4.0 - error).powi(2)
}

// the paper's success criterion: every output on the right side of 0.5
fn solves(network: &Network) -> bool {
    let outputs = outputs(network);
    outputs
        .iter()
        .zip(&CASES)
        .all(|(output, (_, target))| (*output >= 0.5) == (*target == 1.0))
}

fn main() -> Result<()> {
    // the paper's settings, with its fitness sharing: the fitness is maximized and non-negative
    let neat = Neat::builder(2, 1)
        .population_size(150)
        .sharing(Sharing::Raw)
        .seed(1)
        .build()?;
    println!("XOR by NEAT: 150 networks, from 2 inputs and a bias connected to the output");
    // stop at the first generation with a network that solves it
    let abort = Arc::new(AtomicBool::new(false));
    let mut solution: Option<Network> = None;
    // with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    let outcome = Engine::new(neat, fitness)
        .stop_when(Stop::generations(1000))
        .abort_flag(Arc::clone(&abort))
        .on_generation(|snapshot| {
            trace.record(snapshot);
            if solution.is_none() {
                let population = snapshot.population();
                if let Some(found) = population.iter().find(|i| solves(i.genome())) {
                    solution = Some(found.genome().clone());
                    abort.store(true, Ordering::Relaxed);
                }
            }
        })
        .run()?;
    let Some(network) = solution else {
        println!("not solved after {} generations", outcome.generations());
        trace.write();
        return Ok(());
    };
    println!(
        "solved in generation {} after {} evaluations\n",
        outcome.generations(),
        outcome.evaluations()
    );
    println!(
        "the network: {} hidden nodes, {} enabled connections of {}",
        network.hidden(),
        network.enabled(),
        network.connections().len()
    );
    let name = |id: u32| match network
        .nodes()
        .iter()
        .find(|n| n.id() == id)
        .map(|n| n.kind())
    {
        Some(NodeKind::Input) => format!("in{id}"),
        Some(NodeKind::Bias) => "bias".to_string(),
        Some(NodeKind::Output) => "out".to_string(),
        _ => format!("h{id}"),
    };
    for connection in network.connections().iter().filter(|c| c.is_enabled()) {
        println!(
            "  {:>4} -> {:<4} {:>8.3}",
            name(connection.from()),
            name(connection.to()),
            connection.weight()
        );
    }
    println!();
    for (output, ([a, b], expected)) in outputs(&network).iter().zip(CASES) {
        println!("{a:.0} xor {b:.0} = {expected:.0}: {output:.3}");
    }
    trace.write();
    Ok(())
}

python examples/xor_neat/main.py

"""XOR by NEAT: evolve a network's structure and weights until it computes XOR, from networks
without hidden nodes.

The NEAT paper's first experiment (Stanley and Miikkulainen 2002): XOR isn't linearly separable,
so a network needs at least one hidden node, which NEAT has to discover. The initial networks
connect the two inputs and the bias straight to the output; mutations add nodes and connections,
speciation protects the new structure while its weights are tuned. The fitness is the paper's,
(4 - sum |error|)^2, maximized, with its fitness sharing, and the run stops at the paper's success
criterion: every output on the right side of 0.5.

The networks run in Rust (``gx.neat.Network.feed_forward``), so the run is the Rust example's, to
the bit, on every platform.

With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.

    python examples/xor_neat/main.py
"""

import genoxide as gx

from trace import Trace

# the inputs and the expected output
CASES = [
    ((0.0, 0.0), 0.0),
    ((0.0, 1.0), 1.0),
    ((1.0, 0.0), 1.0),
    ((1.0, 1.0), 0.0),
]


def outputs(network):
    """The network's outputs for the four cases."""
    evaluator = network.feed_forward()
    return [float(evaluator.activate(inputs)[0]) for inputs, _ in CASES]


def fitness(network):
    """The paper's fitness: (4 - sum |error|)^2, 16 for a perfect network."""
    error = sum(abs(output - target) for output, (_, target) in zip(outputs(network), CASES))
    return (4.0 - error) * (4.0 - error)


def solves(network):
    """The paper's success criterion: every output on the right side of 0.5."""
    return all(
        (output >= 0.5) == (target == 1.0) for output, (_, target) in zip(outputs(network), CASES)
    )


# the paper's settings, with its fitness sharing: the fitness is maximized and non-negative
neat = gx.Neat(2, 1, population_size=150, sharing="raw", seed=1)
print("XOR by NEAT: 150 networks, from 2 inputs and a bias connected to the output")
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(CASES)
solution = None


def on_generation(progress):
    """Records the generation, and stops the run at the first generation with a network that
    solves XOR."""
    global solution
    trace.record(progress)
    if solution is None:
        solution = next((network for network in progress.population if solves(network)), None)
    return solution is None


result = neat.run(fitness, generations=1000, on_generation=on_generation)

if solution is None:
    print(f"not solved after {result.generations} generations")
else:
    network = solution
    print(f"solved in generation {result.generations} after {result.evaluations} evaluations\n")
    print(
        f"the network: {network.hidden()} hidden nodes, {network.enabled()} enabled connections "
        f"of {len(network.connections())}"
    )
    kinds = {node.id: node.kind for node in network.nodes()}
    names = {"input": "in{}", "bias": "bias", "output": "out"}

    def name(id):
        return names.get(kinds.get(id, "hidden"), "h{}").format(id)

    for connection in network.connections():
        if connection.enabled:
            print(
                f"  {name(connection.from_):>4} -> {name(connection.to):<4} "
                f"{connection.weight:8.3f}"
            )
    print()
    for output, ((a, b), expected) in zip(outputs(network), CASES):
        print(f"{a:.0f} xor {b:.0f} = {expected:.0f}: {output:.3f}")
trace.write()

What it prints, from a seeded run:

XOR by NEAT: 150 networks, from 2 inputs and a bias connected to the output
solved in generation 68 after 9539 evaluations

the network: 3 hidden nodes, 12 enabled connections of 13
   in0 -> out    -0.028
   in1 -> out     0.027
   in0 -> h4      6.451
    h4 -> out    17.523
  bias -> h6      1.516
    h6 -> out   -10.422
   in1 -> h6     -3.136
  bias -> h4     -4.170
   in1 -> h4     -5.762
   in0 -> h27     0.728
   h27 -> h4      0.840
   h27 -> h6     -1.397

0 xor 0 = 0: 0.000
0 xor 1 = 1: 0.532
1 xor 0 = 1: 1.000
1 xor 1 = 0: 0.498