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 */ GeneticAlgorithm( CrossoverPolicy crossoverPolicy, double crossoverRate, MutationPolicy mutationPolicy, double mutationRate, SelectionPolicy selectionPolicy)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 */ setRandomGenerator(RandomGenerator random)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 */ getRandomGenerator()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 */ evolve(Population initial, StoppingCondition condition)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 */ nextGeneration(Population current)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 */ getCrossoverPolicy()181 public CrossoverPolicy getCrossoverPolicy() { 182 return crossoverPolicy; 183 } 184 185 /** 186 * Returns the crossover rate. 187 * @return crossover rate 188 */ getCrossoverRate()189 public double getCrossoverRate() { 190 return crossoverRate; 191 } 192 193 /** 194 * Returns the mutation policy. 195 * @return mutation policy 196 */ getMutationPolicy()197 public MutationPolicy getMutationPolicy() { 198 return mutationPolicy; 199 } 200 201 /** 202 * Returns the mutation rate. 203 * @return mutation rate 204 */ getMutationRate()205 public double getMutationRate() { 206 return mutationRate; 207 } 208 209 /** 210 * Returns the selection policy. 211 * @return selection policy 212 */ getSelectionPolicy()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 */ getGenerationsEvolved()224 public int getGenerationsEvolved() { 225 return generationsEvolved; 226 } 227 228 } 229