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.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 }