README
¶
Documentation
¶
Index ¶
- Variables
- func EvaluatorFunc(natural bool, f FitnessFunc) evaluatorFunc
- func GeneratePopulation(gen Generator, count int, rng *rand.Rand) []interface{}
- func SeedPopulation(gen Generator, count int, seeds []interface{}, rng *rand.Rand) ([]interface{}, error)
- type Condition
- type Dataset
- func (ds *Dataset) AddValue(value float64)
- func (ds *Dataset) AddValues(values ...float64)
- func (ds *Dataset) ArithmeticMean() float64
- func (ds *Dataset) Clear()
- func (ds *Dataset) GeometricMean() float64
- func (ds *Dataset) HarmonicMean() float64
- func (ds *Dataset) Len() int
- func (ds *Dataset) Max() float64
- func (ds *Dataset) MeanDeviation() float64
- func (ds *Dataset) Median() float64
- func (ds *Dataset) Min() float64
- func (ds *Dataset) Product() float64
- func (ds *Dataset) SampleStandardDeviation() float64
- func (ds *Dataset) SampleVariance() float64
- func (ds *Dataset) StandardDeviation() float64
- func (ds *Dataset) Sum() float64
- func (ds *Dataset) Variance() float64
- type Epocher
- type Evaluator
- type FitnessCache
- type FitnessFunc
- type Generator
- type GeneratorFunc
- type Individual
- type Operator
- type Population
- type PopulationStats
- type Selection
- type ZeroEvaluator
Constants ¶
This section is empty.
Variables ¶
var ErrIllegalState = errors.New("illegal state")
ErrIllegalState is the error returned when trying a method of an engine has been called while its state doesn't allow that method call.
var ErrTooManySeedCandidates = errors.New("Too many seed candidates for population size")
ErrTooManySeedCandidates is the error returned by SeedPopulation when the number of seed candidates is greater than the population size.
Functions ¶
func EvaluatorFunc ¶
func EvaluatorFunc(natural bool, f FitnessFunc) evaluatorFunc
EvaluatorFunc is an adapter to allow the use of ordinary functions as fitness evaluators. If f is a function with the appropriate signature, EvaluatorFunc returns an object satisfying the Evaluator interface, for which the Fitness method calls f and IsNatural returns natural.
func GeneratePopulation ¶
GeneratePopulation returns a slice of count random candidates, generated with the provided Generator.
If some control is required over the composition of the initial population, consider using SeedPopulation.
func SeedPopulation ¶
func SeedPopulation(gen Generator, count int, seeds []interface{}, rng *rand.Rand) ([]interface{}, error)
SeedPopulation seeds all or a part of an initial population with some candidates.
Sometimes it is desirable to seed the initial population with some known good candidates, or partial solutions, in order to provide some hints for the evolution process. If the number of seed candidates is less than the required population size, gen will generate the additional candidates to fill the remaining spaces in the population.
Types ¶
type Condition ¶
type Condition interface {
fmt.Stringer
// IsSatisfied examines the given population statistics and
// returns true if it satisfies some predetermined condition.
IsSatisfied(pdata *PopulationStats) bool
}
Condition is the interface that wraps the IsSatisfied method.
IsSatisfied examines the current state of evolution and decides wether a predetermined condition is satisfied.
type Dataset ¶
type Dataset struct {
// contains filtered or unexported fields
}
A Dataset stores some floating point values and compute some statistics about the finite dataset composed of all the values it stores.
func NewDataset ¶
NewDataset creates an empty data set with the provided initial capacity.
The initial capacity for the data set corresponds to the number of values that can be added without needing to resize the internal data storage.
func (*Dataset) AddValue ¶
AddValue adds a single value to the data set and updates any statistics that are calculated cumulatively.
func (*Dataset) AddValues ¶
AddValues adds multiple values to the data set and updates any statistics that are calculated cumulatively.
func (*Dataset) ArithmeticMean ¶
ArithmeticMean returns the arithmetic mean of all elements ion the data set.
The artithmetic mean of an n-element set is the sum of all the elements divided by n. The arithmetic mean is often referred to simply as the "mean" or "average" of a data set.
See GeometricMean()
panics if the data set is empty.
func (*Dataset) Clear ¶
func (ds *Dataset) Clear()
Clear clears all the values previously added and resets the statistics. The dataset capacity remains unchanged.
func (*Dataset) GeometricMean ¶
GeometricMean returns the geometric mean of all elements in the data set.
The geometric mean of an n-element set is the nth-root of the product of all the elements. The geometric mean is used for finding the average factor (e.g. an average interest rate).
See ArithmeticMean() and HarmonicMean()
panics if the data set is empty.
func (*Dataset) HarmonicMean ¶
HarmonicMean returns the harmonic mean of all the elements in the data set.
The harmonic mean of an n-element set is n divided by the sum of the reciprocals of the values (where the reciprocal of a value x is 1/x. The harmonic mean is used to calculate an average rate (e.g. an average speed).
See ArithmeticMean() and GeometricMean()
panics if the data set is empty.
func (*Dataset) Max ¶
Max returns the biggest value in the data set.
panics if the data set is empty.
func (*Dataset) MeanDeviation ¶
MeanDeviation returns the mean absolute deviation of the data set.
The mean deviation is the average (absolute) amount that a single value deviates from the arithmetic mean.
See ArithmeticMean(), Variance() and StandardDeviation()
panics if the data set is empty.
func (*Dataset) Median ¶
Median determines the median value of the data set.
If the number of elements is odd, returns the middle element. If the number of elements is even, returns the midpoint of the two middle elements.
panics if the data set is empty.
func (*Dataset) Min ¶
Min returns the smallest value in the data set.
panics if the data set is empty.
func (*Dataset) Product ¶
Product returns the product of all values.
panics if the data set is empty.
func (*Dataset) SampleStandardDeviation ¶
SampleStandardDeviation returns the sample standard deviation of the data set.
The sample standard deviation is the square root of the sample variance. For large data sets the difference between sample standard deviation and population standard deviation is negligible.
See StandardDeviation(), SampleVariance() and MeanDeviation()
panics if the data set is empty.
func (*Dataset) SampleVariance ¶
SampleVariance returns the sample variance of the data set.
Calculates the variance (a measure of statistical dispersion) of the data set. There are different measures of variance depending on whether the data set is itself a finite population or is a sample from some larger population. For large data sets the difference is negligible. This method calculates the sample variance.
See Variance(), SampleStandardDeviation() and MeanDeviation()
panics if the data set is empty.
func (*Dataset) StandardDeviation ¶
StandardDeviation returns the standard deviation of the population.
The standard deviation is the square root of the variance. This method calculates the population standard deviation as opposed to the sample standard deviation. For large data sets the difference is negligible.
See SampleStandardDeviation(), Variance() and MeanDeviation()
panics if the data set is empty.
func (*Dataset) Variance ¶
Variance returns the population variance of the data set.
The variance is a measure of statistical dispersion of the data set.
There are different measures of variance depending on whether the data set is itself a finite population or is a sample from some larger population. For large data sets the difference is negligible. This method calculates the population variance.
See SampleVariance(), StandardDeviation() and MeanDeviation()
panics if the data set is empty.
type Epocher ¶
type Epocher interface {
// Epoch performs one epoch (i.e generation) of the evolutionary process.
//
// It takes as argument the population to evolve in that step, the elitism
// count -that is how many of the fittest candidates are preserved and
// directly inserted into the nexct generation, without selection- and a
// source of randomess.
//
// It returns the next generation.
Epoch(Population, int, *rand.Rand) Population
}
Epocher is the interface implemented by objects having an Epoch method.
type Evaluator ¶
type Evaluator interface {
// Fitness calculates a fitness score for the given candidate.
//
// Whether a higher score indicates a fitter candidate or not depends on
// whether the fitness scores are natural. This method must always return a
// value greater than or equal to zero. Framework behaviour is undefined for
// negative fitness scores.
//
// cand is the candidate solution to calculate fitness for.
//
// pop is the entire population. This will include the specified candidate.
// This is provided for fitness evaluators that evaluate individuals in the
// context of the population that they are part of (e.g. a program that
// evolves game-playing strategies may wish to play each strategy against
// each of the others). This parameter can be ignored by simple fitness
// evaluators. When iterating over the population, a simple interface
// equality check (==) can be used to identify which member of the
// population is the specified candidate.
//
// Returns the fitness score for the specified candidate. Must always be a
// non-negative value regardless of natural or non-natural evaluation is
// being used.
Fitness(cand interface{}, pop []interface{}) float64
// IsNatural specifies whether this evaluator generates 'natural' fitness
// scores or not.
//
// Natural fitness scores are those in which the fittest individual in a
// population has the highest fitness value. In this case the algorithm is
// attempting to maximise fitness scores. There need not be a specified
// maximum possible value.
// In contrast, 'non-natural' fitness evaluation results in fitter
// individuals being assigned lower scores than weaker individuals. In the
// case of non-natural fitness, the algorithm is attempting to minimise
// fitness scores.
//
// An example of a situation in which non-natural fitness scores are
// preferable is when the fitness corresponds to a cost and the algorithm is
// attempting to minimise that cost.
//
// The terminology of 'natural' and 'non-natural' fitness scores is
// introduced by the evolve Framework to describe the two types of fitness
// scoring that exist within the framework. It does not correspond to either
// standardised fitness or normalised fitness in the EA literature.
// Standardised fitness evaluation generates non-natural
// scores with a score of zero corresponding to the best possible fitness.
// Normalised fitness evaluation is similar to standardised fitness but with
// the scores adjusted to fall within the range 0 - 1.
//
// Returns true if a high fitness score means a fitter candidate or false if
// a low fitness score means a fitter candidate.
IsNatural() bool
}
Evaluator calculates the fitness score of a given candidate of the appropriate type.
Fitness evaluations may be executed concurrently and therefore any concurrent access to a shared state should be properly synchronized.
type FitnessCache ¶
type FitnessCache struct {
// Wrapped is the fitness evaluator for which we want to provide caching
Wrapped Evaluator
// contains filtered or unexported fields
}
FitnessCache provides caching for any Evaluator implementation. The results of fitness evaluations are stored in a cache so that if the same candidate is evaluated twice, the expense of the fitness calculation can be avoided the second time.
Caching of fitness values can be a useful optimisation in situations where the fitness evaluation is expensive and there is a possibility that some candidates will survive from generation to generation unmodified. Programs that use elitism are one example of candidates surviving unmodified. Another scenario is when the configured evolutionary operator does not always modify every candidate in the population for every generation.
Caching of fitness scores is only valid when fitness evaluations are isolated and repeatable. An isolated fitness evaluation is one where the result depends only upon the candidate being evaluated. This is not the case when candidates are evaluated against the other members of the population. So unless the fitness evaluator ignores the second parameter to the Evaluator.Fitness method, caching must not be used.
func (*FitnessCache) Fitness ¶
func (c *FitnessCache) Fitness(cand interface{}, pop []interface{}) float64
Fitness calculates a fitness score for the given candidate.
This implementation performs a cache look-up every time it is invoked. If the fitness evaluator has already calculated the fitness score for the specified candidate that score is returned without delegating to the wrapped evaluator.
func (*FitnessCache) IsNatural ¶
func (c *FitnessCache) IsNatural() bool
IsNatural specifies whether this evaluator generates 'natural' fitness scores or not.
type FitnessFunc ¶
type FitnessFunc func(interface{}, []interface{}) float64
FitnessFunc is the type of function computing the fitness of a candidate solution.
type Generator ¶
type Generator interface {
// Generate returns a new random candidate, using the provided pseudo-random
// number generator.
Generate(*rand.Rand) interface{}
}
A Generator generates random candidates.
It is used by evolution engine to increase genetic diversity and/or add new candidates to a population.
type GeneratorFunc ¶
The GeneratorFunc type is an adapter to allow the use of ordinary functions as candidate generators. If f is a function with the appropriate signature, GeneratorFunc(f) is a Generator that calls f.
func (GeneratorFunc) Generate ¶
func (f GeneratorFunc) Generate(rng *rand.Rand) interface{}
Generate calls f(rng) and returns its return value.
type Individual ¶
type Individual struct {
Candidate interface{}
Fitness float64
}
Individual associates a candidate solution with its fitness score.
type Operator ¶
type Operator interface {
// Apply applies the operation to each entry in the list of selected
// candidates.
//
// It is important to note that this method operates on the list of
// candidates returned by the selection strategy and not on the current
// population. Each entry in the list (not each individual - the list may
// contain the same individual more than once) must be operated on exactly
// once.
//
// Implementing structs should not assume any particular ordering (or lack
// of ordering) for the selection. If ordering or shuffling is required, it
// should be performed by the implementing struct. The implementation should
// not re-order the list provided but instead should make a copy of the list
// and re-order that.
//
// The ordering of the selection should be totally irrelevant for operators
// that process each candidate in isolation, such as mutation. It should
// only be an issue for operators, such as crossover, that deal with
// multiple candidates in a single operation.
//
// The operator must not modify any of the candidates passed. Instead it
// should return a list that contains evolved copies of those candidates
// (umodified candidates can be included in the results without having to be
// copied).
Apply([]interface{}, *rand.Rand) []interface{}
}
Operator is the interface that wraps the Apply method.
It takes a population of candidates and returns a new population that is the result of applying a transformation to the original population.
An implementation of this interface must not modify any of the selected candidate objects passed in. Doing so will affect the correct operation of the evolution engine. Instead the operator should create and return new candidate objects. However, an operator is not required to create copies of unmodified individuals, they may be returned directly.
type Population ¶
type Population []*Individual
Population is a group of individual. TODO: check if and where we would benefit of having a slice of structs instead of pointers
func EvaluatePopulation ¶
func EvaluatePopulation(pop []interface{}, e Evaluator, concurrent bool) Population
EvaluatePopulation evaluates individuals and returns a sorted population.
Every individual is assigned a fitness score with the provided evaluator, after that individuals is inserted into a population. The population is then sorted, either in descending order of fitness for natural scores, or ascending for non natural scores.
Returns the evaluated population (a slice of individuals, each of which associated with its fitness).
func (Population) Len ¶
func (s Population) Len() int
Len is the number of elements in the collection.
func (Population) Less ¶
func (s Population) Less(i, j int) bool
Less reports whether the element with index a should sort before the element with index b.
func (Population) String ¶
func (s Population) String() string
func (Population) Swap ¶
func (s Population) Swap(i, j int)
Swap swaps the elements with indexes i and j.
type PopulationStats ¶
type PopulationStats struct {
// BestCandidate is the fittest candidate present in the population.
// TODO: rename into Best (or: why not having an evluated candidate here, so
// we would have the best candidate ANd their fitness)
BestCand interface{}
// BestFitness is the fitness score for the fittest candidate in the
// population.
BestFitness float64
// Mean is the arithmetic mean of fitness scores for each member of
// the population.
Mean float64
// StdDev is a measure of the variation in fitness scores.
StdDev float64
// Natural indicates, if true, that higher fitness is better.
Natural bool
// Size is the number of individuals in the population.
Size int
// NumElites is the number of candidates preserved via elitism.
NumElites int
// GenNumber is the (zero-based) number of the last generation that was
// processed.
GenNumber int
// Elapsed is the duration elapsed since the evolution start.
Elapsed time.Duration
}
PopulationStats contains statistics about the state of an evolved population and a reference to the fittest candidate solution in the population.
type Selection ¶
type Selection interface {
fmt.Stringer
// Select selects the specified number of candidates from the population.
//
// - pop must be sorted by descending fitness, i.e the fittest individual of the
// population should be pop[0].
// - natural indicates fitter individuals have fitness scores.
// - size is the number of individual selections to perform (not necessarily the
// number of distinct candidates to select, since the same individual may
// potentially be selected more than once).
//
// Returns the selected candidates.
Select(pop Population, natural bool, size int, rng *rand.Rand) []interface{}
}
Selection is the interface that wraps the Select method.
Select implements "natural" selection.
type ZeroEvaluator ¶
type ZeroEvaluator struct{}
ZeroEvaluator is a fitness evaluator always giving a score of 0.
func (ZeroEvaluator) Fitness ¶
func (ZeroEvaluator) Fitness(interface{}, []interface{}) float64
Fitness returns a score of zero, regardless of the candidate being evaluated.
func (ZeroEvaluator) IsNatural ¶
func (ZeroEvaluator) IsNatural() bool
IsNatural always returns true. However, it shouldn't be relevant since fitness is always 0.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package example contains various evolutionary algorithm implementations.
|
Package example contains various evolutionary algorithm implementations. |
|
bits
command
|
|
|
hello
command
|
|
|
sudoku
command
|
|
|
pkg
|
|
|
bitstring
Package bitstring implements a fixed length bit string type and bit string manipulation functions
|
Package bitstring implements a fixed length bit string type and bit string manipulation functions |
|
mt19937
Package mt19937 implements a Mersenne Twister source of random numbers satisfying the rand.Source64 interface.
|
Package mt19937 implements a Mersenne Twister source of random numbers satisfying the rand.Source64 interface. |