Documentation
¶
Overview ¶
Package genetics implements swappable components designed for a variety of genetics algorithms. They were designed as a learning exercise and are based on the instructions in tutorialspoint.com/genetic_algorithms.
Index ¶
- type Chromosome
- type Crossover
- type CrossoverFlag
- type DavisOrderCrossover
- type Evolver
- type Fitness
- type Gene
- type InversionMutation
- type MultiPointCrossover
- type MutationFlag
- type Mutator
- type NaturalSelection
- type NaturalSelectionFlag
- type RandomResettingMutation
- type RankedSelection
- type ScrambleMutation
- type Species
- type StochasticUniversalSampling
- type SwapMutation
- type TournamentSelection
- type WholeArithmeticRecombination
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Chromosome ¶
Chromosome represents a single genetic strategy for a Species.
func (Chromosome) String ¶
func (c Chromosome) String() string
String prints Gene list of a Chromosome but does not preserve the name of the Species.
type Crossover ¶
type Crossover interface {
fmt.Stringer
Crossover(r rand.Rand, a, b Chromosome) (x, y Chromosome)
}
Crossover is a strategy for generating two children based on two parents.
type CrossoverFlag ¶
type CrossoverFlag struct {
// contains filtered or unexported fields
}
CrossoverFlag allows users to set Crossover strategies. Can only be set once. Values include: --flag=MultiPointCrossover(2) --flag=WholeArithmeticRecombination --flag=DavisOrderCrossover
func (CrossoverFlag) String ¶
func (f CrossoverFlag) String() string
type DavisOrderCrossover ¶
type DavisOrderCrossover struct{}
DavisOrderCrossover aka OX1 picks two crossover points, dividing the genomes into three segments. The middle segment is preserved whereas the right and left are rotationally filled with the left and right of the other chromosome. OX1 is appropraite for permutative genes, such as graph algorithms.
func (DavisOrderCrossover) Crossover ¶
func (c DavisOrderCrossover) Crossover(r rand.Rand, a, b Chromosome) (x, y Chromosome)
Crossover implements Crossover
func (DavisOrderCrossover) String ¶
func (DavisOrderCrossover) String() string
type Evolver ¶
type Evolver struct {
ReplacementCount int
MutationRate float32
Selector NaturalSelection
Crossover Crossover
Mutator Mutator
}
Evolver replaces one generation of genes with another
type Fitness ¶
type Fitness int64
Fitness is an arbitrary fitness number based on genomes and their matching traits.
type Gene ¶
type Gene = int
Gene is a single trait to control behavior. IF THIS TYPE IS CHANGED FROM BYTE, Species.NewRand() MUST CHANGE
type InversionMutation ¶
type InversionMutation struct{}
InversionMutation picks two crossover points and then flipps the alleles in the middle segment. This is most appropraite for permutation-encoded Genes, such as graph algorithms.
func (InversionMutation) Mutate ¶
func (m InversionMutation) Mutate(r rand.Rand, c *Chromosome)
Mutate implements Mutator
func (InversionMutation) String ¶
func (InversionMutation) String() string
type MultiPointCrossover ¶
type MultiPointCrossover struct {
Points int
}
MultiPointCrossover is a generalization of the Crossover method. N crossover points are selected and children are made of parens' chromosomes alternating sources at the crossover points. Multi-point crossovers are appropriate for numeric chromosomes NOTE: It might be more appropriate to allow crossovers mid-allele, which might require different int encodings.
func (MultiPointCrossover) Crossover ¶
func (c MultiPointCrossover) Crossover(r rand.Rand, a, b Chromosome) (x, y Chromosome)
Crossover imnplements Crossover. Inefficiency: This algorithm makes n^2 data copies because it assumes N is ~1-3
func (MultiPointCrossover) String ¶
func (c MultiPointCrossover) String() string
type MutationFlag ¶
type MutationFlag struct {
// contains filtered or unexported fields
}
MutationFlag allows developers to specify a Mutator strategy using flag.Value. Valid values include: --flag=RandomResettingMutation --flag=SwapMutation --flag=ScrambleMutation --flag=InversionMutation
func (MutationFlag) String ¶
func (f MutationFlag) String() string
type Mutator ¶
type Mutator interface {
fmt.Stringer
Mutate(r rand.Rand, c *Chromosome)
}
Mutator introduces randomness to the population. While mutations should be rare to avoid turning the algorithm into a random walk, some mutations are necessary to enforce convergence. Mutators work on unpacked Chromosomes because species' bit length is important to some algorithms.
type NaturalSelection ¶
type NaturalSelection interface {
fmt.Stringer
SelectParents(rand rand.Rand, numParents int, fitness []Fitness) (indexes []int)
}
NaturalSelection is an interface to pick the selection method. A NaturalSelection MAY NOT BE GOROUTINE SAFE. It may only be used in one Evolve function at a time. This helps avoid the lock incurred by the top-level rand functions. TODO: consider nested interfaces (NaturalSelection has a Seed() function to return a Selector that implements SelectParents). This would avoid re-generating the roulette wheel in StochasticUniversalSampling
type NaturalSelectionFlag ¶
type NaturalSelectionFlag struct {
// contains filtered or unexported fields
}
NaturalSelectionFlag allows developers to pick a NaturalSelection strategy using flag.Value. Vallid values include: --flag=StochasticUniversalSampling --flag=RankedSelection --flag=TournamentSelection(3)
func (*NaturalSelectionFlag) Get ¶
func (f *NaturalSelectionFlag) Get() NaturalSelection
Get returns a parsed NaturalSelection value
func (*NaturalSelectionFlag) Set ¶
func (f *NaturalSelectionFlag) Set(s string) error
Set implements flag.Value
func (NaturalSelectionFlag) String ¶
func (f NaturalSelectionFlag) String() string
type RandomResettingMutation ¶
type RandomResettingMutation struct{}
RandomResettingMutation (equivalent to Bit Flip Mutation for Species with a bitwidth of 1) Will randomly set an allele to one of the acceptable values. Assumes Species' Genomes accept values of any bit size. This is most useful for chromasomes where genes affect independent behavior (e.g. not permutation-based algorithms).
func (RandomResettingMutation) Mutate ¶
func (m RandomResettingMutation) Mutate(r rand.Rand, c *Chromosome)
Mutate implements the Mutator interface
func (RandomResettingMutation) String ¶
func (RandomResettingMutation) String() string
type RankedSelection ¶
type RankedSelection struct{}
RankedSelection gives each chromosome odds of reproduction not based on its proportional fitness, but its rank in overall fitness. This ensures that populations trend towards optimal solutions still as the problem is converging.
func (RankedSelection) SelectParents ¶
func (s RankedSelection) SelectParents(rand rand.Rand, numParents int, fitness []Fitness) (indexes []int)
SelectParents selects parents in proportion to their fitness' rank.
func (RankedSelection) String ¶
func (s RankedSelection) String() string
type ScrambleMutation ¶
type ScrambleMutation struct{}
ScrambleMutation picks two crossover points and scrambles the alleles in the middle segment. This is most appropraite for permutation-encoded Genes, such as graph algorithms.
func (ScrambleMutation) Mutate ¶
func (m ScrambleMutation) Mutate(r rand.Rand, c *Chromosome)
Mutate implements Mutator
func (ScrambleMutation) String ¶
func (ScrambleMutation) String() string
type Species ¶
Species is a factory for all Genes in a repeated evolutionary experiment. Separating this from the actual Chromosome allows easier reuse of genetic algorithms in multiple circumstances as well as experimentation with the ordering of Chromosomes which influences the rate at which they may be separated by crossovers.
func NewSpecies ¶
NewSpecies initializes a Species
func (*Species) New ¶
func (s *Species) New(g ...Gene) Chromosome
New creates a Chromosome of the species. Any passed Genes are initialized starting at index 0. Any surpluss Genes are ignored and any missing Genes are 0-initialized.
func (*Species) NewPerm ¶
func (s *Species) NewPerm(rng rand.Rand) (Chromosome, error)
NewPerm creates a random
func (*Species) NewRand ¶
func (s *Species) NewRand(rng rand.Rand) (Chromosome, error)
NewRand creates a random-initialized Chromosome of the species; each allele is independently randomized
func (*Species) ParseChromosome ¶
func (s *Species) ParseChromosome(encoded string) (Chromosome, error)
ParseChromosome creates an in-memory representation for Chromosomes encoded with SerializeChromosome
type StochasticUniversalSampling ¶
type StochasticUniversalSampling struct{}
StochasticUniversalSampling creates a "roulette" wheel where each parent gets a slice in proportion to their fitness. We then spin the wheel with two fixed points to select which parents win. If src is nill, a new source is created with the current time.
func (StochasticUniversalSampling) SelectParents ¶
func (s StochasticUniversalSampling) SelectParents(rand rand.Rand, numParents int, fitness []Fitness) (indexes []int)
SelectParents implements the NaturalSelection interface.
func (StochasticUniversalSampling) String ¶
func (s StochasticUniversalSampling) String() string
type SwapMutation ¶
type SwapMutation struct{}
SwapMutation mutations swap the value of two genomes. SwapMutation is a mutation most appropriate for permutation genes (e.g. graph algorithms)
func (SwapMutation) Mutate ¶
func (m SwapMutation) Mutate(r rand.Rand, c *Chromosome)
Mutate implements the mutator interface
func (SwapMutation) String ¶
func (SwapMutation) String() string
type TournamentSelection ¶
type TournamentSelection struct {
Size int
}
TournamentSelection picks each parent by picking Size candidates from a fitness list at random and selecting the parent with the greatest fitness.
func (TournamentSelection) SelectParents ¶
func (s TournamentSelection) SelectParents(rand rand.Rand, numParents int, fitness []Fitness) (indexes []int)
SelectParents selects the len(indexes) parents who win a s.Size-way tournament
func (TournamentSelection) String ¶
func (s TournamentSelection) String() string
type WholeArithmeticRecombination ¶
type WholeArithmeticRecombination struct{}
WholeArithmeticRecombination picks a random float weight from 0-1. The children are a weighted average of the parents with inverse weights. Whole arithmetic recombinatinos are appropriate for numeric chromosomes and will trend towards the average value of the population.
func (WholeArithmeticRecombination) Crossover ¶
func (c WholeArithmeticRecombination) Crossover(r rand.Rand, a, b Chromosome) (x, y Chromosome)
Crossover implements Crossover
func (WholeArithmeticRecombination) String ¶
func (WholeArithmeticRecombination) String() string
Source Files