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 }