# evoli

package module
Version: v1.3.2 Latest Latest

Go to latest
Published: Mar 15, 2021 License: MIT

### evoli

Genetic Algorithm and Particle Swarm Optimization written in Go

#### Example

##### Problem

Given `f(x,y) = cos(x^2 * y^2) * 1/(x^2 * y^2 + 1)`

Find `(x,y)` such as `f(x,y)` reaches its maximum

Answer `f(0,0) = 1`

##### Particle Swarm Optimization
``````package main

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

"github.com/khezen/evoli"
)

// 3d cosine that gets smaller as you move away from 0,0
func f(x, y float64) float64 {
d := x*x + y*y
return math.Cos(d) * (1 / (d/10 + 1))
}

type FIndividual struct {
v       []float64
x       []float64
fitness float64
}

func (i *FIndividual) Equal(other evoli.Individual) bool {
return i == other
}

func (i *FIndividual) Fitness() float64 {
return i.fitness
}

func (i *FIndividual) SetFitness(newFitness float64) {
i.fitness = newFitness
}

type FPositioner struct {
}

func (p *FPositioner) Position(indiv, pBest, gBest evoli.Individual, c1, c2 float64) (evoli.Individual, error) {
fIndiv, ok1 := indiv.(*FIndividual)
fPBest, ok2 := pBest.(*FIndividual)
fGBest, ok3 := gBest.(*FIndividual)
if !ok1 || !ok2 || !ok3 {
return nil, fmt.Errorf("invalid individual type")
}
newIndiv := FIndividual{
v: make([]float64, len(fIndiv.v)),
x: make([]float64, len(fIndiv.v)),
}
w := 0.9
for d := range fIndiv.v {
rp := rand.Float64()
rg := rand.Float64()
newIndiv.v[d] = w*fIndiv.v[d] +
c1*rp*(fPBest.x[d]-fIndiv.x[d]) +
c2*rg*(fGBest.x[d]-fIndiv.x[d])

newIndiv.x[d] = fIndiv.x[d] + newIndiv.v[d]
}
return &newIndiv, nil
}

type FEvaluater struct {
}

func (e *FEvaluater) Evaluate(indiv evoli.Individual) (Fitness float64, err error) {
fIndiv, ok := indiv.(*FIndividual)
if !ok {
return 0, fmt.Errorf("invalid individual type")
}
return f(fIndiv.x[0], fIndiv.x[1]), nil
}

func main() {
pop := evoli.NewPopulation(50)
for i := 0; i < pop.Cap(); i++ {
x := rand.Float64()*20 - 10
y := rand.Float64()*20 - 10
vx := rand.Float64()*20 - 10
vy := rand.Float64()*20 - 10
x: []float64{x, y},
v: []float64{vx, vy},
})
}
positioner := &FPositioner{}
evaluator := &FEvaluater{}

sw := evoli.NewSwarm(pop, positioner, .2, .2, evaluator)

for i := 0; i < 100; i++ {
err := sw.Next()
if err != nil {
panic(err)
}
}

// evaluate the latest population
for _, v := range sw.Population().Slice() {
f, err := evaluator.Evaluate(v)
if err != nil {
panic(err)
}
v.SetFitness(f)
}

fmt.Printf("Max Value: %.2f\n", sw.Alpha().Fitness())
}
``````
``````Max Value: 1.00
``````
##### Gentic Algorithm
``````package main

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

"github.com/khezen/evoli"
)

// 3d cosine that gets smaller as you move away from 0,0
func h(x, y float64) float64 {
d := x*x + y*y
return math.Cos(d) * (1 / (d/10 + 1))
}

type HIndividual struct {
v       []float64
x       []float64
fitness float64
}

func (i *HIndividual) Equal(other evoli.Individual) bool {
return i == other
}

func (i *HIndividual) Fitness() float64 {
return i.fitness
}

func (i *HIndividual) SetFitness(newFitness float64) {
i.fitness = newFitness
}

type HMutater struct {
}

func (m HMutater) Mutate(indiv evoli.Individual) (evoli.Individual, error) {
x := rand.Float64()*20 - 10
y := rand.Float64()*20 - 10
vx := rand.Float64()*20 - 10
vy := rand.Float64()*20 - 10
return &FIndividual{
x: []float64{x, y},
v: []float64{vx, vy},
}, nil
}

type HCrosser struct {
}

func (h HCrosser) Cross(indiv1, indiv2 evoli.Individual) (evoli.Individual, error) {
fIndiv1, _ := indiv1.(*FIndividual)
fIndiv2, _ := indiv2.(*FIndividual)
return &FIndividual{
x: []float64{(fIndiv1.x[0] + fIndiv2.x[0]) / 2, (fIndiv1.x[1] + fIndiv2.x[1]) / 2},
v: []float64{(fIndiv1.v[0] + fIndiv2.v[0]) / 2, (fIndiv1.v[1] + fIndiv2.v[1]) / 2},
}, nil
}

type HEvaluater struct {
}

func (e HEvaluater) Evaluate(indiv evoli.Individual) (Fitness float64, err error) {
fIndiv, ok := indiv.(*FIndividual)
if !ok {
return 0, fmt.Errorf("invalid individual type")
}
return f(fIndiv.x[0], fIndiv.x[1]), nil
}

func main() {
pop := evoli.NewPopulation(50)
for i := 0; i < pop.Cap(); i++ {
x := rand.Float64()*20 - 10
y := rand.Float64()*20 - 10
vx := rand.Float64()*20 - 10
vy := rand.Float64()*20 - 10
x: []float64{x, y},
v: []float64{vx, vy},
})
}
crosser := HCrosser{}
mutater := HMutater{}
evaluator := HEvaluater{}
mutationProbability := .02
selecter := evoli.NewTruncationSelecter()
survivorSize := 30

ga := evoli.NewGenetic(pop, selecter, survivorSize, crosser, mutater, mutationProbability, evaluator)

for i := 0; i < 100; i++ {
err := ga.Next()
if err != nil {
panic(err)
}
}

// evaluate the latest population
for _, v := range ga.Population().Slice() {
f, err := evaluator.Evaluate(v)
if err != nil {
panic(err)
}
v.SetFitness(f)
}

fmt.Printf("Max Value: %.2f\n", ga.Alpha().Fitness())
}
``````
``````Max Value: 1.00
``````

#### Issues

If you have any problems or questions, please ask for help through a GitHub issue.

#### Contributions

Help is always welcome! For example, documentation (like the text you are reading now) can always use improvement. There's always code that can be improved. If you ever see something you think should be fixed, you should own it. If you have no idea what to start on, you can browse the issues labeled with help wanted.

As a potential contributor, your changes and ideas are welcome at any hour of the day or night, weekdays, weekends, and holidays. Please do not ever hesitate to ask a question or send a pull request.

## Documentation ¶

### Constants ¶

This section is empty.

### Variables ¶

View Source
```var (
// ErrSurvivorSize - survivorSize < 1
ErrSurvivorSize = errors.New("ErrSurvivorSize - survivorSize must be >= 1")
// ErrMutationProb - 0<= mutationProbability <= 1
ErrMutationProb = errors.New("ErrMutationProb - mutation probability must be 0 <= mutationProbability <= 1")
)```
View Source
```var (
// ErrCapacity -
ErrCapacity = errors.New("ErrCapacity - capacity must be >= 1")
// ErrIndexOutOfBounds -
ErrIndexOutOfBounds = errors.New("ErrIndexOutOfBounds")
// ErrNotFound -
ErrNotFound = errors.New("ErrNotFound")
)```
View Source
`var ErrArbitration = "ErrArbitration - must provide one or more individuals"`

ErrArbitration - must provide one or more individuals

View Source
```var (
// ErrLearningCoef - c1 & c2 must be > 0
ErrLearningCoef = "ErrLearningCoef - c1 & c2 must be > 0"
)```
View Source
```var (
// ErrPoolEvaluater - all evolutions of a pool must share the same evaluater operator
ErrPoolEvaluater = "ErrPoolEvaluater - all evolution of a pool must share the same evaluater operator"
)```

### Functions ¶

This section is empty.

### Types ¶

#### type Arbitrer ¶

```type Arbitrer interface {
Abritrate(participants ...Individual) (winner Individual, loosers []Individual)
}```

Arbitrer - elect the winner between multiple participants

#### func NewProportionalToFitnessArbitrer ¶

`func NewProportionalToFitnessArbitrer() Arbitrer`

NewProportionalToFitnessArbitrer - based on fitness value

#### func NewProportionalToRankArbitrer ¶

`func NewProportionalToRankArbitrer() Arbitrer`

NewProportionalToRankArbitrer - based on rank

#### func NewRandomArbitrer ¶

`func NewRandomArbitrer() Arbitrer`

NewRandomArbitrer - choose randomly

#### func NewStochasticUniversalSamplingArbitrer ¶ added in v1.3.1

`func NewStochasticUniversalSamplingArbitrer() Arbitrer`

NewStochasticUniversalSamplingArbitrer - based on fitness value

#### func NewTournamentArbitrer ¶

`func NewTournamentArbitrer(p float64) Arbitrer`

NewTournamentArbitrer - High Fitness increase chances to come out vcitorious from a duel

#### func NewTruncationArbitrer ¶

`func NewTruncationArbitrer() Arbitrer`

NewTruncationArbitrer - take the highest fitness

#### type Crosser ¶

```type Crosser interface {
Cross(parent1, parent2 Individual) (child1, child2 Individual, err error)
}```

Crosser produces a new individual from two individuals. This operators provides convergence to a population.

#### type Evaluater ¶

```type Evaluater interface {
Evaluate(Individual) (Fitness float64, err error)
}```

Evaluater calculates individual Fitness

#### type Evolution ¶

```type Evolution interface {
Population() Population
SetPopulation(Population)
Next() error
Evaluater() Evaluater
Alpha() Individual
}```

Evolution - problem solving algorithm exploring the range of solutions

#### func NewGenetic ¶

`func NewGenetic(pop Population, s Selecter, survivorSize int, c Crosser, m Mutater, mutationProbability float64, e Evaluater) Evolution`

NewGenetic - constructor for Genetic Algorithm

Example
```package main

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

"github.com/khezen/evoli"
)

// 3d cosine that gets smaller as you move away from 0,0
func h(x, y float64) float64 {
d := x*x + y*y
return math.Cos(d) * (1 / (d/10 + 1))
}

type HIndividual struct {
v       []float64
x       []float64
fitness float64
}

func (i *HIndividual) Equal(other evoli.Individual) bool {
return i == other
}

func (i *HIndividual) Fitness() float64 {
return i.fitness
}

func (i *HIndividual) SetFitness(newFitness float64) {
i.fitness = newFitness
}

type HMutater struct {
}

func (m HMutater) Mutate(indiv evoli.Individual, p float64) (evoli.Individual, error) {
if rand.Float64() <= p {
x := rand.Float64()*20 - 10
y := rand.Float64()*20 - 10
vx := rand.Float64()*20 - 10
vy := rand.Float64()*20 - 10
return &HIndividual{
x: []float64{x, y},
v: []float64{vx, vy},
}, nil
} else {
return indiv, nil
}

}

type HCrosser struct {
}

func (h HCrosser) Cross(parent1, parent2 evoli.Individual) (child1, child2 evoli.Individual, err error) {
fIndiv1, _ := parent1.(*HIndividual)
fIndiv2, _ := parent2.(*HIndividual)
w := 0.1 + 0.8*rand.Float64()
return &HIndividual{
x: []float64{w*fIndiv1.x[0] + (1-w)*fIndiv2.x[0], w*fIndiv1.x[1] + (1-w)*fIndiv2.x[1]},
v: []float64{w*fIndiv1.v[0] + (1-w)*fIndiv2.v[0], w*fIndiv1.v[1] + (1-w)*fIndiv2.v[1]},
}, &HIndividual{
x: []float64{(1-w)*fIndiv1.x[0] + w*fIndiv2.x[0], (1-w)*fIndiv1.x[1] + w*fIndiv2.x[1]},
v: []float64{(1-w)*fIndiv1.v[0] + w*fIndiv2.v[0], (1-w)*fIndiv1.v[1] + w*fIndiv2.v[1]},
}, nil
}

type HEvaluater struct {
}

func (e HEvaluater) Evaluate(indiv evoli.Individual) (Fitness float64, err error) {
fIndiv, ok := indiv.(*HIndividual)
if !ok {
return 0, fmt.Errorf("invalid individual type")
}
return h(fIndiv.x[0], fIndiv.x[1]), nil
}

func main() {

pop := evoli.NewPopulation(50)
for i := 0; i < pop.Cap(); i++ {
x := rand.Float64()*20 - 10
y := rand.Float64()*20 - 10
vx := rand.Float64()*20 - 10
vy := rand.Float64()*20 - 10
x: []float64{x, y},
v: []float64{vx, vy},
})
}
crosser := HCrosser{}
mutater := HMutater{}
evaluator := HEvaluater{}
mutationProbability := .02
selecter := evoli.NewTruncationSelecter()
survivorSize := 30

ga := evoli.NewGenetic(pop, selecter, survivorSize, crosser, mutater, mutationProbability, evaluator)

for i := 0; i < 100; i++ {
err := ga.Next()
if err != nil {
panic(err)
}
}

// evaluate the latest population
for _, v := range ga.Population().Slice() {
f, err := evaluator.Evaluate(v)
if err != nil {
panic(err)
}
v.SetFitness(f)
}

fmt.Printf("Max Value: %.2f\n", ga.Alpha().Fitness())

}
```
```Output:

Max Value: 1.00
```

#### func NewGeneticSync ¶

`func NewGeneticSync(pop Population, s Selecter, survivorSize int, c Crosser, m Mutater, mutationProbability float64, e Evaluater) Evolution`

NewGeneticSync - constructor for Genetic Algorithm (sync impl)

#### func NewSwarm ¶

`func NewSwarm(pop Population, positioner Positioner, c1, c2 float64, evaluater Evaluater) Evolution`

NewSwarm - constructor for particles swarm optimization algorithm typical value for learning coef is c1 = c2 = 2 the bigger are the coefficients the faster the population converge

Example
```package main

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

"github.com/khezen/evoli"
)

// 3d cosine that gets smaller as you move away from 0,0
func f(x, y float64) float64 {
d := x*x + y*y
return math.Cos(d) * (1 / (d/10 + 1))
}

type FIndividual struct {
v       []float64
x       []float64
fitness float64
}

func (i *FIndividual) Equal(other evoli.Individual) bool {
return i == other
}

func (i *FIndividual) Fitness() float64 {
return i.fitness
}

func (i *FIndividual) SetFitness(newFitness float64) {
i.fitness = newFitness
}

type FPositioner struct {
}

func (p *FPositioner) Position(indiv, pBest, gBest evoli.Individual, c1, c2 float64) (evoli.Individual, error) {
fIndiv, ok1 := indiv.(*FIndividual)
fPBest, ok2 := pBest.(*FIndividual)
fGBest, ok3 := gBest.(*FIndividual)
if !ok1 || !ok2 || !ok3 {
return nil, fmt.Errorf("invalid individual type")
}
newIndiv := FIndividual{
v: make([]float64, len(fIndiv.v)),
x: make([]float64, len(fIndiv.v)),
}
w := 0.9
for d := range fIndiv.v {
rp := rand.Float64()
rg := rand.Float64()
newIndiv.v[d] = w*fIndiv.v[d] +
c1*rp*(fPBest.x[d]-fIndiv.x[d]) +
c2*rg*(fGBest.x[d]-fIndiv.x[d])

newIndiv.x[d] = fIndiv.x[d] + newIndiv.v[d]
}
return &newIndiv, nil
}

type FEvaluater struct {
}

func (e *FEvaluater) Evaluate(indiv evoli.Individual) (Fitness float64, err error) {
fIndiv, ok := indiv.(*FIndividual)
if !ok {
return 0, fmt.Errorf("invalid individual type")
}
return f(fIndiv.x[0], fIndiv.x[1]), nil
}

func main() {

pop := evoli.NewPopulation(50)
for i := 0; i < pop.Cap(); i++ {
x := rand.Float64()*20 - 10
y := rand.Float64()*20 - 10
vx := rand.Float64()*20 - 10
vy := rand.Float64()*20 - 10
x: []float64{x, y},
v: []float64{vx, vy},
})
}
positioner := &FPositioner{}
evaluator := &FEvaluater{}

sw := evoli.NewSwarm(pop, positioner, .2, .2, evaluator)

for i := 0; i < 100; i++ {
err := sw.Next()
if err != nil {
panic(err)
}
}

// evaluate the latest population
for _, v := range sw.Population().Slice() {
f, err := evaluator.Evaluate(v)
if err != nil {
panic(err)
}
v.SetFitness(f)
}

fmt.Printf("Max Value: %.2f\n", sw.Alpha().Fitness())

}
```
```Output:

Max Value: 1.00
```

#### func NewSwarmSync ¶

`func NewSwarmSync(pop Population, positioner Positioner, c1, c2 float64, evaluater Evaluater) Evolution`

NewSwarmSync - constructor for particles swarm optimization algorithm (sync impl) typical value for learning coef is c1 = c2 = 2 the bigger are the coefficients the faster the population converge

#### type Individual ¶

```type Individual interface {
Fitness() float64
SetFitness(float64)
Equal(Individual) bool
}```

Individual refers to a potential solution to the problem we want to solve

#### func NewIndividual ¶

`func NewIndividual(fitness float64) Individual`

NewIndividual is the constructor for individuals

#### func NewIndividualSync ¶

`func NewIndividualSync(fitness float64) Individual`

NewIndividualSync is the constructor for threadsafe individuals

#### type Mutater ¶

```type Mutater interface {
Mutate(indiv Individual, p float64) (Individual, error)
}```

Mutater randomly modify a individual. This operator maintain diversity in a population.

#### type Pool ¶

```type Pool interface {
Delete(Evolution)
Has(Evolution) bool
Alpha() Individual
Individuals() []Individual
Populations() []Population
Evolutions() []Evolution
Shuffle()
Next() error
NextAsync() error
}```

Pool - solve one problem with different algorithms(with different pros/cons) It also make sense to have a pool running multiple instances of the same algorithm asynchronously with smaller populations.

#### func NewPool ¶

`func NewPool(length int) Pool`

NewPool - creates a Pool

#### func NewPoolSync ¶

`func NewPoolSync(length int) Pool`

NewPoolSync creates a sync implementation of Pool

#### type Population ¶

```type Population interface {
sort.Interface
Sort()
Cap() int
SetCap(int)
Get(int) Individual
RemoveAt(int)
Remove(...Individual)
Replace(int, Individual)
Min() Individual
Max() Individual
Has(...Individual) bool
IndexOf(Individual) (int, error)
Each(func(item Individual) bool)
Slice() []Individual
New(cap int) Population
Close()
}```

Population contains the current set of solutions seen as Individual

#### func NewPopulation ¶

`func NewPopulation(capacity int) Population`

NewPopulation is population constructor

#### func NewPopulationSync ¶

`func NewPopulationSync(capacity int) Population`

#### type Positioner ¶

```type Positioner interface {
Position(indiv, pBest, gBest Individual, c1, c2 float64) (Individual, error)
}```

Positioner produces a new individual from its previous version(indiv), its best version since it exists(pBest), the best of the poopulation(gBest) or local neighborhood, and the learning coefficients(c1,c2). typical values are c1=c2=2

#### type Selecter ¶

```type Selecter interface {
}```

Selecter is the selecter operator interface

#### func NewProportionalToFitnessSelecter ¶

`func NewProportionalToFitnessSelecter() Selecter`

NewProportionalToFitnessSelecter is the constructor for selecter based on fitness value

#### func NewProportionalToRankSelecter ¶

`func NewProportionalToRankSelecter() Selecter`

NewProportionalToRankSelecter is the constructor for selecter based on ranking across the population

#### func NewRandomSelecter ¶

`func NewRandomSelecter() Selecter`

NewRandomSelecter is the constructor for random selecter

#### func NewStochasticUniversalSamplingSelecter ¶ added in v1.3.1

`func NewStochasticUniversalSamplingSelecter() Selecter`

NewStochasticUniversalSamplingSelecter is the constructor for selecter based on fitness value

#### func NewTournamentSelecter ¶

`func NewTournamentSelecter(p float64) Selecter`

NewTournamentSelecter is the constructor for tournament selecter. High rank increase chances to be selected

#### func NewTruncationSelecter ¶

`func NewTruncationSelecter() Selecter`

NewTruncationSelecter is the constructor for truncation selecter