org.uncommons.watchmaker.framework.selection
Class RankSelection

java.lang.Object
  org.uncommons.watchmaker.framework.selection.RankSelection

All Implemented Interfaces:

SelectionStrategy<Object>

public class RankSelection
extends Object
implements SelectionStrategy<Object>

A selection strategy that is similar to fitness-proportionate selection except that is uses relative fitness rather than absolute fitness in order to determine the probability of selection for a given individual (i.e. the actual numerical fitness values are ignored and only the ordering of the sorted population is considered).

Rank selection is implemented in terms of a mapping function (mapRankToScore(int, int)) and delegation to a fitness-proportionate selector. The mapping function converts ranks into relative fitness scores that are used to drive the delegate selector.

Author:

Daniel Dyer

Constructor Summary

RankSelection()
Creates a default rank-based selector with a linear mapping function and selection frequencies that correspond to expected values.

RankSelection(SelectionStrategy<Object> delegate)
Creates a rank-based selector with a linear mapping function and configurable delegate for performing the proportionate selection.

Method Summary

protected double	mapRankToScore(int rank, int populationSize) Maps a population index to a relative pseudo-fitness score that can be used for fitness-proportionate selection.
<S> List<S>	select(List<EvaluatedCandidate<S>> population, boolean naturalFitnessScores, int selectionSize, Random rng) Select the specified number of candidates from the population.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

RankSelection

public RankSelection()

Creates a default rank-based selector with a linear mapping function and selection frequencies that correspond to expected values.

RankSelection

public RankSelection(SelectionStrategy<Object> delegate)

Creates a rank-based selector with a linear mapping function and configurable delegate for performing the proportionate selection.

Parameters:

delegate - The proportionate selector that will be delegated to after converting rankings into relative fitness scores.

Method Detail

select

public <S> List<S> select(List<EvaluatedCandidate<S>> population,
                          boolean naturalFitnessScores,
                          int selectionSize,
                          Random rng)

Select the specified number of candidates from the population. Implementations may assume that the population is sorted in descending order according to fitness (so the fittest individual is the first item in the list).

It is an error to call this method with an empty or null population.

Specified by:

select in interface SelectionStrategy<Object>

Type Parameters:

S - The type of evolved entity that we are selecting, a sub-type of T.

Parameters:

population - The population from which to select.

naturalFitnessScores - Whether higher fitness values represent fitter individuals or not.

selectionSize - The number of individual selections to make (not necessarily the number of distinct candidates to select, since the same individual may potentially be selected more than once).

rng - Source of randomness for stochastic selection strategies.

Returns:

A list containing the selected candidates. Some individual canidates may potentially have been selected multiple times.

mapRankToScore

protected double mapRankToScore(int rank,
                                int populationSize)

Maps a population index to a relative pseudo-fitness score that can be used for fitness-proportionate selection. The general contract for the mapping function f is: f(rank) >= f(rank + 1) for all legal values of rank, assuming natural scores.

The default mapping function is a simple linear transformation, but this can be over-ridden in sub-classes. Alternative implementations can be linear or non-linear and either natural or non-natural.

Parameters:

rank - A zero-based index into the population (0 <= rank < populationSize).

populationSize - The number of individuals in the population.

Returns:

populationSize - rank

toString

public String toString()

Overrides:

toString in class Object