README
¶
Package genetic
Package genetic implements genetic algorithms using Golang's Generics support.
What are Genetic Algorithms?
Genetic algorithms are a form of machine learning software inspired by the process of natural selection. GA's can quickly approximate solutions for problems with very large search spaces. They are often used to tackle NP problems whose solutions can vary in levels of quality. In these kinds of problems, measuring a solution's validity and quality are fast, but yet there is no easy way to determine the optimal solution without guessing and checking. Genetic Algorithms provide a means to get a pretty good solution to any such problem. Examples include:
- Transportation routing & logistics
- Storage Optimization (Knapsack Problem)
- 'Travelling Salesman' problems
- Machine Learning meta-parameter tuning
- Hardware and Engineering Design optimization
- Scheduling
GAs work by iteratively evolving a finite pool of possible solutions to your problem. With each iteration, the best solutions are mixed and matched with one another to produce novel solutions, and then mutated to introduce variety. This process repeats until some termination condition is reached, at which point the algorithm terminates and returns the best found solution.
Word Thingies
Terminology that's important to know before using Genetic Algorithms:
- Genome: One possible evolutionary candidate. AKA "Solution".
- Population: A pool of genomes.
- Fitness: A scoring metric which objectively ranks the quality of any genome.
- Crossover: The process of combining information from parent genomes to produce novel child genomes.
- Mutations: Random variations in genome structure or content occurring during crossover.
- Selection: The process of picking which genomes will crossover to produce the next generation of genomes.
- Elitism: Preferential treatment to the highest-scoring genomes, allowing them to survive into the next generation. This prevents regression and loss of quality solutions.
- Allele: A candidate gene for a specific location on the Genome. If two genes are alleles of each other, they are evolutionary competitors.
Usage
Find a full example in example_test.go.
Let's say we want to guess a 33-character string, "how did you ever guess my secret!". Our goal is to evolve a population of random strings into the target string.
Thanks to Generics, genetic can be unopinionated about the data type you use to represent your genomes. Instead, you define several functions acting on those genomes, which in concert will define the evolutionary behavior of a population. In our example, we will store our genomes as byte slices.
We need a GenesisFunc[T] which initializes and returns random genomes of type T, where in our case T is []byte.
func genesis() []byte {
genome := make([]byte, 33)
rand.Read(genome)
return genome
}
We need a FitnessFunc[T] which scores every genome on how many of its bytes match the target string. We'll use a minimum fitness of 1, which means our maximum fitness is 34.
func fitnessFn(guesses [][]byte, fitnesses []int) {
for i, guess := range guesses {
fitnesses[i] = 1
for j, b := range guess {
if b == bytesToGuess[j] {
fitnesses[i]++
}
}
}
}
Since this is a static fitness function (its output is not dependent on the other genomes in the population), we can optimize this slightly with the StaticFitnessFunc utility.
fitnessFn := genetic.StaticFitnessFunc(func(guess []byte) int {
fitness := 1
for j, b := range guess {
if b == bytesToGuess[j] {
fitness++
}
}
return fitness
})
We need a CrossoverFunc[T] which combines two genomes together to produce offspring. genetic provides several simple crossover functions which work on any generic slice type genome. Let's use UniformCrossover, which produces offspring whose genomes are a random mix of their parents' genomes.
crossover := genetic.UniformCrossover[[]byte]
We need a SelectionFunc[T] which will pair genomes off into mating pairs, usually based on their fitnesses. A good selection function should give higher-fitness genomes more opportunities to mate than lower-fitness genomes, but should also ensure that the elite (highest-fitness) genomes do not completely dominate all mating pairs, as genetic homogeneity can lead to evolutionary stagnation.
genetic also provides a couple of classic selection functions which work with any genome type. Let's use TournamentSelection, with a tournament size of 3 - randomly selected genomes will be repeatedly subjected to 'tournaments' where the highest-fitness entrants will become mating candidates.
selection := genetic.TournamentSelection[[]byte](3)
Finally, we need a MutationFunc[T] which should randomly (usually with some small probability) mutate the genomes of each new generation. This injects some diversity, helping to explore more optimal solutions.
func mutate(guess []byte) {
r := make([]byte, len(guess))
rand.Read(r)
for i := range guess {
if rand.Float64() < 0.05 { // 5% mutation rate
guess[i] ^= r[i]
}
}
}
Now we can construct a Population[[]byte] instance:
population := genetic.NewPopulation(
100, // population size
genesis,
crossover,
fitness,
selection,
mutation,
)
This population now contains 100 randomized 33-byte strings. Let's try to evolve them into our target string based solely on how many bytes they guessed correctly.
population.Evolve(
34, // minimum fitness. Evolution terminates upon finding a solution with this fitness or higher.
2000, // max generations. Evolution terminates after iterating through this many generations.
2, // elitism. Carries over this many of the highest-fitness genomes from each previous generation into the next.
)
We can now pull out our best candidate to see how we did.
bestSolution, bestFitness := population.Best()
fmt.Printf("evolved string: %q\n", bestSolution)
fmt.Println("best fitness:", bestFitness)
If we did everything right, we should see our population evolved into our target string and reached maximum fitness 34:
evolved string: "how did you ever guess my secret!"
best fitness: 34
Documentation
¶
Overview ¶
Package genetic provides genetic algorithms to approximate solutions for problems with very large search spaces.
Index ¶
- Constants
- func AsexualCrossover[T any](male, female T) (T, T)
- func RouletteSelection[T any](genomes []T, fitnesses []int) [][2]T
- func SinglePointCrossover[T ~[]E, E any](male, female T) (T, T)
- func UniformCrossover[T ~[]E, E any](male, female T) (T, T)
- type CrossoverFunc
- type FitnessFunc
- type GenesisFunc
- type MutationFunc
- type Population
- type SelectionFunc
Examples ¶
Constants ¶
const PopulationSizeMinimum = 2
PopulationSizeMinimum is the minimum size of a Population.
Variables ¶
This section is empty.
Functions ¶
func AsexualCrossover ¶
func AsexualCrossover[T any](male, female T) (T, T)
AsexualCrossover does not cross over the given genomes - it simply returns them back to the caller, without cloning them.
func RouletteSelection ¶
RouletteSelection spins a virtual roulette wheel to pick mating pairs. Higher fitness genomes get proportionally larger sections of the roulette wheel. Genomes cannot mate with themselves.
func SinglePointCrossover ¶
func SinglePointCrossover[T ~[]E, E any](male, female T) (T, T)
SinglePointCrossover crosses over two segments of equal-length DNA by choosing a random break point in the range of their lengths. It creates two offspring DNA sequences by swapping and splicing together the four resulting subslices of DNA.
SinglePointCrossover is analagous to NPointCrossover(1).
func UniformCrossover ¶
func UniformCrossover[T ~[]E, E any](male, female T) (T, T)
UniformCrossover assembles two child genomes from two parents by randomly picking individual genome elements from parents. Randomization is exclusive: if one child genome inherits one allele from its male parent, the sister genome is guaranteed to inherit the opposite allele from the female parent.
Types ¶
type CrossoverFunc ¶
type CrossoverFunc[T any] func(male, female T) (T, T)
CrossoverFunc recombines two genomes to produce two offspring. Crossover functions should NOT handle mutation.
func NPointCrossover ¶
func NPointCrossover[T ~[]E, E any](pointCount int) CrossoverFunc[T]
NPointCrossover crosses two genomes by choosing pointCount random break points in the domain of their lengths. It creates two offspring DNA sequences by swapping and splicing together the resulting pointCount + 1 subslices of DNA, alternating between male & female parents.
type FitnessFunc ¶
FitnessFunc calculates the fitnesses of all genomes in a population, storing the results in the given fitnesses slice.
Some entries in fitnesses may be prepopulated - these are cached fitnesses for elite genomes surviving from the previous generation. A FitnessFunc may recalculate or skip them as needed.
func StaticFitnessFunc ¶ added in v1.1.0
func StaticFitnessFunc[T any](fitness func(T) int) FitnessFunc[T]
StaticFitnessFunc is a utility which maps a static non-competitive fitness function, whose output is not dependent on other competing genomes, into a FitnessFunc[T]. Use this if your genomes' fitnesses are measured independently of the wider population.
type GenesisFunc ¶
type GenesisFunc[T any] func() T
GenesisFunc is a function which initializes a randomized possible value for T.
type MutationFunc ¶
type MutationFunc[T any] func(T)
MutationFunc randomly alters the DNA of the given genome, in the hopes that some mutatations will result in fitter genomes.
func RandomizedBinaryMutation ¶
func RandomizedBinaryMutation(mutationRate float64) MutationFunc[[]bool]
RandomizedBinaryMutation returns a MutationFunc which acts on binary genomes (slices of booleans). It randomly flips binary genes in the target genome at the given mutationRate, which should be between 0.0 (no mutation) and 1.0 (every gene is flipped).
type Population ¶
type Population[T any] struct { // Crossover is used to recombine two genomes of type T. Crossover CrossoverFunc[T] // Fitness computes the fitnesses of a population of genomes of type T. Fitness FitnessFunc[T] // Selection selects which genomes will reproduce, and which genomes they will mate with. Selection SelectionFunc[T] // Mutation randomly mutates a genome. Mutation MutationFunc[T] // contains filtered or unexported fields }
Population is a struct representing a population of individuals (genomes of type T) which can be evolved using genetic algorithms.
Example ¶
package main
import (
"fmt"
"math/rand"
"time"
"github.com/kklash/genetic"
)
func main() {
rand.Seed(time.Now().Unix())
// We'll try to guess this string using a genetic algorithm.
bytesToGuess := []byte("how did you ever guess my secret!")
population := genetic.NewPopulation(
// population size
100,
// GenesisFunc[[]byte] - generates random solutions to initialize the population.
func() []byte {
genome := make([]byte, len(bytesToGuess))
rand.Read(genome)
return genome
},
// CrossoverFunc[[]byte] - combines two parent genomes into two new child genomes.
genetic.UniformCrossover[[]byte],
// FitnessFunc[[]byte] - determines how accurate each guess genome is.
genetic.StaticFitnessFunc(func(guess []byte) int {
fitness := 1
for j, b := range guess {
if b == bytesToGuess[j] {
fitness++
}
}
return fitness
}),
// SelectionFunc[[]byte] - selects which genomes will reproduce.
genetic.TournamentSelection[[]byte](3),
// MutationFunc[[]byte] - randomly alters a given genome to introduce extra variety.
func(guess []byte) {
r := make([]byte, len(guess))
rand.Read(r)
for i := range guess {
if rand.Float64() < 0.05 { // 5% mutation rate
guess[i] ^= r[i]
}
}
},
)
population.Evolve(
len(bytesToGuess)+1, // minimum fitness. Evolution terminates upon finding a solution with this fitness or higher.
2000, // max generations. Evolution terminates after iterating through this many generations.
2, // elitism. Carries over this many of the highest-fitness genomes from each previous generation into the next.
)
bestSolution, bestFitness := population.Best()
fmt.Printf("evolved string: %q\n", bestSolution)
fmt.Println("best fitness:", bestFitness)
}
Output: evolved string: "how did you ever guess my secret!" best fitness: 34
func NewPopulation ¶
func NewPopulation[T any]( size int, generate GenesisFunc[T], crossover CrossoverFunc[T], fitness FitnessFunc[T], selection SelectionFunc[T], mutation MutationFunc[T], ) *Population[T]
NewPopulation initializes a Population of genomes of the given size. The generate function is used to create a genome population of the given size.
func (*Population[T]) Best ¶
func (population *Population[T]) Best() (T, int)
Best returns the current population's fittest genome and fitness.
func (*Population[T]) Diversity ¶
func (population *Population[T]) Diversity() float64
Diversity compares every genome in the population with one another using reflect.DeepEqual to determine whether they are genetic-identicals. It returns a float in range [0.0, 1.0] indicating the percentage of comparisons which were NOT identical.
The total number of DeepEqual comparison calls made will be ((s-1)^2 + (s-1)) / 2, where s is the population size.
func (*Population[T]) Evolve ¶
func (population *Population[T]) Evolve(fitnessThreshold, maxGenerations, elitism int)
Evolve evolves the population until either a genome is produced which meets the given fitnessThreshold, or the maxGenerations threshold is reached.
func (*Population[T]) EvolveOnce ¶
func (population *Population[T]) EvolveOnce(elitism int)
EvolveOnce evolves the population by one generation, replacing the current population with their children. It calls the population's selection function once, its fitness function once, and crossover once for every mating pair needed to repopulate.
type SelectionFunc ¶
SelectionFunc selects pairs of mates from a given population of genomes. A SelectionFunc is passed a slice of genomes and a corresponding slice of their respective pre-computed fitnesses. It should return a slice of mating pairs whose length is such that len(matingPairs)*2 >= len(genomes).
A SelectionFunc should NOT mutate the values passed to it.
func TournamentSelection ¶
func TournamentSelection[T any](poolSize int) SelectionFunc[T]
TournamentSelection returns a SelectionFunc of T which selects mates by randomly creating 'tournaments' between poolSize contestants. The fittest contestants from each random tournament are selected to mate. Genomes cannot mate with themselves.
Source Files