View Javadoc
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 }