| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.math.genetics; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.List; |
| |
| /** |
| * <p> |
| * 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. |
| * </p> |
| * |
| * <p> |
| * 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). |
| * </p> |
| * |
| * <p> |
| * With this representation, common operators like n-point crossover can be |
| * used, because any such chromosome represents a valid permutation. |
| * </p> |
| * |
| * <p> |
| * Since the chromosome (and thus its arrayRepresentation) is immutable, the |
| * array representation is sorted only once in the constructor. |
| * </p> |
| * |
| * <p> |
| * For details, see: |
| * <ul> |
| * <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and |
| * optimization. ORSA Journal on Computing 6 (1994) 154–160</li> |
| * <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms. |
| * Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag, |
| * Heidelberg (2002)</li> |
| * </ul> |
| * </p> |
| * |
| * @param <T> |
| * type of the permuted objects |
| * @since 2.0 |
| * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ |
| */ |
| public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> { |
| |
| /** |
| * Cache of sorted representation (unmodifiable). |
| */ |
| private final List<Double> sortedRepresentation; |
| |
| /** |
| * Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable). |
| */ |
| private final List<Integer> baseSeqPermutation; |
| |
| /** |
| * Constructor. |
| * |
| * @param representation list of [0,1] values representing the permutation |
| */ |
| public RandomKey(List<Double> representation) { |
| super(representation); |
| // store the sorted representation |
| List<Double> sortedRepr = new ArrayList<Double> (getRepresentation()); |
| Collections.sort(sortedRepr); |
| sortedRepresentation = Collections.unmodifiableList(sortedRepr); |
| // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods |
| baseSeqPermutation = Collections.unmodifiableList( |
| decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation) |
| ); |
| } |
| |
| /** |
| * Constructor. |
| * |
| * @param representation array of [0,1] values representing the permutation |
| */ |
| public RandomKey(Double[] representation) { |
| this(Arrays.asList(representation)); |
| } |
| |
| /** |
| * {@inheritDoc} |
| */ |
| public List<T> decode(List<T> sequence) { |
| return decodeGeneric(sequence, getRepresentation(), sortedRepresentation); |
| } |
| |
| /** |
| * Decodes a permutation represented by <code>representation</code> and |
| * returns a (generic) list with the permuted values. |
| * |
| * @param <S> generic type of the sequence values |
| * @param sequence the unpermuted sequence |
| * @param representation representation of the permutation ([0,1] vector) |
| * @param sortedRepr sorted <code>representation</code> |
| * @return list with the sequence values permuted according to the representation |
| */ |
| private static <S> List<S> decodeGeneric(List<S> sequence, List<Double> representation, List<Double> sortedRepr) { |
| int l = sequence.size(); |
| |
| if (representation.size() != l) { |
| throw new IllegalArgumentException(String.format("Length of sequence for decoding (%s) has to be equal to the length of the RandomKey (%s)", l, representation.size())); |
| } |
| if (representation.size() != sortedRepr.size()) { |
| throw new IllegalArgumentException(String.format("Representation and sortedRepr must have same sizes, %d != %d", representation.size(), sortedRepr.size())); |
| } |
| |
| List<Double> reprCopy = new ArrayList<Double> (representation);// do not modify the orig. representation |
| |
| // now find the indices in the original repr and use them for permuting |
| List<S> res = new ArrayList<S> (l); |
| for (int i=0; i<l; i++) { |
| int index = reprCopy.indexOf(sortedRepr.get(i)); |
| res.add(sequence.get(index)); |
| reprCopy.set(index, null); |
| } |
| return res; |
| } |
| |
| /** |
| * Returns <code>true</code> iff <code>another</code> is a RandomKey and |
| * encodes the same permutation. |
| * |
| * @param another chromosome to compare |
| * @return true iff chromosomes encode the same permutation |
| */ |
| @Override |
| protected boolean isSame(Chromosome another) { |
| // type check |
| if (! (another instanceof RandomKey<?>)) |
| return false; |
| RandomKey<?> anotherRk = (RandomKey<?>) another; |
| // size check |
| if (getLength() != anotherRk.getLength()) |
| return false; |
| |
| // two different representations can still encode the same permutation |
| // the ordering is what counts |
| List<Integer> thisPerm = this.baseSeqPermutation; |
| List<Integer> anotherPerm = anotherRk.baseSeqPermutation; |
| |
| for (int i=0; i<getLength(); i++) { |
| if (thisPerm.get(i) != anotherPerm.get(i)) |
| return false; |
| } |
| // the permutations are the same |
| return true; |
| } |
| |
| /** |
| * {@inheritDoc} |
| */ |
| @Override |
| protected void checkValidity(java.util.List<Double> chromosomeRepresentation) throws InvalidRepresentationException { |
| for (double val : chromosomeRepresentation) { |
| if (val < 0 || val > 1) { |
| throw new InvalidRepresentationException("Values of representation must be in [0,1] interval"); |
| } |
| } |
| } |
| |
| |
| /** |
| * Generates a representation corresponding to a random permutation of |
| * length l which can be passed to the RandomKey constructor. |
| * |
| * @param l |
| * length of the permutation |
| * @return representation of a random permutation |
| */ |
| public static final List<Double> randomPermutation(int l) { |
| List<Double> repr = new ArrayList<Double>(l); |
| for (int i=0; i<l; i++) { |
| repr.add(GeneticAlgorithm.getRandomGenerator().nextDouble()); |
| } |
| return repr; |
| } |
| |
| /** |
| * Generates a representation corresponding to an identity permutation of |
| * length l which can be passed to the RandomKey constructor. |
| * |
| * @param l |
| * length of the permutation |
| * @return representation of an identity permutation |
| */ |
| public static final List<Double> identityPermutation(int l) { |
| List<Double> repr = new ArrayList<Double>(l); |
| for (int i=0; i<l; i++) { |
| repr.add((double)i/l); |
| } |
| return repr; |
| } |
| |
| /** |
| * Generates a representation of a permutation corresponding to the |
| * <code>data</code> sorted by <code>comparator</code>. The |
| * <code>data</code> is not modified during the process. |
| * |
| * This is useful if you want to inject some permutations to the initial |
| * population. |
| * |
| * @param <S> type of the data |
| * @param data list of data determining the order |
| * @param comparator how the data will be compared |
| * @return list representation of the permutation corresponding to the parameters |
| */ |
| public static <S> List<Double> comparatorPermutation(List<S> data, Comparator<S> comparator) { |
| List<S> sortedData = new ArrayList<S> (data); |
| Collections.sort(sortedData, comparator); |
| |
| return inducedPermutation(data, sortedData); |
| } |
| |
| /** |
| * Generates a representation of a permutation corresponding to a |
| * permutation which yields <code>permutedData</code> when applied to |
| * <code>originalData</code>. |
| * |
| * This method can be viewed as an inverse to {@link #decode(List)}. |
| * |
| * @param <S> type of the data |
| * @param originalData the original, unpermuted data |
| * @param permutedData the data, somehow permuted |
| * @return representation of a permutation corresponding to the permutation <code>originalData -> permutedData</code> |
| * @throws IllegalArgumentException iff the <code>permutedData</code> and <code>originalData</code> contains different data |
| */ |
| public static <S> List<Double> inducedPermutation(List<S> originalData, List<S> permutedData) throws IllegalArgumentException { |
| if (originalData.size() != permutedData.size()) { |
| throw new IllegalArgumentException("originalData and permutedData must have same length"); |
| } |
| int l = originalData.size(); |
| |
| List<S> origDataCopy = new ArrayList<S> (originalData); |
| |
| Double[] res = new Double[l]; |
| for (int i=0; i<l; i++) { |
| int index = origDataCopy.indexOf(permutedData.get(i)); |
| if (index == -1) { |
| throw new IllegalArgumentException("originalData and permutedData must contain the same objects."); |
| } |
| res[index] = (double) i / l; |
| origDataCopy.set(index, null); |
| } |
| return Arrays.asList(res); |
| } |
| |
| /** |
| * {@inheritDoc} |
| */ |
| @Override |
| public String toString() { |
| return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation); |
| } |
| |
| /** |
| * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1). |
| * |
| * @param l length of list to generate |
| * @return list of integers from 0 to l-1 |
| */ |
| private static List<Integer> baseSequence(int l) { |
| List<Integer> baseSequence = new ArrayList<Integer> (l); |
| for (int i=0; i<l; i++) { |
| baseSequence.add(i); |
| } |
| return baseSequence; |
| } |
| } |