github.com/MaxHalford/eaopt @v0.4.2

eaopt is an evolutionary optimization library

Table of Contents - Changelog - Example - Background - Features - Usage - General advice - Genetic algorithms - Overview - Implementing the Genome interface - Instantiating the GA struct - Calling the Minimize method - Using the Slice interface - Models - Multiple populations and migration - Speciation - Logging population statistics - Particle swarm optimization - Differential evolution - OpenAI evolution strategy - A note on parallelism - FAQ - Dependencies - License

Changelog

• 11/11/18: a simple version of OpenAI's evolution strategy 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 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.

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
    }
}

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

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

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.

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.

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