View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.genetics;
18  
19  import java.util.ArrayList;
20  import java.util.Arrays;
21  import java.util.Collections;
22  import java.util.Comparator;
23  import java.util.List;
24  
25  /**
26   * <p>
27   * Random Key chromosome is used for permutation representation. It is a vector
28   * of a fixed length of real numbers in [0,1] interval. The index of the i-th
29   * smallest value in the vector represents an i-th member of the permutation.
30   * </p>
31   * 
32   * <p>
33   * For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the
34   * permutation of indices (3,0,1,2). If the original (unpermuted) sequence would
35   * be (a,b,c,d), this would mean the sequence (d,a,b,c).
36   * </p>
37   * 
38   * <p>
39   * With this representation, common operators like n-point crossover can be
40   * used, because any such chromosome represents a valid permutation.
41   * </p>
42   * 
43   * <p>
44   * Since the chromosome (and thus its arrayRepresentation) is immutable, the
45   * array representation is sorted only once in the constructor.
46   * </p>
47   * 
48   * <p>
49   * For details, see:
50   * <ul>
51   * <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and
52   * optimization. ORSA Journal on Computing 6 (1994) 154–160</li>
53   * <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms.
54   * Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag,
55   * Heidelberg (2002)</li>
56   * </ul>
57   * </p>
58   * 
59   * @param <T>
60   *            type of the permuted objects
61   * @since 2.0
62   * @version $Revision: 800113 $ $Date: 2009-08-02 13:23:54 -0400 (Sun, 02 Aug 2009) $
63   */
64  public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> {
65      
66      /**
67       * Cache of sorted representation (unmodifiable).
68       */
69      private final List<Double> sortedRepresentation;
70      
71      /**
72       * Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable).
73       */
74      private final List<Integer> baseSeqPermutation;
75      
76      /**
77       * Constructor.
78       * 
79       * @param representation list of [0,1] values representing the permutation
80       */
81      public RandomKey(List<Double> representation) {
82          super(representation);
83          // store the sorted representation
84          List<Double> sortedRepr = new ArrayList<Double> (getRepresentation());
85          Collections.sort(sortedRepr);
86          sortedRepresentation = Collections.unmodifiableList(sortedRepr);
87          // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods
88          baseSeqPermutation = Collections.unmodifiableList(
89              decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation)
90          );
91      }
92      
93      /**
94       * Constructor.
95       * 
96       * @param representation array of [0,1] values representing the permutation
97       */
98      public RandomKey(Double[] representation) {
99          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> representation) throws InvalidRepresentationException {
176         for (double val : representation) {
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 }