    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.math.genetics;
    018
    019    import java.util.ArrayList;
    020    import java.util.Arrays;
    021    import java.util.Collections;
    022    import java.util.Comparator;
    023    import java.util.List;
    024
    025    /**
    026     * <p>
    027     * Random Key chromosome is used for permutation representation. It is a vector
    028     * of a fixed length of real numbers in [0,1] interval. The index of the i-th
    029     * smallest value in the vector represents an i-th member of the permutation.
    030     * </p>
    031     *
    032     * <p>
    033     * For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the
    034     * permutation of indices (3,0,1,2). If the original (unpermuted) sequence would
    035     * be (a,b,c,d), this would mean the sequence (d,a,b,c).
    036     * </p>
    037     *
    038     * <p>
    039     * With this representation, common operators like n-point crossover can be
    040     * used, because any such chromosome represents a valid permutation.
    041     * </p>
    042     *
    043     * <p>
    044     * Since the chromosome (and thus its arrayRepresentation) is immutable, the
    045     * array representation is sorted only once in the constructor.
    046     * </p>
    047     *
    048     * <p>
    049     * For details, see:
    050     * <ul>
    051     * <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and
    052     * optimization. ORSA Journal on Computing 6 (1994) 154???160</li>
    053     * <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms.
    054     * Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag,
    055     * Heidelberg (2002)</li>
    056     * </ul>
    057     * </p>
    058     *
    059     * @param <T>
    060     *            type of the permuted objects
    061     * @since 2.0
    062     * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $
    063     */
    064    public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> {
    065
    066        /**
    067         * Cache of sorted representation (unmodifiable).
    068         */
    069        private final List<Double> sortedRepresentation;
    070
    071        /**
    072         * Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable).
    073         */
    074        private final List<Integer> baseSeqPermutation;
    075
    076        /**
    077         * Constructor.
    078         *
    079         * @param representation list of [0,1] values representing the permutation
    080         */
    081        public RandomKey(List<Double> representation) {
    082            super(representation);
    083            // store the sorted representation
    084            List<Double> sortedRepr = new ArrayList<Double> (getRepresentation());
    085            Collections.sort(sortedRepr);
    086            sortedRepresentation = Collections.unmodifiableList(sortedRepr);
    087            // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods
    088            baseSeqPermutation = Collections.unmodifiableList(
    089                decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation)
    090            );
    091        }
    092
    093        /**
    094         * Constructor.
    095         *
    096         * @param representation array of [0,1] values representing the permutation
    097         */
    098        public RandomKey(Double[] representation) {
    099            this(Arrays.asList(representation));
    100        }
    101
    102        /**
    103         * {@inheritDoc}
    104         */
    105        public List<T> decode(List<T> sequence) {
    106            return decodeGeneric(sequence, getRepresentation(), sortedRepresentation);
    107        }
    108
    109        /**
    110         * Decodes a permutation represented by <code>representation</code> and
    111         * returns a (generic) list with the permuted values.
    112         *
    113         * @param <S> generic type of the sequence values
    114         * @param sequence the unpermuted sequence
    115         * @param representation representation of the permutation ([0,1] vector)
    116         * @param sortedRepr sorted <code>representation</code>
    117         * @return list with the sequence values permuted according to the representation
    118         */
    119        private static <S> List<S> decodeGeneric(List<S> sequence, List<Double> representation, List<Double> sortedRepr) {
    120            int l = sequence.size();
    121
    122            if (representation.size() != l) {
    123                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()));
    124            }
    125            if (representation.size() != sortedRepr.size()) {
    126                throw new IllegalArgumentException(String.format("Representation and sortedRepr must have same sizes, %d != %d", representation.size(), sortedRepr.size()));
    127            }
    128
    129            List<Double> reprCopy = new ArrayList<Double> (representation);// do not modify the orig. representation
    130
    131            // now find the indices in the original repr and use them for permuting
    132            List<S> res = new ArrayList<S> (l);
    133            for (int i=0; i<l; i++) {
    134                int index = reprCopy.indexOf(sortedRepr.get(i));
    135                res.add(sequence.get(index));
    136                reprCopy.set(index, null);
    137            }
    138            return res;
    139        }
    140
    141        /**
    142         * Returns <code>true</code> iff <code>another</code> is a RandomKey and
    143         * encodes the same permutation.
    144         *
    145         * @param another chromosome to compare
    146         * @return true iff chromosomes encode the same permutation
    147         */
    148        @Override
    149        protected boolean isSame(Chromosome another) {
    150            // type check
    151            if (! (another instanceof RandomKey<?>))
    152                return false;
    153            RandomKey<?> anotherRk = (RandomKey<?>) another;
    154            // size check
    155            if (getLength() != anotherRk.getLength())
    156                return false;
    157
    158            // two different representations can still encode the same permutation
    159            // the ordering is what counts
    160            List<Integer> thisPerm = this.baseSeqPermutation;
    161            List<Integer> anotherPerm = anotherRk.baseSeqPermutation;
    162
    163            for (int i=0; i<getLength(); i++) {
    164                if (thisPerm.get(i) != anotherPerm.get(i))
    165                    return false;
    166            }
    167            // the permutations are the same
    168            return true;
    169        }
    170
    171        /**
    172         * {@inheritDoc}
    173         */
    174        @Override
    175        protected void checkValidity(java.util.List<Double> chromosomeRepresentation) throws InvalidRepresentationException {
    176            for (double val : chromosomeRepresentation) {
    177                if (val < 0 || val > 1) {
    178                    throw new InvalidRepresentationException("Values of representation must be in [0,1] interval");
    179                }
    180            }
    181        }
    182
    183
    184        /**
    185         * Generates a representation corresponding to a random permutation of
    186         * length l which can be passed to the RandomKey constructor.
    187         *
    188         * @param l
    189         *            length of the permutation
    190         * @return representation of a random permutation
    191         */
    192        public static final List<Double> randomPermutation(int l) {
    193            List<Double> repr = new ArrayList<Double>(l);
    194            for (int i=0; i<l; i++) {
    195                repr.add(GeneticAlgorithm.getRandomGenerator().nextDouble());
    196            }
    197            return repr;
    198        }
    199
    200        /**
    201         * Generates a representation corresponding to an identity permutation of
    202         * length l which can be passed to the RandomKey constructor.
    203         *
    204         * @param l
    205         *            length of the permutation
    206         * @return representation of an identity permutation
    207         */
    208        public static final List<Double> identityPermutation(int l) {
    209            List<Double> repr = new ArrayList<Double>(l);
    210            for (int i=0; i<l; i++) {
    211                repr.add((double)i/l);
    212            }
    213            return repr;
    214        }
    215
    216        /**
    217         * Generates a representation of a permutation corresponding to the
    218         * <code>data</code> sorted by <code>comparator</code>. The
    219         * <code>data</code> is not modified during the process.
    220         *
    221         * This is useful if you want to inject some permutations to the initial
    222         * population.
    223         *
    224         * @param <S> type of the data
    225         * @param data list of data determining the order
    226         * @param comparator how the data will be compared
    227         * @return list representation of the permutation corresponding to the parameters
    228         */
    229        public static <S> List<Double> comparatorPermutation(List<S> data, Comparator<S> comparator) {
    230            List<S> sortedData = new ArrayList<S> (data);
    231            Collections.sort(sortedData, comparator);
    232
    233            return inducedPermutation(data, sortedData);
    234        }
    235
    236        /**
    237         * Generates a representation of a permutation corresponding to a
    238         * permutation which yields <code>permutedData</code> when applied to
    239         * <code>originalData</code>.
    240         *
    241         * This method can be viewed as an inverse to {@link #decode(List)}.
    242         *
    243         * @param <S> type of the data
    244         * @param originalData the original, unpermuted data
    245         * @param permutedData the data, somehow permuted
    246         * @return representation of a permutation corresponding to the permutation <code>originalData -> permutedData</code>
    247         * @throws IllegalArgumentException iff the <code>permutedData</code> and <code>originalData</code> contains different data
    248         */
    249        public static <S> List<Double> inducedPermutation(List<S> originalData, List<S> permutedData) throws IllegalArgumentException {
    250            if (originalData.size() != permutedData.size()) {
    251                throw new IllegalArgumentException("originalData and permutedData must have same length");
    252            }
    253            int l = originalData.size();
    254
    255            List<S> origDataCopy = new ArrayList<S> (originalData);
    256
    257            Double[] res = new Double[l];
    258            for (int i=0; i<l; i++) {
    259                int index = origDataCopy.indexOf(permutedData.get(i));
    260                if (index == -1) {
    261                    throw new IllegalArgumentException("originalData and permutedData must contain the same objects.");
    262                }
    263                res[index] = (double) i / l;
    264                origDataCopy.set(index, null);
    265            }
    266            return Arrays.asList(res);
    267        }
    268
    269        /**
    270         * {@inheritDoc}
    271         */
    272        @Override
    273        public String toString() {
    274            return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation);
    275        }
    276
    277        /**
    278         * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).
    279         *
    280         * @param l length of list to generate
    281         * @return list of integers from 0 to l-1
    282         */
    283        private static List<Integer> baseSequence(int l) {
    284            List<Integer> baseSequence = new ArrayList<Integer> (l);
    285            for (int i=0; i<l; i++) {
    286                baseSequence.add(i);
    287            }
    288            return baseSequence;
    289        }
    290    }