1dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond/*
2dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Licensed to the Apache Software Foundation (ASF) under one or more
3dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * contributor license agreements.  See the NOTICE file distributed with
4dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * this work for additional information regarding copyright ownership.
5dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * The ASF licenses this file to You under the Apache License, Version 2.0
6dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * (the "License"); you may not use this file except in compliance with
7dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * the License.  You may obtain a copy of the License at
8dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond *
9dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond *      http://www.apache.org/licenses/LICENSE-2.0
10dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond *
11dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Unless required by applicable law or agreed to in writing, software
12dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * distributed under the License is distributed on an "AS IS" BASIS,
13dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * See the License for the specific language governing permissions and
15dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * limitations under the License.
16dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */
17dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondpackage org.apache.commons.math.genetics;
18dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
19dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.random.RandomGenerator;
20dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.random.JDKRandomGenerator;
21dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
22dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond/**
23dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Implementation of a genetic algorithm. All factors that govern the operation
24dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * of the algorithm can be configured for a specific problem.
25dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond *
26dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @since 2.0
27dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @version $Revision: 925812 $ $Date: 2010-03-21 16:49:31 +0100 (dim. 21 mars 2010) $
28dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */
29dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondpublic class GeneticAlgorithm {
30dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
31dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
32dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Static random number generator shared by GA implementation classes.
33dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Set the randomGenerator seed to get reproducible results.
34dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative
35dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * to the default JDK-provided PRNG.
36dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
37dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    //@GuardedBy("this")
38dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private static RandomGenerator randomGenerator = new JDKRandomGenerator();
39dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
40dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /** the crossover policy used by the algorithm. */
41dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private final CrossoverPolicy crossoverPolicy;
42dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
43dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /** the rate of crossover for the algorithm. */
44dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private final double crossoverRate;
45dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
46dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /** the mutation policy used by the algorithm. */
47dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private final MutationPolicy mutationPolicy;
48dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
49dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /** the rate of mutation for the algorithm. */
50dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private final double mutationRate;
51dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
52dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /** the selection policy used by the algorithm. */
53dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private final SelectionPolicy selectionPolicy;
54dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
55dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */
56dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    private int generationsEvolved = 0;
57dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
58dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
59dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param crossoverPolicy The {@link CrossoverPolicy}
60dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
61dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param mutationPolicy The {@link MutationPolicy}
62dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
63dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param selectionPolicy The {@link SelectionPolicy}
64dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
65dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public GeneticAlgorithm(
66dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            CrossoverPolicy crossoverPolicy, double crossoverRate,
67dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            MutationPolicy mutationPolicy, double mutationRate,
68dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            SelectionPolicy selectionPolicy) {
69dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        if (crossoverRate < 0 || crossoverRate > 1) {
70dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            throw new IllegalArgumentException("crossoverRate must be between 0 and 1");
71dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        }
72dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        if (mutationRate < 0 || mutationRate > 1) {
73dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            throw new IllegalArgumentException("mutationRate must be between 0 and 1");
74dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        }
75dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        this.crossoverPolicy = crossoverPolicy;
76dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        this.crossoverRate = crossoverRate;
77dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        this.mutationPolicy = mutationPolicy;
78dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        this.mutationRate = mutationRate;
79dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        this.selectionPolicy = selectionPolicy;
80dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
81dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
82dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
83dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Set the (static) random generator.
84dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *
85dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param random random generator
86dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
87dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public static synchronized void setRandomGenerator(RandomGenerator random) {
88dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        randomGenerator = random;
89dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
90dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
91dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
92dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the (static) random generator.
93dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *
94dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return the static random generator shared by GA implementation classes
95dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
96dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public static synchronized RandomGenerator getRandomGenerator() {
97dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return randomGenerator;
98dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
99dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
100dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
101dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Evolve the given population. Evolution stops when the stopping condition
102dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved}
103dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * property with the number of generations evolved before the StoppingCondition
104dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * is satisfied.
105dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *
106dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param initial the initial, seed population.
107dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param condition the stopping condition used to stop evolution.
108dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return the population that satisfies the stopping condition.
109dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
110dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public Population evolve(Population initial, StoppingCondition condition) {
111dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        Population current = initial;
112dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        generationsEvolved = 0;
113dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        while (!condition.isSatisfied(current)) {
114dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            current = nextGeneration(current);
115dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            generationsEvolved++;
116dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        }
117dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return current;
118dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
119dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
120dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
121dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * <p>Evolve the given population into the next generation.</p>
122dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * <p><ol>
123dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *    <li>Get nextGeneration population to fill from <code>current</code>
124dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *        generation, using its nextGeneration method</li>
125dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *    <li>Loop until new generation is filled:</li>
126dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *    <ul><li>Apply configured SelectionPolicy to select a pair of parents
127dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *            from <code>current</code></li>
128dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *        <li>With probability = {@link #getCrossoverRate()}, apply
129dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *            configured {@link CrossoverPolicy} to parents</li>
130dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *        <li>With probability = {@link #getMutationRate()}, apply
131dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *            configured {@link MutationPolicy} to each of the offspring</li>
132dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *        <li>Add offspring individually to nextGeneration,
133dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *            space permitting</li>
134dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *    </ul>
135dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *    <li>Return nextGeneration</li>
136dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *    </ol>
137dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * </p>
138dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *
139dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @param current the current population.
140dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return the population for the next generation.
141dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
142dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public Population nextGeneration(Population current) {
143dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        Population nextGeneration = current.nextGeneration();
144dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
145dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        RandomGenerator randGen = getRandomGenerator();
146dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
147dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
148dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            // select parent chromosomes
149dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            ChromosomePair pair = getSelectionPolicy().select(current);
150dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
151dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            // crossover?
152dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            if (randGen.nextDouble() < getCrossoverRate()) {
153dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                // apply crossover policy to create two offspring
154dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond());
155dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            }
156dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
157dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            // mutation?
158dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            if (randGen.nextDouble() < getMutationRate()) {
159dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                // apply mutation policy to the chromosomes
160dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                pair = new ChromosomePair(
161dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                    getMutationPolicy().mutate(pair.getFirst()),
162dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                    getMutationPolicy().mutate(pair.getSecond()));
163dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            }
164dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
165dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            // add the first chromosome to the population
166dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            nextGeneration.addChromosome(pair.getFirst());
167dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            // is there still a place for the second chromosome?
168dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
169dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                // add the second chromosome to the population
170dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond                nextGeneration.addChromosome(pair.getSecond());
171dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond            }
172dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        }
173dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
174dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return nextGeneration;
175dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
176dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
177dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
178dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the crossover policy.
179dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return crossover policy
180dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
181dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public CrossoverPolicy getCrossoverPolicy() {
182dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return crossoverPolicy;
183dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
184dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
185dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
186dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the crossover rate.
187dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return crossover rate
188dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
189dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public double getCrossoverRate() {
190dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return crossoverRate;
191dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
192dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
193dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
194dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the mutation policy.
195dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return mutation policy
196dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
197dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public MutationPolicy getMutationPolicy() {
198dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return mutationPolicy;
199dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
200dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
201dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
202dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the mutation rate.
203dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return mutation rate
204dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
205dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public double getMutationRate() {
206dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return mutationRate;
207dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
208dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
209dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
210dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the selection policy.
211dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return selection policy
212dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
213dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public SelectionPolicy getSelectionPolicy() {
214dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return selectionPolicy;
215dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
216dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
217dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    /**
218dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * Returns the number of generations evolved to
219dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * reach {@link StoppingCondition} in the last run.
220dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     *
221dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @return number of generations evolved
222dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     * @since 2.1
223dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond     */
224dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    public int getGenerationsEvolved() {
225dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond        return generationsEvolved;
226dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond    }
227dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond
228dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond}
229