goga

package module
v0.0.0-...-f4ca47f Latest Latest
Warning

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

 Go to latest Published: Apr 13, 2022 License: GPL-3.0 Imports: 3 Imported by: 3

README

goga Build Status Coverage Status Go Report Card

Golang implementation of a genetic algorithm. See ./examples for info on how to use the library.

Overview

Goga is a genetic algorithm solution written in Golang. It is used and configured by injecting different behaviours into the main genetic algorithm object. The main injectable components are the simulator, selector and mater.

The simulator provides a function that accepts a single genome and assigns a fitness score to it. The higher the fitness, the better the genome has done in the simulation. A genome can be simulated by however the application sees fit as long as it can be encoded into a bitset of 0s and 1s. A simulator also provides a function to tell the algorithm when to stop.

The selector object takes a popualtion of genomes and the total fitness and returns a genome from the population that it has chosen. A common implementation is roulette in which a random value between 0..totalFitness is generated and the genomes are cycled through subtracting their fitness away from this random number. Then this number goes below 0 then a genome has been 'selected'. The idea is that a genome with a higher fitness will be more likely to be chosen.

A mater accepts two genomes from the selector and combines them to produce two others. There are some common predefined mating algorithms but the user is also free to define their own.

As genomes that have a fitness are more likely to mate, the program will slowly work its way towards what it thinks is an optimal solution.

Examples

This section will talk through any example programs using this library.

examples/string_matcher.go

To run:

cd examples
go run string_matcher.go

The string matcher is a program that can be configured with any string and the goga library will attempt to generate a bitset that decodes to this string. Each character is representated by 8 bits in each genome.

There are some configuration constants just above the main function, use this to configure the string you'd like the algorithm to match to.

const (
	kTargetString = "abcdefghijklmnopqrstuvwxyz"
	// ...
)

The elite consumer is called after each simulation with the best genome of that iteration. It prints it out along with the iteration number and the fitness for that particular genome. A typical output might look something like this:

1 	 Øoâ|-7rPKw
                   D( 	 71
2 	 Xnæ=írVÏw
T3 	 74
3 	 oî,ë.2wës
# 	 81
4 	 XOà|m,WOz
D" 	 84
5 	 XOålo,rWorD# 	 89
6 	 XOìlo.0WozD# 	 91
7 	 Xgflm,pWorND# 	 93
8 	 Xgllo,0WorD# 	 96
9 	 Xgllo.0WorNd# 	 97
10 	 Xello.0WorNd# 	 98
11 	 Hello,0WorNd# 	 100
12 	 Hello,0WorNd# 	 100
13 	 Hello, WorNd# 	 101
14 	 Hello, Wornd! 	 103
15 	 Hello, Wornd! 	 103
16 	 Hello, World! 	 104
151.88245ms

You can see the string slowly becoming more like the input string as there are more iterations.

examples/image_matcher.go

To run:

cd examples
go run image_matcher.go <path_to_image>

Image matcher takes an input image and attempts to produce an output image that is as close to it as possible only using RGBA coloured rectangles and circles. There are a few parameters at the top of the file that are interesting to fiddle with:

numShapes = 100
populationSize = 1000
maxIterations = 9999999
bitsPerCoordinateNumber = 9
parallelSimulations = 24
maxCircleRadiusFactor = 3
  • numShapes - the number of shapes that are used when the algorithm re-creates the input image
  • populationSize - the number of genomes in each population. Each genome can be decoded into a picture. A high value will mean each iteration takes longer, and usually results in the algorithm finding its optimal solution in less iterations.
  • maxIterations - the maximum number of simulations/iterations to run. Providing a huge number will essentially run until the algorithm has figured out what it thinks is an optimal solution.
  • bitsPerCoordinateNumber - Each shape is positioned using coordinates. A rect is represented by the top left and bottom right coordinates, and a circle by its centre. A coordinate is made up of two numbers, each number is represented by this many bits. The number generated is used to calculate a percentage of the overall width/height of the image for the coordinate to be positioned at. For example, if bitsPerCoordinateNumber is 8, that means the maximum value a coordinte can be is 0b11111111, or 255. To calculate the coordinates number relative to the image's width and height we normalise this and apply the decimal to the pictures dimensions. For example, if our X coordinate produced by the algorithm is 233, and our images width is 120. ( 233 / 255 ) * 120 == 109 == our X coordinate. Setting this to a high value means the algorithm has more accuracy when placing shapes. A low value of 2 or 3 also creates some interesting effects.
  • parallelSimulations - The number of simulations to run in parallel. A higher value usually means each iteration takes less time, up to a certain point.
  • maxCircleRadiusFactor - A number to divide a circles radius by. 1 will mean a circles radius can be anywhere between 1 and max( inputImageWidth, inputImageHeight ). From experimenting, restricting the radius a little creates 'better' images quicker

The script outputs the 'best' genome from each iteration to "elite.png" as well as the original overlayed in "elite_with_original.png".

Here's an example of what can be generated. Input, output and both overlayed over the top of each other:

input output overlayed

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Mutate 

func Mutate(g1, g2 Genome) (Genome, Genome)

Mutate - Accepts 2 genomes and mutates a single bit in the first to create a new very slightly different genome i.e. input genomes of: 000000 and 111111 could produce output genomes of: 001000 and 111111

func OnePointCrossover 

func OnePointCrossover(g1, g2 Genome) (Genome, Genome)

OnePointCrossover - Accepts 2 genomes and combines them to create 2 new genomes using one point crossover i.e. input genomes of: 000000 and 111111 could produce output genomes of: 000111 and 111000

func TwoPointCrossover 

func TwoPointCrossover(g1, g2 Genome) (Genome, Genome)

TwoPointCrossover - Accepts 2 genomes and combines them to create 2 new genomes using two point crossover i.e. input genomes of: 000000 and 111111 could produce output genomes of: 001100 and 110011

func UniformCrossover 

func UniformCrossover(g1, g2 Genome) (Genome, Genome)

UniformCrossover - Accepts 2 genomes and combines them to create 2 new genomes using uniform crossover i.e. input genomes of: 000000 and 111111 could produce output genomes of: 101010 and 010101

Types

type Bitset 

type Bitset struct {
	// contains filtered or unexported fields
}

Bitset - a simple bitset implementation

func (*Bitset) Create 

func (b *Bitset) Create(size int)

Create - creates a bitset of length 'size'

func (*Bitset) CreateCopy 

func (b *Bitset) CreateCopy() Bitset

CreateCopy returns a bit for bit copy of the bitset

func (*Bitset) Get 

func (b *Bitset) Get(index int) int

Get returns the value in the bitset at index 'index' or -1 if the index is out of range

func (*Bitset) GetAll 

func (b *Bitset) GetAll() []int

GetAll returns an int array of all the bits in the bitset

func (*Bitset) GetSize 

func (b *Bitset) GetSize() int

GetSize returns the size of the bitset

func (*Bitset) Set 

func (b *Bitset) Set(index, value int) bool

Set assigns value 'value' to the bit at index 'index'

func (*Bitset) SetAll 

func (b *Bitset) SetAll(value int)

SetAll assigns the value 'value' to all the bits in the set

func (*Bitset) Slice 

func (b *Bitset) Slice(startingBit, size int) Bitset

Slice returns an out of memory slice of the current bitset between bits 'startingBit' and 'startingBit + size'

type BitsetCreate 

type BitsetCreate interface {
	Go() Bitset
}

BitsetCreate - an interface to a bitset create struct

type BitsetParse 

type BitsetParse interface {
	SetFormat([]int)
	Process(*Bitset) []uint64
}

BitsetParse - an interface to an object that is able to parse a bitset into an array of uint64s

func CreateBitsetParse 

func CreateBitsetParse() BitsetParse

CreateBitsetParse returns an instance of a bitset parser

type EliteConsumer 

type EliteConsumer interface {
	OnElite(Genome)
}

EliteConsumer - an interface to the elite consumer

type GeneticAlgorithm 

type GeneticAlgorithm struct {
	Mater         Mater
	EliteConsumer EliteConsumer
	Simulator     Simulator
	Selector      Selector
	BitsetCreate  BitsetCreate
	// contains filtered or unexported fields
}

GeneticAlgorithm - The main component of goga, holds onto the state of the algorithm - * Mater - combining evolved genomes * EliteConsumer - an optional class that accepts the 'elite' of each population generation * Simulator - a simulation component used to score each genome in each generation * BitsetCreate - used to create the initial population of genomes

func NewGeneticAlgorithm 

func NewGeneticAlgorithm() GeneticAlgorithm

NewGeneticAlgorithm returns a new GeneticAlgorithm structure with null implementations of EliteConsumer, Mater, Simulator, Selector and BitsetCreate

func (*GeneticAlgorithm) GetPopulation 

func (ga *GeneticAlgorithm) GetPopulation() []Genome

GetPopulation returns the population

func (*GeneticAlgorithm) Init 

func (ga *GeneticAlgorithm) Init(populationSize, parallelSimulations int)

Init initialises internal components, sets up the population size and number of parallel simulations

func (*GeneticAlgorithm) Simulate 

func (ga *GeneticAlgorithm) Simulate() bool

Simulate runs the genetic algorithm

func (*GeneticAlgorithm) SimulateUntil 

func (ga *GeneticAlgorithm) SimulateUntil(exitFunc func(Genome) bool) bool

SimulateUntil simulates a population until 'exitFunc' returns true The 'exitFunc' is passed the elite of each population and should return true if the elite reaches a certain criteria (e.g. fitness above a certain threshold)

type Genome 

type Genome interface {
	GetFitness() int
	SetFitness(int)
	GetBits() *Bitset
}

IGenome associates a fitness with a bitset

func NewGenome 

func NewGenome(bitset Bitset) Genome

NewGenome creates a genome with a bitset and a zero'd fitness score

func Roulette 

func Roulette(genomeArray []Genome, totalFitness int) Genome

Roulette is a selection function that selects a genome where genomes that have a higher fitness are more likely to be picked

type Mater 

type Mater interface {
	Go(Genome, Genome) (Genome, Genome)
	OnElite(Genome)
}

Mater - an interface to a mater object

func NewMater 

func NewMater(materConfig []MaterFunctionProbability) Mater

NewMater returns an instance of an IMater with several MaterFuncProbabilities

type MaterFunctionProbability 

type MaterFunctionProbability struct {
	P        float32
	F        func(Genome, Genome) (Genome, Genome)
	UseElite bool
}

MaterFunctionProbability - An implementation of IMater that has a function and a probability where mater function 'F' is called with a probability of 'P' where 'P' is a value between 0 and 1 0 = never called, 1 = called for every genome

type NullBitsetCreate 

type NullBitsetCreate struct {
}

NullBitsetCreate - a null implementation of the IBitsetCreate interface

func (*NullBitsetCreate) Go 

func (ngc *NullBitsetCreate) Go() Bitset

Go returns a bitset with no content

type NullEliteConsumer 

type NullEliteConsumer struct {
}

NullEliteConsumer - a null implementation of the elite consumer

func (*NullEliteConsumer) OnElite 

func (nec *NullEliteConsumer) OnElite(Genome)

OnElite - null implementation on OnElite from the EliteConsumer interface

type NullMater 

type NullMater struct {
}

NullMater - null implementation of the IMater interface

func (*NullMater) Go 

func (nm *NullMater) Go(a, b Genome) (Genome, Genome)

Go - null implementation of the IMater go func

func (*NullMater) OnElite 

func (nm *NullMater) OnElite(a Genome)

OnElite - null implementation of the IMater OnElite func

type NullSelector 

type NullSelector struct {
}

NullSelector - a null implementation of the Selector interface

func (*NullSelector) Go 

func (ns *NullSelector) Go(genomes []Genome, totalFitness int) Genome

Go - a null implementation of Selector's 'go'

type NullSimulator 

type NullSimulator struct {
}

NullSimulator - a null implementation of the Simulator interface

func (*NullSimulator) ExitFunc 

func (ns *NullSimulator) ExitFunc(Genome) bool

ExitFunc - a null implementation of Simulator's 'ExitFunc'

func (*NullSimulator) OnBeginSimulation 

func (ns *NullSimulator) OnBeginSimulation()

OnBeginSimulation - a null implementation of Simulator's 'OnBeginSimulation'

func (*NullSimulator) OnEndSimulation 

func (ns *NullSimulator) OnEndSimulation()

OnEndSimulation - a null implementation of Simulator's 'OnEndSimulation'

func (*NullSimulator) Simulate 

func (ns *NullSimulator) Simulate(Genome)

Simulate - a null implementation of Simulator's 'Simulate'

type Selector 

type Selector interface {
	Go([]Genome, int) Genome
}

Selector - a selector interface used to pick 2 genomes to mate

func NewSelector 

func NewSelector(selectorConfig []SelectorFunctionProbability) Selector

NewSelector returns an instance of an ISelector with several SelectorFunctionProbabiities

type SelectorFunctionProbability 

type SelectorFunctionProbability struct {
	P float32
	F func([]Genome, int) Genome
}

SelectorFunctionProbability - Contains a selector function and a probability where selector function 'F' is called with probability 'P' where 'P' is a value between 0 and 1 0 = never called, 1 = called every time we need a new genome to mate

type Simulator 

type Simulator interface {
	OnBeginSimulation()
	Simulate(Genome)
	OnEndSimulation()
	ExitFunc(Genome) bool
}

Simulator - a Simulator interface

Source Files

View all Source files

Directories

Path Synopsis
examples
image_matcher
string_matcher

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.