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 */ 17package org.apache.commons.math.genetics; 18 19import java.util.ArrayList; 20import java.util.Arrays; 21import java.util.Collections; 22import java.util.Comparator; 23import 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: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ 63 */ 64public 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> 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} 291