    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: 925812 $ $Date: 2010-03-21 16:49:31 +0100 (dim. 21 mars 2010) $
    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        /** the crossover policy used by the algorithm. */
    041        private final CrossoverPolicy crossoverPolicy;
    042
    043        /** the rate of crossover for the algorithm. */
    044        private final double crossoverRate;
    045
    046        /** the mutation policy used by the algorithm. */
    047        private final MutationPolicy mutationPolicy;
    048
    049        /** the rate of mutation for the algorithm. */
    050        private final double mutationRate;
    051
    052        /** the selection policy used by the algorithm. */
    053        private final SelectionPolicy selectionPolicy;
    054
    055        /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */
    056        private int generationsEvolved = 0;
    057
    058        /**
    059         * @param crossoverPolicy The {@link CrossoverPolicy}
    060         * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
    061         * @param mutationPolicy The {@link MutationPolicy}
    062         * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
    063         * @param selectionPolicy The {@link SelectionPolicy}
    064         */
    065        public GeneticAlgorithm(
    066                CrossoverPolicy crossoverPolicy, double crossoverRate,
    067                MutationPolicy mutationPolicy, double mutationRate,
    068                SelectionPolicy selectionPolicy) {
    069            if (crossoverRate < 0 || crossoverRate > 1) {
    070                throw new IllegalArgumentException("crossoverRate must be between 0 and 1");
    071            }
    072            if (mutationRate < 0 || mutationRate > 1) {
    073                throw new IllegalArgumentException("mutationRate must be between 0 and 1");
    074            }
    075            this.crossoverPolicy = crossoverPolicy;
    076            this.crossoverRate = crossoverRate;
    077            this.mutationPolicy = mutationPolicy;
    078            this.mutationRate = mutationRate;
    079            this.selectionPolicy = selectionPolicy;
    080        }
    081
    082        /**
    083         * Set the (static) random generator.
    084         *
    085         * @param random random generator
    086         */
    087        public static synchronized void setRandomGenerator(RandomGenerator random) {
    088            randomGenerator = random;
    089        }
    090
    091        /**
    092         * Returns the (static) random generator.
    093         *
    094         * @return the static random generator shared by GA implementation classes
    095         */
    096        public static synchronized RandomGenerator getRandomGenerator() {
    097            return randomGenerator;
    098        }
    099
    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    }