    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.math3.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    import org.apache.commons.math3.exception.DimensionMismatchException;
    026    import org.apache.commons.math3.exception.MathIllegalArgumentException;
    027    import org.apache.commons.math3.exception.util.LocalizedFormats;
    028
    029    /**
    030     * Random Key chromosome is used for permutation representation. It is a vector
    031     * of a fixed length of real numbers in [0,1] interval. The index of the i-th
    032     * smallest value in the vector represents an i-th member of the permutation.
    033     * <p>
    034     * For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the
    035     * permutation of indices (3,0,1,2). If the original (unpermuted) sequence would
    036     * be (a,b,c,d), this would mean the sequence (d,a,b,c).
    037     * <p>
    038     * With this representation, common operators like n-point crossover can be
    039     * used, because any such chromosome represents a valid permutation.
    040     * <p>
    041     * Since the chromosome (and thus its arrayRepresentation) is immutable, the
    042     * array representation is sorted only once in the constructor.
    043     * <p>
    044     * For details, see:
    045     * <ul>
    046     *   <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and
    047     *       optimization. ORSA Journal on Computing 6 (1994) 154-160</li>
    048     *   <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms.
    049     *       Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag,
    050     *       Heidelberg (2002)</li>
    051     * </ul>
    052     *
    053     * @param <T> type of the permuted objects
    054     * @since 2.0
    055     * @version $Id: RandomKey.java 1416643 2012-12-03 19:37:14Z tn $
    056     */
    057    public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> {
    058
    059        /** Cache of sorted representation (unmodifiable). */
    060        private final List<Double> sortedRepresentation;
    061
    062        /**
    063         * Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable).
    064         */
    065        private final List<Integer> baseSeqPermutation;
    066
    067        /**
    068         * Constructor.
    069         *
    070         * @param representation list of [0,1] values representing the permutation
    071         * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome
    072         */
    073        public RandomKey(final List<Double> representation) throws InvalidRepresentationException {
    074            super(representation);
    075            // store the sorted representation
    076            List<Double> sortedRepr = new ArrayList<Double> (getRepresentation());
    077            Collections.sort(sortedRepr);
    078            sortedRepresentation = Collections.unmodifiableList(sortedRepr);
    079            // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods
    080            baseSeqPermutation = Collections.unmodifiableList(
    081                decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation)
    082            );
    083        }
    084
    085        /**
    086         * Constructor.
    087         *
    088         * @param representation array of [0,1] values representing the permutation
    089         * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome
    090         */
    091        public RandomKey(final Double[] representation) throws InvalidRepresentationException {
    092            this(Arrays.asList(representation));
    093        }
    094
    095        /**
    096         * {@inheritDoc}
    097         */
    098        public List<T> decode(final List<T> sequence) {
    099            return decodeGeneric(sequence, getRepresentation(), sortedRepresentation);
    100        }
    101
    102        /**
    103         * Decodes a permutation represented by <code>representation</code> and
    104         * returns a (generic) list with the permuted values.
    105         *
    106         * @param <S> generic type of the sequence values
    107         * @param sequence the unpermuted sequence
    108         * @param representation representation of the permutation ([0,1] vector)
    109         * @param sortedRepr sorted <code>representation</code>
    110         * @return list with the sequence values permuted according to the representation
    111         * @throws DimensionMismatchException iff the length of the <code>sequence</code>,
    112         *   <code>representation</code> or <code>sortedRepr</code> lists are not equal
    113         */
    114        private static <S> List<S> decodeGeneric(final List<S> sequence, List<Double> representation,
    115                                                 final List<Double> sortedRepr)
    116            throws DimensionMismatchException {
    117
    118            int l = sequence.size();
    119
    120            // the size of the three lists must be equal
    121            if (representation.size() != l) {
    122                throw new DimensionMismatchException(representation.size(), l);
    123            }
    124            if (sortedRepr.size() != l) {
    125                throw new DimensionMismatchException(sortedRepr.size(), l);
    126            }
    127
    128            // do not modify the original representation
    129            List<Double> reprCopy = new ArrayList<Double> (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(final Chromosome another) {
    150            // type check
    151            if (! (another instanceof RandomKey<?>)) {
    152                return false;
    153            }
    154            RandomKey<?> anotherRk = (RandomKey<?>) another;
    155            // size check
    156            if (getLength() != anotherRk.getLength()) {
    157                return false;
    158            }
    159
    160            // two different representations can still encode the same permutation
    161            // the ordering is what counts
    162            List<Integer> thisPerm = this.baseSeqPermutation;
    163            List<Integer> anotherPerm = anotherRk.baseSeqPermutation;
    164
    165            for (int i=0; i<getLength(); i++) {
    166                if (thisPerm.get(i) != anotherPerm.get(i)) {
    167                    return false;
    168                }
    169            }
    170            // the permutations are the same
    171            return true;
    172        }
    173
    174        /**
    175         * {@inheritDoc}
    176         */
    177        @Override
    178        protected void checkValidity(final List<Double> chromosomeRepresentation)
    179            throws InvalidRepresentationException {
    180
    181            for (double val : chromosomeRepresentation) {
    182                if (val < 0 || val > 1) {
    183                    throw new InvalidRepresentationException(LocalizedFormats.OUT_OF_RANGE_SIMPLE,
    184                                                             val, 0, 1);
    185                }
    186            }
    187        }
    188
    189
    190        /**
    191         * Generates a representation corresponding to a random permutation of
    192         * length l which can be passed to the RandomKey constructor.
    193         *
    194         * @param l length of the permutation
    195         * @return representation of a random permutation
    196         */
    197        public static final List<Double> randomPermutation(final int l) {
    198            List<Double> repr = new ArrayList<Double>(l);
    199            for (int i=0; i<l; i++) {
    200                repr.add(GeneticAlgorithm.getRandomGenerator().nextDouble());
    201            }
    202            return repr;
    203        }
    204
    205        /**
    206         * Generates a representation corresponding to an identity permutation of
    207         * length l which can be passed to the RandomKey constructor.
    208         *
    209         * @param l length of the permutation
    210         * @return representation of an identity permutation
    211         */
    212        public static final List<Double> identityPermutation(final int l) {
    213            List<Double> repr = new ArrayList<Double>(l);
    214            for (int i=0; i<l; i++) {
    215                repr.add((double)i/l);
    216            }
    217            return repr;
    218        }
    219
    220        /**
    221         * Generates a representation of a permutation corresponding to the
    222         * <code>data</code> sorted by <code>comparator</code>. The
    223         * <code>data</code> is not modified during the process.
    224         *
    225         * This is useful if you want to inject some permutations to the initial
    226         * population.
    227         *
    228         * @param <S> type of the data
    229         * @param data list of data determining the order
    230         * @param comparator how the data will be compared
    231         * @return list representation of the permutation corresponding to the parameters
    232         */
    233        public static <S> List<Double> comparatorPermutation(final List<S> data,
    234                                                             final Comparator<S> comparator) {
    235            List<S> sortedData = new ArrayList<S>(data);
    236            Collections.sort(sortedData, comparator);
    237
    238            return inducedPermutation(data, sortedData);
    239        }
    240
    241        /**
    242         * Generates a representation of a permutation corresponding to a
    243         * permutation which yields <code>permutedData</code> when applied to
    244         * <code>originalData</code>.
    245         *
    246         * This method can be viewed as an inverse to {@link #decode(List)}.
    247         *
    248         * @param <S> type of the data
    249         * @param originalData the original, unpermuted data
    250         * @param permutedData the data, somehow permuted
    251         * @return representation of a permutation corresponding to the permutation
    252         *   <code>originalData -> permutedData</code>
    253         * @throws DimensionMismatchException iff the length of <code>originalData</code>
    254         *   and <code>permutedData</code> lists are not equal
    255         * @throws MathIllegalArgumentException iff the <code>permutedData</code> and
    256         *   <code>originalData</code> lists contain different data
    257         */
    258        public static <S> List<Double> inducedPermutation(final List<S> originalData,
    259                                                          final List<S> permutedData)
    260            throws DimensionMismatchException, MathIllegalArgumentException {
    261
    262            if (originalData.size() != permutedData.size()) {
    263                throw new DimensionMismatchException(permutedData.size(), originalData.size());
    264            }
    265            int l = originalData.size();
    266
    267            List<S> origDataCopy = new ArrayList<S> (originalData);
    268
    269            Double[] res = new Double[l];
    270            for (int i=0; i<l; i++) {
    271                int index = origDataCopy.indexOf(permutedData.get(i));
    272                if (index == -1) {
    273                    throw new MathIllegalArgumentException(LocalizedFormats.DIFFERENT_ORIG_AND_PERMUTED_DATA);
    274                }
    275                res[index] = (double) i / l;
    276                origDataCopy.set(index, null);
    277            }
    278            return Arrays.asList(res);
    279        }
    280
    281        @Override
    282        public String toString() {
    283            return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation);
    284        }
    285
    286        /**
    287         * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).
    288         *
    289         * @param l length of list to generate
    290         * @return list of integers from 0 to l-1
    291         */
    292        private static List<Integer> baseSequence(final int l) {
    293            List<Integer> baseSequence = new ArrayList<Integer> (l);
    294            for (int i=0; i<l; i++) {
    295                baseSequence.add(i);
    296            }
    297            return baseSequence;
    298        }
    299    }