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