001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.math.genetics; 018 019 import org.apache.commons.math.random.RandomGenerator; 020 import org.apache.commons.math.random.JDKRandomGenerator; 021 022 /** 023 * Implementation of a genetic algorithm. All factors that govern the operation 024 * of the algorithm can be configured for a specific problem. 025 * 026 * @since 2.0 027 * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $ 028 */ 029 public class GeneticAlgorithm { 030 031 /** 032 * Static random number generator shared by GA implementation classes. 033 * Set the randomGenerator seed to get reproducible results. 034 * Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative 035 * to the default JDK-provided PRNG. 036 */ 037 //@GuardedBy("this") 038 private static RandomGenerator randomGenerator = new JDKRandomGenerator(); 039 040 /** 041 * Set the (static) random generator. 042 * 043 * @param random random generator 044 */ 045 public synchronized static void setRandomGenerator(RandomGenerator random) { 046 randomGenerator = random; 047 } 048 049 /** 050 * Returns the (static) random generator. 051 * 052 * @return the static random generator shared by GA implementation classes 053 */ 054 public synchronized static RandomGenerator getRandomGenerator() { 055 return randomGenerator; 056 } 057 058 /** the crossover policy used by the algorithm. */ 059 private final CrossoverPolicy crossoverPolicy; 060 061 /** the rate of crossover for the algorithm. */ 062 private final double crossoverRate; 063 064 /** the mutation policy used by the algorithm. */ 065 private final MutationPolicy mutationPolicy; 066 067 /** the rate of mutation for the algorithm. */ 068 private final double mutationRate; 069 070 /** the selection policy used by the algorithm. */ 071 private final SelectionPolicy selectionPolicy; 072 073 /** 074 * @param crossoverPolicy The {@link CrossoverPolicy} 075 * @param crossoverRate The crossover rate as a percentage (0-1 inclusive) 076 * @param mutationPolicy The {@link MutationPolicy} 077 * @param mutationRate The mutation rate as a percentage (0-1 inclusive) 078 * @param selectionPolicy The {@link SelectionPolicy} 079 */ 080 public GeneticAlgorithm( 081 CrossoverPolicy crossoverPolicy, double crossoverRate, 082 MutationPolicy mutationPolicy, double mutationRate, 083 SelectionPolicy selectionPolicy) { 084 if (crossoverRate < 0 || crossoverRate > 1) { 085 throw new IllegalArgumentException("crossoverRate must be between 0 and 1"); 086 } 087 if (mutationRate < 0 || mutationRate > 1) { 088 throw new IllegalArgumentException("mutationRate must be between 0 and 1"); 089 } 090 this.crossoverPolicy = crossoverPolicy; 091 this.crossoverRate = crossoverRate; 092 this.mutationPolicy = mutationPolicy; 093 this.mutationRate = mutationRate; 094 this.selectionPolicy = selectionPolicy; 095 } 096 097 /** 098 * Evolve the given population. Evolution stops when the stopping condition 099 * 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 }