evo

README

Evo

Evo is a framework for implementing evolutionary algorithms in Go.

go get github.com/cbarrick/evo

Documentation

https://godoc.org/github.com/cbarrick/evo

Status & Contributing

Evo is a general framework for developing genetic algorithms and more. It began life in fall 2015 as I studied evolutionary algorithms as an undergrad. The most recent release is v0.1.3.

Contributions are welcome! I am currently a student and inexperienced maintainer, so please bear with me as I learn. The focus of the project thus far has been on the API design and less on performance. I am particularly interested in hearing about use-cases that are not well covered and success stories of where Evo excels. Testing, code reviews, and performance audits are always welcome and needed.

Overview

Evo exposes a clean and flexible API oriented around two interfaces: Genome and Population. Genomes represent candidate solutions to the user's problem and are implemented by the user. Genomes define their own means of evolution, allowing for a multiplicity of techniques ranging from genetic algorithms to evolution strategies and beyond. Populations represent the architecture under which genomes are evolved. Multiple population types are provided by Evo to enable the construction of both common and novel architectures.

The body of the evolutionary loop is defined by the Evolve method of the Genome type being evolved. For each genome in a population, the Evolve method is called, receiving some subset of the population, called the suitors, as arguments. The Evolve method then applies operators to the suiters (selection, mutation, etc) and returns a genome that will replace the caller within the population for the next iteration. The concrete genome type is problem specific and defined by the user, while common operators for a variety of domains are provided as subpackages of Evo.

Populations orchestrate the evolution of genomes. A few different population types are provided by Evo under the package evo/pop. Populations themselves implement the Genome interface, making them composeable. The Evolve method of the builtin populations implements uniform random migration: A random population is chosen from the pool of suitors. Then the first population and its suitor exchange random members. This allows novel architectures like the island model to be implemented by nesting populations.

Examples

You can browse example problems in the example subpackage. The examples are maintained as a development tool rather than to provide optimal solutions to the problems they tackle. Reading the examples should give you a good idea of how easy it is to write code with Evo.

License

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Documentation

Overview

Evo is a framework for implementing evolutionary algorithms in Go.

Evo exposes a clean and flexible API oriented around two interfaces: `Genome` and `Population`. Genomes represent candidate solutions to the user's problem and are implemented by the user. Genomes define their own means of evolution, allowing for a multiplicity of techniques ranging from genetic algorithms to evolution strategies and beyond. Populations represent the architecture under which genomes are evolved. Multiple population types are provided by Evo to enable the construction of both common and novel architectures.

The body of the evolutionary loop is defined by the Evolve method of the Genome type being evolved. For each genome in a population, the Evolve method is called, receiving some subset of the population, called the suitors, as arguments. The Evolve method then applies operators to the suiters (selection, mutation, etc) and returns a genome that will replace the caller within the population for the next iteration. The concrete genome type is problem specific and defined by the user, while common operators for a variety of domains are provided as subpackages of Evo.

Populations orchestrate the evolution of genomes. A few different population types are provided by Evo under the package `evo/pop`. Populations themselves implement the Genome interface, making them composeable. The Evolve method of the builtin populations implements uniform random migration: A random population is chosen from the pool of suitors. Then the first population and its suitor exchange random members. This allows novel architectures like the island model to be implemented by nesting populations.

Index

• type Genome
  • func Max(pop Population) (best Genome)
• type Iterator
• type Population
• type Stats
  • func (s Stats) Count() int
  • func (s Stats) Max() float64
  • func (s Stats) Mean() float64
  • func (s Stats) Merge(t Stats) Stats
  • func (s Stats) Min() float64
  • func (s Stats) Put(x float64) Stats
  • func (s Stats) RSD() float64
  • func (s Stats) Range() float64
  • func (s Stats) SD() float64
  • func (s Stats) String() string
  • func (s Stats) Var() float64

Types

type Genome

type Genome interface {
	Evolve(...Genome) Genome
	Fitness() float64
	Close()
}

Genomes represent candidate solutions and are implemented by the user. Your genome type defines the inner loop of the evolutionary algorithm as the Evolve method: For each genome in a population, the Evolve method is called, passing some subset of the population, called the suitors, as arguments. The value returned is will replace the caller within the population. In a typical geneticl algorithm, the Evolve method will select one or more parents from the suiters, apply some kind of recombination operator to generate a new child genome, possibly apply a mutation operator, and return the child. A more complicated replacement scheme may require coordinating with other genomes in the population.

Genomes may implement two optional methods, Fitness and Close. The Fitness method has no effect on the population, but may be used by helper methods included within Evo. The Stats method of the Population type returns statistics of the population's fitness, thus Fitness must be non-trivial to use this feature. You may simply return 0 if you do not wish to implement Fitness.

The Close method will be registered as a finalizer on the genome. This can be used to recycle memory from dying genomes to newborn genomes. The Close method is not guarenteed to be called. See https://godoc.org/runtime#SetFinalizer

Genomes must be pointer types.

func Max

func Max(pop Population) (best Genome)

Max returns the genome with the highest fitness.

type Iterator

type Iterator interface {
	Value() Genome
	Next()
}

Iterators iterate over the genomes in a population and are returned by Population.Iter().

The Value method returns the current Genome pointed to by the iterator, or nil if the iterator has reached the end of the population.

The Next method advances the iterator.

To iterate over a population:

for i := pop.Iter(); i.Value() != nil; i.Next() {
    // do something with i.Value()
}

type Population

type Population interface {
	Genome

	// The Start method starts evolving the population in a separate goroutine.
	// Use the Close method to stop.
	Start()

	// SetDelay sets a delay between each iteration of the evolution loop.
	SetDelay(time.Duration)

	// The Stats method returns statistics about the fitness of genomes in the
	// population.
	Stats() Stats

	// The Iter method returns an iterator over the genomes in the population.
	// If called on a meta-population, i.e. one whose members are themselves
	// populations, then the iterator walks over the leaf-level genomes.
	Iter() Iterator
}

Populations orchestrate the evolution of genomes.

Populations are composable, i.e. the can be used as Genomes in other populations. The Evolve method implements a migration between the method receiver and one or more populations in the mating pool. Architectures like the island model can be implemented by nesting populations.

The builtin populations live in the package evo/pop.

type Stats

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

A Stats object is a statistics collector. A common source of Stats objects is the return value of Population.Stats() which gives statistics about the fitness of genomes in the population.

func (Stats) Count

func (s Stats) Count() int

Count returns the size of the data.

func (Stats) Max

func (s Stats) Max() float64

Max returns the maximum data point.

func (Stats) Mean

func (s Stats) Mean() float64

Mean returns the average of the data.

func (Stats) Merge

func (s Stats) Merge(t Stats) Stats

Merge merges the data of two Stats objects.

func (Stats) Min

func (s Stats) Min() float64

Min returns the minimum data point.

func (Stats) Put

func (s Stats) Put(x float64) Stats

Put inserts a new value into the data.

func (Stats) RSD

func (s Stats) RSD() float64

RSD returns the population relative standard deviation of the data, also known as the coefficient of variation.

func (Stats) Range

func (s Stats) Range() float64

Range returns the difference in the maximum and minimum data points.

func (Stats) SD

func (s Stats) SD() float64

SD returns the population standard deviation of the data.

func (Stats) String

func (s Stats) String() string

String returns a string listing a summary of the statistics.

func (Stats) Var

func (s Stats) Var() float64

Var returns the population variance of the data.