evoli

package module
Version: v1.3.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 15, 2021 License: MIT Imports: 4 Imported by: 0

README

evoli

GoDoc Build Status codecov Go Report Card

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
		pop.Add(&FIndividual{
			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
		pop.Add(&FIndividual{
			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.

Code of conduct.

Documentation

Index

Examples

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
		pop.Add(&HIndividual{
			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
		pop.Add(&FIndividual{
			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 {
	Add(Evolution)
	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)
	Add(...Individual)
	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

NewPopulationSync creates a threadsafe 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 {
	Select(pop Population, survivorsSize int) (survivors Population, deads Population, err error)
}

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL