neat

package module
v0.0.0-...-e130fdf Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 12, 2016 License: BSD-2-Clause Imports: 6 Imported by: 0

README

Update

This project has been discontinued here and continued under a new project called EVO by klokare.

RedQ.NEAT

This a Go implementation of NeuralEvolution of Augmenting Topologies (NEAT). From the NEAT F.A.Q.

NEAT stands for NeuroEvolution of Augmenting Topologies. It is a method for evolving artificial neural networks with a genetic algorithm. NEAT implements the idea that it is most effective to start evolution with small, simple networks and allow them to become increasingly complex over generations. That way, just as organisms in nature increased in complexity since the first cell, so do neural networks in NEAT. This process of continual elaboration allows finding highly sophisticated and complex neural networks.

More information will be provided on the blog redq.me.

Installation

go get github.com/rqme/neat

Usage

The API documentation can be found at GoDoc.

The Context and Experiment are the central components of the library. The latter encapsulates everything needed for execution and the former provides access to all the necessary helpers. There are several convenience functions in the starter package.

RedQ.NEAT includes several demonstration experiments, each built at the onset of adding a new feature (like phased mutation) or concept (like Novelty Search). These proof-of-concepts are intended to valid this library with the idea being tested as well as compare different helpers (such as HyperNEAT vs regular NEAT). The experiments are each in their own package in the x/experiments directory.

Running experiments

Each experiment builds off the trials package which provides a way to compare multiple runs of an experiment against each other. This package provides several command line arguments that are common to all experiments and displays its output in the console window. For example, here is the output of the XOR experiment:

$ xor --check-stop --trials 40
Run   Iters.   Seconds    Nodes     Conns    Fitness   Fail   Comment 
--- --------- --------- --------- --------- --------- ------ ---------
  0        28     1.339         9        16    16.000        
  1        26     1.192         8        14    15.443        
  2        59     3.384         7        17    16.000        
  3        59     3.609        14        28    16.000        
...
 36        45     2.513        11        20    16.000        
 37        30     1.265         7        12    12.250        
 38        28     1.246         9        17    16.000        
 39        19     0.822         6        12    13.930        

Summary for trials excluding failures (and time for skipped)
      Iters.   Seconds    Nodes     Conns    Fitness
--- --------- --------- --------- --------- ---------
AVG        34     1.769         9        17    14.894        
MED        32     1.625         9        16    15.996        
SDV        13     0.905         2         5     1.637        
MIN         9     0.303         5         7    10.782        
MAX        66     4.503        15        33    16.000  
Common command-line arguments
flag description default
config-name Common name used as a prefix to archive files defaults to the name of the executable
config-path Directory containing the initial configuration file and, if available, state files Current directory
trials The number of trial runs to perform 10
check-stop Experiments which do not end with an explicit stop are considered to have failed. false
show-work Informs the Evaluator (if it implements Demonstrable) to show its work during evaluation. This is used only for the best genome. false
skip-evolve Skips evolution and only performs summary of archived runs. Best used with --show-work and setting the config-path to the ArchivePath used in the settings file. false

Experiments

XOR

Exclusive OR, or XOR for short, is the starter experiment to verify the NEAT (called Classic in RedQ.NEAT) functionality. Located in the x/examples/xor directory, the package produces a standalone executable file. A configuration file, xor-config.json, is provided.

The experiment provides no new command-line arguments but it is recommended to use --check-stop when running to catch trials that do not produce a solution.

RedQ.NEAT was able to find a solution in 40 out of 40 trials. The median number of nodes and connections were 9 and 16 respectively. The results of this experiment are detailed in the wiki.

Background

The core of this library, often called Classic in the code, was written from the ground up using Dr. Kenneth Stanley's PhD dissertation as a guide. NEAT has changed a bit since that paper and I have made some adjustments based on the F.A.Q. I have also add some flexibility in the design to allow for growing the library via helpers which will provide for adding HyperNEAT, Novelty Search, etc. to the library without changing the core API.

The library and proof-of-concept experiments utilize SVG to visualize the network of the best genome as well as the experiment's history. This visualization is based on the NeuroEvolution Visualization Toolkit (NEVT). Each image is output into an .html file for viewing from your desktop or presented through a web server.

Documentation

Overview

Copyright (c) 2015, Brian Hummer (brian@redq.me) All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  • Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

Constants

This section is empty.

Variables

Functions

func DirectActivation

func DirectActivation(x float64) float64

func InverseAbsActivation

func InverseAbsActivation(x float64) float64

func Run

func Run(e *Experiment) error

Runs a configured experiment. If restoring, including just the configuration, this must be done prior to calling Run.

func SigmoidActivation

func SigmoidActivation(x float64) float64

func SteependSigmoidActivation

func SteependSigmoidActivation(x float64) float64

func TanhActivation

func TanhActivation(x float64) float64

Types

type ActivationType

type ActivationType byte
const (
	Direct          ActivationType = iota + 1 // 1
	SteependSigmoid                           // 2
	Sigmoid                                   // 3
	Tanh                                      // 4
	InverseAbs                                // 5
)

func (ActivationType) Range

func (a ActivationType) Range() (float64, float64)

func (ActivationType) String

func (a ActivationType) String() string

type Archiver

type Archiver interface {
	// Archives the current configuration and state to a more permanent medium
	Archive(Context) error
}

Helper which provides access to archive storage

type Behaviorable

type Behaviorable interface {
	// Returns the expressed behaviors
	Behavior() []float64
}

Behaviorable describes an item tracks behaviors expressed during evaluation

type Comparer

type Comparer interface {
	// Returns the compatibility (similarity) between two genomes
	Compare(g1, g2 Genome) (float64, error)
}

Helper to compare two genomes similarity

type Connection

type Connection struct {
	Innovation     int     // Innovation number for this connection
	Source, Target int     // Innovation numbers of the source and target nodes
	Weight         float64 // Connection weight
	Enabled        bool    // Is this connection enabled?
}

Definition of a synapse

func (Connection) Key

func (c Connection) Key() (k InnoKey)

func (Connection) String

func (c Connection) String() string

type Connections

type Connections map[int]Connection

func (Connections) MarshalJSON

func (cm Connections) MarshalJSON() ([]byte, error)

func (*Connections) UnmarshalJSON

func (cm *Connections) UnmarshalJSON(data []byte) error

type Context

type Context interface {
	// Component helpers
	Archiver() Archiver
	Comparer() Comparer
	Crosser() Crosser
	Decoder() Decoder
	Evaluator() Evaluator
	Generator() Generator
	Mutator() Mutator
	Searcher() Searcher
	Speciater() Speciater
	Visualizer() Visualizer

	// State is a registry of elements to be persisted
	State() map[string]interface{}

	// Returns the next ID in the sequence
	NextID() int

	// Returns the innovation number for the gene
	Innovation(t InnoType, k InnoKey) int
}

type Contextable

type Contextable interface {
	SetContext(Context) error
}

Contextable describes an item that can receive a context

type Crosser

type Crosser interface {
	// Returns new genome that is a cross between two genomes
	Cross(g1, g2 Genome) (Genome, error)
}

Helper to produce new genome

type Crossoverable

type Crossoverable interface {
	SetCrossover(bool) error
}

type Decoder

type Decoder interface {
	// Returns a decoded version of the genome
	Decode(Genome) (Phenome, error)
}

Helper to decode a genome into a phenome

type Demonstrable

type Demonstrable interface {
	// ShowWork toggles the flag informing the helper to show (or) not the details during execution
	ShowWork(bool)
}

Demonstrable indicates that a helper is capable of showing (or hiding) detail of its work during execution. This is typically employed by an evaluator and turned on when evaluating the "best" genome after the evolution is completed.

type Evaluator

type Evaluator interface {
	// Evaluates a phenome for the problem. Returns the result.
	Evaluate(Phenome) Result
}

type Experiment

type Experiment struct {
	ExperimentSettings
	// contains filtered or unexported fields
}

Experiment provides the definition of how to solve the problem using NEAT

func (Experiment) Context

func (e Experiment) Context() Context

func (Experiment) Iteration

func (e Experiment) Iteration() int

func (Experiment) Population

func (e Experiment) Population() Population

func (*Experiment) SetContext

func (e *Experiment) SetContext(x Context) error

func (Experiment) Stopped

func (e Experiment) Stopped() bool

func (Experiment) String

func (e Experiment) String() string

String returns a description of the experiment

type ExperimentSettings

type ExperimentSettings interface {
	Iterations() int
	Traits() Traits
	FitnessType() FitnessType
	ExperimentName() string
}

type FitnessType

type FitnessType byte
const (
	Absolute FitnessType = iota + 1 // 1
	Relative                        // 2
)

func (FitnessType) String

func (f FitnessType) String() string

type Generator

type Generator interface {
	// Generates a subsequent population based on the current one
	Generate(curr Population) (next Population, err error)
}

A helper to generate populations

type Genome

type Genome struct {
	ID          int         // Identifier for this genome
	SpeciesIdx  int         // Index of species in the population
	Nodes       Nodes       // Neuron definitions
	Conns       Connections // Synapse definitions
	Traits      []float64   // Trait values
	Fitness     float64     // Fitness of genome as it relates to the problem itself
	Improvement float64     // Fitness of genome as it relates to the improvement of the population
	Birth       int         // Generation during which this genome was born
}

An encoded solution

func CopyGenome

func CopyGenome(g1 Genome) (g2 Genome)

Returns a copy of the genome

func (Genome) Complexity

func (g Genome) Complexity() int

func (Genome) GenesByInnovation

func (g Genome) GenesByInnovation() ([]Node, []Connection)

Returns the genome's genes by their markers

func (Genome) GenesByPosition

func (g Genome) GenesByPosition() ([]Node, []Connection)

Returns the genome's genes by their keys

func (Genome) String

func (g Genome) String() string

type Genomes

type Genomes []Genome

func (Genomes) Len

func (gs Genomes) Len() int

func (Genomes) Less

func (gs Genomes) Less(i, j int) bool

func (Genomes) Swap

func (gs Genomes) Swap(i, j int)

type Improvable

type Improvable interface {
	Improvement() float64
}

type InnoKey

type InnoKey [2]float64

type InnoType

type InnoType byte
const (
	NodeInnovation InnoType = iota + 1
	ConnInnovation
)

type Mutator

type Mutator interface {
	// Mutates a genome
	Mutate(*Genome) error
}

Helper to mutate a genome

type Network

type Network interface {

	// Activates the neural network using the inputs. Returns the ouput values.
	Activate(inputs []float64) (outputs []float64, err error)
}

Represents a neural network

type NeuronType

type NeuronType byte
const (
	Bias   NeuronType = iota + 1 // 1
	Input                        // 2
	Hidden                       // 3
	Output                       // 4
)

func (NeuronType) String

func (n NeuronType) String() string

type Node

type Node struct {
	Innovation int
	X, Y       float64
	NeuronType
	ActivationType
}

Definition of a neuron

func (Node) Key

func (n Node) Key() (k InnoKey)

func (Node) String

func (n Node) String() string

type Nodes

type Nodes map[int]Node

Nodes is a map of nodes by innovation number

func (Nodes) MarshalJSON

func (nm Nodes) MarshalJSON() ([]byte, error)

MarshalJSON marshals the nodes map into JSON

func (*Nodes) UnmarshalJSON

func (nm *Nodes) UnmarshalJSON(data []byte) error

UnmarshalJSON unmarshals JSON into a nodes map

type OriginalFitnessable

type OriginalFitnessable interface {
	OriginalFitness() float64
}

type Phenomable

type Phenomable interface {
	// Provides the phenomes to the helper
	SetPhenomes(Phenomes) error
}

A helper that would like to see the active phenomes

type Phenome

type Phenome interface {
	ID() int           // The identify of the underlying genome
	Traits() []float64 // Trait values which could be used during evaluation
	Network            // The decoded genome
}

A decoded solution

type Phenomes

type Phenomes []Phenome

type Populatable

type Populatable interface {
	// Provides the population to the helper
	SetPopulation(Population) error
}

A helper that would like to see the population

type Population

type Population struct {
	Generation int
	Species    []Species
	Genomes    Genomes
}

Population of genomes for a given generation

type Restorer

type Restorer interface {
	// Restores the configuration and/or the state of a previous experiment
	Restore(Context) error
}

Helper to restore an experiment

type Result

type Result interface {
	ID() int          // Returns the ID of the phenome
	Fitness() float64 // Returns the fitness of the phenome for the problem
	Err() error       // Returns the error, if any, occuring while evaluating the phenome.
	Stop() bool       // Returns true if the stop condition was met
}

The result of an evaluation

type Results

type Results []Result

type Searcher

type Searcher interface {
	// Searches the problem's solution space using the phenomes
	Search([]Phenome) ([]Result, error)
}

Helper to search the problem's solution space

type Setupable

type Setupable interface {
	// Sets up the helper
	Setup() error
}

Provides setup actions in the helper's lifestyle

type Speciater

type Speciater interface {
	// Assigns the genomes to a species. Returns new collection of species.
	Speciate(curr []Species, genomes []Genome) (next []Species, err error)
}

Helper to assign genomes to an exist or new species

type Species

type Species struct {
	Age         int // Age in terms of generations
	Stagnation  int // Number of generations since an improvement
	Improvement float64
	Example     Genome
}

type Takedownable

type Takedownable interface {
	// Takes down the helper
	Takedown() error
}

Provides takedown actions in the helper's lifecycle

type Trait

type Trait struct {
	Name      string
	Min, Max  float64
	IsSetting bool
}

type Traits

type Traits []Trait

func (Traits) IndexOf

func (t Traits) IndexOf(name string) int

type Trialable

type Trialable interface {
	SetTrial(int) error
}

type Visualizer

type Visualizer interface {
	// Creates visual(s) of the population
	Visualize(Population) error
}

Helper to visualize a population

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL