neuroevolution of augmenting topologies.


home | gallery | neuroevolution of augmenting topologies (UNFINISHED)


Neuroevolution of Augmenting Topologies (furthermore referred to as NEAT) is a machine learning algorithm. (todo: insert something about what it does broadly, especially compared to other neural networks.)

The NEAT algorithm shall now be described.

The genome and phenome (a network)

In NEAT, networks are represented in two ways: the "genome", and the "phenome". The genome is a flat representation of all nodes and all genes (connections) in a network. It is used to track all data about the network, including data not useful during the network's evaluation. The phenome is the genome transformed into an easily-traversable format. A phenome only need exist while being evaluated, while a genome must always maintained during an entire generation. (A generation refers to the epoch in which all networks are evaluated once.)


A genome is a structure containing a list of nodes and a list of genes (connections).

A node contains an id:int from [1,∞), and a kind, which can either be sensor, bias, hidden, or output. A sensor node corresponds to a specific input to the network. A bias node is a sensor node that has a constant value of 1.0. An output node is a node that corresponds to a specific output in the network. A hidden node is a node added by a structural mutation (discussed later), somewhere between the sensor layer and the output layer.

A gene contains an in_node:int identifying which node gives it input, an out_node:int identifying which node it goes out to, the weight of the connection as a float from [-1,1], an enabled bit, and an "innovation number" (discussed later) innov:int from [1,∞).

Programmatically, this looks like:

type kind = Sensor | Bias | Hidden | Output
type node = 
    { id   : int (* [1,∞) *)
    ; kind : kind

type gene = 
    { in_node  : int   (* [1,∞)  *)
    ; out_node : int   (* [1,∞)  *)
    ; weight   : float (* [-1,1] *)
    ; enabled  : bool
    ; innov    : int   (* [1,∞)  *)

type genome = 
    { nodes : list node
    ; genes : list gene

NB: I use the list type here in order to remain purely functional, but in impure languages you are welcome to substitute it for an equivalent container type like an array for efficiency.


The phenome of a network is the genome with all information unnecessary for evaluation removed and restructured. The genome representation, while convenient for random insertion of nodes/genes and tracking important data like innovation numbers across generations, is unsuited for traversal. The actual network being evaluated does not need to keep track of anything other than nodes and the weights of the enabled outgoing genes from nodes. So, a reduced gene type is used for the phenome's genes:

type phenome_gene = 
    { out_node : int   (* [1,∞)  *)
    ; weight   : float (* [-1,1] *)

And thus a phenome is simply:

type phenome = map node (list phenome_gene)

In order to convert from a genome to a phenome, you must write a conversion function. (todo: give an example conversion function.)

Network starting conditions, and mutations

All genomes begin minimally (i.e. genome.genes begins as []). The network itself is gradually created through one of three mutations. There are two kinds of mutations: structural mutations and nonstructural mutations. Structural mutations add nodes or genes to the network. The (only) nonstructural mutation adjusts or randomizes a weight of the existing structure. (todo: add images of each of the mutations.)

Mutation: Add Connection (structural)

Let in_node be the id of a random node in the network. Let out_node be the id of a random Hidden or Output node. Let weight be a random float from [-1,1]. Let i be the current innovation number. Insert { in_node; out_node; weight; enabled = true; innov = i + 1} into the network's genome.genes. The global innovation number is incremented.

Mutate Add Node (structural)

Let (todo: fill out.)

Mutation: Adjust weight (nonstructural)

Let (todo: fill out.)