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 org.apache.commons.math.random.RandomGenerator; |
| 20 | import org.apache.commons.math.random.JDKRandomGenerator; |
| 21 | |
| 22 | /** |
| 23 | * Implementation of a genetic algorithm. All factors that govern the operation |
| 24 | * of the algorithm can be configured for a specific problem. |
| 25 | * |
| 26 | * @since 2.0 |
| 27 | * @version $Revision: 925812 $ $Date: 2010-03-21 16:49:31 +0100 (dim. 21 mars 2010) $ |
| 28 | */ |
| 29 | public class GeneticAlgorithm { |
| 30 | |
| 31 | /** |
| 32 | * Static random number generator shared by GA implementation classes. |
| 33 | * Set the randomGenerator seed to get reproducible results. |
| 34 | * Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative |
| 35 | * to the default JDK-provided PRNG. |
| 36 | */ |
| 37 | //@GuardedBy("this") |
| 38 | private static RandomGenerator randomGenerator = new JDKRandomGenerator(); |
| 39 | |
| 40 | /** the crossover policy used by the algorithm. */ |
| 41 | private final CrossoverPolicy crossoverPolicy; |
| 42 | |
| 43 | /** the rate of crossover for the algorithm. */ |
| 44 | private final double crossoverRate; |
| 45 | |
| 46 | /** the mutation policy used by the algorithm. */ |
| 47 | private final MutationPolicy mutationPolicy; |
| 48 | |
| 49 | /** the rate of mutation for the algorithm. */ |
| 50 | private final double mutationRate; |
| 51 | |
| 52 | /** the selection policy used by the algorithm. */ |
| 53 | private final SelectionPolicy selectionPolicy; |
| 54 | |
| 55 | /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */ |
| 56 | private int generationsEvolved = 0; |
| 57 | |
| 58 | /** |
| 59 | * @param crossoverPolicy The {@link CrossoverPolicy} |
| 60 | * @param crossoverRate The crossover rate as a percentage (0-1 inclusive) |
| 61 | * @param mutationPolicy The {@link MutationPolicy} |
| 62 | * @param mutationRate The mutation rate as a percentage (0-1 inclusive) |
| 63 | * @param selectionPolicy The {@link SelectionPolicy} |
| 64 | */ |
| 65 | public GeneticAlgorithm( |
| 66 | CrossoverPolicy crossoverPolicy, double crossoverRate, |
| 67 | MutationPolicy mutationPolicy, double mutationRate, |
| 68 | SelectionPolicy selectionPolicy) { |
| 69 | if (crossoverRate < 0 || crossoverRate > 1) { |
| 70 | throw new IllegalArgumentException("crossoverRate must be between 0 and 1"); |
| 71 | } |
| 72 | if (mutationRate < 0 || mutationRate > 1) { |
| 73 | throw new IllegalArgumentException("mutationRate must be between 0 and 1"); |
| 74 | } |
| 75 | this.crossoverPolicy = crossoverPolicy; |
| 76 | this.crossoverRate = crossoverRate; |
| 77 | this.mutationPolicy = mutationPolicy; |
| 78 | this.mutationRate = mutationRate; |
| 79 | this.selectionPolicy = selectionPolicy; |
| 80 | } |
| 81 | |
| 82 | /** |
| 83 | * Set the (static) random generator. |
| 84 | * |
| 85 | * @param random random generator |
| 86 | */ |
| 87 | public static synchronized void setRandomGenerator(RandomGenerator random) { |
| 88 | randomGenerator = random; |
| 89 | } |
| 90 | |
| 91 | /** |
| 92 | * Returns the (static) random generator. |
| 93 | * |
| 94 | * @return the static random generator shared by GA implementation classes |
| 95 | */ |
| 96 | public static synchronized RandomGenerator getRandomGenerator() { |
| 97 | return randomGenerator; |
| 98 | } |
| 99 | |
| 100 | /** |
| 101 | * Evolve the given population. Evolution stops when the stopping condition |
| 102 | * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved} |
| 103 | * property with the number of generations evolved before the StoppingCondition |
| 104 | * is satisfied. |
| 105 | * |
| 106 | * @param initial the initial, seed population. |
| 107 | * @param condition the stopping condition used to stop evolution. |
| 108 | * @return the population that satisfies the stopping condition. |
| 109 | */ |
| 110 | public Population evolve(Population initial, StoppingCondition condition) { |
| 111 | Population current = initial; |
| 112 | generationsEvolved = 0; |
| 113 | while (!condition.isSatisfied(current)) { |
| 114 | current = nextGeneration(current); |
| 115 | generationsEvolved++; |
| 116 | } |
| 117 | return current; |
| 118 | } |
| 119 | |
| 120 | /** |
| 121 | * <p>Evolve the given population into the next generation.</p> |
| 122 | * <p><ol> |
| 123 | * <li>Get nextGeneration population to fill from <code>current</code> |
| 124 | * generation, using its nextGeneration method</li> |
| 125 | * <li>Loop until new generation is filled:</li> |
| 126 | * <ul><li>Apply configured SelectionPolicy to select a pair of parents |
| 127 | * from <code>current</code></li> |
| 128 | * <li>With probability = {@link #getCrossoverRate()}, apply |
| 129 | * configured {@link CrossoverPolicy} to parents</li> |
| 130 | * <li>With probability = {@link #getMutationRate()}, apply |
| 131 | * configured {@link MutationPolicy} to each of the offspring</li> |
| 132 | * <li>Add offspring individually to nextGeneration, |
| 133 | * space permitting</li> |
| 134 | * </ul> |
| 135 | * <li>Return nextGeneration</li> |
| 136 | * </ol> |
| 137 | * </p> |
| 138 | * |
| 139 | * @param current the current population. |
| 140 | * @return the population for the next generation. |
| 141 | */ |
| 142 | public Population nextGeneration(Population current) { |
| 143 | Population nextGeneration = current.nextGeneration(); |
| 144 | |
| 145 | RandomGenerator randGen = getRandomGenerator(); |
| 146 | |
| 147 | while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { |
| 148 | // select parent chromosomes |
| 149 | ChromosomePair pair = getSelectionPolicy().select(current); |
| 150 | |
| 151 | // crossover? |
| 152 | if (randGen.nextDouble() < getCrossoverRate()) { |
| 153 | // apply crossover policy to create two offspring |
| 154 | pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond()); |
| 155 | } |
| 156 | |
| 157 | // mutation? |
| 158 | if (randGen.nextDouble() < getMutationRate()) { |
| 159 | // apply mutation policy to the chromosomes |
| 160 | pair = new ChromosomePair( |
| 161 | getMutationPolicy().mutate(pair.getFirst()), |
| 162 | getMutationPolicy().mutate(pair.getSecond())); |
| 163 | } |
| 164 | |
| 165 | // add the first chromosome to the population |
| 166 | nextGeneration.addChromosome(pair.getFirst()); |
| 167 | // is there still a place for the second chromosome? |
| 168 | if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { |
| 169 | // add the second chromosome to the population |
| 170 | nextGeneration.addChromosome(pair.getSecond()); |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | return nextGeneration; |
| 175 | } |
| 176 | |
| 177 | /** |
| 178 | * Returns the crossover policy. |
| 179 | * @return crossover policy |
| 180 | */ |
| 181 | public CrossoverPolicy getCrossoverPolicy() { |
| 182 | return crossoverPolicy; |
| 183 | } |
| 184 | |
| 185 | /** |
| 186 | * Returns the crossover rate. |
| 187 | * @return crossover rate |
| 188 | */ |
| 189 | public double getCrossoverRate() { |
| 190 | return crossoverRate; |
| 191 | } |
| 192 | |
| 193 | /** |
| 194 | * Returns the mutation policy. |
| 195 | * @return mutation policy |
| 196 | */ |
| 197 | public MutationPolicy getMutationPolicy() { |
| 198 | return mutationPolicy; |
| 199 | } |
| 200 | |
| 201 | /** |
| 202 | * Returns the mutation rate. |
| 203 | * @return mutation rate |
| 204 | */ |
| 205 | public double getMutationRate() { |
| 206 | return mutationRate; |
| 207 | } |
| 208 | |
| 209 | /** |
| 210 | * Returns the selection policy. |
| 211 | * @return selection policy |
| 212 | */ |
| 213 | public SelectionPolicy getSelectionPolicy() { |
| 214 | return selectionPolicy; |
| 215 | } |
| 216 | |
| 217 | /** |
| 218 | * Returns the number of generations evolved to |
| 219 | * reach {@link StoppingCondition} in the last run. |
| 220 | * |
| 221 | * @return number of generations evolved |
| 222 | * @since 2.1 |
| 223 | */ |
| 224 | public int getGenerationsEvolved() { |
| 225 | return generationsEvolved; |
| 226 | } |
| 227 | |
| 228 | } |