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