Evolutionary optimization library for Go (genetic algorithm, partical swarm optimization, differential evolution)

Overview
logo


eaopt is an evolutionary optimization library

Table of Contents

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.

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

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

    // Optional fields
    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
    • 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.
    • 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.
    • 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:

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:

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.

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 and the TSP example.

Models

eaopt makes it easy to use different so called models. Simply put, a models defines how a GA evolves a population of individuals through a sequence of genetic operators. It does so without considering whatsoever the intrinsics of 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.

generational
Steady state model

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.

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

select-down-to-size
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.

ring
Mutation only

It's possible to run a GA without crossover simply by mutating individuals. This can be done with the ModMutationOnly struct. At each generation each individual is mutated. ModMutationOnly has a strict field to determine if the mutant should replace the initial individual only if it's fitness is lower.

Speciation

Clusters, also called species in the literature, are a partitioning of individuals into smaller groups of similar individuals. Programmatically a cluster is a list of lists that each contain 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 the selection phase. Thus speciation was introduced so that neural networks evolved in similar groups in order for 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 eaopt 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.

speciation

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 eaopt a GA struct contains a Populations field which stores each population in a slice. The number of populations is specified in the GAConfig's NPops field.

If Migrator and MigFrequency are not provided the populations will be run independently in parallel. However, if they are provided then at each generation number that is divisible by MigFrequency (for example 5 divides generation number 25) individuals will be exchanged between the populations following the Migrator.

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 eaopt you can use multi-populations and speciation at the same time. The following flowchart shows what that would look like.

multi-population_and_speciation

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.

Particle swarm optimization

Description

Particle swarm optimization (PSO) can be used to optimize real valued functions. It maintains a population of candidate solutions called particles. The particles move around the search-space according to a mathematical formula that takes as input the particle's position and it's velocity. Each particle's movement is influenced by its's local best encountered position, as well as the best overall position in the search-space (these values are updated after each generation). This is expected to move the swarm toward the best solutions.

As can be expected there are many variants of PSO. The SPSO struct implements the SPSO-2011 standard.

Example

In this example we're going to minimize th Styblinski-Tang function with two dimensions. The global minimum is about -39.16599 times the number of dimensions.

package main

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

    "github.com/MaxHalford/eaopt"
)

func StyblinskiTang(X []float64) (y float64) {
    for _, x := range X {
        y += m.Pow(x, 4) - 16*m.Pow(x, 2) + 5*x
    }
    return 0.5 * y
}

func main() {
    // Instantiate SPSO
    var spso, err = eaopt.NewDefaultSPSO()
    if err != nil {
        fmt.Println(err)
        return
    }

    // Fix random number generation
    spso.GA.RNG = rand.New(rand.NewSource(42))

    // Run minimization
    _, y, err := spso.Minimize(StyblinskiTang, 2)
    if err != nil {
        fmt.Println(err)
        return
    }

    // Output best encountered solution
    fmt.Printf("Found minimum of %.5f, the global minimum is %.5f\n", y, -39.16599*2)
}

This should produce the following output.

>>> Found minimum of -78.23783, the global minimum is -78.33198

Parameters

You can (and should) instantiate an SPSO with the NewSPSO method. You can also use the NewDefaultSPSO method as is done in the previous example.

func NewSPSO(nParticles, nSteps uint, min, max, w float64, parallel bool, rng *rand.Rand) (*SPSO, error)
  • nParticles is the number of particles to use
  • nSteps is the number of steps during which evolution occurs
  • min and max are the boundaries from which the initial values are sampled from
  • w is the velocity amplifier
  • parallel determines if the particles are evaluated in parallel or not
  • rng is a random number generator, you can set it to nil if you want it to be random

Differential evolution

Description

Differential evolution (DE) somewhat resembles PSO and is also used for optimizing real-valued functions. At each generation, each so-called agent is moved according to the position of 3 randomly sampled agents. If the new position is not better than the current one then it is discarded.

As can be expected there are many variants of PSO. The SPSO struct implements the SPSO-2011 standard.

Example

In this example we're going to minimize th Ackley function with two dimensions. The global minimum is 0.

package main

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

    "github.com/MaxHalford/eaopt"
)

func Ackley(x []float64) float64 {
    var (
        a, b, c = 20.0, 0.2, 2 * m.Pi
        s1, s2  float64
        d       = float64(len(x))
    )
    for _, xi := range x {
        s1 += xi * xi
        s2 += m.Cos(c * xi)
    }
    return -a*m.Exp(-b*m.Sqrt(s1/d)) - m.Exp(s2/d) + a + m.Exp(1)
}

func main() {
    // Instantiate DiffEvo
    var de, err = eaopt.NewDefaultDiffEvo()
    if err != nil {
        fmt.Println(err)
        return
    }

    // Fix random number generation
    de.GA.RNG = rand.New(rand.NewSource(42))

    // Run minimization
    _, y, err := de.Minimize(Ackley, 2)
    if err != nil {
        fmt.Println(err)
        return
    }

    // Output best encountered solution
    fmt.Printf("Found minimum of %.5f, the global minimum is 0\n", y)
}

This should produce the following output.

>>> Found minimum of 0.00137, the global minimum is 0

Parameters

You can (and should) instantiate an DiffEvo with the NewDiffEvo method. You can also use the NewDefaultDiffEvo method as is done in the previous example.

func NewDiffEvo(nAgents, nSteps uint, min, max, cRate, dWeight float64, parallel bool, rng *rand.Rand) (*DiffEvo, error)
  • nAgents is the number of agents to use (it has to be at least 4)
  • nSteps is the number of steps during which evolution occurs
  • min and max are the boundaries from which the initial values are sampled from
  • cRate is the crossover rate
  • dWeight is the differential weight
  • parallel determines if the agents are evaluated in parallel or not
  • rng is a random number generator, you can set it to nil if you want it to be random

OpenAI evolution strategy

Description

OpenAI proposed a simple evolution strategy based on the use of natural gradients. The algorithm is dead simple:

  1. Choose a center mu at random
  2. Sample points around mu using a normal distribution
  3. Evaluate each point and obtain the natural gradient g
  4. Move mu along the natural gradient g using a learning rate
  5. Repeat from step 2 until satisfied

Example

In this example we're going to minimize th Rastrigin function with three dimensions. The global minimum is 0.

package main

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

    "github.com/MaxHalford/eaopt"
)

func Rastrigin(x []float64) (y float64) {
    y = 10 * float64(len(x))
    for _, xi := range x {
        y += m.Pow(xi, 2) - 10*m.Cos(2*m.Pi*xi)
    }
    return y
}

func main() {
    // Instantiate DiffEvo
    var oes, err = eaopt.NewDefaultOES()
    if err != nil {
        fmt.Println(err)
        return
    }

    // Fix random number generation
    oes.GA.RNG = rand.New(rand.NewSource(42))

    // Run minimization
    _, y, err := oes.Minimize(Rastrigin, 2)
    if err != nil {
        fmt.Println(err)
        return
    }

    // Output best encountered solution
    fmt.Printf("Found minimum of %.5f, the global minimum is 0\n", y)
}

This should produce the following output.

>>> Found minimum of 0.02270, the global minimum is 0

Parameters

You can (and should) instantiate an OES with the NewOES method. You can also use the NewDefaultOES method as is done in the previous example.

func NewOES(nPoints, nSteps uint, sigma, lr float64, parallel bool, rng *rand.Rand) (*OES, error)
  • nPoints is the number of points to use (it has to be at least 3)
  • nSteps is the number of steps during which evolution occurs
  • sigma determines the shape of the normal distribution used to sample new points
  • lr is the learning rate
  • parallel determines if the agents are evaluated in parallel or not
  • rng is a random number generator, you can set it to nil if you want it to be random

A note on parallelism

Evolutionary algorithms are famous for being embarrassingly parallel. Most of the operations 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 eaopt 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 eaopt.Genome, rng *rand.Rand) {}

Why aren't my Mutate and Crossover methods modifying my Genomes?

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) {
    eaopt.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()
}

Are evolutionary optimization algorithms any good?

For real-valued, differentiable functions, evolutionary optimization algorithms will probably not fair well against methods based on gradient descent. Intuitively this is because evolutionary optimization algorithms ignore the shape and slope of the function. However gradient descent algorithms usually get stuck in local optimas, whereas evolutionary optimization algorithms don't.

As mentioned earlier, some problems can simply not be written down as closed-form expressions. In this case methods based on gradient information can't be used whilst evolutionary optimization algorithms can still be used. 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.

How can I contribute?

Feel free to implement your own operators or to make suggestions! Check out the CONTRIBUTING file for some guidelines. This repository has a long list of existing evolutionary algorithms.

Dependencies

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

License

The MIT License (MIT). Please see the LICENSE file for more information.

Issues
  • Very big repository

    Very big repository

    Is it possible to separate the big files (eg. those in examples) from the core library?

    My network speed is very slow that it takes a very long time to clone the repository......

    I think it's around ~~100MiB~~........(still cloning Receiving objects: 15% (266/1694), 16.08 MiB | 180.00 KiB/s)

    opened by AP-Nothize 22
  • Crash...

    Crash...

    Hello,

    This may be my fault (almost certainly is) but it may be enlightening. I'll triple-check my code.

    So first, from the Generation step down to the GA # 4 has a minimum is from my Callback routine.

    Interestingly, it looks like it doesn't get called for the next few generations, and then the crash comes.

    My setup is:

    	var ga = gago.Generational(MakeNewVectorFunc(NUM, -0.1, 0.1))
    	ga.NPops = 5
    	ga.PopSize = 250
    	ga.Speciator = gago.SpecKMedoids{
    		K:             10,
    		MinPerCluster: 10,
    		Metric:        l1Distance,
    		MaxIterations: 5,
    	}
    	ga.Callback = checkStats
    	ga.Initialize()
    

    I stole the l1Distance bodily from your source... I'll tell you where to send the ransom money :-)

    here's the backtrace info:

    Generation step took 3m14.626519066s
    GA has 5 Populations.
    GA 0 has 250 individuals.
    GA # 0 has a minimum 4302236.000000000000, maximum 20046975.000000000000
    GA 1 has 250 individuals.
    GA # 1 has a minimum 4387752.000000000000, maximum 20046975.000000000000
    GA 2 has 250 individuals.
    GA # 2 has a minimum 4315952.000000000000, maximum 20046975.000000000000
    GA 3 has 250 individuals.
    GA # 3 has a minimum 4276399.000000000000, maximum 20046975.000000000000
    GA 4 has 250 individuals.
    GA # 4 has a minimum 4256291.000000000000, maximum 20046975.000000000000
    Best fitness at generation    5: 3675431.000000
    Best fitness at generation    6: 3675431.000000
    Best fitness at generation    7: 3675431.000000
    Best fitness at generation    8: 3675431.000000
    panic: runtime error: index out of range
    
    goroutine 65 [running]:
    github.com/MaxHalford/gago.SpecKMedoids.Apply(0xa, 0xa, 0x146ed90, 0x5, 0xc42324a000, 0xfa, 0xfa, 0xc420014e70, 0x0, 0x0, ...)
            /Volumes/Second/Chris/hacks/gofigure/src/github.com/MaxHalford/gago/speciation.go:60 +0x754
    github.com/MaxHalford/gago.(*SpecKMedoids).Apply(0xc42000c220, 0xc42324a000, 0xfa, 0xfa, 0xc420014e70, 0x0, 0x0, 0x0, 0x0, 0x0)
            <autogenerated>:85 +0xa0
    github.com/MaxHalford/gago.(*Population).speciateEvolveMerge(0xc4200e8240, 0x1627a40, 0xc42000c220, 0x16279c0, 0xc42000c180, 0x1, 0x3)
            /Volumes/Second/Chris/hacks/gofigure/src/github.com/MaxHalford/gago/ga.go:181 +0x77
    github.com/MaxHalford/gago.(*GA).Enhance.func1(0x8, 0x146f890)
            /Volumes/Second/Chris/hacks/gofigure/src/github.com/MaxHalford/gago/ga.go:142 +0x97
    golang.org/x/sync/errgroup.(*Group).Go.func1(0xc420010480, 0xc422890150)
            /Volumes/Second/Chris/hacks/gofigure/src/golang.org/x/sync/errgroup/errgroup.go:58 +0x57
    created by golang.org/x/sync/errgroup.(*Group).Go
            /Volumes/Second/Chris/hacks/gofigure/src/golang.org/x/sync/errgroup/errgroup.go:66 +0x66
    exit status 2
    
    opened by csterritt 14
  • Pass aditional data in Evaluate function

    Pass aditional data in Evaluate function

    Hi

    I need to access some data (which is not contained in Genome) to compute fitness. I looked in the documentation but didn't find a way to pass additional data to the Evaluate function. One option would be using global variables, but i think that is not the best way.

    Do you have any ideas?

    opened by franzon 10
  • Gene Uniqueness - PMX/OX

    Gene Uniqueness - PMX/OX

    First of all, thank you for all the work on this amazing library!

    Now using your predefined crossover functions it seems that if one wants to preserve gene uniqueness one could either use PMX or OX. In my case, however, trying to optimize the order of a set of pointers. Now the issue is that a single pointer can have several occurrences in a gnome, like here:

    geneA := "A"
    geneB := "B"
    geneC := "C"
    gnome := []*string {&geneA, &geneA, &geneB, &geneC, &geneC, &geneC}
    

    It seems in cases like this the uniqueness of the number of occurrences is not preserved between crossovers. Is this the intended behavior, as the gnome is not comprised out of unique genes?

    opened by theveloped 9
  • Parallelizing Individual Evaluate() calls?

    Parallelizing Individual Evaluate() calls?

    Hi! Thanks for writing gago - it is very useful. I was in the middle of writing my own GA loop, when I realized I shouldn't be reinventing the wheel and stumbled accross your library.

    per the docs:

    Talking about parallelism, there is a reason why the populations are run in parallel and not the individuals. First of all for parallelism at an individual level each individual would have to be assigned a new random number generator, which isn't very efficient. Second of all, even though Golang has an efficient concurrency model, spawning routines nonetheless has an overhead. It's simply not worth using a routine for each individual because operations at an individual level are often not time consuming enough.

    This makes sense for GA operations, specifically those that require an RNG - mutate, crossover, et al. Those generally are fairly fast too, so the argument against overhead is totally valid.

    With that said, my Evaluate() function is relatively expensive (upwards to 1 second for each call) and already does not have access to the population's RNG. Would it make sense then to parallelize Evaluate() calls on individuals within a population? We could make this default to off for use cases where the Evaluate() function is fast and doing this would just cause overhead.

    Let me know what you think. If this sounds good, I'll be glad to work on it when I get a chance and submit a PR. If you have any implementation suggestions / preferences, let me know too

    opened by andrewortman 7
  • Evaluate against other genome

    Evaluate against other genome

    Hi, I'm not knowledgeable in the AI/GA domain, and I had an idea in head that confused me.

    Now that I sat back, I got it and it's normal, we're trying to optimize a function.

    But as I saw it previously, I thought we would evaluate genomes against each other and have the best ones sorted out. But in the current implementation of gago (and in GA in general I guess), the evaluation is against a function, not against another genome.

    To explain my idea, an example might help. I have a game with characters that can be created with abilities values (strength, dexterity, constitution) and I would like to know what is the optimum way to dispatch ability point in those abilities to have a good fighter. So I wanted to simulate a fight between 2 genomes to determine a winner as the evaluation. Instead, right now, I just try to optimize ability score because mechanically it will make a better fighter, but it doesn't correspond to the idea I had.

    Is this a good idea? Is it applied in other fields/lib? Is it doable already with the current gago?

    opened by dolanor 7
  • Minimum score goes up rather than down sometimes

    Minimum score goes up rather than down sometimes

    I'm trying to use your library, but I'm getting some really strange results sometimes. For certain models, the population seems to be getting worse (fitness function going up) as time goes on rather than better.

    Here's one configuration I used:

    		ga = gago.GA {
    			NewGenome: ScheduleFactory,
    			NPops:     2,
    			PopSize:   200,
    			Model: gago.ModMutationOnly {
    				NChosen: 50,
    				Selector: gago.SelElitism { },
    				Strict: true,
    			},
    		}
    

    And here is some sample output from the log:

    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-42968.000000 max=-30081.000000 avg=-37780.345000 std=2289.283752
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-43257.000000 max=-30794.000000 avg=-38022.870000 std=2217.460431
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-40642.000000 max=-30794.000000 avg=-37369.045000 std=1836.562951
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-42115.000000 max=-30081.000000 avg=-37158.315000 std=1909.202324
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-40086.000000 max=-29913.000000 avg=-36747.050000 std=1707.612365
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-41925.000000 max=-30081.000000 avg=-36540.960000 std=1655.269854
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-39933.000000 max=-29913.000000 avg=-36240.105000 std=1729.159343
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-38890.000000 max=-30081.000000 avg=-36017.890000 std=1539.559852
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-38513.000000 max=-29207.000000 avg=-35519.680000 std=1576.155255
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-39357.000000 max=-29246.000000 avg=-35797.325000 std=1668.239338
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-37953.000000 max=-28815.000000 avg=-34964.755000 std=1669.453927
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-37595.000000 max=-29246.000000 avg=-35396.215000 std=1585.120926
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-37417.000000 max=-28293.000000 avg=-34983.050000 std=1591.166527
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-37705.000000 max=-27978.000000 avg=-34526.410000 std=1685.592140
    schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-37663.000000 max=-27978.000000 avg=-34086.300000 std=1585.385521
    schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-37050.000000 max=-28293.000000 avg=-34562.515000 std=1506.342066
    schedule.go 2018/06/01 10:26:10 pop_id=UIe min=-36376.000000 max=-28293.000000 avg=-34127.960000 std=1417.550041
    schedule.go 2018/06/01 10:26:10 pop_id=IJN min=-36434.000000 max=-27978.000000 avg=-33659.550000 std=1565.961796
    schedule.go 2018/06/01 10:26:10 pop_id=UIe min=-35553.000000 max=-27834.000000 avg=-33776.890000 std=1439.687274
    schedule.go 2018/06/01 10:26:10 pop_id=IJN min=-35779.000000 max=-27978.000000 avg=-33276.435000 std=1571.765547
    

    [snip]

    schedule.go 2018/06/01 10:26:37 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13105.810000 std=569.072591
    schedule.go 2018/06/01 10:26:37 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13208.310000 std=622.588318
    schedule.go 2018/06/01 10:26:37 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13090.395000 std=564.413234
    schedule.go 2018/06/01 10:26:37 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13067.800000 std=570.242484
    schedule.go 2018/06/01 10:26:37 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13205.330000 std=620.816141
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13187.325000 std=620.124810
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13044.520000 std=574.277441
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13041.195000 std=569.691186
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13176.480000 std=618.033826
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13031.840000 std=566.920034
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13164.640000 std=617.818768
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13132.580000 std=628.239830
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13024.580000 std=564.373736
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12997.095000 std=570.329112
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13126.275000 std=624.070653
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12983.905000 std=583.783818
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13120.270000 std=623.693280
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12973.925000 std=579.498947
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13110.700000 std=627.804500
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12954.475000 std=586.226440
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13108.250000 std=626.450770
    schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14752.000000 max=-9746.000000 avg=-13091.415000 std=630.471350
    schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12931.535000 std=578.849565
    

    As you can see, the minimum fitness (with random starting points) started around -42k, and ended around -14k 30 seconds later. Regardless of how I implement the Genome interface, I don't see how this should be possible.

    opened by gwd 6
  • More generation statistics?

    More generation statistics?

    Hey --

    First of all, thanks so much for such awesome documentation. I've been doing GA stuff for a while, and seeing the "a lot of intellectual fog around the concept of genetic algorithms" quote made me happy.

    Anyway, can't wait to use this.

    One thing that I miss about using GENESIS system by Grefenstette was that it kept track of the number of gene-bits that were "lost" and those that were "converged". The lost bits were bits that were (in a specific point on the genome) all 1 or all 0. The converged ones were mostly the same (maybe 70%?).

    It was a very useful metric to let you know when the system had, effectively, hit a local minima.

    opened by csterritt 6
  • Allow parallel initialization of individuals

    Allow parallel initialization of individuals

    This PR adds the feature to run the individuals initialization in parallel, which can boost the performance of use cases that require heavy initialization methods.

    It is implemented by adding the GAConfig.ParallelInit, which is false by default in a similar manner it is already done by GAConfig.ParallelEval.

    opened by qmuntal 5
  • [tanghaibao] Add support for CrossRate in models

    [tanghaibao] Add support for CrossRate in models

    @MaxHalford Thanks for the awesome package - I'm adding support to specify crossover rate. Naturally, the MutRate controls how fast one explore new solutions; CrossRate controls how much mixing amongst good solutions.

    The old behavior was essentially CrossRate = 1, which, for most applications is too much. One could see this pathological behavior in the example of grid_tsp.go, where it seems to lack the ability to mutate (since crossover is dominating).

    This PR allows one to specify CrossRate inside the model.

    Haibao

    opened by tanghaibao 5
  • minor docs edits

    minor docs edits

    Hi there. I wasn't really looking to be a proofreader, but when I came across the word intellirngtly I decided to make a lil PR. This should be ready to go.

    (Addendum:) As I'm exploring the code base / trying to understand how things work, I'm finding more minor things to add. 🙂

    opened by emgrasmeder 5
  • Multiple Objectives

    Multiple Objectives

    Dear all,

    from a scan of the (very nicely done) documentation, am I right, that eaopt currently does not support multiple objectives for optimization in evolutionary algorithms (incl. getting the pareto-optimal solutions)?

    This might also be a point being clarified in the abstract, assisting the choose-a-library process :)

    Best, Lukas

    opened by merklel 0
  • Most models do not honor ParallelEval

    Most models do not honor ParallelEval

    Problem

    Most of the models defined in models.go evaluate the fitness function sequentially, even if ParallelEval is set to true. From what I can tell from inspecting the source code, this applies to ModDownToSize, ModRing, and ModMutationOnly. This poses a problem because SPSO, DiffEvo, and OES all hard-wire ModMutationOnly as their model.

    Reproducer

    Here's a reproducer:

    pareval.zip

    Run first with the ModRing stanza commented out then with the ModGenerational stanza commented out and observe the performance difference. Here's what I measured:

    ModGenerational

    $ time ./pareval 
    Best fitness at generation 0: -0.348941
    Best fitness at generation 1: -0.757410
    Best fitness at generation 2: -0.960569
    Best fitness at generation 3: -0.960569
    Best fitness at generation 4: -0.968049
    Best fitness at generation 5: -0.968049
    Best fitness at generation 6: -0.968049
    Best fitness at generation 7: -0.968049
    Best fitness at generation 8: -0.968049
    Best fitness at generation 9: -0.983219
    Best fitness at generation 10: -0.999640
    
    real	0m42.007s
    user	0m0.014s
    sys	0m0.000s
    

    ModRing

    $ time ./pareval 
    Best fitness at generation 0: -0.522594
    Best fitness at generation 1: -0.928452
    Best fitness at generation 2: -0.928452
    Best fitness at generation 3: -0.928452
    Best fitness at generation 4: -0.935102
    Best fitness at generation 5: -0.935497
    Best fitness at generation 6: -0.996757
    Best fitness at generation 7: -0.996757
    Best fitness at generation 8: -0.996757
    Best fitness at generation 9: -0.996757
    Best fitness at generation 10: -0.998831
    
    real	7m32.042s
    user	0m0.050s
    sys	0m0.033s
    

    Resolution

    Unfortunately, this may be a difficult problem to fix. As far as I can tell, a Model has no access to a GAConfig and therefore can't determine if ParallelEval is set to true or false. If nothing else, others can reference this issue if, like I, they find that SPSO, DiffEvo, and OES run substantially slower than GA when given a computationally intense fitness function.

    opened by spakin 0
  • Crossover method not modifying genome

    Crossover method not modifying genome

    Hello @MaxHalford ,

    Thanks for making a cool open source project! It's been interesting to learn about genetic algorithms by working with it. I'm also new to golang, so I may be missing something, but I'm having issues getting my Crossover function to work. When I set a pointer receiver (indicated here as the way to modify variables https://tour.golang.org/methods/4 ), I get a build error like below:

    func (r *Route) Crossover(s eaopt.Genome, rng *rand.Rand) {

    cannot use nearestNeighborRoute (type Route) as type eaopt.Genome in return argument:
    	Route does not implement eaopt.Genome (Crossover method has pointer receiver)
    

    .. When I change this to not being a pointer, it builds and executes func (r Route) Crossover(s eaopt.Genome, rng *rand.Rand) {

    at the end of the Crossover method, I'm assigning the new offspring to the r variable, but when I step thru the code from individual.go, the genome is unchanged

    // bottom of my Crossover method:
    r = offspring1
    
    
    // in individual.go, indi.Genome is unchanged, it has the original r value, not the new crossover one.
    func (indi *Individual) Crossover(mate Individual, rng *rand.Rand) {
    	indi.Genome.Crossover(mate.Genome, rng)
    	indi.Evaluated = false
    	mate.Evaluated = false
    }
    

    I saw the note about how slices work better, so I changed my code to use Route instead of RouteState, which is a slice of Deliveries, but still seeing the issue

    old data structure:

    type RouteState struct {
    	Deliveries []*Delivery
    }
    

    new data structure: type Route []*Delivery

    opened by ableeda 2
  • CrossCX and CrossERX relies on hashable types

    CrossCX and CrossERX relies on hashable types

    I have a genome which isn't hashable. When I run my application, it panics:

    panic: runtime error: hash of unhashable type scheduler.ScheduleRequest
    
    goroutine 20 [running]:
    github.com/JensRantil/eaopt.getNeighbours(0x118e300, 0xc0000990a0, 0xc000099140)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/slice.go:70 +0xfd
    github.com/JensRantil/eaopt.CrossERX(0x118e300, 0xc0000990a0, 0x118e300, 0xc0000990c0)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/crossover.go:262 +0x156
    github.com/JensRantil/meeting-scheduler.(*solution).Crossover(0xc000099040, 0x118d280, 0xc000099080, 0xc000076360)
    	/Users/jrantil/src/meeting-scheduler/lib.go:163 +0xa3
    github.com/JensRantil/eaopt.(*Individual).Crossover(...)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/individual.go:82
    github.com/JensRantil/eaopt.generateOffsprings(0x1e, 0xc0000bc000, 0x1e, 0x1e, 0x118c400, 0xc00008a070, 0x3fe6666666666666, 0xc000076360, 0x110b8b9, 0x116362b, ...)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/models.go:32 +0x362
    github.com/JensRantil/eaopt.ModGenerational.Apply(0x118c400, 0xc00008a070, 0x3fe0000000000000, 0x3fe6666666666666, 0xc000088640, 0xf, 0x0)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/models.go:64 +0x8c
    github.com/JensRantil/eaopt.(*GA).evolve.func1(0xc000088640, 0xc00003ef60, 0x10759e6)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/ga.go:102 +0x240
    github.com/JensRantil/eaopt.Populations.Apply.func1(0xc00003ef68, 0xc00003efc0)
    	/Users/jrantil/go/pkg/mod/github.com/!jens!rantil/[email protected]/population.go:56 +0x45
    golang.org/x/sync/errgroup.(*Group).Go.func1(0xc000076f90, 0xc000076fc0)
    	/Users/jrantil/go/pkg/mod/golang.org/x/[email protected]/errgroup/errgroup.go:57 +0x64
    created by golang.org/x/sync/errgroup.(*Group).Go
    	/Users/jrantil/go/pkg/mod/golang.org/x/[email protected]/errgroup/errgroup.go:54 +0x66
    FAIL	github.com/JensRantil/meeting-scheduler	0.227s
    

    and

    panic: runtime error: hash of unhashable type scheduler.ScheduleRequest
    
    goroutine 20 [running]:
    github.com/MaxHalford/eaopt.newIndexLookup(0x118c560, 0xc00009b120, 0x20)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/slice.go:33 +0x84
    github.com/MaxHalford/eaopt.getCycles(0x118c560, 0xc00009b120, 0x118c560, 0xc00009b140, 0x5a0, 0x114c940, 0x1267960)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/slice.go:42 +0x50
    github.com/MaxHalford/eaopt.CrossCX(0x118c560, 0xc00009b120, 0x118c560, 0xc00009b140)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/crossover.go:220 +0xc6
    github.com/JensRantil/meeting-scheduler.(*solution).Crossover(0xc00009b0c0, 0x118b540, 0xc00009b100, 0xc000078360)
    	/Users/jrantil/src/meeting-scheduler/lib.go:163 +0xa3
    github.com/MaxHalford/eaopt.(*Individual).Crossover(...)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/individual.go:82
    github.com/MaxHalford/eaopt.generateOffsprings(0x1e, 0xc0000be000, 0x1e, 0x1e, 0x118a6c0, 0xc00008c070, 0x3fe6666666666666, 0xc000078360, 0x110a809, 0x1161cab, ...)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/models.go:32 +0x362
    github.com/MaxHalford/eaopt.ModGenerational.Apply(0x118a6c0, 0xc00008c070, 0x3fe0000000000000, 0x3fe6666666666666, 0xc00008a640, 0xf, 0x0)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/models.go:64 +0x8c
    github.com/MaxHalford/eaopt.(*GA).evolve.func1(0xc00008a640, 0xc00003ef60, 0x10755b6)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/ga.go:102 +0x240
    github.com/MaxHalford/eaopt.Populations.Apply.func1(0xc00003ef68, 0xc00003efc0)
    	/Users/jrantil/go/pkg/mod/github.com/!max!halford/[email protected]c095/population.go:56 +0x45
    golang.org/x/sync/errgroup.(*Group).Go.func1(0xc000078f90, 0xc000078fc0)
    	/Users/jrantil/go/pkg/mod/golang.org/x/[email protected]/errgroup/errgroup.go:57 +0x64
    created by golang.org/x/sync/errgroup.(*Group).Go
    	/Users/jrantil/go/pkg/mod/golang.org/x/[email protected]/errgroup/errgroup.go:54 +0x66
    FAIL	github.com/JensRantil/meeting-scheduler	0.229s
    

    Assuming that interface{} is hashable is probably a bad idea.

    opened by JensRantil 1
  • Feature/implement genome marshaling

    Feature/implement genome marshaling

    @MaxHalford ~~This is my first pass at adding Population marshaling to the repo. There are some issues with serializing the GA object, namely issues with interfaces (Model, Migrator, etc) that definitely could be solved, but beyond the immediate goal which I think is being able to restart a Minimize run from where a GA's population has left off.~~ See below, the entire GA is now marshaled.

    ~~In this branch, when creating a GA one can add an io.Reader and/or io.Writer. If a Reader is present, then the Populations will be regenerated from the marshaled data. Likewise, if a Writer (and a Context) is present, then GA will attempt to marshal the populations on exit.~~

    JSON encodings are supported. See the Vector implementation in setup_test.go for what's required to marshal concrete objects that implement Genome.

    Have a look, if you're cool with the direction it's going I'll update the documentation and remove the Work in Progress status of this PR.

    opened by matthewmcneely 5
  • NOffsprings has to higher than 0

    NOffsprings has to higher than 0

    The unsigned int mod.NOffsprings can be never negative hence here is a logic bug.

    if mod.NOffsprings <= 0 {
       return errors.New("NOffsprings has to higher than 0")
    }
    

    Could this not just be a int as uint normally used in Go just for binary operations?

    models.go:217

    // Validate ModDownToSize fields.
    func (mod ModDownToSize) Validate() error {
    	// Check the number of offsprings value
    	if mod.NOffsprings <= 0 {
    		return errors.New("NOffsprings has to higher than 0")
    	}
    	// Check the first selection method presence
    	if mod.SelectorA == nil {
    		return errNilSelector
    	}
    	// Check the first selection method parameters
    	var errSelectorA = mod.SelectorA.Validate()
    	if errSelectorA != nil {
    		return errSelectorA
    	}
    	// Check the second selection method presence
    	if mod.SelectorB == nil {
    		return errNilSelector
    	}
    	// Check the second selection method parameters
    	var errSelectorB = mod.SelectorB.Validate()
    	if errSelectorB != nil {
    		return errSelectorB
    	}
    	// Check the mutation rate in the presence of a mutator
    	if mod.MutRate < 0 || mod.MutRate > 1 {
    		return errInvalidMutRate
    	}
    	return nil
    }
    
    opened by tegk 3
Releases(0.4.1)
  • 0.4.1(Nov 28, 2017)

    • Population.rng has been promoted to Population.RNG. This makes it easier to implement custom models in another package than gago
    • Renamed Enhance to Evolve for esthetics
    • Refactored parallel code for reusability
    Source code(tar.gz)
    Source code(zip)
  • 0.4.0(Nov 17, 2017)

    The Genome's Crossover method now has to be done in-place. Although this breaks the API it is well worth as it makes it more consistent and requires less boilerplate code for deep copying.

    Source code(tar.gz)
    Source code(zip)
  • 0.3.1(Nov 14, 2017)

  • 0.3.0(Nov 11, 2017)

  • 0.2.3(Nov 10, 2017)

  • 0.2.2(Nov 10, 2017)

  • 0.2.1(Sep 18, 2017)

  • 0.2.0(Sep 16, 2017)

    • Added GA.Initialized() to indicate if a GA has been initialized or not.
    • Back to 100% test coverage
    • Tidied naming
    • Added String() functions to Individual and Individuals
    • Added sub-tests to table-driven tests
    Source code(tar.gz)
    Source code(zip)
  • 0.1.0(Jul 28, 2017)

Owner
Max Halford
Data wizard @alan-eu. PhD in machine learning applied to query optimization. Kaggle competitions Master. Online machine learning nut.
Max Halford
Export the private key from a Swarm json key file

exportSwarmKey Currently it is a pain in the A** to export bee key in to metamask as they are not compatible. This programe will export the private ke

Zahoor Mohamed 39 Mar 4, 2022
SampleD - scalable sample collection, routing, and schema evolution

SampleD Realtime event analytics capture and processor Emit samples from your application code (libraries provided) Configure fluentbit to capture sam

Simon Mirco 2 Mar 4, 2022
Go-enum-algorithm - Implement an enumeration algorithm in GO

go-enum-algorithm implement an enumeration algorithm in GO run the code go run m

Leon 1 Feb 15, 2022
Geth client which picks the most profitable blocks to mine using a greedy algorithm

Greeden-Geth Greeden-Geth is a protocol-agnostic client which uses a greedy algorithm to pick the most profitable blocks to submit to the network out

Nathan 71 May 30, 2022
Go implementation of Donald Knuth's Algorithm 7.2.2.1C for exact cover with colors.

go-dlx Go implementation of Donald Knuth's Algorithm 7.2.2.1C for exact cover with colors. This code is based on the Algorithm C described in http://w

Soojin Nam 2 Dec 4, 2021
Simple distributed kv-store using ABD algorithm.

Distributed-kv-store Simple distributed kv-store using ABD algorithm. API GET /key Get value by key. 302 = found key. PUT /key Put key with value. 201

null 0 Dec 14, 2021
Snowflake algorithm generation worker Id sequence

sequence snowflake algorithm generation worker Id sequence 使用雪花算法生成ID,生成100万个只需要

null 1 Jan 21, 2022
An implementation of the consensus algorithm Map Reduce.

An implementation of the consensus algorithm Map Reduce. Framework written by Professor Matthew. Implemented by Makara Teu.

Makara Teu 1 May 3, 2022
Go-opera-test - EVM-compatible chain secured by the Lachesis consensus algorithm

Opera EVM-compatible chain secured by the Lachesis consensus algorithm. Building

Tenderly 0 Feb 14, 2022
Implementation of the Feynman algorithm to solve any problem!

Feynman Algorithm Allegedly coined in jest by Murray Gell-Mann to describe Richard Feynman's incredible problem solving ability, this simple algorithm

Jack 1 Mar 16, 2022
Library to work with MimeHeaders and another mime types. Library support wildcards and parameters.

Mime header Motivation This library created to help people to parse media type data, like headers, and store and match it. The main features of the li

Anton Ohorodnyk 27 May 1, 2022
cross-platform, normalized battery information library

battery Cross-platform, normalized battery information library. Gives access to a system independent, typed battery state, capacity, charge and voltag

null 204 Jun 6, 2022
GoLang Library for Browser Capabilities Project

Browser Capabilities GoLang Project PHP has get_browser() function which tells what the user's browser is capable of. You can check original documenta

Maksim N. 40 Jun 13, 2022
Go bindings for unarr (decompression library for RAR, TAR, ZIP and 7z archives)

go-unarr Golang bindings for the unarr library from sumatrapdf. unarr is a decompression library and CLI for RAR, TAR, ZIP and 7z archives. GoDoc See

Milan Nikolic 186 Jun 22, 2022
Type-safe Prometheus metrics builder library for golang

gotoprom A Prometheus metrics builder gotoprom offers an easy to use declarative API with type-safe labels for building and using Prometheus metrics.

Cabify 93 Jun 9, 2022
An easy to use, extensible health check library for Go applications.

Try browsing the code on Sourcegraph! Go Health Check An easy to use, extensible health check library for Go applications. Table of Contents Example M

Claudemiro 431 May 31, 2022
An simple, easily extensible and concurrent health-check library for Go services

Healthcheck A simple and extensible RESTful Healthcheck API implementation for Go services. Health provides an http.Handlefunc for use as a healthchec

Ether Labs 221 May 24, 2022
Simple licensing library for golang.

license-key A simple licensing library in Golang, that generates license files containing arbitrary data. Note that this implementation is quite basic

Hyperboloide 247 Jun 19, 2022
Library for interacting with LLVM IR in pure Go.

llvm Library for interacting with LLVM IR in pure Go. Introduction Introductory blog post "LLVM IR and Go" Our Document Installation go get -u github.

null 912 Jun 18, 2022