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 */
17package org.apache.commons.math.genetics;
18
19import org.apache.commons.math.random.RandomGenerator;
20import 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: 925812 $ $Date: 2010-03-21 16:49:31 +0100 (dim. 21 mars 2010) $
28 */
29public 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    /** 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 = 0;
57
58    /**
59     * @param crossoverPolicy The {@link CrossoverPolicy}
60     * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
61     * @param mutationPolicy The {@link MutationPolicy}
62     * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
63     * @param selectionPolicy The {@link SelectionPolicy}
64     */
65    public GeneticAlgorithm(
66            CrossoverPolicy crossoverPolicy, double crossoverRate,
67            MutationPolicy mutationPolicy, double mutationRate,
68            SelectionPolicy selectionPolicy) {
69        if (crossoverRate < 0 || crossoverRate > 1) {
70            throw new IllegalArgumentException("crossoverRate must be between 0 and 1");
71        }
72        if (mutationRate < 0 || mutationRate > 1) {
73            throw new IllegalArgumentException("mutationRate must be between 0 and 1");
74        }
75        this.crossoverPolicy = crossoverPolicy;
76        this.crossoverRate = crossoverRate;
77        this.mutationPolicy = mutationPolicy;
78        this.mutationRate = mutationRate;
79        this.selectionPolicy = selectionPolicy;
80    }
81
82    /**
83     * Set the (static) random generator.
84     *
85     * @param random random generator
86     */
87    public static synchronized void setRandomGenerator(RandomGenerator random) {
88        randomGenerator = random;
89    }
90
91    /**
92     * Returns the (static) random generator.
93     *
94     * @return the static random generator shared by GA implementation classes
95     */
96    public static synchronized RandomGenerator getRandomGenerator() {
97        return randomGenerator;
98    }
99
100    /**
101     * Evolve the given population. Evolution stops when the stopping condition
102     * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved}
103     * property with the number of generations evolved before the StoppingCondition
104     * is satisfied.
105     *
106     * @param initial the initial, seed population.
107     * @param condition the stopping condition used to stop evolution.
108     * @return the population that satisfies the stopping condition.
109     */
110    public Population evolve(Population initial, StoppingCondition condition) {
111        Population current = initial;
112        generationsEvolved = 0;
113        while (!condition.isSatisfied(current)) {
114            current = nextGeneration(current);
115            generationsEvolved++;
116        }
117        return current;
118    }
119
120    /**
121     * <p>Evolve the given population into the next generation.</p>
122     * <p><ol>
123     *    <li>Get nextGeneration population to fill from <code>current</code>
124     *        generation, using its nextGeneration method</li>
125     *    <li>Loop until new generation is filled:</li>
126     *    <ul><li>Apply configured SelectionPolicy to select a pair of parents
127     *            from <code>current</code></li>
128     *        <li>With probability = {@link #getCrossoverRate()}, apply
129     *            configured {@link CrossoverPolicy} to parents</li>
130     *        <li>With probability = {@link #getMutationRate()}, apply
131     *            configured {@link MutationPolicy} to each of the offspring</li>
132     *        <li>Add offspring individually to nextGeneration,
133     *            space permitting</li>
134     *    </ul>
135     *    <li>Return nextGeneration</li>
136     *    </ol>
137     * </p>
138     *
139     * @param current the current population.
140     * @return the population for the next generation.
141     */
142    public Population nextGeneration(Population current) {
143        Population nextGeneration = current.nextGeneration();
144
145        RandomGenerator randGen = getRandomGenerator();
146
147        while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
148            // select parent chromosomes
149            ChromosomePair pair = getSelectionPolicy().select(current);
150
151            // crossover?
152            if (randGen.nextDouble() < getCrossoverRate()) {
153                // apply crossover policy to create two offspring
154                pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond());
155            }
156
157            // mutation?
158            if (randGen.nextDouble() < getMutationRate()) {
159                // apply mutation policy to the chromosomes
160                pair = new ChromosomePair(
161                    getMutationPolicy().mutate(pair.getFirst()),
162                    getMutationPolicy().mutate(pair.getSecond()));
163            }
164
165            // add the first chromosome to the population
166            nextGeneration.addChromosome(pair.getFirst());
167            // is there still a place for the second chromosome?
168            if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
169                // add the second chromosome to the population
170                nextGeneration.addChromosome(pair.getSecond());
171            }
172        }
173
174        return nextGeneration;
175    }
176
177    /**
178     * Returns the crossover policy.
179     * @return crossover policy
180     */
181    public CrossoverPolicy getCrossoverPolicy() {
182        return crossoverPolicy;
183    }
184
185    /**
186     * Returns the crossover rate.
187     * @return crossover rate
188     */
189    public double getCrossoverRate() {
190        return crossoverRate;
191    }
192
193    /**
194     * Returns the mutation policy.
195     * @return mutation policy
196     */
197    public MutationPolicy getMutationPolicy() {
198        return mutationPolicy;
199    }
200
201    /**
202     * Returns the mutation rate.
203     * @return mutation rate
204     */
205    public double getMutationRate() {
206        return mutationRate;
207    }
208
209    /**
210     * Returns the selection policy.
211     * @return selection policy
212     */
213    public SelectionPolicy getSelectionPolicy() {
214        return selectionPolicy;
215    }
216
217    /**
218     * Returns the number of generations evolved to
219     * reach {@link StoppingCondition} in the last run.
220     *
221     * @return number of generations evolved
222     * @since 2.1
223     */
224    public int getGenerationsEvolved() {
225        return generationsEvolved;
226    }
227
228}
229