Package org.apache.commons.math.genetics

Class 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) $

    • Constructor Summary

      Constructors 
      Constructor Description
      RandomKey​(java.lang.Double[] representation)
      Constructor.
      RandomKey​(java.util.List<java.lang.Double> representation)
      Constructor.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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.
      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 java.lang.Object

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

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

        fitness

    • 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

      • 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

      • 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