Raymond | dee0849 | 2015-04-02 10:43:13 -0700 | [diff] [blame] | 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: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 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> 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 | } |