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

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

Type Parameters:

T - The type of entity evolved by the evolution engine.

All Implemented Interfaces:

EvolutionEngine<T>

Direct Known Subclasses:

EvolutionStrategyEngine, GenerationalEvolutionEngine, SteadyStateEvolutionEngine

public abstract class AbstractEvolutionEngine<T>
extends Object
implements EvolutionEngine<T>

Base class for EvolutionEngine implementations.

Author:

Daniel Dyer

See Also:

CandidateFactory, FitnessEvaluator

Constructor Summary

protected

AbstractEvolutionEngine(CandidateFactory<T> candidateFactory, FitnessEvaluator<? super T> fitnessEvaluator, Random rng) Creates a new evolution engine by specifying the various components required by an evolutionary algorithm.

Method Summary

void	addEvolutionObserver(EvolutionObserver<? super T> observer) Adds a listener to receive status updates on the evolution progress.
protected List<EvaluatedCandidate<T>>	evaluatePopulation(List<T> population) Takes a population, assigns a fitness score to each member and returns the members with their scores attached, sorted in descending order of fitness (descending order of fitness score for natural scores, ascending order of scores for non-natural scores).
T	evolve(int populationSize, int eliteCount, Collection<T> seedCandidates, TerminationCondition... conditions) Execute the evolutionary algorithm until one of the termination conditions is met, then return the fittest candidate from the final generation.
T	evolve(int populationSize, int eliteCount, TerminationCondition... conditions) Execute the evolutionary algorithm until one of the termination conditions is met, then return the fittest candidate from the final generation.
List<EvaluatedCandidate<T>>	evolvePopulation(int populationSize, int eliteCount, Collection<T> seedCandidates, TerminationCondition... conditions) Execute the evolutionary algorithm until one of the termination conditions is met, then return all of the candidates from the final generation.
List<EvaluatedCandidate<T>>	evolvePopulation(int populationSize, int eliteCount, TerminationCondition... conditions) Execute the evolutionary algorithm until one of the termination conditions is met, then return all of the candidates from the final generation.
List<TerminationCondition>	getSatisfiedTerminationConditions() Returns a list of all TerminationConditions that are satisfied by the current state of the evolution engine.
protected abstract List<EvaluatedCandidate<T>>	nextEvolutionStep(List<EvaluatedCandidate<T>> evaluatedPopulation, int eliteCount, Random rng) This method performs a single step/iteration of the evolutionary process.
void	removeEvolutionObserver(EvolutionObserver<? super T> observer) Removes an evolution progress listener.
void	setSingleThreaded(boolean singleThreaded) By default, fitness evaluations are performed on separate threads (as many as there are available cores/processors).

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractEvolutionEngine

protected AbstractEvolutionEngine(CandidateFactory<T> candidateFactory,
                                  FitnessEvaluator<? super T> fitnessEvaluator,
                                  Random rng)

Creates a new evolution engine by specifying the various components required by an evolutionary algorithm.

Parameters:

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

fitnessEvaluator - A function for assigning fitness scores to candidate solutions.

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

Method Detail

evolve

public T evolve(int populationSize,
                int eliteCount,
                TerminationCondition... conditions)

Execute the evolutionary algorithm until one of the termination conditions is met, then return the fittest candidate from the final generation. To return the entire population rather than just the fittest candidate, use the EvolutionEngine.evolvePopulation(int, int, TerminationCondition[]) method instead.

Specified by:

evolve in interface EvolutionEngine<T>

Parameters:

populationSize - The number of candidate solutions present in the population at any point in time.

eliteCount - The number of candidates preserved via elitism. In elitism, a sub-set of the population with the best fitness scores are preserved unchanged in the subsequent generation. Candidate solutions that are preserved unchanged through elitism remain eligible for selection for breeding the remainder of the next generation. This value must be non-negative and less than the population size. A value of zero means that no elitism will be applied.

conditions - One or more conditions that may cause the evolution to terminate.

Returns:

The fittest solution found by the evolutionary process.

See Also:

EvolutionEngine.evolve(int, int, Collection, TerminationCondition[])

evolve

public T evolve(int populationSize,
                int eliteCount,
                Collection<T> seedCandidates,
                TerminationCondition... conditions)

Execute the evolutionary algorithm until one of the termination conditions is met, then return the fittest candidate from the final generation. To return the entire population rather than just the fittest candidate, use the EvolutionEngine.evolvePopulation(int, int, Collection, TerminationCondition[]) method instead.

Specified by:

evolve in interface EvolutionEngine<T>

Parameters:

populationSize - The number of candidate solutions present in the population at any point in time.

eliteCount - The number of candidates preserved via elitism. In elitism, a sub-set of the population with the best fitness scores are preserved unchanged in the subsequent generation. Candidate solutions that are preserved unchanged through elitism remain eligible for selection for breeding the remainder of the next generation. This value must be non-negative and less than the population size. A value of zero means that no elitism will be applied.

seedCandidates - A set of candidates to seed the population with. The size of this collection must be no greater than the specified population size.

conditions - One or more conditions that may cause the evolution to terminate.

Returns:

The fittest solution found by the evolutionary process.

See Also:

EvolutionEngine.evolve(int,int,TerminationCondition[])

evolvePopulation

public List<EvaluatedCandidate<T>> evolvePopulation(int populationSize,
                                                    int eliteCount,
                                                    TerminationCondition... conditions)

Execute the evolutionary algorithm until one of the termination conditions is met, then return all of the candidates from the final generation. To return just the fittest candidate rather than the entire population, use the EvolutionEngine.evolve(int, int, TerminationCondition[]) method instead.

Specified by:

evolvePopulation in interface EvolutionEngine<T>

Parameters:

populationSize - The number of candidate solutions present in the population at any point in time.

eliteCount - The number of candidates preserved via elitism. In elitism, a sub-set of the population with the best fitness scores are preserved unchanged in the subsequent generation. Candidate solutions that are preserved unchanged through elitism remain eligible for selection for breeding the remainder of the next generation. This value must be non-negative and less than the population size. A value of zero means that no elitism will be applied.

conditions - One or more conditions that may cause the evolution to terminate.

Returns:

The fittest solution found by the evolutionary process.

See Also:

EvolutionEngine.evolve(int, int, Collection, TerminationCondition[]), EvolutionEngine.evolvePopulation(int, int, Collection, TerminationCondition[])

evolvePopulation

public List<EvaluatedCandidate<T>> evolvePopulation(int populationSize,
                                                    int eliteCount,
                                                    Collection<T> seedCandidates,
                                                    TerminationCondition... conditions)

Execute the evolutionary algorithm until one of the termination conditions is met, then return all of the candidates from the final generation. To return just the fittest candidate rather than the entire population, use the EvolutionEngine.evolve(int, int, Collection, TerminationCondition[]) method instead.

Specified by:

evolvePopulation in interface EvolutionEngine<T>

Parameters:

populationSize - The number of candidate solutions present in the population at any point in time.

eliteCount - The number of candidates preserved via elitism. In elitism, a sub-set of the population with the best fitness scores are preserved unchanged in the subsequent generation. Candidate solutions that are preserved unchanged through elitism remain eligible for selection for breeding the remainder of the next generation. This value must be non-negative and less than the population size. A value of zero means that no elitism will be applied.

seedCandidates - A set of candidates to seed the population with. The size of this collection must be no greater than the specified population size.

conditions - One or more conditions that may cause the evolution to terminate.

Returns:

The fittest solution found by the evolutionary process.

See Also:

EvolutionEngine.evolve(int, int, Collection, TerminationCondition[]), EvolutionEngine.evolvePopulation(int, int, Collection, TerminationCondition[])

nextEvolutionStep

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

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

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.

evaluatePopulation

protected List<EvaluatedCandidate<T>> evaluatePopulation(List<T> population)

Takes a population, assigns a fitness score to each member and returns the members with their scores attached, sorted in descending order of fitness (descending order of fitness score for natural scores, ascending order of scores for non-natural scores).

Parameters:

population - The population to evaluate (each candidate is assigned a fitness score).

Returns:

The evaluated population (a list of candidates with attached fitness scores).

getSatisfiedTerminationConditions

public List<TerminationCondition> getSatisfiedTerminationConditions()

Returns a list of all TerminationConditions that are satisfied by the current state of the evolution engine. Usually this list will contain only one item, but it is possible that mutliple termination conditions will become satisfied at the same time. In this case the condition objects in the list will be in the same order that they were specified when passed to the engine.

If the evolution has not yet terminated (either because it is still in progress or because it hasn't even been started) then an IllegalStateException will be thrown.

If the evolution terminated because the request thread was interrupted before any termination conditions were satisfied then this method will return an empty list.

Specified by:

getSatisfiedTerminationConditions in interface EvolutionEngine<T>

Returns:

A list of statisfied conditions. The list is guaranteed to be non-null. The list may be empty because it is possible for evolution to terminate without any conditions being matched. The only situation in which this occurs is when the request thread is interrupted.

Throws:

IllegalStateException - If this method is invoked on an evolution engine before evolution is started or while it is still in progress.

addEvolutionObserver

public void addEvolutionObserver(EvolutionObserver<? super T> observer)

Adds a listener to receive status updates on the evolution progress. Updates are dispatched synchronously on the request thread. Observers should complete their processing and return in a timely manner to avoid holding up the evolution.

Specified by:

addEvolutionObserver in interface EvolutionEngine<T>

Parameters:

observer - An evolution observer call-back.

See Also:

removeEvolutionObserver(EvolutionObserver)

removeEvolutionObserver

public void removeEvolutionObserver(EvolutionObserver<? super T> observer)

Removes an evolution progress listener.

Specified by:

removeEvolutionObserver in interface EvolutionEngine<T>

Parameters:

observer - An evolution observer call-back.

See Also:

addEvolutionObserver(EvolutionObserver)

setSingleThreaded

public void setSingleThreaded(boolean singleThreaded)

By default, fitness evaluations are performed on separate threads (as many as there are available cores/processors). Use this method to force evaluation to occur synchronously on the request thread. This is useful in restricted environments where programs are not permitted to start or control threads. It might also lead to better performance for programs that have extremely lightweight/trivial fitness evaluations.

Parameters:

singleThreaded - If true, fitness evaluations will be performed synchronously on the request thread. If false, fitness evaluations will be performed by worker threads.