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 */
017package org.apache.commons.math4.genetics;
018
019import java.util.ArrayList;
020import java.util.Arrays;
021import java.util.Collections;
022import java.util.Comparator;
023import java.util.List;
024
025import org.apache.commons.math4.exception.DimensionMismatchException;
026import org.apache.commons.math4.exception.MathIllegalArgumentException;
027import org.apache.commons.math4.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 */
056public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> {
057
058    /** Cache of sorted representation (unmodifiable). */
059    private final List<Double> sortedRepresentation;
060
061    /**
062     * Base sequence [0,1,...,n-1], permuted according to the representation (unmodifiable).
063     */
064    private final List<Integer> baseSeqPermutation;
065
066    /**
067     * Constructor.
068     *
069     * @param representation list of [0,1] values representing the permutation
070     * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome
071     */
072    public RandomKey(final List<Double> representation) throws InvalidRepresentationException {
073        super(representation);
074        // store the sorted representation
075        List<Double> sortedRepr = new ArrayList<> (getRepresentation());
076        Collections.sort(sortedRepr);
077        sortedRepresentation = Collections.unmodifiableList(sortedRepr);
078        // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods
079        baseSeqPermutation = Collections.unmodifiableList(
080            decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation)
081        );
082    }
083
084    /**
085     * Constructor.
086     *
087     * @param representation array of [0,1] values representing the permutation
088     * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome
089     */
090    public RandomKey(final Double[] representation) throws InvalidRepresentationException {
091        this(Arrays.asList(representation));
092    }
093
094    /**
095     * {@inheritDoc}
096     */
097    @Override
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<> (representation);
130
131        // now find the indices in the original repr and use them for permuting
132        List<S> res = new ArrayList<> (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<>(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<>(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<>(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}
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<> (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    /** {@inheritDoc} */
282    @Override
283    public String toString() {
284        return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation);
285    }
286
287    /**
288     * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).
289     *
290     * @param l length of list to generate
291     * @return list of integers from 0 to l-1
292     */
293    private static List<Integer> baseSequence(final int l) {
294        List<Integer> baseSequence = new ArrayList<> (l);
295        for (int i=0; i<l; i++) {
296            baseSequence.add(i);
297        }
298        return baseSequence;
299    }
300}