    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.math3.genetics;
    018
    019    import org.apache.commons.math3.exception.OutOfRangeException;
    020    import org.apache.commons.math3.exception.util.LocalizedFormats;
    021    import org.apache.commons.math3.random.RandomGenerator;
    022    import 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     */
    031    public 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    }