Eaopt
:four_leaf_clover: Evolutionary optimization library for Go (genetic algorithm, partical swarm optimization, differential evolution)
Install / Use
/learn @MaxHalford/EaoptREADME
Table of Contents
- Changelog
- Example
- Background
- Features
- Usage
- 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.
<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>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
GAstruct - 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
Minimizefunction 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
NewPSOfunction instead of instantiating thePSOstruct 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
GAstruct 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:
- Generate random solutions to a problem.
- Assign a fitness to each solutions.
- Check if a new best solution has been found.
- Apply genetic operators following a given evolutionary model.
- Repeat from step 2 until the stopping criterion is satisfied.
This
