The genome

The thing evolution edits, why it starts as small as it possibly can, and why every genome in the first generation is the same one

A genome is a description of a network that has not been built yet. It is what mutation edits, what crossover combines, and what gets written to disk when a run finds something worth keeping.

type Layers [][]network.Node

type Genome struct {
	Layers      Layers
	Connections []network.Connection
}

Why layers

The paper does not have layers. A NEAT genome is a bag of nodes and a bag of connections, and the network’s shape is whatever the connections say it is.

I keep them in layers anyway, because two of the structural mutations need to know which way is forwards.

• Adding a node splits a connection, and the node has to go between the two ends. Without an ordering there is no “between”.
• Adding a connection has to know whether the edge it is about to create runs forwards or backwards, because a backward edge in a feed-forward network is a cycle, and a cycle will not compile.

Layers give a cheap partial order that answers both. They are not a constraint on what can be expressed - connections may skip layers freely - they are bookkeeping.

The minimal genome

layer 0            layer 1
(inputs)           (outputs)

 in0 ---------\
               >------ out0
 in1 ---------/

2 nodes in, 1 out, 2 connections, no hidden structure at all

That is where every run starts. There is no hidden layer to configure because growing one is the algorithm’s job.

// NewGenome builds a minimal genome: every layer described by cfg.Layers,
// fully connected between adjacent layers.
//
// Input and bias nodes are structural, not learnable. Inputs pass their value
// through untouched and bias nodes emit a constant 1, so both are created with
// a zero bias and are never mutated. Giving an input node a bias or a squashing
// activation would corrupt the very signal the network is meant to read.
func (b *Breeder) NewGenome() (Genome, error) {

That last sentence is a bug I wrote and then had to find. If input nodes are mutable like any other, evolution will happily put a bias on one, and the network is then reading a sensor that lies to it - by an amount that drifts every generation.

// mutableNode reports whether a node carries learnable parameters. Input and
// bias nodes do not: they are fixed signal sources.
func mutableNode(node network.Node) bool {
	return node.Type == network.Hidden || node.Type == network.Output
}

Every mutation checks that, and so does the compatibility distance.

Bias nodes are off by default

The classic NEAT layout has an extra input node that always emits 1, so that connections from it act as a per-node bias.

// BiasNodes is the number of bias nodes, constant sources of 1 in the
// input layer, to start every genome with.
//
// Hidden and output nodes carry a bias of their own, so a bias node adds
// nothing a genome cannot already express; what it adds is a connection
// per node for the search to fit. On XOR one bias node costs about forty
// percent more generations to a solution. The default is therefore none.
BiasNodes int

Since every hidden and output node already has a Bias field, a bias node is a strictly more expensive way of saying the same thing: instead of one number on the node, it is one number on a connection plus a connection gene for mutation, crossover and the compatibility distance to carry around.

Forty per cent more generations is a large price for a feature that does nothing new. It is still there, because a tool that reads genomes may expect the classic layout.

Every genome in the first generation is the same genome

This is the one that would have cost me a week if the paper had not warned about it.

// GeneratePopulation builds the initial population.
//
// Every member is a copy of one template genome with freshly drawn weights and
// biases. That shared genotype matters: NEAT identifies genes by their
// historical marking, so if each genome were generated independently they would
// share no gene IDs at all, every genome would look maximally different from
// every other, and the population would shatter into one species per genome
// before evolution had run a single step.

Generate 150 genomes independently and you get 150 structurally identical networks whose genes have 150 disjoint sets of IDs. The compatibility distance counts genes that only one genome has, so every pair looks maximally different, and generation one is 150 species of one member each. Nothing can cross over with anything, fitness sharing has nothing to share, and the algorithm has been reduced to a very slow random search.

So one template is built, and the population is copies of it with the weights redrawn:

// RandomizeWeights returns a copy of genome with freshly sampled weights
// and biases but identical structure and identical gene IDs.
//
// This is how an initial population is seeded. Every member must share one
// genotype so that their genes line up under crossover and the compatibility
// distance sees them as one species; only the weights differ.
func (b *Breeder) RandomizeWeights(genome Genome) Genome {
	cfg, rng := b.cfg, b.rng
	genome = CopyGenome(genome)
	for i, layer := range genome.Layers {
		for j, node := range layer {
			if !mutableNode(node) {
				continue
			}
			genome.Layers[i][j].Bias = cfg.RandBias(rng)
		}
	}
	for i := range genome.Connections {
		genome.Connections[i].Weight = cfg.RandWeight(rng)
	}
	return genome
}

Copying

Genomes are values, but they contain slices, so a Genome assignment shares its guts with the original. Everything that mutates works on a copy:

func CopyGenome(genome Genome) Genome {
	cp := Genome{
		Layers:      make([][]network.Node, len(genome.Layers)),
		Connections: make([]network.Connection, len(genome.Connections)),
	}

	for i, layer := range genome.Layers {
		cp.Layers[i] = make([]network.Node, len(layer))
		copy(cp.Layers[i], layer)
	}
	copy(cp.Connections, genome.Connections)
	return cp
}

There is a public MutateX for each mutation which copies first, and an internal mutateX which does not:

// mutateGenome mutates a genome the caller already owns exclusively, without
// copying it first. Crossover hands back a freshly built genome that nothing
// else references, so copying it again before mutating would duplicate every
// node and connection for nothing.

Six mutations are applied to every offspring. Copying once instead of six times is most of what reproduction costs.

Counting genes

// NumGenes is the total number of node and connection genes, which is the
// genome size used to normalise the compatibility distance.
func (g Genome) NumGenes() int {
	return g.NumNodes() + g.NumConnections()
}

Nodes and connections are both genes, and both count. That comes up again in speciation, where a large genome must not automatically look distant from everything.

Becoming a network

// CompileFor builds the genome the way cfg asks for it, which is what a run
// does. Compile it yourself only when you know which of the two you want.
func (g Genome) CompileFor(cfg Config) (*network.Network, error) {
	if cfg.Recurrent {
		return g.CompileRecurrent()
	}
	return g.Compile()
}

Layers.Nodes() flattens the layers back into the single list network.Compile wants. The layers were only ever for the mutations.

Next: the ID on every one of those genes, and why it cannot come from a counter.