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    }