Most neural network training holds the shape of the network fixed and moves the weights. NEAT moves both. A run starts from the smallest network that could possibly answer the question - every input wired straight to every output, nothing in between - and grows hidden nodes and connections one at a time, keeping whatever happens to help.

I have wanted to build one properly for years. This series is that: neatgo, a piece at a time.

NEAT is Kenneth Stanley’s, and the paper is short and readable. I am not going to restate it here. What I am going to do is write the thing, and be specific about the places where “what the paper says” and “what actually works” are not the same sentence.

What it looks like to use

func evaluate(_ context.Context, net *network.Network) (float64, error) {
	output := make([]float64, net.NumOutputs())

	fitness := .0
	for i, input := range xorInputs {
		if err := net.ActivateInto(input, output); err != nil {
			return 0, err
		}
		// Squared error, so a confident right answer scores better than a
		// hesitant one.
		fitness += 1 - math.Pow(output[0]-xorAnswers[i], 2)
	}
	return fitness, nil
}

func main() {
	// 2 inputs, 1 output. NEAT starts minimal and grows the hidden structure
	// itself, so no hidden layer is specified here.
	cfg := neat.DefaultConfig(2, 1)
	cfg.PopulationSize = 150

	pop, err := neat.GeneratePopulation(cfg)
	if err != nil {
		log.Fatal(err)
	}

	pop, err = neat.Run(context.Background(), pop, evaluate, neat.RunOptions{
		MaxGenerations: 300,
		Solved: func(pop neat.Population) bool {
			return pop.BestGenomeFitness >= 3.9
		},
	})
	if err != nil {
		log.Fatal(err)
	}

	best, err := pop.BestEverGenome.Compile()
	if err != nil {
		log.Fatal(err)
	}
	output, err := best.Activate([]float64{1, 0})
}

You write a function that scores one network, and the library runs it across the population. That is the whole interface. XOR falls in about 32 generations on average, and in 300 out of 300 seeded runs within 80.

The pieces

There are two packages, and the split is the first design decision worth defending.

network/            the thing that runs
    Node, Connection, ActivationFunction
    Compile, CompileRecurrent
    Network.Activate, Network.Step

neat/               the thing that evolves
    Genome          nodes and connections, as genes
    Innovations     historical markings
    Breeder         mutation and crossover
    Species         who competes with whom
    Population      a generation, and how to get the next one

network knows nothing about evolution. It takes a list of nodes and a list of connections, compiles them into something that runs fast, and runs it. You could use it on its own with a network you wrote by hand.

neat knows nothing about how a network is executed. It builds and mutates genomes, and hands them to network to compile.

That means the fiddly part - the graph, the topological sort, the flat arrays that make activation fast - is testable without any evolution in sight, and the evolutionary part is testable without caring how a float gets from one node to another.

A genome is not a network

The distinction the whole library turns on:

genome                          compiled network

Layers  [][]Node                nodes in evaluation order
Connections []Connection        each node's inputs resolved
                                to slice indices and weights

mutated, crossed over,          immutable, fast, safe to
saved to disk                   share across goroutines

A genome is the thing evolution edits: a bag of nodes and connections, each carrying a historical marking. A network is what you get when you compile one, and compiling resolves the evaluation order, the activation functions and every connection source once, so that running it afterwards is a flat loop over slices.

Compiling costs about the same as a few dozen activations, so you compile once per genome per generation and activate as many times as the problem needs.

The posts

I will update this list with links as I write them.

  1. Introduction
  2. The utilities everything else is built on
  3. Compiling and running a network
  4. The genome
  5. Historical markings
  6. Mutating the parameters
  7. Mutating the structure
  8. Crossover
  9. Speciation
  10. Selection
  11. Reproduction
  12. Running a run

If you would rather see it pointed at something than built, I used it to play snake, where it beat every player I wrote by hand.