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

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

Type Parameters:

T - The type of evolvable entity that can be evaluated.

All Implemented Interfaces:

FitnessEvaluator<T>

public class CachingFitnessEvaluator<T>
extends Object
implements FitnessEvaluator<T>

A wrapper that provides caching for FitnessEvaluator implementations. 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. The cache uses weak references in order to avoid memory leakage.

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.

Unmodified candidates are identified by reference equality. This is a valid assumption since evolutionary operators are required to return distinct objects, except when the candidate is unaffected by the evolution, as per the contract of the EvolutionaryOperator interface. In other words, the Watchmaker Framework treats candidate representations as immutable even when that is not strictly the case.

Caching of fitness scores is provided as an option rather than as the default Watchmaker Framework behaviour because caching 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 getFitness(Object, List) method, caching must not be used.

Author:

Daniel Dyer

Constructor Summary

CachingFitnessEvaluator(FitnessEvaluator<T> delegate)
Creates a caching fitness evaluator that wraps the specified evaluator.

Method Summary

double	getFitness(T candidate, List<? extends T> population) Calculates a fitness score for the given candidate.
boolean	isNatural() Specifies whether this evaluator generates natural fitness scores or not.

Methods inherited from class java.lang.Object

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

Constructor Detail

CachingFitnessEvaluator

public CachingFitnessEvaluator(FitnessEvaluator<T> delegate)

Creates a caching fitness evaluator that wraps the specified evaluator.

Parameters:

delegate - The fitness evaluator that performs the actual calculations.

Method Detail

getFitness

public double getFitness(T candidate,
                         List<? extends T> population)

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 (see FitnessEvaluator.isNatural()). This method must always return a value greater than or equal to zero. Framework behaviour is undefined for negative fitness scores.

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.

Specified by:

getFitness in interface FitnessEvaluator<T>

Parameters:

candidate - The candidate solution to calculate fitness for.

population - 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 reference 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.

isNatural

public boolean 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 Watchmaker 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.

Specified by:

isNatural in interface FitnessEvaluator<T>

Returns:

True if a high fitness score means a fitter candidate or false if a low fitness score means a fitter candidate.