org.apache.commons.math.genetics
Class RandomKey<T>

java.lang.Object
  org.apache.commons.math.genetics.Chromosome
      org.apache.commons.math.genetics.AbstractListChromosome<java.lang.Double>
          org.apache.commons.math.genetics.RandomKey<T>

Type Parameters:

T - type of the permuted objects

All Implemented Interfaces:

java.lang.Comparable<Chromosome>, Fitness, PermutationChromosome<T>

public abstract class RandomKey<T>
extends AbstractListChromosome<java.lang.Double>
implements PermutationChromosome<T>

Random Key chromosome is used for permutation representation. It is a vector of a fixed length of real numbers in [0,1] interval. The index of the i-th smallest value in the vector represents an i-th member of the permutation.

For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the permutation of indices (3,0,1,2). If the original (unpermuted) sequence would be (a,b,c,d), this would mean the sequence (d,a,b,c).

With this representation, common operators like n-point crossover can be used, because any such chromosome represents a valid permutation.

Since the chromosome (and thus its arrayRepresentation) is immutable, the array representation is sorted only once in the constructor.

For details, see:

• Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 6 (1994) 154–160
• Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms. Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag, Heidelberg (2002)

Since:

2.0

Version:

$Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $

Field Summary

private java.util.List<java.lang.Integer>	baseSeqPermutation Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable).
private java.util.List<java.lang.Double>	sortedRepresentation Cache of sorted representation (unmodifiable).

Constructor Summary

RandomKey(java.lang.Double[] representation)
Constructor.

RandomKey(java.util.List<java.lang.Double> representation)
Constructor.

Method Summary

private static java.util.List<java.lang.Integer>	baseSequence(int l) Helper for constructor.
protected void	checkValidity(java.util.List<java.lang.Double> chromosomeRepresentation) Asserts that representation can represent a valid chromosome.
static <S> java.util.List<java.lang.Double>	comparatorPermutation(java.util.List<S> data, java.util.Comparator<S> comparator) Generates a representation of a permutation corresponding to the data sorted by comparator.
java.util.List<T>	decode(java.util.List<T> sequence) Permutes the sequence of objects of type T according to the permutation this chromosome represents.
private static <S> java.util.List<S>	decodeGeneric(java.util.List<S> sequence, java.util.List<java.lang.Double> representation, java.util.List<java.lang.Double> sortedRepr) Decodes a permutation represented by representation and returns a (generic) list with the permuted values.
static java.util.List<java.lang.Double>	identityPermutation(int l) Generates a representation corresponding to an identity permutation of length l which can be passed to the RandomKey constructor.
static <S> java.util.List<java.lang.Double>	inducedPermutation(java.util.List<S> originalData, java.util.List<S> permutedData) Generates a representation of a permutation corresponding to a permutation which yields permutedData when applied to originalData.
protected boolean	isSame(Chromosome another) Returns true iff another is a RandomKey and encodes the same permutation.
static java.util.List<java.lang.Double>	randomPermutation(int l) Generates a representation corresponding to a random permutation of length l which can be passed to the RandomKey constructor.
java.lang.String	toString()

Methods inherited from class org.apache.commons.math.genetics.AbstractListChromosome

getLength, getRepresentation, newFixedLengthChromosome

Methods inherited from class org.apache.commons.math.genetics.Chromosome

compareTo, findSameChromosome, getFitness, searchForFitnessUpdate

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.apache.commons.math.genetics.Fitness

fitness

Field Detail

sortedRepresentation

private final java.util.List<java.lang.Double> sortedRepresentation

Cache of sorted representation (unmodifiable).

baseSeqPermutation

private final java.util.List<java.lang.Integer> baseSeqPermutation

Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable).

Constructor Detail

RandomKey

public RandomKey(java.util.List<java.lang.Double> representation)

Constructor.

Parameters:

representation - list of [0,1] values representing the permutation

RandomKey

public RandomKey(java.lang.Double[] representation)

Constructor.

Parameters:

representation - array of [0,1] values representing the permutation

Method Detail

decode

public java.util.List<T> decode(java.util.List<T> sequence)

Permutes the sequence of objects of type T according to the permutation this chromosome represents. For example, if this chromosome represents a permutation (3,0,1,2), and the unpermuted sequence is (a,b,c,d), this yields (d,a,b,c).

Specified by:

decode in interface PermutationChromosome<T>

Parameters:

sequence - the unpermuted (original) sequence of objects

Returns:

permutation of sequence represented by this permutation

decodeGeneric

private static <S> java.util.List<S> decodeGeneric(java.util.List<S> sequence,
                                                   java.util.List<java.lang.Double> representation,
                                                   java.util.List<java.lang.Double> sortedRepr)

Decodes a permutation represented by representation and returns a (generic) list with the permuted values.

Type Parameters:

S - generic type of the sequence values

Parameters:

sequence - the unpermuted sequence

representation - representation of the permutation ([0,1] vector)

sortedRepr - sorted representation

Returns:

list with the sequence values permuted according to the representation

isSame

protected boolean isSame(Chromosome another)

Returns true iff another is a RandomKey and encodes the same permutation.

Overrides:

isSame in class Chromosome

Parameters:

another - chromosome to compare

Returns:

true iff chromosomes encode the same permutation

checkValidity

protected void checkValidity(java.util.List<java.lang.Double> chromosomeRepresentation)
                      throws InvalidRepresentationException

Asserts that representation can represent a valid chromosome.

Specified by:

checkValidity in class AbstractListChromosome<java.lang.Double>

Parameters:

chromosomeRepresentation - representation of the chromosome

Throws:

InvalidRepresentationException - iff the representation can not represent a valid chromosome

randomPermutation

public static final java.util.List<java.lang.Double> randomPermutation(int l)

Generates a representation corresponding to a random permutation of length l which can be passed to the RandomKey constructor.

Parameters:

l - length of the permutation

Returns:

representation of a random permutation

identityPermutation

public static final java.util.List<java.lang.Double> identityPermutation(int l)

Generates a representation corresponding to an identity permutation of length l which can be passed to the RandomKey constructor.

Parameters:

l - length of the permutation

Returns:

representation of an identity permutation

comparatorPermutation

public static <S> java.util.List<java.lang.Double> comparatorPermutation(java.util.List<S> data,
                                                                         java.util.Comparator<S> comparator)

Generates a representation of a permutation corresponding to the data sorted by comparator. The data is not modified during the process. This is useful if you want to inject some permutations to the initial population.

Type Parameters:

S - type of the data

Parameters:

data - list of data determining the order

comparator - how the data will be compared

Returns:

list representation of the permutation corresponding to the parameters

inducedPermutation

public static <S> java.util.List<java.lang.Double> inducedPermutation(java.util.List<S> originalData,
                                                                      java.util.List<S> permutedData)
                                                           throws java.lang.IllegalArgumentException

Generates a representation of a permutation corresponding to a permutation which yields permutedData when applied to originalData. This method can be viewed as an inverse to decode(List).

Type Parameters:

S - type of the data

Parameters:

originalData - the original, unpermuted data

permutedData - the data, somehow permuted

Returns:

representation of a permutation corresponding to the permutation originalData -> permutedData

Throws:

java.lang.IllegalArgumentException - iff the permutedData and originalData contains different data

toString

public java.lang.String toString()

Overrides:

toString in class AbstractListChromosome<java.lang.Double>

baseSequence

private static java.util.List<java.lang.Integer> baseSequence(int l)

Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).

Parameters:

l - length of list to generate

Returns:

list of integers from 0 to l-1