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: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $ 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 /** 41 * Set the (static) random generator. 42 * 43 * @param random random generator 44 */ 45 public synchronized static void setRandomGenerator(RandomGenerator random) { 46 randomGenerator = random; 47 } 48 49 /** 50 * Returns the (static) random generator. 51 * 52 * @return the static random generator shared by GA implementation classes 53 */ 54 public synchronized static RandomGenerator getRandomGenerator() { 55 return randomGenerator; 56 } 57 58 /** the crossover policy used by the algorithm. */ 59 private final CrossoverPolicy crossoverPolicy; 60 61 /** the rate of crossover for the algorithm. */ 62 private final double crossoverRate; 63 64 /** the mutation policy used by the algorithm. */ 65 private final MutationPolicy mutationPolicy; 66 67 /** the rate of mutation for the algorithm. */ 68 private final double mutationRate; 69 70 /** the selection policy used by the algorithm. */ 71 private final SelectionPolicy selectionPolicy; 72 73 /** 74 * @param crossoverPolicy The {@link CrossoverPolicy} 75 * @param crossoverRate The crossover rate as a percentage (0-1 inclusive) 76 * @param mutationPolicy The {@link MutationPolicy} 77 * @param mutationRate The mutation rate as a percentage (0-1 inclusive) 78 * @param selectionPolicy The {@link SelectionPolicy} 79 */ 80 public GeneticAlgorithm( 81 CrossoverPolicy crossoverPolicy, double crossoverRate, 82 MutationPolicy mutationPolicy, double mutationRate, 83 SelectionPolicy selectionPolicy) { 84 if (crossoverRate < 0 || crossoverRate > 1) { 85 throw new IllegalArgumentException("crossoverRate must be between 0 and 1"); 86 } 87 if (mutationRate < 0 || mutationRate > 1) { 88 throw new IllegalArgumentException("mutationRate must be between 0 and 1"); 89 } 90 this.crossoverPolicy = crossoverPolicy; 91 this.crossoverRate = crossoverRate; 92 this.mutationPolicy = mutationPolicy; 93 this.mutationRate = mutationRate; 94 this.selectionPolicy = selectionPolicy; 95 } 96 97 /** 98 * Evolve the given population. Evolution stops when the stopping condition 99 * is satisfied. 100 * 101 * @param initial the initial, seed population. 102 * @param condition the stopping condition used to stop evolution. 103 * @return the population that satisfies the stopping condition. 104 */ 105 public Population evolve(Population initial, StoppingCondition condition) { 106 Population current = initial; 107 while (!condition.isSatisfied(current)) { 108 current = nextGeneration(current); 109 } 110 return current; 111 } 112 113 /** 114 * <p>Evolve the given population into the next generation.</p> 115 * <p><ol> 116 * <li>Get nextGeneration population to fill from <code>current</code> 117 * generation, using its nextGeneration method</li> 118 * <li>Loop until new generation is filled:</li> 119 * <ul><li>Apply configured SelectionPolicy to select a pair of parents 120 * from <code>current</code></li> 121 * <li>With probability = {@link #getCrossoverRate()}, apply 122 * configured {@link CrossoverPolicy} to parents</li> 123 * <li>With probability = {@link #getMutationRate()}, apply 124 * configured {@link MutationPolicy} to each of the offspring</li> 125 * <li>Add offspring individually to nextGeneration, 126 * space permitting</li> 127 * </ul> 128 * <li>Return nextGeneration</li> 129 * </ol> 130 * </p> 131 * 132 * @param current the current population. 133 * @return the population for the next generation. 134 */ 135 public Population nextGeneration(Population current) { 136 Population nextGeneration = current.nextGeneration(); 137 138 RandomGenerator randGen = getRandomGenerator(); 139 140 while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { 141 // select parent chromosomes 142 ChromosomePair pair = getSelectionPolicy().select(current); 143 144 // crossover? 145 if (randGen.nextDouble() < getCrossoverRate()) { 146 // apply crossover policy to create two offspring 147 pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond()); 148 } 149 150 // mutation? 151 if (randGen.nextDouble() < getMutationRate()) { 152 // apply mutation policy to the chromosomes 153 pair = new ChromosomePair( 154 getMutationPolicy().mutate(pair.getFirst()), 155 getMutationPolicy().mutate(pair.getSecond())); 156 } 157 158 // add the first chromosome to the population 159 nextGeneration.addChromosome(pair.getFirst()); 160 // is there still a place for the second chromosome? 161 if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { 162 // add the second chromosome to the population 163 nextGeneration.addChromosome(pair.getSecond()); 164 } 165 } 166 167 return nextGeneration; 168 } 169 170 /** 171 * Returns the crossover policy. 172 * @return crossover policy 173 */ 174 public CrossoverPolicy getCrossoverPolicy() { 175 return crossoverPolicy; 176 } 177 178 /** 179 * Returns the crossover rate. 180 * @return crossover rate 181 */ 182 public double getCrossoverRate() { 183 return crossoverRate; 184 } 185 186 /** 187 * Returns the mutation policy. 188 * @return mutation policy 189 */ 190 public MutationPolicy getMutationPolicy() { 191 return mutationPolicy; 192 } 193 194 /** 195 * Returns the mutation rate. 196 * @return mutation rate 197 */ 198 public double getMutationRate() { 199 return mutationRate; 200 } 201 202 /** 203 * Returns the selection policy. 204 * @return selection policy 205 */ 206 public SelectionPolicy getSelectionPolicy() { 207 return selectionPolicy; 208 } 209 210 }