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 }