GeneticAlgorithm.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.math4.legacy.genetics;

  19. import org.apache.commons.math4.legacy.exception.OutOfRangeException;
  20. import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
  21. import org.apache.commons.rng.simple.RandomSource;
  22. import org.apache.commons.rng.UniformRandomProvider;

  24. /**
  25.  * Implementation of a genetic algorithm. All factors that govern the operation
  26.  * of the algorithm can be configured for a specific problem.
  27.  *
  28.  * @since 2.0
  29.  */
  30. public class GeneticAlgorithm {

  32.     /**
  33.      * Static random number generator shared by GA implementation classes.
  34.      * Use {@link #setRandomGenerator(UniformRandomProvider)} to supply an
  35.      * alternative to the default PRNG, and/or select a specific seed.
  36.      */
  37.     //@GuardedBy("this")
  38.     private static UniformRandomProvider randomGenerator = RandomSource.WELL_19937_C.create();

  40.     /** the crossover policy used by the algorithm. */
  41.     private final CrossoverPolicy crossoverPolicy;

  43.     /** the rate of crossover for the algorithm. */
  44.     private final double crossoverRate;

  46.     /** the mutation policy used by the algorithm. */
  47.     private final MutationPolicy mutationPolicy;

  49.     /** the rate of mutation for the algorithm. */
  50.     private final double mutationRate;

  52.     /** the selection policy used by the algorithm. */
  53.     private final SelectionPolicy selectionPolicy;

  55.     /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */
  56.     private int generationsEvolved;

  58.     /**
  59.      * Create a new genetic algorithm.
  60.      * @param crossoverPolicy The {@link CrossoverPolicy}
  61.      * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
  62.      * @param mutationPolicy The {@link MutationPolicy}
  63.      * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
  64.      * @param selectionPolicy The {@link SelectionPolicy}
  65.      * @throws OutOfRangeException if the crossover or mutation rate is outside the [0, 1] range
  66.      */
  67.     public GeneticAlgorithm(final CrossoverPolicy crossoverPolicy,
  68.                             final double crossoverRate,
  69.                             final MutationPolicy mutationPolicy,
  70.                             final double mutationRate,
  71.                             final SelectionPolicy selectionPolicy) throws OutOfRangeException {

  73.         if (crossoverRate < 0 || crossoverRate > 1) {
  74.             throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE,
  75.                                           crossoverRate, 0, 1);
  76.         }
  77.         if (mutationRate < 0 || mutationRate > 1) {
  78.             throw new OutOfRangeException(LocalizedFormats.MUTATION_RATE,
  79.                                           mutationRate, 0, 1);
  80.         }
  81.         this.crossoverPolicy = crossoverPolicy;
  82.         this.crossoverRate = crossoverRate;
  83.         this.mutationPolicy = mutationPolicy;
  84.         this.mutationRate = mutationRate;
  85.         this.selectionPolicy = selectionPolicy;
  86.     }

  88.     /**
  89.      * Set the (static) random generator.
  90.      *
  91.      * @param random random generator
  92.      */
  93.     public static synchronized void setRandomGenerator(final UniformRandomProvider random) {
  94.         randomGenerator = random;
  95.     }

  97.     /**
  98.      * Returns the (static) random generator.
  99.      *
  100.      * @return the static random generator shared by GA implementation classes
  101.      */
  102.     public static synchronized UniformRandomProvider getRandomGenerator() {
  103.         return randomGenerator;
  104.     }

  106.     /**
  107.      * Evolve the given population. Evolution stops when the stopping condition
  108.      * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved}
  109.      * property with the number of generations evolved before the StoppingCondition
  110.      * is satisfied.
  111.      *
  112.      * @param initial the initial, seed population.
  113.      * @param condition the stopping condition used to stop evolution.
  114.      * @return the population that satisfies the stopping condition.
  115.      */
  116.     public Population evolve(final Population initial, final StoppingCondition condition) {
  117.         Population current = initial;
  118.         generationsEvolved = 0;
  119.         while (!condition.isSatisfied(current)) {
  120.             current = nextGeneration(current);
  121.             generationsEvolved++;
  122.         }
  123.         return current;
  124.     }

  126.     /**
  127.      * Evolve the given population into the next generation.
  128.      * <ol>
  129.      *  <li>Get nextGeneration population to fill from <code>current</code>
  130.      *      generation, using its nextGeneration method</li>
  131.      *  <li>Loop until new generation is filled:
  132.      *  <ul><li>Apply configured SelectionPolicy to select a pair of parents
  133.      *          from <code>current</code></li>
  134.      *      <li>With probability = {@link #getCrossoverRate()}, apply
  135.      *          configured {@link CrossoverPolicy} to parents</li>
  136.      *      <li>With probability = {@link #getMutationRate()}, apply
  137.      *          configured {@link MutationPolicy} to each of the offspring</li>
  138.      *      <li>Add offspring individually to nextGeneration,
  139.      *          space permitting</li>
  140.      *  </ul></li>
  141.      *  <li>Return nextGeneration</li>
  142.      * </ol>
  143.      *
  144.      * @param current the current population.
  145.      * @return the population for the next generation.
  146.      */
  147.     public Population nextGeneration(final Population current) {
  148.         Population nextGeneration = current.nextGeneration();

  150.         UniformRandomProvider randGen = getRandomGenerator();

  152.         while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
  153.             // select parent chromosomes
  154.             ChromosomePair pair = getSelectionPolicy().select(current);

  156.             // crossover?
  157.             if (randGen.nextDouble() < getCrossoverRate()) {
  158.                 // apply crossover policy to create two offspring
  159.                 pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond());
  160.             }

  162.             // mutation?
  163.             if (randGen.nextDouble() < getMutationRate()) {
  164.                 // apply mutation policy to the chromosomes
  165.                 pair = new ChromosomePair(
  166.                     getMutationPolicy().mutate(pair.getFirst()),
  167.                     getMutationPolicy().mutate(pair.getSecond()));
  168.             }

  170.             // add the first chromosome to the population
  171.             nextGeneration.addChromosome(pair.getFirst());
  172.             // is there still a place for the second chromosome?
  173.             if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
  174.                 // add the second chromosome to the population
  175.                 nextGeneration.addChromosome(pair.getSecond());
  176.             }
  177.         }

  179.         return nextGeneration;
  180.     }

  182.     /**
  183.      * Returns the crossover policy.
  184.      * @return crossover policy
  185.      */
  186.     public CrossoverPolicy getCrossoverPolicy() {
  187.         return crossoverPolicy;
  188.     }

  190.     /**
  191.      * Returns the crossover rate.
  192.      * @return crossover rate
  193.      */
  194.     public double getCrossoverRate() {
  195.         return crossoverRate;
  196.     }

  198.     /**
  199.      * Returns the mutation policy.
  200.      * @return mutation policy
  201.      */
  202.     public MutationPolicy getMutationPolicy() {
  203.         return mutationPolicy;
  204.     }

  206.     /**
  207.      * Returns the mutation rate.
  208.      * @return mutation rate
  209.      */
  210.     public double getMutationRate() {
  211.         return mutationRate;
  212.     }

  214.     /**
  215.      * Returns the selection policy.
  216.      * @return selection policy
  217.      */
  218.     public SelectionPolicy getSelectionPolicy() {
  219.         return selectionPolicy;
  220.     }

  222.     /**
  223.      * Returns the number of generations evolved to reach {@link StoppingCondition} in the last run.
  224.      *
  225.      * @return number of generations evolved
  226.      * @since 2.1
  227.      */
  228.     public int getGenerationsEvolved() {
  229.         return generationsEvolved;
  230.     }
  231. }
Created with JaCoCo 0.8.10.202304240956Code Coverage Report for Apache Commons Math 4.0-SNAPSHOT