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

java.lang.Object
  extended by org.apache.commons.math3.genetics.Chromosome
      extended by org.apache.commons.math3.genetics.AbstractListChromosome<Double>
          extended by org.apache.commons.math3.genetics.RandomKey<T>
Type Parameters:
T - type of the permuted objects
All Implemented Interfaces:
Comparable<Chromosome>, Fitness, PermutationChromosome<T>

public abstract class RandomKey<T>
extends AbstractListChromosome<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:

Since:
2.0
Version:
$Id: RandomKey.java 1416643 2012-12-03 19:37:14Z tn $

Constructor Summary
RandomKey(Double[] representation)
          Constructor.
RandomKey(List<Double> representation)
          Constructor.
 
Method Summary
protected  void checkValidity(List<Double> chromosomeRepresentation)
          Asserts that representation can represent a valid chromosome.
static
<S> List<Double>
comparatorPermutation(List<S> data, Comparator<S> comparator)
          Generates a representation of a permutation corresponding to the data sorted by comparator.
 List<T> decode(List<T> sequence)
          Permutes the sequence of objects of type T according to the permutation this chromosome represents.
static List<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> List<Double>
inducedPermutation(List<S> originalData, 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 List<Double> randomPermutation(int l)
          Generates a representation corresponding to a random permutation of length l which can be passed to the RandomKey constructor.
 String toString()
           
 
Methods inherited from class org.apache.commons.math3.genetics.AbstractListChromosome
getLength, getRepresentation, newFixedLengthChromosome
 
Methods inherited from class org.apache.commons.math3.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.math3.genetics.Fitness
fitness
 

Constructor Detail

RandomKey

public RandomKey(List<Double> representation)
          throws InvalidRepresentationException
Constructor.

Parameters:
representation - list of [0,1] values representing the permutation
Throws:
InvalidRepresentationException - iff the representation can not represent a valid chromosome

RandomKey

public RandomKey(Double[] representation)
          throws InvalidRepresentationException
Constructor.

Parameters:
representation - array of [0,1] values representing the permutation
Throws:
InvalidRepresentationException - iff the representation can not represent a valid chromosome
Method Detail

decode

public List<T> decode(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

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(List<Double> chromosomeRepresentation)
                      throws InvalidRepresentationException
Asserts that representation can represent a valid chromosome.

Specified by:
checkValidity in class AbstractListChromosome<Double>
Parameters:
chromosomeRepresentation - representation of the chromosome
Throws:
InvalidRepresentationException - iff the representation can not represent a valid chromosome

randomPermutation

public static final List<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 List<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> List<Double> comparatorPermutation(List<S> data,
                                                     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> List<Double> inducedPermutation(List<S> originalData,
                                                  List<S> permutedData)
                                       throws DimensionMismatchException,
                                              MathIllegalArgumentException
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:
DimensionMismatchException - iff the length of originalData and permutedData lists are not equal
MathIllegalArgumentException - iff the permutedData and originalData lists contain different data

toString

public String toString()
Overrides:
toString in class AbstractListChromosome<Double>


Copyright © 2003-2013 The Apache Software Foundation. All Rights Reserved.