org.uncommons.watchmaker.framework
Class SteadyStateEvolutionEngine<T>

java.lang.Object
  org.uncommons.watchmaker.framework.AbstractEvolutionEngine<T>
      org.uncommons.watchmaker.framework.SteadyStateEvolutionEngine<T>

Type Parameters:

T - The type of entity that is to be evolved.

All Implemented Interfaces:

EvolutionEngine<T>

public class SteadyStateEvolutionEngine<T>
extends AbstractEvolutionEngine<T>

An implementation of steady-state evolution, which is a type of evolutionary algorithm where a population is changed incrementally, with one individual evolved at a time. This differs from GenerationalEvolutionEngine in which the entire population is evolved in parallel.

Author:

Daniel Dyer

See Also:

GenerationalEvolutionEngine, EvolutionStrategyEngine

Constructor Summary

SteadyStateEvolutionEngine(CandidateFactory<T> candidateFactory, EvolutionaryOperator<T> evolutionScheme, FitnessEvaluator<? super T> fitnessEvaluator, SelectionStrategy<? super T> selectionStrategy, int selectionSize, boolean forceSingleCandidateUpdate, Random rng)
Create a steady-state evolution strategy in which one or more (usually just one) evolved offspring replace randomly-chosen individuals.

Method Summary

protected void	doReplacement(List<EvaluatedCandidate<T>> existingPopulation, List<EvaluatedCandidate<T>> newCandidates, int eliteCount, Random rng) Add the offspring to the population, removing the same number of existing individuals to make space for them.
protected List<EvaluatedCandidate<T>>	nextEvolutionStep(List<EvaluatedCandidate<T>> evaluatedPopulation, int eliteCount, Random rng) This method performs a single step/iteration of the evolutionary process.

Methods inherited from class org.uncommons.watchmaker.framework.AbstractEvolutionEngine

addEvolutionObserver, evaluatePopulation, evolve, evolve, evolvePopulation, evolvePopulation, getSatisfiedTerminationConditions, removeEvolutionObserver, setSingleThreaded

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SteadyStateEvolutionEngine

public SteadyStateEvolutionEngine(CandidateFactory<T> candidateFactory,
                                  EvolutionaryOperator<T> evolutionScheme,
                                  FitnessEvaluator<? super T> fitnessEvaluator,
                                  SelectionStrategy<? super T> selectionStrategy,
                                  int selectionSize,
                                  boolean forceSingleCandidateUpdate,
                                  Random rng)

Create a steady-state evolution strategy in which one or more (usually just one) evolved offspring replace randomly-chosen individuals.

Parameters:

candidateFactory - Factory used to create the initial population that is iteratively evolved.

evolutionScheme - The evolutionary operator that modifies the population. The number of candidates used as input is controlled by the selectionSize parameter. The number of candidates that will be outputted depends on the implementation. Typically it will be the same as the input size, but this is not necessary. In fact, for steady-state evolution, it is typical that the output size is always 1, regardless of the input size, so that only one member of the population is replaced at a time. To acheive this using cross-over requires a cross-over implementation that returns only one offspring, rather than the normal two.

fitnessEvaluator - The fitness function.

selectionStrategy - The strategy for selecting which candidate(s) will be the parent(s) when evolving individuals.

selectionSize - How many parent candidates are required by the evolution scheme. This controls how many individuals will be provided to the evolutionary operator at each iteration. If you are just using mutation, this will typically be 1. For cross-over, two separate parents are required, so this must be set to 2.

forceSingleCandidateUpdate - Some evolutionary operators, specifically cross-over operators, generate more than one evolved individual. A true steady-state algorithm will only replace one individual at a time. Setting this parameter to true forces the evolution to discard any additional generated offspring so that for each iteration of the algorithm there is only one updated individual. This allows cross-over operators that were designed for generational evolutionary algorithms to be reused for steady-state evolution. A more efficient, but less straightforward, alternative would be to implement a steady-state-specific cross-over operator that returns only a single evolved individual. Setting this parameter to false permits multiple candidates to be replaced per iteration, depending on the specifics of the evolutionary operator(s).

rng - The source of randomness used by all stochastic processes (including evolutionary operators and selection strategies).

Method Detail

nextEvolutionStep

protected List<EvaluatedCandidate<T>> nextEvolutionStep(List<EvaluatedCandidate<T>> evaluatedPopulation,
                                                        int eliteCount,
                                                        Random rng)

This method performs a single step/iteration of the evolutionary process.

Specified by:

nextEvolutionStep in class AbstractEvolutionEngine<T>

Parameters:

evaluatedPopulation - The population at the beginning of the process.

eliteCount - The number of the fittest individuals that must be preserved.

rng - A source of randomness.

Returns:

The updated population after the evolutionary process has proceeded by one step/iteration.

doReplacement

protected void doReplacement(List<EvaluatedCandidate<T>> existingPopulation,
                             List<EvaluatedCandidate<T>> newCandidates,
                             int eliteCount,
                             Random rng)

Add the offspring to the population, removing the same number of existing individuals to make space for them. This method randomly chooses which individuals should be replaced, but it can be over-ridden in sub-classes if alternative behaviour is required.

Parameters:

existingPopulation - The full popultation, sorted in descending order of fitness.

newCandidates - The (unsorted) newly-created individual(s) that should replace existing members of the population.

eliteCount - The number of the fittest individuals that should be exempt from being replaced.

rng - A source of randomness.