gago

README

gago is a framework for running genetic algorithms. It is written in Go.

In its most basic form, a genetic algorithm solves a mathematically posed problem by doing the following:

1. Generate random solutions.
2. Evaluate the solutions.
3. Sort the solutions by increasing (or decreasing) order.
4. Apply genetic operators (such as mutation and crossover).
5. Repeat from step 2 until satisfied.

Genetic algorithms can be applied to many problems, the only variable being the problem itself. Indeed, the underlying structure does not have to change between problems. With this in mind, gago has been built to be reusable. What's more, gago is a multi-population genetic algorithm implementing the migration model, in that sense it performs better than a traditional genetic algorithm.

Genetic algorithms are notorious for being embarrassingly parallel. Indeed, most calculations can be run in parallel because they only affect one individual. Luckily Go provides good support for parallelism. As some gophers may know, the math/rand module can be problematic because there is a global lock the random number generator, the problem is described in this stackoverflow post. This can be circumvented by providing each deme with it's own generator.

The following flowchart shows the steps the algorithms takes. As can be seen only the search for the best individual and the migration can't be parallelized.

Terminology

The terms surrounding genetic algorithms (GAs) are roughly analogous to those found in biology.

• GAs are intended to optimize a function called the fitness function.
• Candidate solutions to the optimization problem are called individuals.
• Each individual has genes to which a fitness is assigned.
• The number of genes is simply the number of variables defined by the problem.
• Individuals are sorted based on their fitness towards a problem.
• Offsprings are born by applying crossover on selected individuals.
• The selection method is crucial and determines most of the behavior of the algorithm.
• Genes can be randomly modified through mutation.
• Classically, individuals are contained in a structure called a population.
• Multi-population GAs add another layer in-between called demes.
• Demes exchange individuals through a process known as migration.

Usage

The following code shows a basic usage of gago.

package main

import (
	"fmt"
	"math"

	"github.com/MaxHalford/gago"
)

// Sphere function minimum is 0
func sphere(X []float64) float64 {
	sum := 0.0
	for _, x := range X {
		sum += math.Pow(x, 2)
	}
	return sum
}

func main() {
	// Instantiate a population
	ga := gago.Float
	// Wrap the function
	ga.Ff = gago.FloatFunction{sphere}
	// Initialize the genetic algorithm with two variables per individual
	ga.Initialize(2)
	// Enhance the individuals
	for i := 0; i < 20; i++ {
		ga.Enhance()
	}
	// Display the best obtained solution
	fmt.Printf("The best obtained solution is %f", ga.Best.Fitness)
}

The user has a function Sphere he wishes to minimize. He initiates a predefined set of parameters gago.Float. He then wraps his function with gago.FloatFunction{Sphere} so that gago knows what it has to minimize. Finally the user orders gago to find an appropriate solution with ga.Enhance(). By convention gago will try to minimize the fitness function. If instead you want to maximize a function f(x), you can minimize -f(x) or 1/f(x).

Parameters

To modify the behavior off the GA, you can change the gago.Population struct before running ga.Initialize. You can either instantiate a new gago.Population or use a predefined one from the configuration.go file.

Variable in the code	Type	Description
NbDemes	int	Number of demes in the population.
NbIndividuals	int	Number of individuals in each deme.
NbGenes	int	Number of genes in each individual.
Initializer (struct)	Initializer (interface)	Method for initializing a new individual.
Selector (struct)	Selector (interface)	Method for selecting one individual from a group of individuals.
Crossover (struct)	Crossover (interface)	Method for producing a new individual (called the offspring).
Mutators (struct)	[]Mutator (slice of interface)	Method for modifying an individual's genes.
Migrator (struct)	Migrator (interface)	Method for exchanging individuals between the demes.

The gago.Population struct also contains a Best variable which is of type Individual, it represents the best individual overall demes for the current generation. Alternatively the Demes variable is a slice containing each deme in the population; the demes are sorted at each generation so that the first individual in the deme is the best individual from that deme.

gago is designed to be flexible. You can change every parameter of the algorithm as long as you implement functions that use the correct types as input/output. A good way to start is to look into the source code and see how the methods are implemented, I've made an effort to comment it. If you want to add a new generic operator (initializer, selector, crossover, mutator, migrator), then you can simply copy and paste an existing method into your code and change the logic as you please. All that matters is that you correctly implement the existing interfaces.

If you wish to not use certain genetic operators, you can set them to nil. This is available for the Crossover, the Mutator and the Migrator (the other ones are part of minimum requirements). Each operator contains an explanatory description that can be read in the documentation.

Using different types

Some genetic operators target a specific type, these ones are prefixed with the name of the type (Float, String). The ones that don't have prefixes work with any types, which is down to the way they are implemented. Default configurations are available in configuration.go.

You should think of gago as a framework for implementing your problems, and not as an all in one solution. It's quite easy to implement your own for exotic problems, for example the TSP problem.

The only requirement for solving a problem is that the problem can be modeled as a function that returns a floating point value, that's it. Because Go is statically typed, you have to provide a wrapper for the function and make sure that the genetic operators make sense for your problem.

Documentation

• godoc
• Each operator (selection, crossover, mutation, migration) is described in its comments.
• An introduction to genetic algorithms is quite thorough.
• The Multipopulation Genetic Algorithm: Local Selection and Migration is an easy read.

Examples

• Check out the examples/minimization/ folder for basic examples. Test functions were found here.
• examples/plot-fitness/ is an example of plotting the fitness per generation with gonum/plot.
• examples/curve-fitting/ is an attempt to fit a set of points with non-linear polynomial function.
• examples/tsp/ contain examples of solving the Traveling Salesman Problem.

Roadmap

• Error handling.
• Statistics.
• Benchmarking.
• Profiling.
• Compare with other algorithms/libraries.
• Implement more genetic operators.
• More examples.

Why use gago?

• It's generic, your only constraint is to model your problem and gago will do all the hard work for you.
• You can easily add your own genetic operators.
• gago implements parallel populations (called "demes") who exchange individuals for better performance.
• gago will be well maintained.

Suggestions

• Please post suggestions/issues in GitHub's issues section.
• You can use the reddit thread or my email address for comments/enquiries.

Documentation

Overview

Package gago has a convention for naming genetic operators. The name begins with a letter or a short sequence of letters to specify which kind of operator it is:

- `C`: crossover - `Mut`: mutator - `Mig`: migrator - `S`: selector

Then comes the second part of the name which indicates on what kind of genomes the operator works:

- `F`: `float64` - `S`: `string` - No letter means the operator works on any kind of genome, regardless of the underlying type.

Finally the name of the operator ends with a word to indicate what it does.

Index

• Variables
• type CFProportionate
• type CFUniform
• type CPMX
• type CPoint
• type Crossover
• type Deme
• type FitnessFunction
• type FloatFunction
• type Genome
  • func (g Genome) CastFloat() []float64
  • func (g Genome) CastString() []string
• type IFGaussian
• type IFUniform
• type ISUniform
• type ISUnique
• type Individual
  • func (indi *Individual) Evaluate(ff FitnessFunction)
• type Individuals
  • func (indis Individuals) Len() int
  • func (indis Individuals) Less(i, j int) bool
  • func (indis Individuals) Sort()
  • func (indis Individuals) Swap(i, j int)
• type Initializer
• type MigShuffle
• type Migrator
• type MutFNormal
• type MutPermute
• type MutSplice
• type Mutator
• type Population
  • func (pop *Population) Enhance()
  • func (pop *Population) Initialize(variables int)
• type SElitism
• type STournament
• type Selector
• type StringFunction

Variables

var Float = Population{
	NbDemes:       2,
	NbIndividuals: 30,
	Initializer: IFUniform{
		Lower: -10,
		Upper: 10,
	},
	Selector: STournament{
		NbParticipants: 3,
	},
	Crossover: CFUniform{},
	Mutators: []Mutator{
		MutFNormal{
			Rate: 0.1,
			Std:  1,
		},
	},
	Migrator: MigShuffle{},
}

Float problem configuration.

Types

type CFProportionate

type CFProportionate struct {
	// Should be any integer above or equal to two
	NbIndividuals int
}

CFProportionate crossover combines any number of individuals. Each of the offspring's genes is a random combination of the selected individuals genes. Each individual is assigned a weight such that the sum of the weights is equal to 1, this is done by normalizing each weight by the sum of the generated weights. With this crossover method the CrossSize can be set to any positive integer, in other words any number of individuals can be combined to generate an offspring. Only works for floating point values.

type CFUniform

type CFUniform struct{}

CFUniform crossover combines two individuals (the parents) into one (the offspring). Each parent's contribution to the Genome is determined by the value of a probability p. The offspring can inherit from it's mother's genes (p <= 0.33), from it's father's genes (0.33 < p <= 0.66) or from a random mix of both (0.66 < p <= 1). A coin is thrown for each gene. Only works for floating point values.

type CPMX

type CPMX struct{}

CPMX (Partially Mapped Crossover) randomly picks a crossover point. The offspring is built by copying one of the parents and then copying the other parent's values up to the crossover point. Each gene that is replaced is permuted with the gene that is copied in the first parent's genome. Two offsprings are generated in such a way (because there are two parents). This crossover method ensures the offspring's genomes are composed of unique genes, which is particularly useful for permutation problems such as the Traveling Salesman Problem (TSP).

type CPoint

type CPoint struct {
	NbPoints int
}

CPoint selects identical random points on each parent's genome and exchanges mirroring segments. It generalizes one-point crossover and two-point crossover to n-point crossover. One of the generated offsprings is returned at random.

type Crossover

type Crossover interface {
	// contains filtered or unexported methods
}

Crossover mixes two or more individuals into a new individual called the offspring.

type Deme

type Deme struct {
	// Individuals
	Individuals Individuals
	// contains filtered or unexported fields
}

A Deme contains individuals. Individuals mate within a deme. Individuals can migrate from one deme to another.

type FitnessFunction

type FitnessFunction interface {
	// contains filtered or unexported methods
}

FitnessFunction wraps user defined functions in order to generalize other functions.

type FloatFunction

type FloatFunction struct {
	Image func([]float64) float64
}

FloatFunction is for functions with floating point slices as input.

type Genome

type Genome []interface{}

A Genome contains the genes of an individual.

func (Genome) CastFloat

func (g Genome) CastFloat() []float64

CastFloat casts each to a float.

func (Genome) CastString

func (g Genome) CastString() []string

CastString casts each gene to a string.

type IFGaussian

type IFGaussian struct {
	Mean, Std float64
}

IFGaussian generates random floating point values sampled from a normal distribution.

type IFUniform

type IFUniform struct {
	Lower, Upper float64
}

IFUniform generates random floating points x such that lower < x < upper.

type ISUniform

type ISUniform struct {
	Corpus []string
}

ISUniform generates random string slices based on a given corpus.

type ISUnique

type ISUnique struct {
	Corpus []string
}

ISUnique generates random string slices based on a given corpus, each element from the corpus is only represented once in each slice. The method starts by shuffling, it then assigns the elements of the corpus in increasing index order to an individual. Usually the length of the individual's genome should match the length of the corpus.

type Individual

type Individual struct {
	Genome  Genome
	Fitness float64
}

An Individual represents a potential solution to a problem. The individual's is defined by it's genome, which is a slice containing genes. Every gene is a floating point numbers. The fitness is the individual's phenotype and is represented by a floating point number.

func (*Individual) Evaluate

func (indi *Individual) Evaluate(ff FitnessFunction)

Evaluate the fitness of an individual.

type Individuals

type Individuals []Individual

Individuals type is necessary for sorting and selection purposes.

func (Individuals) Len

func (indis Individuals) Len() int

func (Individuals) Less

func (indis Individuals) Less(i, j int) bool

func (Individuals) Sort

func (indis Individuals) Sort()

Sort the individuals of a deme in ascending order based on their fitness. The convention is that we always want to minimize a function. A function f(x) can be function maximized by minimizing -f(x) or 1/f(x).

func (Individuals) Swap

func (indis Individuals) Swap(i, j int)

type Initializer

type Initializer interface {
	// contains filtered or unexported methods
}

The Initializer is here to create the first generation of individuals in a deme. It applies to an individual level and instantiates it's genome gene by gene.

type MigShuffle

type MigShuffle struct{}

MigShuffle migration exchanges individuals between demes in a random fashion.

type Migrator

type Migrator interface {
	// contains filtered or unexported methods
}

Migrator applies crossover to the population level, as such it doesn't require an independent random number generator and can use the global one.

type MutFNormal

type MutFNormal struct {
	// Mutation rate
	Rate float64
	// Standard deviation
	Std float64
}

MutFNormal mutation modifies a float gene if a coin toss is under a defined mutation rate. It does so for each gene. The new gene value is a random value sampled from a normal distribution centered on the gene's current value and with the intensity parameter as it's standard deviation. Only works for floating point values.

type MutPermute

type MutPermute struct {
	// Mutation rate
	Rate float64
}

MutPermute permutes two genes.

type MutSplice

type MutSplice struct {
	// Mutation rate
	Rate float64
}

MutSplice a genome and glue it back in another order.

type Mutator

type Mutator interface {
	// contains filtered or unexported methods
}

Mutator mutates an individual by modifying part of it's genome.

type Population

type Population struct {
	// Number of demes
	NbDemes int
	// Number of individuals in each deme
	NbIndividuals int
	// Number of genes in each individual (imposed by the problem)
	NbGenes int
	// Demes
	Demes []Deme
	// Overall best individual (dummy initialization at the beginning)
	Best Individual
	// Fitness function to evaluate individuals (imposed by the problem)
	Ff FitnessFunction
	// Initial random boundaries
	Initializer Initializer
	// Selection method
	Selector Selector
	// Crossover method
	Crossover Crossover
	// Mutation methods
	Mutators []Mutator
	// Migration method
	Migrator Migrator
}

A Population contains deme which themselves contain individuals.

func (*Population) Enhance

func (pop *Population) Enhance()

Enhance each deme in the population. The deme level operations are done in parallel with a wait group. After all the deme operations have been run, the population level operations are run.

func (*Population) Initialize

func (pop *Population) Initialize(variables int)

Initialize each deme in the population and assign an initial fitness to each individual in each deme.

type SElitism

type SElitism struct{}

SElitism selection returns the best individuals in the population.

type STournament

type STournament struct {
	NbParticipants int
}

STournament selection chooses an individual through tournament selection. The tournament is composed of randomly chosen individuals. The winner of the tournament is the individual with the lowest fitness.

type Selector

type Selector interface {
	// contains filtered or unexported methods
}

Selector chooses a sample of individual from a larger of individuals.

type StringFunction

type StringFunction struct {
	Image func([]string) float64
}

StringFunction is for function with string slices as input.