eaopt

About eaopt

This large README is shown as a plain-text preview. Read the full README at the source

<div align="center">
  <!-- Logo -->
  <img src="https://docs.google.com/drawings/d/e/2PACX-1vRzNhZcghWl-xRaynEAQn4moZeyh6pmD8helS099eJ7V_TRGM9dE6e0T5IF9bOG7S4K62CKZtSUpans/pub?w=477&h=307" alt="logo"/>
</div>

<div align="center">
  <!-- Awesome Go -->
  <a href="https://github.com/avelino/awesome-go">
    <img src="https://cdn.rawgit.com/sindresorhus/awesome/d7305f38d29fed78fa85652e3a63e154dd8e8829/media/badge.svg" alt="awesome_go" />
  </a>
  <!-- Awesome Machine Learning -->
  <a href="https://github.com/josephmisiti/awesome-machine-learning">
    <img src="https://cdn.rawgit.com/sindresorhus/awesome/d7305f38d29fed78fa85652e3a63e154dd8e8829/media/badge.svg" alt="awesome_ml" />
  </a>
</div>

<br/>

<div align="center">
  <!-- godoc -->
  <a href="https://godoc.org/github.com/MaxHalford/eaopt">
    <img src="https://img.shields.io/badge/godoc-reference-blue.svg?style=flat-square" alt="godoc" />
  </a>
  <!-- Build status -->
  <a href="https://travis-ci.org/MaxHalford/eaopt">
    <img src="https://img.shields.io/travis/MaxHalford/eaopt/master.svg?style=flat-square" alt="build_status" />
  </a>
  <!-- Test coverage -->
  <a href="https://coveralls.io/github/MaxHalford/eaopt?branch=master">
    <img src="https://coveralls.io/repos/github/MaxHalford/eaopt/badge.svg?branch=master&style=flat-square" alt="test_coverage" />
  </a>
  <!-- Go report card -->
  <a href="https://goreportcard.com/report/github.com/MaxHalford/eaopt">
    <img src="https://goreportcard.com/badge/github.com/MaxHalford/eaopt?style=flat-square" alt="go_report_card" />
  </a>
  <!-- Code Climate -->
  <a href="https://codeclimate.com/github/MaxHalford/eaopt">
    <img src="https://codeclimate.com/github/MaxHalford/eaopt/badges/gpa.svg" alt="Code Climate" />
  </a>
  <!-- Hound -->
  <a href="https://houndci.com">
    <img src="https://img.shields.io/badge/Reviewed_by-Hound-8E64B0.svg" alt="Hound" />
  </a>
  <!-- License -->
  <a href="https://opensource.org/licenses/MIT">
    <img src="http://img.shields.io/:license-mit-ff69b4.svg?style=flat-square" alt="license"/>
  </a>
</div>

<br/>

<div align="center">eaopt is an evolutionary optimization library</div>

<br/>

**Table of Contents**
  - [Changelog](#changelog)
  - [Example](#example)
  - [Background](#background)
  - [Features](#features)
  - [Usage](#usage)
    - [General advice](#general-advice)
    - [Genetic algorithms](#genetic-algorithms)
      - [Overview](#overview)
      - [Implementing the Genome interface](#implementing-the-genome-interface)
      - [Instantiating the GA struct](#instantiating-the-ga-struct)
      - [Calling the Minimize method](#calling-the-minimize-method)
      - [Using the Slice interface](#using-the-slice-interface)
      - [Models](#models)
      - [Multiple populations and migration](#multiple-populations-and-migration)
      - [Speciation](#speciation)
      - [Logging population statistics](#logging-population-statistics)
    - [Particle swarm optimization](#particle-swarm-optimization)
    - [Differential evolution](#differential-evolution)
    - [OpenAI evolution strategy](#openai-evolution-strategy)
    - [Hill climbing](#hill-climbing)
    - [Simulated annealing](#simulated-annealing)
  - [A note on parallelism](#a-note-on-parallelism)
  - [FAQ](#faq)
  - [Dependencies](#dependencies)
  - [License](#license)

## Changelog

- **11/11/18**: a simple version of [OpenAI's evolution strategy](https://blog.openai.com/evolution-strategies/) has been implemented, it's called `OES`.
- **02/08/18**: gago has now become eaopt. You can still everything you could do before but the scope is now larger than genetic algorithms. The goal is to implement many more evolutionary optimization algorithms on top of the existing codebase.

## Example

The following example attempts to minimize the [Drop-Wave function](https://www.sfu.ca/~ssurjano/drop.html) using a genetic algorithm. The Drop-Wave function is known to have a minimum value of -1 when each of it's arguments is equal to 0.

<div align="center">
  <img src="https://github.com/MaxHalford/eaopt-examples/blob/master/drop_wave/chart.png" alt="drop_wave_chart" />
  <img src="https://github.com/MaxHalford/eaopt-examples/blob/master/drop_wave/function.png" alt="drop_wave_function" />
</div>

```go
package main

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

    "github.com/MaxHalford/eaopt"
)

// 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). The function is simple so there
// isn't any error handling to do.
func (X Vector) Evaluate() (float64, error) {
    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, nil
}

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

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

// Clone a Vector to produce a new one that points to a different slice.
func (X Vector) Clone() eaopt.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) eaopt.Genome {
    return Vector(eaopt.InitUnifFloat64(2, -10, 10, rng))
}

func main() {
    // Instantiate a GA with a GAConfig
    var ga, err = eaopt.NewDefaultGAConfig().NewGA()
    if err != nil {
        fmt.Println(err)
        return
    }

    // Set the number of generations to run for
    ga.NGenerations = 10

    // Add a custom print function to track progress
    ga.Callback = func(ga *eaopt.GA) {
        fmt.Printf("Best fitness at generation %d: %f\n", ga.Generations, ga.HallOfFame[0].Fitness)
    }

    // Find the minimum
    err = ga.Minimize(VectorFactory)
    if err != nil {
        fmt.Println(err)
        return
    }
}

```

```sh
>>> 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
>>> Best fitness at generation 10: -0.999999
```

All the examples can be found [in this repository](https://github.com/MaxHalford/eaopt-examples).

## Background

Evolutionary optimization algorithms are a subdomain of evolutionary computation. Their goal is to minimize/maximize a function without using any gradient information (usually because there isn't any gradient available). They share the common property of exploring the search space by breeding, mutating, evaluating, and sorting so-called *individuals*. Most evolutionary algorithms are designed to handle real valued functions, however in practice they are commonly used for handling more exotic problems. For example genetic algorithms can be used to find the optimal structure of a neural network.

eaopt provides implementations for various evolutionary optimization algorithms. Implementation-wise, the idea is that most (if not all) of said algorithms can be written as special cases of a genetic algorithm. Indeed this is made possible by using a generic definition of a genetic algorithm by allowing the mutation, crossover, selection, and replacement procedures to be modified at will. The `GA` struct is thus the most flexible struct of eaopt, the other algorithms are written on top of it. If you don't find any algorithm that suits your need then you can easily write your own operators (as is done in most of the [examples](https://github.com/MaxHalford/eaopt-examples)).

## Features

- Different evolutionary algorithms are available with a consistent API
- You can practically do anything by using the `GA` struct
- Speciation and migration procedures are available
- Common genetic operators (mutation, crossover, selection, migration, speciation) are already implemented
- Function evaluation can be done in parallel if your function is costly

## Usage

### General advice

- Evolutionary algorithms are usually designed for solving specific kinds of problems. Take a look at the `Minimize` function of each method to get an idea of what type of function it can optimize.
- Use the associated constructor function of each method to initialize it. For example use the `NewPSO` function instead of instantiating the `PSO` struct yourself. Along with making your life easier, these functions provide the added benefit of checking for parameter input errors.
- If you're going to use the `GA` struct then be aware that some evolutionary operators are already implemented in eaopt (you don't necessarily have to reinvent the wheel).
- Don't feel overwhelmed by the fact that algorithms are implemented as special cases of genetic algorithms. It doesn't matter if you just want to get things done, it just makes things easier under the hood.

### Genetic algorithms

#### Overview

Genetic algorithms are the backbone of eaopt. Most of the other algorithms available in eaopt are implemented as special cases of GAs. A GA isn't an algorithm per say, but rather a blueprint which can be used to optimize any kind of problem.

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

1. Generate random solutions to a problem.
2. Assign a fitness to each solutions.
3. Check if a new best solution has been found.
4. Apply genetic operators following a given evolutionary model.
5. Repeat from step 2 until the stopping criterion is satisfied.

This description is voluntarily vague. It is up to the user to define the problem and the genetic operators to use. Different categories of genetic operators exist:

- Mutation operators modify an existing solution.
- Crossover operators generate a new solution by combining two or more existing ones.
- Selection operators selects individuals that are to be evolved.
- Migration swaps individuals between populations.
- Speciation clusters individuals into subpopulations.

Popular stopping criteria include

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

Genetic algorithms can be used via the `GA` struct. The necessary steps for using the GA struct are

1. Implement the `Genome` interface to model your problem
2. Instantiate a `GA` struct (preferably via the `GAConfig` struct)
3. Call the GA's `Minimize` function and check the `HallOfFame` field


#### Implementing the Genome interface

To use the `GA` struct you first have to implement the `Genome` interface, which is used to define the logic that is specific to your problem (logic that eaopt 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). Apart from a good design pattern, decoupling the problem definition from the optimization through the `Genome` interface means that eaopt can be used to optimize *any* kind of problem.

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

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

The `Evaluate()` method returns the fitness of a 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. The `Evaluate()` method is *your* problem to deal with. eaopt only needs it's output to be able to function. You can also return an `error` which eaopt will catch and return when calling `ga.Initialize()` and `ga.Evolve()`.

The `Mutate(rng *rand.Rand)` method is where you can modify an existing solution by tinkering with it's variables. The way in which you should mutate a solution essentially boils down to your particular problem. eaopt provides some common mutation methods that you can use instead of reinventing the wheel -- this is what is being done in most of the [examples](https://github.com/MaxHalford/eaopt-examples).

The `Crossover(genome Genome, rng *rand.Rand)` method combines 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 `Clone()` 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 identical memory addresses. Usually this is not too difficult implement; you just have to make sure that the clones you produce are not shallow copies of the genome that is being cloned. This is also fairly easy to unit test.

Once you have implemented the `Genome` interface you have provided eaopt with all the information it couldn't guess for you.

#### Instantiate the GA struct

You can now instantiate a `GA` and use it to find an optimal solution to your problem. The `GA` struct has a lot of fields, hence the recommended way is to use the `GAConfig` struct and call it's `NewGA` method.

Let's have a look at the `GAConfig` struct.

```go
type GAConfig struct {
    // Required fields
    NPops        uint
    PopSize      uint
    NGenerations uint
    HofSize      uint
    Model        Model

    // Optional fields
	  ParallelInit bool // Whether to initialize Individuals in parallel or not
    ParallelEval bool // Whether to evaluate Individuals in parallel or not
    Migrator     Migrator
    MigFrequency uint // Frequency at which migrations occur
    Speciator    Speciator
    Logger       *log.Logger
    Callback     func(ga *GA)
    EarlyStop    func(ga *GA) bool
    RNG          *rand.Rand
}
```

- Required fields
  - `NPops` determines the number of populations that will be used.
  - `PopSize` determines the number of individuals inside each population.
  - `NGenerations` determines for many generations the populations will be evolved.
  - `HofSize` determines how many of the best individuals should be recorded.
  - `Model` is a struct that determines how to evolve each population of individuals.
- Optional fields
  - `ParallelInit` determines if a population is initialized in parallel. The rule of thumb is to set this to `true` if your genome initialization method is expensive, if not it won't be worth the overhead. Refer to the [section on parallelism](#a-note-on-parallelism) for a more comprehensive explanation.
  - `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](#a-note-on-parallelism) for a more comprehensive explanation.
  - `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` can be used to record basic population statistics, you can read more about it in the [logging section](#logging-population-statistics).
  - `Callback` 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 convergence
  - `EarlyStop` will be called before each generation to check if the evolution should be stopped early.
  - `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))`.

Once you have instantiated a `GAConfig` you can call it's `NewGA` method to obtain a `GA`. The `GA` struct has the following definition:

```go
type GA struct {
    GAConfig

    Populations Populations
    HallOfFame  Individuals
    Age         time.Duration
    Generations uint
}
```

Naturally a `GA` stores a copy of the `GAConfig` that was used to instantiate it. Apart from this the following fields are available:

- `Populations` is where all the current populations and individuals are kept.
- `HallOfFame` contains the `HofSize` best 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 evolving.
- `Generations` indicates how many how many generations have gone by.

You could bypass the `NewGA` method instantiate a `GA` with a `GAConfig` but this would leave the `GAConfig`'s fields unchecked for input errors.


#### Calling the Minimize method

You are now all set to find an optimal solution to your problem. To do so you have to call the GA's `Minimize` function which has the following signature:

```go
func (ga *GA) Minimize(newGenome func(rng *rand.Rand) Genome) error
```

You have to provide the `Minimize` a function which returns a `Genome`. It is recommended that the `Genome` thus produced contains random values. This is where the connection between the `Genome` interface and the `GA` struct is made.

The `Minimize` function will return an error (`nil` if everything went okay) once it is done. You can done access the first entry in the `HallOfFame` field to retrieve the best encountered solution.


#### 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 available in eaopt are based on the `Slice` interface which has the following definition.

```go
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 with 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`](slice.go) and the [TSP example](https://github.com/MaxHalford/eaopt-examples/tree/master/tsp_grid).


#### Models

Frequently Asked Questions