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     */
017    package org.apache.commons.math.genetics;
018    
019    import org.apache.commons.math.random.RandomGenerator;
020    import org.apache.commons.math.random.JDKRandomGenerator;
021    
022    /**
023     * Implementation of a genetic algorithm. All factors that govern the operation
024     * of the algorithm can be configured for a specific problem.
025     *
026     * @since 2.0
027     * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
028     */
029    public class GeneticAlgorithm {
030    
031        /**
032         * Static random number generator shared by GA implementation classes.
033         * Set the randomGenerator seed to get reproducible results.  
034         * Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative
035         * to the default JDK-provided PRNG.
036         */
037        //@GuardedBy("this")
038        private static RandomGenerator randomGenerator = new JDKRandomGenerator();
039        
040        /**
041         * Set the (static) random generator.
042         * 
043         * @param random random generator
044         */
045        public synchronized static void setRandomGenerator(RandomGenerator random) {
046            randomGenerator = random;
047        }
048        
049        /**
050         * Returns the (static) random generator.
051         * 
052         * @return the static random generator shared by GA implementation classes
053         */
054        public synchronized static RandomGenerator getRandomGenerator() {
055            return randomGenerator;
056        }
057          
058        /** the crossover policy used by the algorithm. */
059        private final CrossoverPolicy crossoverPolicy;
060    
061        /** the rate of crossover for the algorithm. */
062        private final double crossoverRate;
063    
064        /** the mutation policy used by the algorithm. */
065        private final MutationPolicy mutationPolicy;
066    
067        /** the rate of mutation for the algorithm. */
068        private final double mutationRate;
069    
070        /** the selection policy used by the algorithm. */
071        private final SelectionPolicy selectionPolicy;
072        
073        /**
074         * @param crossoverPolicy The {@link CrossoverPolicy}
075         * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
076         * @param mutationPolicy The {@link MutationPolicy}
077         * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
078         * @param selectionPolicy The {@link SelectionPolicy}
079         */
080        public GeneticAlgorithm(
081                CrossoverPolicy crossoverPolicy, double crossoverRate,
082                MutationPolicy mutationPolicy, double mutationRate,
083                SelectionPolicy selectionPolicy) {
084            if (crossoverRate < 0 || crossoverRate > 1) {
085                throw new IllegalArgumentException("crossoverRate must be between 0 and 1");
086            }
087            if (mutationRate < 0 || mutationRate > 1) {
088                throw new IllegalArgumentException("mutationRate must be between 0 and 1");
089            }
090            this.crossoverPolicy = crossoverPolicy;
091            this.crossoverRate = crossoverRate;
092            this.mutationPolicy = mutationPolicy;
093            this.mutationRate = mutationRate;
094            this.selectionPolicy = selectionPolicy;
095        }
096        
097        /**
098         * Evolve the given population. Evolution stops when the stopping condition
099         * 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    }