goNEAT

README

goNEAT 🇺🇦

NeuroEvolution — evolving Artificial Neural Networks topology from the scratch

Branch	Tests	Coverage	Linting	Code Security
master

Overview

This repository provides implementation of NeuroEvolution of Augmenting Topologies (NEAT) method written in Go language.

The NeuroEvolution (NE) is an artificial evolution of Neural Networks (NN) using genetic algorithms to find optimal NN parameters and network topology. NeuroEvolution of NN may assume a search for optimal weights of connections between NN nodes and search for the optimal topology of the resulting network graph. The NEAT method implemented in this work searches for optimal connection weights and the network graph topology for a given task (number of NN nodes per layer and their interconnections).

Minimum requirements

Requirement	Notes
Go version	Go1.17 or higher

Releases

Please do not depend on master as your production branch. Use releases instead.

Quick Start

You can evaluate the NEAT algorithm performance by running the following command:

cd $GOPATH/src/github.com/yaricom/goNEAT
go run executor.go -out ./out/xor -context ./data/xor.neat -genome ./data/xorstartgenes -experiment XOR

Or

make run-xor

The command above will run the XOR problem solver experiment and save the collected data samples. You can use saved experimental data for analysis using standard plotting libraries as in the figure below.

The figure was created using Matplotlib. You can find more details in the Jupyter notebook.

Documentation

You can find the algorithm performance evaluation and related documentation in the project's wiki

The goNEAT library saves results of the experiments using Numpy NPZ format, which allows analysis of collected experimental data samples using a variety of readily available Python libraries.

For your reference, we included Jupyter notebook with an example of the collected experimental data analysis, which can be used as a starter kit to analyze data samples acquired from your experiments.

Installation

Make sure you have at least GO 1.15.x installed onto your system and execute the following command:

go get github.com/yaricom/goNEAT

For new projects, consider using the v2 of the library with the following import:

import "github.com/yaricom/goNEAT/v3"

Essential Packages

genetics package

The genetics package provides the genetic part of the NEAT algorithm describing all the machinery related to genome mutations, mating, and speciation of the population of organisms.

It contains implementation of all important types related to the NEAT algorithm:

• Gene type in this system specifies a "Connection Gene."
• MIMOControlGene type is the Multiple-Input Multiple-Output (MIMO) control Gene which allows creation of modular genomes
• Genome type is the primary source of genotype information used to create a phenotype.
• Organism type is Genotypes (Genomes) and Phenotypes (Networks) combined with fitness information, i.e. the genotype and phenotype together.
• Population type is a group of Organisms including their Species
• Species type is a group of similar Organisms. Reproduction takes place mostly within a single species, so that compatible organisms can mate.

Additionally, it contains variety of utility functions to serialise/deserialize specified above types using two supported data formats:

• plain text
• YAML

The current implementation supports sequential and parallel execution of evolution epoch which controlled by related parameter in the NEAT context options.

math package

Package math defines standard mathematical primitives used by the NEAT algorithm as well as utility functions

network package

Package network provides data structures and utilities to describe Artificial Neural Network and network solvers.

The most important types are:

• NNode type defines the node of the network and is a part of organism's genotype as well as phenotype
• Link type is a connection from one node to another with an associated weight.
• Network type is a collection of all nodes within an organism's phenotype, which effectively defines Neural Network topology.
• Solver type defines network solver interface, which allows propagation of the activation waves through the underlying network graph.

The current implementation supports two types of network solvers:

• FastModularNetworkSolver is the network solver implementation to be used for large neural networks simulation.
• Standard Network Solver implemented by the Network type

The topology of the Neural Network represented by the Network fully supports the directed graph presentation as defined by Gonum graph package. This feature can be used for analysis of the network topology as well as encoding the graph in variety of popular graph presentation formats.

experiment package

Package experiment defines standard evolutionary epochs evaluators and experimental data samples collectors. It provides standardised approach to define experiments using the NEAT algorithm implementation.

The most important type here is:

• GenerationEvaluator is the interface to be implemented by custom experiments

You can find examples of GenerationEvaluator implementations at examples:

• pole - single-, double-pole balancing experiments
• xor - XOR solver experiment

The following code snippet demonstrates how to run experiments using different implementations of the GenerationEvaluator and the experiment.Execute:

// create experiment
expt := experiment.Experiment{
    Id:       0,
    Trials:   make(experiment.Trials, neatOptions.NumRuns),
    RandSeed: seed,
}
var generationEvaluator experiment.GenerationEvaluator
switch *experimentName {
case "XOR":
    expt.MaxFitnessScore = 16.0 // as given by fitness function definition
    generationEvaluator = xor.NewXORGenerationEvaluator(outDir)
case "cart_pole":
    expt.MaxFitnessScore = 1.0 // as given by fitness function definition
    generationEvaluator = pole.NewCartPoleGenerationEvaluator(outDir, true, 500000)
case "cart_2pole_markov":
    expt.MaxFitnessScore = 1.0 // as given by fitness function definition
    generationEvaluator = pole.NewCartDoublePoleGenerationEvaluator(outDir, true, pole.ContinuousAction)
case "cart_2pole_non-markov":
    generationEvaluator = pole.NewCartDoublePoleGenerationEvaluator(outDir, false, pole.ContinuousAction)
default:
    log.Fatalf("Unsupported experiment: %s", *experimentName)
}

// prepare to execute
errChan := make(chan error)
ctx, cancel := context.WithCancel(context.Background())

// run experiment in the separate GO routine
go func() {
    if err = expt.Execute(neat.NewContext(ctx, neatOptions), startGenome, generationEvaluator, nil); err != nil {
        errChan <- err
    } else {
        errChan <- nil
    }
}()

For more details, take a look at the experiment executor implementation provided with the goNEAT library.

neat package

Package neat is an entry point to the NEAT algorithm. It defines the NEAT execution context and configuration options.

You can find all available configuration options in the Options.

The configuration options can be saved either using plain text or the YAML format. We recommend using the YAML format for new projects because it allows for a more flexible setup and detailed documentation of the configuration parameters.

Take a look at the example configuration file to get a better understanding.

The NEAT context options can be read as follows:

// Loading YAML options
optFile, err := os.Open("./data/xor_test.neat.yml")
if err != nil {
	return err
}
options, err := neat.LoadYAMLOptions(optFile)

Or with plain-text format:

// Loading plain-text options
optFile, err := os.Open("./data/xor_test.neat")
if err != nil {
	return err
}
options, err := neat.LoadNeatOptions(optFile)

Phenotype Network Graph Visualization

The formats package provides support for various network graph serialization formats which can be used to visualize the graph with help of well-known tools. Currently, we have support for DOT and CytoscapeJS data formats.

The CytoscapeJS JSON format

Another important data format supported by the library is the CytoscapeJS JSON. The Network graph serialized into this format can be easily rendered using either Cytoscape App or the corresponding CytoscapeJS JavaScript library.

The following code snippet demonstrates how this can be done:

import (
"github.com/yaricom/goNEAT/v3/neat/network"
"github.com/yaricom/goNEAT/v3/neat/network/formats"
"bytes"
"fmt"
)

allNodes := []*network.NNode{
	network.NewNNode(1, network.InputNeuron), 
	network.NewNNode(2, network.InputNeuron), 
	network.NewNNode(3, network.BiasNeuron), 
	network.NewNNode(4, network.HiddenNeuron), 
	network.NewNNode(5, network.HiddenNeuron), 
	network.NewNNode(6, network.HiddenNeuron), 
	network.NewNNode(7, network.OutputNeuron), 
	network.NewNNode(8, network.OutputNeuron),
}

// HIDDEN 4
allNodes[3].connectFrom(allNodes[0], 15.0)
allNodes[3].connectFrom(allNodes[1], 10.0)
// HIDDEN 5
allNodes[4].connectFrom(allNodes[1], 5.0)
allNodes[4].connectFrom(allNodes[2], 1.0)
// HIDDEN 6
allNodes[5].connectFrom(allNodes[4], 17.0)
// OUTPUT 7
allNodes[6].connectFrom(allNodes[3], 7.0)
allNodes[6].connectFrom(allNodes[5], 4.5)
// OUTPUT 8
allNodes[7].connectFrom(allNodes[5], 13.0)

net := network.NewNetwork(allNodes[0:3], allNodes[6:8], allNodes, 0)

b := bytes.NewBufferString("")
err := formats.WriteCytoscapeJSON(b, net)
fmt.Println(b)

The produced output looks like the following:

{
  "elements": {
    "nodes": [
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#339FDC",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "1",
          "in_connections_count": 0,
          "neuron_type": "INPT",
          "node_type": "SENSOR",
          "out_connections_count": 1,
          "parent": "",
          "shape": "diamond"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#339FDC",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "2",
          "in_connections_count": 0,
          "neuron_type": "INPT",
          "node_type": "SENSOR",
          "out_connections_count": 2,
          "parent": "",
          "shape": "diamond"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#FFCC33",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "3",
          "in_connections_count": 0,
          "neuron_type": "BIAS",
          "node_type": "SENSOR",
          "out_connections_count": 1,
          "parent": "",
          "shape": "pentagon"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#009999",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "4",
          "in_connections_count": 2,
          "neuron_type": "HIDN",
          "node_type": "NEURON",
          "out_connections_count": 1,
          "parent": "",
          "shape": "hexagon"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#009999",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "5",
          "in_connections_count": 2,
          "neuron_type": "HIDN",
          "node_type": "NEURON",
          "out_connections_count": 1,
          "parent": "",
          "shape": "hexagon"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#009999",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "6",
          "in_connections_count": 1,
          "neuron_type": "HIDN",
          "node_type": "NEURON",
          "out_connections_count": 2,
          "parent": "",
          "shape": "hexagon"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#E7298A",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "7",
          "in_connections_count": 2,
          "neuron_type": "OUTP",
          "node_type": "NEURON",
          "out_connections_count": 0,
          "parent": "",
          "shape": "round-rectangle"
        },
        "selectable": true
      },
      {
        "data": {
          "activation_function": "SigmoidSteepenedActivation",
          "activation_value": 0,
          "background-color": "#E7298A",
          "border-color": "#CCCCCC",
          "control_node": false,
          "id": "8",
          "in_connections_count": 1,
          "neuron_type": "OUTP",
          "node_type": "NEURON",
          "out_connections_count": 0,
          "parent": "",
          "shape": "round-rectangle"
        },
        "selectable": true
      }
    ],
    "edges": [
      {
        "data": {
          "id": "1-4",
          "recurrent": false,
          "source": "1",
          "target": "4",
          "time_delayed": false,
          "weight": 15
        },
        "selectable": true
      },
      {
        "data": {
          "id": "2-4",
          "recurrent": false,
          "source": "2",
          "target": "4",
          "time_delayed": false,
          "weight": 10
        },
        "selectable": true
      },
      {
        "data": {
          "id": "2-5",
          "recurrent": false,
          "source": "2",
          "target": "5",
          "time_delayed": false,
          "weight": 5
        },
        "selectable": true
      },
      {
        "data": {
          "id": "3-5",
          "recurrent": false,
          "source": "3",
          "target": "5",
          "time_delayed": false,
          "weight": 1
        },
        "selectable": true
      },
      {
        "data": {
          "id": "5-6",
          "recurrent": false,
          "source": "5",
          "target": "6",
          "time_delayed": false,
          "weight": 17
        },
        "selectable": true
      },
      {
        "data": {
          "id": "4-7",
          "recurrent": false,
          "source": "4",
          "target": "7",
          "time_delayed": false,
          "weight": 7
        },
        "selectable": true
      },
      {
        "data": {
          "id": "6-7",
          "recurrent": false,
          "source": "6",
          "target": "7",
          "time_delayed": false,
          "weight": 4.5
        },
        "selectable": true
      },
      {
        "data": {
          "id": "6-8",
          "recurrent": false,
          "source": "6",
          "target": "8",
          "time_delayed": false,
          "weight": 13
        },
        "selectable": true
      }
    ]
  },
  "layout": {
    "name": "circle"
  },
  "style": [
    {
      "selector": "node",
      "style": {
        "background-color": "data(background-color)",
        "border-color": "data(border-color)",
        "border-width": 3,
        "label": "data(id)",
        "shape": "data(shape)"
      }
    },
    {
      "selector": "edge",
      "style": {
        "curve-style": "bezier",
        "line-color": "#CCCCCC",
        "target-arrow-color": "#CCCCCC",
        "target-arrow-shape": "triangle-backcurve",
        "width": 5
      }
    }
  ]
}

The above CYJS can be visualized as following with Cytoscape App.

You can find more interesting visualizations at project's Wiki.

The DOT format

The Network can be serialized into popular GraphViz DOT format. The following code snippet demonstrates how this can be done:

import (
"github.com/yaricom/goNEAT/v3/neat/network"
"github.com/yaricom/goNEAT/v3/neat/network/formats"
"bytes"
"fmt"
)

allNodes := []*network.NNode{
	network.NewNNode(1, network.InputNeuron), 
	network.NewNNode(2, network.InputNeuron), 
	network.NewNNode(3, network.BiasNeuron), 
	network.NewNNode(4, network.HiddenNeuron), 
	network.NewNNode(5, network.HiddenNeuron), 
	network.NewNNode(6, network.HiddenNeuron), 
	network.NewNNode(7, network.OutputNeuron), 
	network.NewNNode(8, network.OutputNeuron),
}

// HIDDEN 4
allNodes[3].connectFrom(allNodes[0], 15.0)
allNodes[3].connectFrom(allNodes[1], 10.0)
// HIDDEN 5
allNodes[4].connectFrom(allNodes[1], 5.0)
allNodes[4].connectFrom(allNodes[2], 1.0)
// HIDDEN 6
allNodes[5].connectFrom(allNodes[4], 17.0)
// OUTPUT 7
allNodes[6].connectFrom(allNodes[3], 7.0)
allNodes[6].connectFrom(allNodes[5], 4.5)
// OUTPUT 8
allNodes[7].connectFrom(allNodes[5], 13.0)

net := network.NewNetwork(allNodes[0:3], allNodes[6:8], allNodes, 0)
net.Name = "TestNN"

b := bytes.NewBufferString("")
err := formats.WriteDOT(b, net)
fmt.Println(b)

The DOT output can be saved into the file for subsequent visualization by variety of tools listed at GraphViz Downloads.

Conclusion

The experiments described in this work confirm that introduced NEAT algorithm implementation can evolve new structures in the Artificial Neural Networks (XOR experiments) and can solve reinforcement learning tasks under conditions of incomplete knowledge (single-pole balancing and double-pole balancing).

We hope that you will find great applications in your research and work projects for the provided NEAT algorithm's implementation as well as utilities to run experiments while collecting relevant data samples.

Projects Using goNEAT library

• Learning to play Asteroids in Golang with NEAT - interesting article about implementation of the intelligent agent to play classic Asteroid game using the NEAT algorithm.
• NEAT with Novelty Search - implementation of the Novelty Search optimization algorithm for solution search in the deceptive environments.
• Evolvable-Substrate HyperNEAT - is hypercube-based extension of the NEAT allowing to encode ANNs in the substrate with specific geometric topology and with significant number of neural units.

References

• The original C++ NEAT implementation created by Kenneth Stanley, see: NEAT
• Other NEAT implementations may be found at NEAT Software Catalog
• Iaroslav Omelianenko, NeuroEvolution — evolving Artificial Neural Networks topology from the scratch, Medium, 2018
• Kenneth O. Stanley, Ph.D. Dissertation: EFFICIENT EVOLUTION OF NEURAL NETWORKS THROUGH COMPLEXIFICATION, Department of Computer Sciences, The University of Texas at Austin, Technical Report~AI-TR-04–39, August 2004
• Hands-On NeuroEvolution with Python, Build high-performing artificial neural network architectures using neuroevolution-based algorithms, Iaroslav Omelianenko, Birmingham: Packt Publishing, 2019

This source code maintained and managed by Iaroslav Omelianenko