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 */
017package org.apache.commons.math3.genetics;
018
019import org.apache.commons.math3.exception.OutOfRangeException;
020import org.apache.commons.math3.exception.util.LocalizedFormats;
021import org.apache.commons.math3.random.RandomGenerator;
022import org.apache.commons.math3.random.JDKRandomGenerator;
023
024/**
025 * Implementation of a genetic algorithm. All factors that govern the operation
026 * of the algorithm can be configured for a specific problem.
027 *
028 * @since 2.0
029 * @version $Id: GeneticAlgorithm.java 1416643 2012-12-03 19:37:14Z tn $
030 */
031public class GeneticAlgorithm {
032
033    /**
034     * Static random number generator shared by GA implementation classes. Set the randomGenerator seed to get
035     * reproducible results. Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative to the default
036     * JDK-provided PRNG.
037     */
038    //@GuardedBy("this")
039    private static RandomGenerator randomGenerator = new JDKRandomGenerator();
040
041    /** the crossover policy used by the algorithm. */
042    private final CrossoverPolicy crossoverPolicy;
043
044    /** the rate of crossover for the algorithm. */
045    private final double crossoverRate;
046
047    /** the mutation policy used by the algorithm. */
048    private final MutationPolicy mutationPolicy;
049
050    /** the rate of mutation for the algorithm. */
051    private final double mutationRate;
052
053    /** the selection policy used by the algorithm. */
054    private final SelectionPolicy selectionPolicy;
055
056    /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */
057    private int generationsEvolved = 0;
058
059    /**
060     * Create a new genetic algorithm.
061     * @param crossoverPolicy The {@link CrossoverPolicy}
062     * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
063     * @param mutationPolicy The {@link MutationPolicy}
064     * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
065     * @param selectionPolicy The {@link SelectionPolicy}
066     * @throws OutOfRangeException if the crossover or mutation rate is outside the [0, 1] range
067     */
068    public GeneticAlgorithm(final CrossoverPolicy crossoverPolicy,
069                            final double crossoverRate,
070                            final MutationPolicy mutationPolicy,
071                            final double mutationRate,
072                            final SelectionPolicy selectionPolicy) throws OutOfRangeException {
073
074        if (crossoverRate < 0 || crossoverRate > 1) {
075            throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE,
076                                          crossoverRate, 0, 1);
077        }
078        if (mutationRate < 0 || mutationRate > 1) {
079            throw new OutOfRangeException(LocalizedFormats.MUTATION_RATE,
080                                          mutationRate, 0, 1);
081        }
082        this.crossoverPolicy = crossoverPolicy;
083        this.crossoverRate = crossoverRate;
084        this.mutationPolicy = mutationPolicy;
085        this.mutationRate = mutationRate;
086        this.selectionPolicy = selectionPolicy;
087    }
088
089    /**
090     * Set the (static) random generator.
091     *
092     * @param random random generator
093     */
094    public static synchronized void setRandomGenerator(final RandomGenerator random) {
095        randomGenerator = random;
096    }
097
098    /**
099     * Returns the (static) random generator.
100     *
101     * @return the static random generator shared by GA implementation classes
102     */
103    public static synchronized RandomGenerator getRandomGenerator() {
104        return randomGenerator;
105    }
106
107    /**
108     * Evolve the given population. Evolution stops when the stopping condition
109     * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved}
110     * property with the number of generations evolved before the StoppingCondition
111     * is satisfied.
112     *
113     * @param initial the initial, seed population.
114     * @param condition the stopping condition used to stop evolution.
115     * @return the population that satisfies the stopping condition.
116     */
117    public Population evolve(final Population initial, final StoppingCondition condition) {
118        Population current = initial;
119        generationsEvolved = 0;
120        while (!condition.isSatisfied(current)) {
121            current = nextGeneration(current);
122            generationsEvolved++;
123        }
124        return current;
125    }
126
127    /**
128     * Evolve the given population into the next generation.
129     * <p>
130     * <ol>
131     *  <li>Get nextGeneration population to fill from <code>current</code>
132     *      generation, using its nextGeneration method</li>
133     *  <li>Loop until new generation is filled:</li>
134     *  <ul><li>Apply configured SelectionPolicy to select a pair of parents
135     *          from <code>current</code></li>
136     *      <li>With probability = {@link #getCrossoverRate()}, apply
137     *          configured {@link CrossoverPolicy} to parents</li>
138     *      <li>With probability = {@link #getMutationRate()}, apply
139     *          configured {@link MutationPolicy} to each of the offspring</li>
140     *      <li>Add offspring individually to nextGeneration,
141     *          space permitting</li>
142     *  </ul>
143     *  <li>Return nextGeneration</li>
144     * </ol>
145     *
146     * @param current the current population.
147     * @return the population for the next generation.
148     */
149    public Population nextGeneration(final Population current) {
150        Population nextGeneration = current.nextGeneration();
151
152        RandomGenerator randGen = getRandomGenerator();
153
154        while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
155            // select parent chromosomes
156            ChromosomePair pair = getSelectionPolicy().select(current);
157
158            // crossover?
159            if (randGen.nextDouble() < getCrossoverRate()) {
160                // apply crossover policy to create two offspring
161                pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond());
162            }
163
164            // mutation?
165            if (randGen.nextDouble() < getMutationRate()) {
166                // apply mutation policy to the chromosomes
167                pair = new ChromosomePair(
168                    getMutationPolicy().mutate(pair.getFirst()),
169                    getMutationPolicy().mutate(pair.getSecond()));
170            }
171
172            // add the first chromosome to the population
173            nextGeneration.addChromosome(pair.getFirst());
174            // is there still a place for the second chromosome?
175            if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
176                // add the second chromosome to the population
177                nextGeneration.addChromosome(pair.getSecond());
178            }
179        }
180
181        return nextGeneration;
182    }
183
184    /**
185     * Returns the crossover policy.
186     * @return crossover policy
187     */
188    public CrossoverPolicy getCrossoverPolicy() {
189        return crossoverPolicy;
190    }
191
192    /**
193     * Returns the crossover rate.
194     * @return crossover rate
195     */
196    public double getCrossoverRate() {
197        return crossoverRate;
198    }
199
200    /**
201     * Returns the mutation policy.
202     * @return mutation policy
203     */
204    public MutationPolicy getMutationPolicy() {
205        return mutationPolicy;
206    }
207
208    /**
209     * Returns the mutation rate.
210     * @return mutation rate
211     */
212    public double getMutationRate() {
213        return mutationRate;
214    }
215
216    /**
217     * Returns the selection policy.
218     * @return selection policy
219     */
220    public SelectionPolicy getSelectionPolicy() {
221        return selectionPolicy;
222    }
223
224    /**
225     * Returns the number of generations evolved to reach {@link StoppingCondition} in the last run.
226     *
227     * @return number of generations evolved
228     * @since 2.1
229     */
230    public int getGenerationsEvolved() {
231        return generationsEvolved;
232    }
233
234}