Compiling and running a network
Turning a bag of nodes and connections into a flat loop over slices
Before there is anything to evolve there has to be something to run. The network package takes a list of nodes and a list of connections and turns them into something that activates fast, and it knows nothing at all about evolution.
The two genes
type Node struct {
ID int
Type NodeType
Bias float64
ActivationFn ActivationFunctionName
}
type Connection struct {
ID int
From, To int
Weight float64
Enabled bool
}
Four node types: Input, Output, Hidden and Bias. Inputs and bias nodes are constant sources - an input passes its value through untouched and a bias node emits 1 - so they ignore their own bias, their activation, and anything wired into them.
ActivationFn is a name, not a function, because a genome has to survive a trip through encoding/json and come back. The names are resolved against a registry at compile time.
Enabled is there because NEAT switches connections off rather than deleting them. A disabled gene is still a gene: it still has a historical marking, it still lines up under crossover, and it can be switched back on later.
The registry
var ActivationRegistry = newActivationRegistry()
Nineteen functions - sigmoid, tanh, relu, gauss, sin, abs, cube and so on - and you can register your own. Reads are lock-free: the table is swapped atomically on write, because Get is called for every node of every genome of every generation and a mutex there would be contention for nothing.
Most of them clamp their input first:
func SigmoidFn(x float64) float64 {
x = clamp(5*x, -60, 60)
return 1.0 / (1.0 + math.Exp(-x))
}
// clamp limits x to [lo, hi]. math.Max and math.Min are not used because they
// special-case NaN and signed zero on every call, which shows up when an
// activation runs for every node of every genome in a generation.
func clamp(x, lo, hi float64) float64 {
if x > hi {
return hi
}
if x < lo {
return lo
}
return x
}
That is not a micro-optimisation for its own sake. Evolution will find a genome with a weight of 8 feeding a node with a bias of 8 feeding an exponential, and without the clamp the whole population’s fitness goes to NaN and the run quietly stops meaning anything.
What compiling does
// Compile builds a runnable network from a genome's nodes and connections.
//
// Connections that are disabled, that reference a node not in nodes, or that
// lead into an input or bias node are dropped. Compile fails if the remaining
// connections contain a cycle, if a node uses an unregistered activation
// function or an unknown type, or if two nodes share an ID.
func Compile(nodes []Node, connections []Connection) (*Network, error)
Three things get resolved once, so that activating never has to do them again:
genome compiled
Node{ID: 7, Fn: "sigmoid"} nodes[3] = {
Connection{From: 4, To: 7, kind: kindComputed,
Weight: 0.8} bias: 0.31,
Connection{From: 5, To: 7, activation: SigmoidFn,
Weight: -1.2} inputs: [{from: 1, weight: 0.8},
{from: 2, weight: -1.2}],
}
IDs and names slice indices and function pointers,
in evaluation order
The evaluation order comes from a topological sort - Kahn’s algorithm over a flat adjacency layout - so that by the time a node is reached, every node feeding it already has a value:
// topologicalOrder fills order with an evaluation order in which every node
// appears after all the nodes feeding it.
func topologicalOrder(outStart, outTargets, inDegree, order, queue []int) error {
queue = queue[:0]
for i := range inDegree {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
sorted := 0
for len(queue) > 0 {
i := queue[len(queue)-1]
queue = queue[:len(queue)-1]
order[sorted] = i
sorted++
for k := outStart[i]; k < outStart[i+1]; k++ {
to := outTargets[k]
inDegree[to]--
if inDegree[to] == 0 {
queue = append(queue, to)
}
}
}
if sorted != len(inDegree) {
return fmt.Errorf("%w and cannot be activated feed-forward", ErrCycle)
}
return nil
}
If it cannot order every node, there is a cycle, and a feed-forward network with a cycle in it is not a network - it is a mistake. That check is why mutateAddConnection can be relaxed about what it wires up.
Everything in flat arrays
The obvious layout is a slice of inputs per node. It allocates once per node and again every time one grows, and a population compiles every genome afresh every generation, so that adds up to a lot of garbage.
Instead, the dozen small integer tables compiling needs are carved out of one allocation:
// intTables hands out fixed-size integer slices from one backing array, so
// that the dozen small tables compile needs cost one allocation between them.
type intTables struct {
buf []int
}
// take returns the next size ints, zeroed, with no spare capacity so that an
// append can never spill into the table after it.
func (t *intTables) take(size int) []int {
s := t.buf[:size:size]
t.buf = t.buf[size:]
return s
}
and every node’s inputs are windows into one shared array:
// One backing array for every node's inputs, forward and remembered
// alike; each node takes two adjacent windows of it. Every edge lands in
// exactly one window, so the total never exceeds len(edges): the array
// never reallocates and the windows handed out stay valid.
all := make([]weightedInput, 0, len(edges))
The three-index slice expression - all[start:split:split] - is what makes that safe. Without capping the capacity, an append to one node’s inputs would silently overwrite the next node’s.
Activating
for i := range n.nodes {
node := &n.nodes[i]
switch node.kind {
case kindInput:
// Sensors pass their value through untouched.
values[i] = input[node.inputPos]
case kindBias:
values[i] = 1
default:
state := node.bias
for _, in := range node.inputs {
state += values[in.from] * in.weight
}
for _, in := range node.remembered {
state += mem.previous[in.from] * in.weight
}
values[i] = node.activation(state)
}
}
That is the whole of it. No map lookups, no graph walking, no allocation.
kind is a uint8 rather than the NodeType string it came from, because this switch runs for every node of every activation and a string comparison per node is not free.
Three ways in:
output, err := net.Activate(input) // allocates the output slice
err = net.ActivateInto(input, output) // reuses yours; zero allocations
err = net.Step(mem, input, output) // recurrent, with memory
A compiled network is immutable, so Activate is safe from any number of goroutines at once. The scratch buffer it needs comes from a sync.Pool, so concurrent callers do not fight over one.
Memory
A feed-forward network answers only from what it is being shown. A recurrent one can answer from what it has seen.
// CompileRecurrent builds a network that may contain loops.
//
// Nodes are evaluated in the order they are given, which for a genome is layer
// order with each layer in the order its nodes were added. A connection from a
// node earlier in that order to one later behaves exactly as it does in a
// feed-forward network; any other - to a node earlier in the order, or to
// itself - reads the value its source held at the end of the previous
// activation.
So there is no cycle to resolve inside a single pass, and a genome with no backward connections compiles to exactly the same network either way.
evaluation order: in0 in1 h0 h1 out
h1 -> h0 backwards in the order, so h0 reads what h1 held last step
h0 -> out forwards, so it is an ordinary connection this step
h1 -> h1 itself, which is the smallest memory there is
What it costs is that activation is no longer a pure function of the input, so the remembered values have to live somewhere:
// Memory is what a recurrent network carries from one activation to the next.
//
// It belongs to whoever is running the network rather than to the network
// itself, so that one compiled network can be run on many goroutines at once,
// each with its own. Reset it between episodes: a network that starts a game
// still remembering the end of the last one is being asked a question about a
// board that no longer exists.
type Memory struct {
previous []float64
}
Putting the memory on the caller rather than on the network is the decision that keeps everything else simple. A network stays immutable, evaluation stays parallel, and “reset between episodes” is something the evaluator does rather than something the library has to guess at.
What is next
That is the part that runs. Next: the part that gets evolved.