# gago

package module
v0.0.0-...-502b393 Latest Latest

Go to latest
Published: Aug 3, 2018 License: MIT

⚠ This is gago, the old version of eaopt. The repository only exists so that existing projects importing gago won't break. Please use eaopt if you're starting a new project or switch to it if your project is using it.

### Example

The following example attempts to minimize the Drop-Wave function which is known to have a minimum value of -1.

``````package main

import (
"fmt"
m "math"
"math/rand"

"github.com/MaxHalford/gago"
)

// A Vector contains float64s.
type Vector []float64

// Evaluate a Vector with the Drop-Wave function which takes two variables as
// input and reaches a minimum of -1 in (0, 0).
func (X Vector) Evaluate() float64 {
var (
numerator   = 1 + m.Cos(12*m.Sqrt(m.Pow(X[0], 2)+m.Pow(X[1], 2)))
denominator = 0.5*(m.Pow(X[0], 2)+m.Pow(X[1], 2)) + 2
)
return -numerator / denominator
}

// Mutate a Vector by resampling each element from a normal distribution with
// probability 0.8.
func (X Vector) Mutate(rng *rand.Rand) {
gago.MutNormalFloat64(X, 0.8, rng)
}

// Crossover a Vector with another Vector by applying uniform crossover.
func (X Vector) Crossover(Y gago.Genome, rng *rand.Rand) {
gago.CrossUniformFloat64(X, Y.(Vector), rng)
}

// Clone a Vector to produce a new one that points to a different slice.
func (X Vector) Clone() gago.Genome {
var Y = make(Vector, len(X))
copy(Y, X)
return Y
}

// VectorFactory returns a random vector by generating 2 values uniformally
// distributed between -10 and 10.
func VectorFactory(rng *rand.Rand) gago.Genome {
return Vector(gago.InitUnifFloat64(2, -10, 10, rng))
}

func main() {
var ga = gago.Generational(VectorFactory)
ga.Initialize()

fmt.Printf("Best fitness at generation 0: %f\n", ga.Best.Fitness)
for i := 1; i < 10; i++ {
ga.Evolve()
fmt.Printf("Best fitness at generation %d: %f\n", i, ga.Best.Fitness)
}
}

``````
``````>>> Best fitness at generation 0: -0.550982
>>> Best fitness at generation 1: -0.924220
>>> Best fitness at generation 2: -0.987282
>>> Best fitness at generation 3: -0.987282
>>> Best fitness at generation 4: -0.987282
>>> Best fitness at generation 5: -0.987282
>>> Best fitness at generation 6: -0.987282
>>> Best fitness at generation 7: -0.997961
>>> Best fitness at generation 8: -0.999954
>>> Best fitness at generation 9: -0.999995
``````

More examples

All the examples can be found here.

### Background

There is a lot of intellectual fog around the concept of genetic algorithms (GAs). It's important to appreciate the fact that GAs are composed of many nuts and bolts. There isn't a single definition of genetic algorithms. `gago` is intended to be a toolkit where one may run many kinds of genetic algorithms, with different evolution models and various genetic operators.

#### Terminology

• Fitness function: The fitness function is simply the function associated to a given problem. It takes in an input and returns an output.
• Individual: An individual contains a genome which represents a candidate solution. In the physical world, an individual's genome is composed of acids. In an imaginary world, it could be composed of floating point numbers or string sequences representing cities. A fitness can be associated to a genome thanks to the fitness function. For example, one could measure the height of a group of individuals in order to rank them. In this case the genome is the body of the individual, the fitness function is the act of measuring the height of the individual's body and the fitness is the height of individual measured by the fitness function.
• Population: Individuals are contained in a population wherein they can interact.
• Crossover: A crossover acts on two or more individuals (called parents) and mixes their genome in order to produce one or more new individuals (called offsprings). Crossover is really what sets genetic algorithms apart from other evolutionary methods.
• Selection: Selection is a process in which parents are selected to generate offsprings, most often by applying a crossover method. Popular selection methods include elitism selection and tournament selection.
• Mutation: Mutation applies random modifications to an individual's genome without interacting with other individuals.
• Migration: Multi-population GAs run more than one population in parallel and exchange individuals between each other.
• Speciation: In the physical world, individuals do not mate at random. Instead, they mate with similar individuals. For some problems such as neural network topology optimization, crossover will often generate poor solutions. Speciation sidesteps this by mating similar individuals (called species) separately.
• Evolution model: An evolution model describes the exact manner and order in which genetic operators are applied to a population. The most popular models are the steady state model and the generational model.

#### Methodology

In a nutshell, a GA solves an optimization problem by doing the following:

1. Generate random solutions.
2. Evaluate the solutions.
3. Sort the solutions according to their evaluation score.
4. Apply genetic operators following a model.
5. Repeat from step 2 until the stopping criterion is not satisfied.

This description is voluntarily vague as to how the genetic operators are applied. It's important to understand that there isn't a single way of applying genetic algorithms. For example some people believe that crossover is useless and use mutation for generating new individuals. Genetic operators are applied following a model, a fact that is often omitted in introductions to genetic algorithms. Popular stopping criteria include

• a fixed number of generations,
• a fixed duration,
• an indicator that the population is stagnating.

### Features

• gago is extensible, you can control most of what's happening
• Different evolution models are available
• Popular operators are already implemented
• Speciation is available
• Multiple population migration is available

### Usage

The two requirements for using gago are

• Implement the `Genome` interface.
• Instantiate a `GA` struct.

The `Genome` interface is used define the logic that is specific to your problem; logic that gago doesn't know about. For example this is where you will define an `Evaluate()` method for evaluating a particular problem. The `GA` struct contains context-agnostic information. For example this is where you can choose the number of individuals in a population (which is a separate concern from your particular problem).

#### Implementing the Genome interface

Let's have a look at the `Genome` interface.

``````type Genome interface {
Evaluate() float64
Mutate(rng *rand.Rand)
Crossover(genome Genome, rng *rand.Rand)
Clone() Genome
}
``````

The `Evaluate()` method assigns a score to a given genome. The sweet thing is that you can do whatever you want in this method. Your struct that implements the interface doesn't necessarily have to be a slice (which is a common representation). The `Evaluate()` method is your problem to deal with, gago only needs it's output to be able to function.

The `Mutate(rng *rand.Rand)` method is where you can mutate a solution by tinkering with it's variables. The way in which you should mutate a solution essentially boils down to your particular problem. gago provides some common mutation methods that you can use to not reinvent the wheel; this is what is being done in most of the provided examples.

The `Crossover(genome Genome, rng *rand.Rand)` method mixes two individuals. The important thing to notice is that the type of first argument differs from the struct calling the method. Indeed the first argument is a `Genome` that has to be casted into your struct before being able to apply a crossover operator. This is due to the fact that Go doesn't provide generics out of the box; it's easier to convince yourself by checking out the examples.

The `Genome()` method is there to produce independent copies of the struct you want to evolve. This is necessary for internal reasons and ensures that pointer fields are not pointing to same values memory addresses. Usually this is not too difficult implement; you just have to make sure that the clones you produce are totally independent from the genome they have been produced with. This is also not too difficult to unit test.

Once you have implemented the `Genome` you have provided gago with all the information it couldn't guess for you. Essentially you have total control over the definition of your problem, gago will handle the rest and find a good solution to the problem.

#### Using the Slice interface

Classically GAs are used to optimize problems where the genome has a slice representation - eg. a vector or a sequence of DNA code. Almost all the mutation and crossover algorithms gago makes available are based on the `Slice` interface which has the following definition.

``````type Slice interface {
At(i int) interface{}
Set(i int, v interface{})
Len() int
Swap(i, j int)
Slice(a, b int) Slice
Split(k int) (Slice, Slice)
Append(Slice) Slice
Replace(Slice)
Copy() Slice
}
``````

Internally `IntSlice`, `Float64Slice` and `StringSlice` implement this interface so that you can use the available operators for most use cases. If however you wish to use the operators which slices of a different type you will have to implement the `Slice` interface. Although there are many methods to implement, they are all trivial (have a look at `slice.go` and the TSP example.

#### Instantiating a GA struct

Let's have a look at the GA struct.

``````type GA struct {
NewGenome   NewGenome
NPops        int
PopSize      int
Model        Model

// Optional fields
NBest        int
Migrator     Migrator
MigFrequency int
Speciator    Speciator
Logger       *log.Logger
Callback     func(ga *GA)
RNG          *rand.Rand
ParallelEval bool

// Fields generated at runtime
Populations        Populations
HallOfFame         Individuals
Age                time.Duration
Generations        int
}
``````

You have to fill in the first set of fields, the rest are generated when calling the `GA`'s `Initialize()` method. Check out the examples in `presets.go` to get an idea of how to fill them out.

• `NewGenome` is a method that returns a random genome that you defined in the previous step. gago will use this method to produce an initial population. Again, gago provides some methods for common random genome generation.
• `NPops` determines the number of populations that will be used.
• `PopSize` determines the number of individuals inside each population.
• `Model` determines how to use the genetic operators you chose in order to produce better solutions, in other words it's a recipe. A dedicated section is available in the model section.
• Optional fields
• `NBest` determines how many of the best individuals encountered should be regarded in the `HallOfFame` field. This defaults to 1.
• `Migrator` and `MigFrequency` should be provided if you want to exchange individuals between populations in case of a multi-population GA. If not the populations will be run independently. Again this is an advanced concept in the genetic algorithms field that you shouldn't deal with at first.
• `Speciator` will split each population in distinct species at each generation. Each specie will be evolved separately from the others, after all the species has been evolved they are regrouped.
• `Logger` is optional and provides basic population statistics, you can read more about it in the logging section.
• `Callback` is optional will execute any piece of code you wish every time `ga.Evolve()` is called. `Callback` will also be called when `ga.Initialize()` is. Using a callback can be useful for many things:
• Calculating specific population statistics that are not provided by the logger
• Changing parameters of the GA after a certain number of generations
• Monitoring for converging populations
• `RNG` can be set to make results reproducible. If it is not provided then a default `rand.New(rand.NewSource(time.Now().UnixNano()))` will be used. If you want to make your results reproducible use a constant source, e.g. `rand.New(rand.NewSource(42))`.
• `ParallelEval` determines if a population is evaluated in parallel. The rule of thumb is to set this to `true` if your `Evaluate` method is expensive, if not it won't be worth the overhead. Refer to the section on parallelism for a more comprehensive explanation.
• Fields populated at runtime
• `Populations` is where all the current populations and individuals are kept.
• `HallOfFame` contains the `NBest` individuals ever encountered. This slice is always sorted, meaning that the first element of the slice will be the best individual ever encountered.
• `Age` indicates the duration the GA has spent calling the `Evolve` method.
• `Generations` indicates how many times the `Evolve` method has been called.

#### Running a GA

Once you have implemented the `Genome` interface and instantiated a `GA` struct you are good to go. You can call the `GA`'s `Evolve` method which will apply a model once (see the models section). It's your choice if you want to call `Evolve` method multiple by using a loop or by imposing a time limit. The `Evolve` method will return an `error` which you should handle. If your population is evolving when you call `Evolve` it's most likely because `Evolve` did not return a `nil` error.

At any time you have access to the `GA`'s `Best` field which contains a `Fitness` field and a `Genome` field respectively indicating the overall best obtained solution and the parameters of that solution. Moreover, the `GA`'s`CurrentBest` field contains the best solution and parameters obtained by the current generation.

#### Models

`gago` makes it easy to use different so called models. Simply put, a models tells the story of how a GA enhances a population of individuals through a sequence of genetic operators. It does so without considering whatsoever the underlying operators. In a nutshell, an evolution model attempts to mimic evolution in the real world. It's extremely important to choose a good model because it is usually the highest influence on the performance of a GA.

##### Generational model

The generational model is one the, if not the most, popular models. Simply put it generates n offsprings from a population of size n and replaces the population with the offsprings. The offsprings are generated by selecting 2 individuals from the population and applying a crossover method to the selected individuals until the n offsprings have been generated. The newly generated offsprings are then optionally mutated before replacing the original population. Crossover generates two new individuals, thus if the population size isn't an even number then the second individual from the last crossover (individual n+1) won't be included in the new population.

The steady state model differs from the generational model in that the entire population isn't replaced between each generations. Instead of adding the children of the selected parents into the next generation, the 2 best individuals out of the two parents and two children are added back into the population so that the population size remains constant. However, one may also replace the parents with the children regardless of their fitness. This method has the advantage of not having to evaluate the newly generated offsprings. Whats more, crossover often generates individuals who are sub-par but who have a lot of potential; giving individuals generated from crossover a chance can be beneficial on the long run.

##### Select down to size model

The select down to size model uses two selection rounds. The first one is similar to the one used in the generational model. Parents are selected to generate new individuals through crossover. However, the offsprings are then merged with the original population and a second selection round occurs to determine which individuals will survive to the next generation. Formally m offsprings are generated from a population of n, the n+m individuals are then "selected down to size" so that there only remains n individuals.

##### Ring model

In the ring model, crossovers are applied to neighbours in a one-directional ring topology. Two by the two neighbours generate 2 offsprings. The best out of the 4 individuals (2 parents + 2 offsprings) replaces the first neighbour.

##### Simulated annealing

Although simulated annealing isn't a genetic algorithm, it can nonetheless be implemented with gago. A mutator is the only necessary operator. Other than that a starting temperature, a stopping temperature and a decrease rate have to be provided. Effectively a single simulated annealing is run for each individual in the population.

The temperature evolution is relative to one single generation. In order to mimic the original simulated annealing algorithm, one would the number of individuals to 1 and would run the algorithm for only 1 generation. However, nothing stops you from running many simulated annealings and to repeat them over many generations.

##### Mutation only

It's possible to run a GA without crossover simply by mutating individuals. Essentially this boils down to doing hill climbing because there is not interaction between individuals. Indeed taking a step in hill climbing is equivalent to mutation for genetic algorithms. What's nice is that by using a population of size n you are essentially running multiple independent hill climbs.

#### Speciation

Clusters, also called speciation in the literature, are a partitioning of individuals into smaller groups of similar individuals. Programmatically a cluster is a list of lists each containing individuals. Individuals inside each species are supposed to be similar. The similarity depends on a metric, for example it could be based on the fitness of the individuals. In the literature, speciation is also called speciation.

The purpose of a partitioning individuals is to apply genetic operators to similar individuals. In biological terms this encourages "incest" and maintains isolated species. For example in nature animals usually breed with local mates and don't breed with different animal species.

Using speciation/speciation with genetic algorithms became "popular" when they were first applied to the optimization of neural network topologies. By mixing two neural networks during crossover, the resulting neural networks were often useless because the inherited weights were not optimized for the new topology. This meant that newly generated neural networks were not performing well and would likely disappear during selection. Thus speciation was introduced so that neural networks evolved in similar groups so that new neural networks wouldn't disappear immediately. Instead the similar neural networks would evolve between each other until they were good enough to mixed with the other neural networks.

With gago it's possible to use speciation on top of all the rest. To do so the `Speciator` field of the `GA` struct has to specified.

#### Multiple populations and migration

Multi-populations GAs run independent populations in parallel. They are not frequently used, however they are very easy to understand and to implement. In gago a `GA` struct contains a `Populations` field which contains each population. The number of populations is specified in the `GA`'s `Topology` field.

If `Migrator` and `MigFrequency` are not provided the populations will be run independently, in parallel. However, if they are provided then at every generation number that divides `MigFrequency` individuals will be exchanged between the populations following the `Migrator` protocol.

Using multi-populations can be an easy way to gain in diversity. Moreover, not using multi-populations on a multi-core architecture is a waste of resources.

With gago you can use multi-populations and speciation at the same time. The following flowchart shows what that would look like.

#### Presets

Some preset GA instances are available to get started as fast as possible. They are available in the presets.go file. These instances also serve as example instantiations of the GA struct. To obtain optimal solutions you should fill in the fields manually!

#### Logging population statistics

It's possible to log statistics for each population at every generation. To do so you simply have to provide the `GA` struct a `Logger` from the Go standard library. This is quite convenient because it allows you to decide where to write the log output, whether it be in a file or directly in the standard output.

``````ga.Logger = log.New(os.Stdout, "", log.Ldate|log.Ltime)
``````

If a logger is provided, each row in the log output will include

• the population ID,
• the population minimum fitness,
• the population maximum fitness,
• the population average fitness,
• the population's fitness standard deviation.

### A note on parallelism

Genetic algorithms are famous for being embarrassingly parallel. Most of the operations used in the GA can be run independently each one from another. For example individuals can be mutated in parallel because mutation doesn't have any side effects.

The Go language provides nice mechanisms to run stuff in parallel, provided you have more than one core available. However, parallelism is only worth it when the functions you want to run in parallel are "heavy". If the functions are cheap then the overhead of spawning routines will be too high and not worth it. It's simply not worth using a routine for each individual because operations at an individual level are often not time consuming enough.

By default gago will evolve populations in parallel. This is because evolving one population implies a lot of operations and parallelism is worth it. If your `Evaluate` method is heavy then it might be worth evaluating individuals in parallel, which can done by setting the `GA`'s `ParallelEval` field to `true`. Evaluating individuals in parallel can be done regardless of the fact that you are using more than one population.

### FAQ

What if I don't want to use crossover?

Alas you still have to implement the `Genome` interface. You can however provide a blank `Crossover` method just to satisfy the interface.

``````type Vector []float64

func (X Vector) Crossover(Y gago.Genome, rng *rand.Rand) (gago.Genome, gago.Genome) {
return X, Y.(Vector)
}
``````

Why aren't my `Mutate` and `Crossover` methods modifying my `Genome`s?

The `Mutate` and `Crossover` methods have to modify the values of the `Genome` in-place. The following code will work because the `Vector` is a slice; slices in Go are references to underlying data, hence modifying a slice modifies them in-place.

``````type Vector []float64

func (X Vector) Mutate(rng *rand.Rand) {
gago.MutNormal(X, rng, 0.5)
}
``````

On the contrary, mutating other kind of structs will require the `*` symbol to access the struct's pointer. Notice the `*Name` in the following example.

``````type Name string

func (n *Name) Mutate(rng *rand.Rand) {
n = randomName()
}
``````

Should I be using genetic algorithms?

Genetic algorithms (GAs) are often used for NP-hard problems. They usually perform better than hill climbing and simulated annealing because they explore the search space more intelligently. However, GAs can also be used for classical problems where the search space makes it difficult for, say, gradient algorithms to be efficient (like the introductory example).

As mentioned earlier, some problems can simply not be written down as closed-form expressions. For example tuning the number of layers and of neurons per layer in a neural network is an open problem that doesn't yet have a reliable solution. Neural networks architectures used in production are usually designed by human experts. The field of neuroevolution aims to train neural networks with evolutionary algorithms. As such genetic algorithms are a good candidate for training neural networks, usually by optimizing the network's topology.

How can I contribute?

Feel free to implement your own operators or to make suggestions! Check out the CONTRIBUTING file for some guidelines.

### Dependencies

You can see the list of dependencies here and the graph view here. Here is the list of external dependencies:

## Documentation ¶

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

#### func CrossCX ¶

`func CrossCX(p1, p2 Slice)`

CrossCX (Cycle Crossover). Cycles between the parents are indentified, they are then copied alternatively onto the offsprings. The CX method is deterministic and preserves gene uniqueness.

#### func CrossCXFloat64 ¶

`func CrossCXFloat64(s1 []float64, s2 []float64)`

CrossCXFloat64 calls CrossCX on a float64 slice.

#### func CrossCXInt ¶

`func CrossCXInt(s1 []int, s2 []int)`

CrossCXInt calls CrossCX on an int slice.

#### func CrossCXString ¶

`func CrossCXString(s1 []string, s2 []string)`

CrossCXString calls CrossCX on a string slice.

#### func CrossERX ¶

`func CrossERX(p1, p2 Slice)`

CrossERX (Edge Recombination Crossover).

#### func CrossERXFloat64 ¶

`func CrossERXFloat64(s1 []float64, s2 []float64)`

CrossERXFloat64 callsCrossERX on a float64 slice.

#### func CrossERXInt ¶

`func CrossERXInt(s1 []int, s2 []int)`

CrossERXInt calls CrossERX on an int slice.

#### func CrossERXString ¶

`func CrossERXString(s1 []string, s2 []string)`

CrossERXString calls CrossERX on a string slice.

#### func CrossGNX ¶

`func CrossGNX(p1 Slice, p2 Slice, n int, rng *rand.Rand)`

CrossGNX (Generalized N-point Crossover). An identical point is chosen on each parent's genome and the mirroring segments are switched. n determines the number of crossovers (aka mirroring segments) to perform. n has to be equal or lower than the number of genes in each parent.

#### func CrossGNXFloat64 ¶

`func CrossGNXFloat64(s1 []float64, s2 []float64, n int, rng *rand.Rand)`

CrossGNXFloat64 calls CrossGNX on two float64 slices.

#### func CrossGNXInt ¶

`func CrossGNXInt(s1 []int, s2 []int, n int, rng *rand.Rand)`

CrossGNXInt calls CrossGNX on two int slices.

#### func CrossGNXString ¶

`func CrossGNXString(s1 []string, s2 []string, n int, rng *rand.Rand)`

CrossGNXString calls CrossGNX on two string slices.

#### func CrossOX ¶

`func CrossOX(p1 Slice, p2 Slice, rng *rand.Rand)`

CrossOX (Ordered Crossover). Part of the first parent's genome is copied onto the first offspring's genome. Then the second parent's genome is iterated over, starting on the right of the part that was copied. Each gene of the second parent's genome is copied onto the next blank gene of the first offspring's genome if it wasn't already copied from the first parent. The OX method preserves gene uniqueness.

#### func CrossOXFloat64 ¶

`func CrossOXFloat64(s1 []float64, s2 []float64, rng *rand.Rand)`

CrossOXFloat64 calls CrossOX on a float64 slice.

#### func CrossOXInt ¶

`func CrossOXInt(s1 []int, s2 []int, rng *rand.Rand)`

CrossOXInt calls CrossOX on a int slice.

#### func CrossOXString ¶

`func CrossOXString(s1 []string, s2 []string, rng *rand.Rand)`

CrossOXString calls CrossOX on a string slice.

#### func CrossPMX ¶

`func CrossPMX(p1 Slice, p2 Slice, rng *rand.Rand)`

CrossPMX (Partially Mapped Crossover). The offsprings are generated by copying one of the parents and then copying the other parent's values up to a randomly chosen 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). The PMX method preserves gene uniqueness.

#### func CrossPMXFloat64 ¶

`func CrossPMXFloat64(s1 []float64, s2 []float64, rng *rand.Rand)`

CrossPMXFloat64 calls CrossPMX on a float64 slice.

#### func CrossPMXInt ¶

`func CrossPMXInt(s1 []int, s2 []int, rng *rand.Rand)`

CrossPMXInt calls CrossPMX on an int slice.

#### func CrossPMXString ¶

`func CrossPMXString(s1 []string, s2 []string, rng *rand.Rand)`

CrossPMXString calls CrossPMX on a string slice.

#### func CrossUniformFloat64 ¶

`func CrossUniformFloat64(p1 []float64, p2 []float64, rng *rand.Rand)`

CrossUniformFloat64 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. Each offspring receives a proportion of both of it's parents genomes. The new values are located in the hyper-rectangle defined between both parent's position in Cartesian space.

#### func InitJaggFloat64 ¶

`func InitJaggFloat64(n int, lower, upper []float64, rng *rand.Rand) (floats []float64)`

InitJaggFloat64 generates random float64s x such that lower < x < upper with jagged bounds

#### func InitNormFloat64 ¶

`func InitNormFloat64(n int, mean, std float64, rng *rand.Rand) (floats []float64)`

InitNormFloat64 generates random float64s sampled from a normal distribution.

#### func InitUnifFloat64 ¶

`func InitUnifFloat64(n int, lower, upper float64, rng *rand.Rand) (floats []float64)`

InitUnifFloat64 generates random float64s x such that lower < x < upper.

#### func InitUnifString ¶

`func InitUnifString(n int, corpus []string, rng *rand.Rand) (strings []string)`

InitUnifString generates random strings based on a given corpus. The strings are not necessarily distinct.

#### func InitUniqueString ¶

`func InitUniqueString(n int, corpus []string, rng *rand.Rand) (strings []string)`

InitUniqueString 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.

#### func MutNormalFloat64 ¶

`func MutNormalFloat64(genome []float64, rate float64, rng *rand.Rand)`

MutNormalFloat64 modifies a float64 gene if a coin toss is under a defined mutation rate. The new gene value is a random value sampled from a normal distribution centered on the gene's current value and with a standard deviation proportional to the current value. It does so for each gene.

#### func MutPermute ¶

`func MutPermute(genome Slice, n int, rng *rand.Rand)`

MutPermute permutes two genes at random n times.

#### func MutPermuteFloat64 ¶

`func MutPermuteFloat64(s []float64, n int, rng *rand.Rand)`

MutPermuteFloat64 calls MutPermute on a float64 slice.

#### func MutPermuteInt ¶

`func MutPermuteInt(s []int, n int, rng *rand.Rand)`

MutPermuteInt calls MutPermute on an int slice.

#### func MutPermuteString ¶

`func MutPermuteString(s []string, n int, rng *rand.Rand)`

MutPermuteString callsMutPermute on a string slice.

#### func MutSplice ¶

`func MutSplice(genome Slice, rng *rand.Rand)`

MutSplice splits a genome in 2 and glues the pieces back together in reverse order.

#### func MutSpliceFloat64 ¶

`func MutSpliceFloat64(s []float64, rng *rand.Rand)`

MutSpliceFloat64 calls MutSplice on a float64 slice.

#### func MutSpliceInt ¶

`func MutSpliceInt(s []int, rng *rand.Rand)`

MutSpliceInt calls MutSplice on an int slice.

#### func MutSpliceString ¶

`func MutSpliceString(s []string, rng *rand.Rand)`

MutSpliceString calls MutSplice on a string slice.

#### func MutUniformString ¶

`func MutUniformString(genome []string, corpus []string, n int, rng *rand.Rand)`

MutUniformString picks a gene at random and replaces it with a random from a provided corpus. It repeats this n times.

### Types ¶

#### type DistanceMemoizer ¶

```type DistanceMemoizer struct {
Metric    Metric
Distances map[string]map[string]float64
// contains filtered or unexported fields
}```

A DistanceMemoizer computes and stores Metric calculations.

#### func (*DistanceMemoizer) GetDistance ¶

`func (dm *DistanceMemoizer) GetDistance(a, b Individual) float64`

GetDistance returns the distance between two Individuals based on the DistanceMemoizer's Metric field. If the two individuals share the same ID then GetDistance returns 0. DistanceMemoizer stores the calculated distances so that if GetDistance is called twice with the two same Individuals then the second call will return the stored distance instead of recomputing it.

#### type Float64Slice ¶

`type Float64Slice []float64`

Float64Slice attaches the methods of Slice to []float64

#### func (Float64Slice) Append ¶

`func (s Float64Slice) Append(t Slice) Slice`

Append method from Slice

#### func (Float64Slice) At ¶

`func (s Float64Slice) At(i int) interface{}`

At method from Slice

#### func (Float64Slice) Copy ¶

`func (s Float64Slice) Copy() Slice`

Copy method from Slice

#### func (Float64Slice) Len ¶

`func (s Float64Slice) Len() int`

Len method from Slice

#### func (Float64Slice) Replace ¶

`func (s Float64Slice) Replace(t Slice)`

Replace method from Slice

#### func (Float64Slice) Set ¶

`func (s Float64Slice) Set(i int, v interface{})`

Set method from Slice

#### func (Float64Slice) Slice ¶

`func (s Float64Slice) Slice(a, b int) Slice`

Slice method from Slice

#### func (Float64Slice) Split ¶

`func (s Float64Slice) Split(k int) (Slice, Slice)`

Split method from Slice

#### func (Float64Slice) Swap ¶

`func (s Float64Slice) Swap(i, j int)`

Swap method from Slice

#### type GA ¶

```type GA struct {
NewGenome NewGenome `json:"-"`
NPops     int       `json:"-"` // Number of Populations
PopSize   int       `json:"-"` // Number of Individuls per Population
Model     Model     `json:"-"`

// Optional fields
NBest        int          `json:"-"` // Length of HallOfFame
Migrator     Migrator     `json:"-"`
MigFrequency int          `json:"-"` // Frequency at which migrations occur
Speciator    Speciator    `json:"-"`
Logger       *log.Logger  `json:"-"`
Callback     func(ga *GA) `json:"-"`
RNG          *rand.Rand   `json:"-"`
ParallelEval bool         `json:"-"`

// Fields generated at runtime
Populations Populations   `json:"populations"`
HallOfFame  Individuals   `json:"hall_of_fame"` // Sorted best Individuals ever encountered
Age         time.Duration `json:"duration"`     // Duration during which the GA has been evolved
Generations int           `json:"generations"`  // Number of generations the GA has been evolved
}```

A GA contains population which themselves contain individuals.

#### func Generational ¶

`func Generational(NewGenome NewGenome) GA`

Generational returns a GA instance that uses the generational model.

#### func HillClimbing ¶

`func HillClimbing(NewGenome NewGenome) GA`

HillClimbing returns a GA instance that mimicks a basic hill-climbing procedure.

#### func SimulatedAnnealing ¶

`func SimulatedAnnealing(NewGenome NewGenome) GA`

SimulatedAnnealing returns a GA instance that mimicks a basic simulated annealing procedure.

#### func (*GA) Evolve ¶

`func (ga *GA) Evolve() error`

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

#### func (*GA) Initialize ¶

`func (ga *GA) Initialize()`

Initialize each population in the GA and assign an initial fitness to each individual in each population. Running Initialize after running Evolve will reset the GA entirely.

#### func (GA) Initialized ¶

`func (ga GA) Initialized() bool`

Initialized indicates if the GA has been initialized or not.

#### func (GA) Validate ¶

`func (ga GA) Validate() error`

Validate the parameters of a GA to ensure it will run correctly; some settings or combination of settings may be incoherent during runtime.

#### type Genome ¶

```type Genome interface {
Evaluate() float64
Mutate(rng *rand.Rand)
Crossover(genome Genome, rng *rand.Rand)
Clone() Genome
}```

A Genome is an object that can have any number and kinds of properties. As long as it can be evaluated, mutated and crossedover then it can evolved.

#### type Individual ¶

```type Individual struct {
Genome    Genome  `json:"genome"`
Fitness   float64 `json:"fitness"`
Evaluated bool    `json:"-"`
ID        string  `json:"id"`
}```

An Individual wraps a Genome and contains the fitness assigned to the Genome.

#### func NewIndividual ¶

`func NewIndividual(genome Genome, rng *rand.Rand) Individual`

NewIndividual returns a fresh individual.

#### func (Individual) Clone ¶

`func (indi Individual) Clone(rng *rand.Rand) Individual`

Clone an individual to produce a new individual with a different pointer and a different ID.

#### func (*Individual) Crossover ¶

`func (indi *Individual) Crossover(mate Individual, rng *rand.Rand)`

Crossover an individual by calling the Crossover method of it's Genome.

#### func (*Individual) Evaluate ¶

`func (indi *Individual) Evaluate()`

Evaluate the fitness of an individual. Don't evaluate individuals that have already been evaluated.

#### func (*Individual) GetFitness ¶

`func (indi *Individual) GetFitness() float64`

GetFitness returns the fitness of an Individual after making sure it has been evaluated.

#### func (Individual) IdxOfClosest ¶

`func (indi Individual) IdxOfClosest(indis Individuals, dm DistanceMemoizer) (i int)`

IdxOfClosest returns the index of the closest individual from a slice of individuals based on the Metric field of a DistanceMemoizer.

#### func (*Individual) Mutate ¶

`func (indi *Individual) Mutate(rng *rand.Rand)`

Mutate an individual by calling the Mutate method of it's Genome.

#### func (Individual) String ¶

`func (indi Individual) String() string`

String representation of an Individual. A tick (✔) or cross (✘) marker is added at the end to indicate if the Individual has been evaluated or not.

#### type Individuals ¶

`type Individuals []Individual`

Individuals is a convenience type, methods that belong to an Individual can be called declaratively.

#### func (Individuals) Apply ¶

`func (indis Individuals) Apply(f func(indi *Individual) error, parallel bool) error`

Apply a function to a slice of Individuals.

#### func (Individuals) Clone ¶

`func (indis Individuals) Clone(rng *rand.Rand) Individuals`

Clone returns the same exact same slice of individuals but with different pointers and ID fields.

#### func (Individuals) Evaluate ¶

`func (indis Individuals) Evaluate(parallel bool)`

Evaluate each Individual. If parallel is true then each Individual will be evaluated in parallel thanks to the golang.org/x/sync/errgroup package. If not then a simple sequential loop will be used. Evaluating in parallel is only recommended for cases where evaluating an Individual takes a "long" time. Indeed there won't necessarily be a speed-up when evaluating in parallel. In fact performance can be degraded if evaluating an Individual is too cheap.

#### func (Individuals) FitAvg ¶

`func (indis Individuals) FitAvg() float64`

FitAvg returns the average fitness of a slice of individuals.

#### func (Individuals) FitMax ¶

`func (indis Individuals) FitMax() float64`

FitMax returns the best fitness of a slice of individuals.

#### func (Individuals) FitMin ¶

`func (indis Individuals) FitMin() float64`

FitMin returns the best fitness of a slice of individuals.

#### func (Individuals) FitStd ¶

`func (indis Individuals) FitStd() float64`

FitStd returns the standard deviation of the fitness of a slice of individuals.

#### func (Individuals) IsSortedByFitness ¶

`func (indis Individuals) IsSortedByFitness() bool`

IsSortedByFitness checks if individuals are ascendingly sorted by fitness.

#### func (Individuals) Mutate ¶

`func (indis Individuals) Mutate(mutRate float64, rng *rand.Rand)`

Mutate each individual.

#### func (Individuals) SortByDistanceToMedoid ¶

`func (indis Individuals) SortByDistanceToMedoid(dm DistanceMemoizer)`

SortByDistanceToMedoid sorts Individuals according to their distance to the medoid. The medoid is the Individual that has the lowest average distance to the rest of the Individuals.

#### func (Individuals) SortByFitness ¶

`func (indis Individuals) SortByFitness()`

SortByFitness ascendingly sorts individuals by fitness.

#### func (Individuals) String ¶

`func (indis Individuals) String() string`

String representation of a slice of Individuals.

#### type IntSlice ¶

`type IntSlice []int`

IntSlice attaches the methods of Slice to []float64

#### func (IntSlice) Append ¶

`func (s IntSlice) Append(t Slice) Slice`

Append method from Slice

#### func (IntSlice) At ¶

`func (s IntSlice) At(i int) interface{}`

At method from Slice

#### func (IntSlice) Copy ¶

`func (s IntSlice) Copy() Slice`

Copy method from Slice

#### func (IntSlice) Len ¶

`func (s IntSlice) Len() int`

Len method from Slice

#### func (IntSlice) Replace ¶

`func (s IntSlice) Replace(t Slice)`

Replace method from Slice

#### func (IntSlice) Set ¶

`func (s IntSlice) Set(i int, v interface{})`

Set method from Slice

#### func (IntSlice) Slice ¶

`func (s IntSlice) Slice(a, b int) Slice`

Slice method from Slice

#### func (IntSlice) Split ¶

`func (s IntSlice) Split(k int) (Slice, Slice)`

Split method from Slice

#### func (IntSlice) Swap ¶

`func (s IntSlice) Swap(i, j int)`

Swap method from Slice

#### type Metric ¶

`type Metric func(a, b Individual) float64`

A Metric returns the distance between two genomes.

#### type MigRing ¶

```type MigRing struct {
NMigrants int // Number of migrants per exchange between Populations
}```

MigRing migration exchanges individuals between consecutive Populations in a random fashion. One by one, each population exchanges NMigrants individuals at random with the next population. NMigrants should be higher than the number of individuals in each population, else all the individuals will migrate and it will be as if nothing happened.

#### func (MigRing) Apply ¶

`func (mig MigRing) Apply(pops Populations, rng *rand.Rand)`

Apply MigRing.

#### func (MigRing) Validate ¶

`func (mig MigRing) Validate() error`

Validate MigRing fields.

#### type Migrator ¶

```type Migrator interface {
Apply(pops Populations, rng *rand.Rand)
Validate() error
}```

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

#### type ModDownToSize ¶

```type ModDownToSize struct {
NOffsprings int
SelectorA   Selector
SelectorB   Selector
MutRate     float64
}```

ModDownToSize implements the select down to size model.

#### func (ModDownToSize) Apply ¶

`func (mod ModDownToSize) Apply(pop *Population) error`

Apply ModDownToSize.

#### func (ModDownToSize) Validate ¶

`func (mod ModDownToSize) Validate() error`

Validate ModDownToSize fields.

#### type ModGenerational ¶

```type ModGenerational struct {
Selector Selector
MutRate  float64
}```

ModGenerational implements the generational model.

#### func (ModGenerational) Apply ¶

`func (mod ModGenerational) Apply(pop *Population) error`

Apply ModGenerational.

#### func (ModGenerational) Validate ¶

`func (mod ModGenerational) Validate() error`

Validate ModGenerational fields.

#### type ModMutationOnly ¶

```type ModMutationOnly struct {
NChosen  int // Number of individuals that are mutated each generation
Selector Selector
Strict   bool
}```

ModMutationOnly implements the mutation only model. Each generation, NChosen are selected and are replaced with mutants. Mutants are obtained by mutating the selected Individuals. If Strict is set to true, then the mutants replace the chosen individuals only if they have a lower fitness.

#### func (ModMutationOnly) Apply ¶

`func (mod ModMutationOnly) Apply(pop *Population) error`

Apply ModMutationOnly.

#### func (ModMutationOnly) Validate ¶

`func (mod ModMutationOnly) Validate() error`

Validate ModMutationOnly fields.

#### type ModRing ¶

```type ModRing struct {
Selector Selector
MutRate  float64
}```

ModRing implements the island ring model.

#### func (ModRing) Apply ¶

`func (mod ModRing) Apply(pop *Population) error`

Apply ModRing.

#### func (ModRing) Validate ¶

`func (mod ModRing) Validate() error`

Validate ModRing fields.

#### type ModSimAnn ¶

```type ModSimAnn struct {
T     float64 // Starting temperature
Tmin  float64 // Stopping temperature
Alpha float64 // Decrease rate per iteration
}```

ModSimAnn implements simulated annealing. Enhancing a GA with the ModSimAnn model only has to be done once for the simulated annealing to do a complete run. Successive enhancements will simply reset the temperature and run the simulated annealing again (which can potentially stagnate).

#### func (ModSimAnn) Apply ¶

`func (mod ModSimAnn) Apply(pop *Population) error`

Apply ModSimAnn.

#### func (ModSimAnn) Validate ¶

`func (mod ModSimAnn) Validate() error`

Validate ModSimAnn fields.

```type ModSteadyState struct {
Selector Selector
KeepBest bool
MutRate  float64
}```

`func (mod ModSteadyState) Apply(pop *Population) error`

`func (mod ModSteadyState) Validate() error`

#### type Model ¶

```type Model interface {
Apply(pop *Population) error
Validate() error
}```

A Model specifies a protocol for applying genetic operators to a population at generation i in order for it obtain better individuals at generation i+1.

#### type NewGenome ¶

`type NewGenome func(rng *rand.Rand) Genome`

A NewGenome is a method that generates a new Genome with random properties.

#### type Population ¶

```type Population struct {
Individuals Individuals   `json:"indis"`
Age         time.Duration `json:"age"`
Generations int           `json:"generations"`
ID          string        `json:"id"`
RNG         *rand.Rand
}```

A Population contains individuals. Individuals mate within a population. Individuals can migrate from one population to another. Each population has a random number generator to bypass the global rand mutex.

#### func (Population) Log ¶

`func (pop Population) Log(logger *log.Logger)`

Log a Population's current statistics with a provided log.Logger.

#### type Populations ¶

`type Populations []Population`

Populations type is necessary for migration and speciation purposes.

#### func (Populations) Apply ¶

`func (pops Populations) Apply(f func(pop *Population) error, parallel bool) error`

Apply a function to a slice of Populations.

#### type SelElitism ¶

`type SelElitism struct{}`

SelElitism selection returns the n best individuals of a group.

#### func (SelElitism) Apply ¶

`func (sel SelElitism) Apply(n int, indis Individuals, rng *rand.Rand) (Individuals, []int, error)`

Apply SelElitism.

#### func (SelElitism) Validate ¶

`func (sel SelElitism) Validate() error`

Validate SelElitism fields.

#### type SelRoulette ¶

`type SelRoulette struct{}`

SelRoulette samples individuals through roulette wheel selection (also known as fitness proportionate selection).

#### func (SelRoulette) Apply ¶

`func (sel SelRoulette) Apply(n int, indis Individuals, rng *rand.Rand) (Individuals, []int, error)`

Apply SelRoulette.

#### func (SelRoulette) Validate ¶

`func (sel SelRoulette) Validate() error`

Validate SelRoulette fields.

#### type SelTournament ¶

```type SelTournament struct {
NContestants int
}```

SelTournament samples individuals through tournament selection. The tournament is composed of randomly chosen individuals. The winner of the tournament is the chosen individual with the lowest fitness. The obtained individuals are all distinct.

#### func (SelTournament) Apply ¶

`func (sel SelTournament) Apply(n int, indis Individuals, rng *rand.Rand) (Individuals, []int, error)`

Apply SelTournament.

#### func (SelTournament) Validate ¶

`func (sel SelTournament) Validate() error`

Validate SelTournament fields.

#### type Selector ¶

```type Selector interface {
Apply(n int, indis Individuals, rng *rand.Rand) (selected Individuals, indexes []int, err error)
Validate() error
}```

Selector chooses a subset of size n from a group of individuals. The group of individuals a Selector is applied to is expected to be sorted.

#### type Slice ¶

```type Slice interface {
At(i int) interface{}
Set(i int, v interface{})
Len() int
Swap(i, j int)
Slice(a, b int) Slice
Split(k int) (Slice, Slice)
Append(Slice) Slice
Replace(Slice)
Copy() Slice
}```

A Slice is a genome with a list-like structure.

#### type SpecFitnessInterval ¶

```type SpecFitnessInterval struct {
K int // Number of intervals
}```

SpecFitnessInterval speciates a population based on the fitness of each individual where each species contains m = n/k (rounded to the closest upper integer) individuals with similar fitnesses. For example, with 4 species, 30 individuals would be split into 3 groups of 8 individuals and 1 group of 6 individuals (3*8 + 1*6 = 30). More generally each group is of size min(n-i, m) where i is a multiple of m.

#### func (SpecFitnessInterval) Apply ¶

`func (spec SpecFitnessInterval) Apply(indis Individuals, rng *rand.Rand) ([]Individuals, error)`

Apply SpecFitnessInterval.

#### func (SpecFitnessInterval) Validate ¶

`func (spec SpecFitnessInterval) Validate() error`

Validate SpecFitnessInterval fields.

#### type SpecKMedoids ¶

```type SpecKMedoids struct {
K             int // Number of medoids
MinPerCluster int
Metric        Metric // Dissimimilarity measure
MaxIterations int
}```

SpecKMedoids (k-medoid clustering).

#### func (SpecKMedoids) Apply ¶

`func (spec SpecKMedoids) Apply(indis Individuals, rng *rand.Rand) ([]Individuals, error)`

Apply SpecKMedoids.

#### func (SpecKMedoids) Validate ¶

`func (spec SpecKMedoids) Validate() error`

Validate SpecKMedoids fields.

#### type Speciator ¶

```type Speciator interface {
Apply(indis Individuals, rng *rand.Rand) ([]Individuals, error)
Validate() error
}```

A Speciator partitions a population into n smaller subpopulations. Each subpopulation shares the same random number generator inherited from the initial population.

#### type StringSlice ¶

`type StringSlice []string`

StringSlice attaches the methods of Slice to []float64

#### func (StringSlice) Append ¶

`func (s StringSlice) Append(t Slice) Slice`

Append method from Slice

#### func (StringSlice) At ¶

`func (s StringSlice) At(i int) interface{}`

At method from Slice

#### func (StringSlice) Copy ¶

`func (s StringSlice) Copy() Slice`

Copy method from Slice

#### func (StringSlice) Len ¶

`func (s StringSlice) Len() int`

Len method from Slice

#### func (StringSlice) Replace ¶

`func (s StringSlice) Replace(t Slice)`

Replace method from Slice

#### func (StringSlice) Set ¶

`func (s StringSlice) Set(i int, v interface{})`

Set method from Slice

#### func (StringSlice) Slice ¶

`func (s StringSlice) Slice(a, b int) Slice`

Slice method from Slice

#### func (StringSlice) Split ¶

`func (s StringSlice) Split(k int) (Slice, Slice)`

Split method from Slice

#### func (StringSlice) Swap ¶

`func (s StringSlice) Swap(i, j int)`

Swap method from Slice