goevo

README

GoEvo Rewrite

This branch is an experimental rewrite from the ground up. I am making it as fast, simple, and bug-free as possible.

GoEvo - Evolutionary Algorithms Based on NEAT, in Golang

GoEvo is a package for Go that performs a variety of evolutionary algorithms to optimise a neural network. The networks do not only evolve their weights, but also the neurons within, and therefore their whole structure. I have tried to base GoEvo networks on the ones described in the original NEAT paper, Evolving Neural Networks Through Augmenting Topologies, however, I have taken some liberties during development. Despite this, the networks function in broadly the same way as originally described.

GoEvo also does not just support the NEAT algorithm. NEAT genotypes can be used with many other types of genetic algorithms, with various methods of selection, mutation, and speciation. For this reason, GoEvo strives to support many different algorithms, all focusing on optimising the genotype type, which equates to DNA. GoEvo is also built to be very extensible, allowing the user to implement new evolutionary processes with ease.

About NEAT

NeuroEvolution of Augmenting Topologies (NEAT) is an algorithm to grow neural networks optimised for a specific task. Instead of traditional machine learning, NEAT is not usually used in a supervised manner where the correct answer is always known, but instead tends to be used in scenarios like controlling a robot to walk, where there is no correct solution to the problem.

There are two main components to NEAT:

• Genotype/phenotype: A genotype represents DNA, and can be crossed over and mutated. A phenotype is the brain that results from compiling the genotype. The phenotype is the part that can take a set of inputs and return an output.
• Evolutionary Algorithm: This is analogous to the environment that the phenotypes live in. The Evolutionary algorithm of NEAT tracks each genotype and assigns it to a species. The Evolutionary algorithm also chooses which genotypes can reproduce to create the next generation.

In GoEvo, there is only one genotype implementation, but there are many alternative evolutionary algorithm implementations, including the original NEAT one.

Example Genotype

Below is a visualisation (generated by the Draw() method) of a genotype that was evolved to solve the XOR problem. Data flows from right to left in this drawing. Green nodes represent input neurons, black nodes are hidden neurons, and red nodes are outputs. Each node has a unique ID (N301 for example), an execution order ([4]), and an activation (tanh). Synapses, represented by arrows, each have a weight, which in this instance was capped between -3 and 3.

You may have noticed that there are three inputs, instead of the two you would expect. This is because NEAT networks you need to manually add a bias by appending an additional 1 onto the end of the input sequence. In this case, the bias node, represented as N3, is actually not connected to any other nodes, suggesting that it was not necessary.

To validate the network does indeed work, I hardcoded the evolved network quickly in python, in the file README_ASSETS/xor.py. You can see that the network does in fact perform an XOR operation.

GoEvo Features

• Fast gene mutation and crossover
• Efficient execution of genes by first compiling them into a Phenotype
• Both forward and recurrent connections supported
• Hidden neurons can each have different activations
• Supports many types of genetic algorithms for evolving Genotypes
• Easy saving and loading of genotypes using json
• Supports drawing genotypes to an image using graphviz

Future Work

• HyperNEAT: I already implemented this in the original package before I rewrote it, so this should be trivial. HyperNEAT basically allows NEAT to evolve much larger networks.
• Implement NEAT algorithm: This should be coming very soon, as I just need to convert the code from the original into this package. Currently, there is a simple population.
• Document EVERYTHING
• Examples directory
• More Tests
• Implement a second phenotype that propagates one neuron per timestep. This is possibly the original way that it was done.

Documentation

Index

• type Activation
  • func (a Activation) MarshalJSON() ([]byte, error)
  • func (a Activation) String() string
  • func (a *Activation) UnmarshalJSON(bs []byte) error
• type Agent
  • func NewAgent(gt *Genotype) *Agent
• type Counter
  • func NewCounter() *Counter
  • func (c *Counter) Next() int
• type Forwarder
• type Genotype
  • func NewGenotype(counter *Counter, inputs, outputs int, outputActivation Activation) *Genotype
  • func (g *Genotype) AddRandomNeuron(counter *Counter, activations ...Activation) bool
  • func (g *Genotype) AddRandomSynapse(counter *Counter, weightStd float64, recurrent bool) bool
  • func (g *Genotype) Build() *Phenotype
  • func (g *Genotype) Clone() *Genotype
  • func (g *Genotype) CrossoverWith(g2 *Genotype) *Genotype
  • func (g *Genotype) Draw(width, height float64) image.Image
  • func (g *Genotype) MarshalJSON() ([]byte, error)
  • func (g *Genotype) MutateRandomActivation(activations ...Activation) bool
  • func (g *Genotype) MutateRandomSynapse(std float64) bool
  • func (g *Genotype) NumHiddenNeurons() int
  • func (g *Genotype) NumInputNeurons() int
  • func (g *Genotype) NumNeurons() int
  • func (g *Genotype) NumOutputNeurons() int
  • func (g *Genotype) NumSynapses() int
  • func (g *Genotype) RemoveRandomSynapse() bool
  • func (g *Genotype) ResetRandomSynapse() bool
  • func (g *Genotype) UnmarshalJSON(bs []byte) error
  • func (g *Genotype) Validate() error
• type NeuronID
• type Phenotype
  • func (p *Phenotype) Forward(x []float64) []float64
• type Reproduction
• type Selection
• type SimplePopulation
  • func NewSimplePopulation(newGenotype func() *Genotype, n int) *SimplePopulation
  • func (p *SimplePopulation) Agents() []*Agent
  • func (p *SimplePopulation) NextGeneration(selection Selection, reproduction Reproduction) *SimplePopulation
• type StdReproduction
  • func (r *StdReproduction) Reproduce(a, b *Genotype) *Genotype
• type SynapseEP
• type SynapseID
• type TournamentSelection
  • func (t *TournamentSelection) Select() *Agent
  • func (t *TournamentSelection) SetAgents(agents []*Agent)

Types

type Activation

type Activation int

const (
	Relu Activation = iota
	Linear
	Sigmoid
	Tanh
	Sin
	Cos
)

func (Activation) MarshalJSON

func (a Activation) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (Activation) String

func (a Activation) String() string

func (*Activation) UnmarshalJSON

func (a *Activation) UnmarshalJSON(bs []byte) error

UnmarshalJSON implements json.Unmarshaler.

type Agent

type Agent struct {
	Genotype *Genotype
	Fitness  float64
}

func NewAgent

func NewAgent(gt *Genotype) *Agent

type Counter

type Counter struct {
	// contains filtered or unexported fields
}

func NewCounter

func NewCounter() *Counter

func (*Counter) Next

func (c *Counter) Next() int

type Forwarder

type Forwarder interface {
	Forward([]float64) []float64
}

type Genotype

type Genotype struct {
	// contains filtered or unexported fields
}

Genotype represents the DNA of a creature. It is optimised for mutating, but cannot be run directly.

func NewGenotype

func NewGenotype(counter *Counter, inputs, outputs int, outputActivation Activation) *Genotype

func (*Genotype) AddRandomNeuron

func (g *Genotype) AddRandomNeuron(counter *Counter, activations ...Activation) bool

func (*Genotype) AddRandomSynapse

func (g *Genotype) AddRandomSynapse(counter *Counter, weightStd float64, recurrent bool) bool

func (*Genotype) Build

func (g *Genotype) Build() *Phenotype

func (*Genotype) Clone

func (g *Genotype) Clone() *Genotype

clones the genotype

func (*Genotype) CrossoverWith

func (g *Genotype) CrossoverWith(g2 *Genotype) *Genotype

Simple crossover of the genotypes, where g is fitter than g2

func (*Genotype) Draw

func (g *Genotype) Draw(width, height float64) image.Image

Render this genotype to an image.Image, with a width and height in inches

func (*Genotype) MarshalJSON

func (g *Genotype) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (*Genotype) MutateRandomActivation

func (g *Genotype) MutateRandomActivation(activations ...Activation) bool

Change the activation of a rnadom HIDDEN neuron to one of the supplied activations

func (*Genotype) MutateRandomSynapse

func (g *Genotype) MutateRandomSynapse(std float64) bool

func (*Genotype) NumHiddenNeurons

func (g *Genotype) NumHiddenNeurons() int

func (*Genotype) NumInputNeurons

func (g *Genotype) NumInputNeurons() int

func (*Genotype) NumNeurons

func (g *Genotype) NumNeurons() int

func (*Genotype) NumOutputNeurons

func (g *Genotype) NumOutputNeurons() int

func (*Genotype) NumSynapses

func (g *Genotype) NumSynapses() int

func (*Genotype) RemoveRandomSynapse

func (g *Genotype) RemoveRandomSynapse() bool

This will delete a random synapse. It will leave hanging neurons, because they may be useful later.

func (*Genotype) ResetRandomSynapse

func (g *Genotype) ResetRandomSynapse() bool

This will set the weight of a random synapse to 0. Kind of similar to disabling a synapse, which this implementation does not have.

func (*Genotype) UnmarshalJSON

func (g *Genotype) UnmarshalJSON(bs []byte) error

UnmarshalJSON implements json.Unmarshaler. TODO: needs more validation

func (*Genotype) Validate

func (g *Genotype) Validate() error

This will run as many checks as possible to check the genotype is valid. It is really only designed to be used as part of a test suite to catch errors with the package. This should never throw an error, but if it does either there is a bug in the package, or the user has somehow invalidated the genotype.

type NeuronID

type NeuronID int

type Phenotype

type Phenotype struct {
	// contains filtered or unexported fields
}

func (*Phenotype) Forward

func (p *Phenotype) Forward(x []float64) []float64

type Reproduction

type Reproduction interface {
	// A is assumed to be the fitter parent
	Reproduce(a, b *Genotype) *Genotype
}

type Selection

type Selection interface {
	SetAgents(agents []*Agent)
	Select() *Agent
}

type SimplePopulation

type SimplePopulation struct {
	// contains filtered or unexported fields
}

SimplePopulation has a single species, and generates the entire next generation by selcting and breeding from the previous

func NewSimplePopulation

func NewSimplePopulation(newGenotype func() *Genotype, n int) *SimplePopulation

func (*SimplePopulation) Agents

func (p *SimplePopulation) Agents() []*Agent

func (*SimplePopulation) NextGeneration

func (p *SimplePopulation) NextGeneration(selection Selection, reproduction Reproduction) *SimplePopulation

type StdReproduction

type StdReproduction struct {
	StdNumNewSynapses          float64
	StdNumNewRecurrentSynapses float64
	StdNumNewNeurons           float64
	StdNumMutateSynapses       float64
	StdNumPruneSynapses        float64
	StdNumMutateActivations    float64

	StdNewSynapseWeight    float64
	StdMutateSynapseWeight float64

	MaxHiddenNeurons int

	Counter             *Counter
	PossibleActivations []Activation
}

func (*StdReproduction) Reproduce

func (r *StdReproduction) Reproduce(a, b *Genotype) *Genotype

type SynapseEP

type SynapseEP struct {
	From NeuronID
	To   NeuronID
}

SynapseEP is the endpoints of a synapse

type SynapseID

type SynapseID int

type TournamentSelection

type TournamentSelection struct {
	TournamentSize int
	// contains filtered or unexported fields
}

func (*TournamentSelection) Select

func (t *TournamentSelection) Select() *Agent

func (*TournamentSelection) SetAgents

func (t *TournamentSelection) SetAgents(agents []*Agent)