diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math/genetics')
22 files changed, 1925 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math/genetics/AbstractListChromosome.java b/src/main/java/org/apache/commons/math/genetics/AbstractListChromosome.java new file mode 100644 index 0000000..c618dff --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/AbstractListChromosome.java @@ -0,0 +1,104 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +/** + * Chromosome represented by an immutable list of a fixed length. + * + * @param <T> type of the representation list + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + * @since 2.0 + */ +public abstract class AbstractListChromosome<T> extends Chromosome { + + /** List representing the chromosome */ + private final List<T> representation; + + /** + * Constructor. + * @param representation inner representation of the chromosome + */ + public AbstractListChromosome(final List<T> representation) { + try { + checkValidity(representation); + } catch (InvalidRepresentationException e) { + throw new IllegalArgumentException(String.format("Invalid representation for %s", getClass().getSimpleName()), e); + } + this.representation = Collections.unmodifiableList(new ArrayList<T> (representation)); + } + + /** + * Constructor. + * @param representation inner representation of the chromosome + */ + public AbstractListChromosome(final T[] representation) { + this(Arrays.asList(representation)); + } + + /** + * + * Asserts that <code>representation</code> can represent a valid chromosome. + * @param chromosomeRepresentation representation of the chromosome + * @throws InvalidRepresentationException iff the <code>representation</code> can not represent + * a valid chromosome + */ + protected abstract void checkValidity(List<T> chromosomeRepresentation) throws InvalidRepresentationException; + + /** + * Returns the (immutable) inner representation of the chromosome. + * @return the representation of the chromosome + */ + protected List<T> getRepresentation() { + return representation; + } + + /** + * Returns the length of the chromosome. + * @return the length of the chromosome + */ + public int getLength() { + return getRepresentation().size(); + } + + /** + * Creates a new instance of the same class as <code>this</code> is, with a + * given <code>arrayRepresentation</code>. This is needed in crossover and + * mutation operators, where we need a new instance of the same class, but + * with different array representation. + * + * Usually, this method just calls a constructor of the class. + * + * @param chromosomeRepresentation + * the inner array representation of the new chromosome. + * @return new instance extended from FixedLengthChromosome with the given + * arrayRepresentation + */ + public abstract AbstractListChromosome<T> newFixedLengthChromosome(final List<T> chromosomeRepresentation); + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return String.format("(f=%s %s)", getFitness(), getRepresentation()); + } +} diff --git a/src/main/java/org/apache/commons/math/genetics/BinaryChromosome.java b/src/main/java/org/apache/commons/math/genetics/BinaryChromosome.java new file mode 100644 index 0000000..19dab38 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/BinaryChromosome.java @@ -0,0 +1,92 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.List; + + +/** + * Chromosome represented by a vector of 0s and 1s. + * + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + * @since 2.0 + */ +public abstract class BinaryChromosome extends AbstractListChromosome<Integer> { + + /** + * Constructor. + * @param representation list of {0,1} values representing the chromosome + */ + public BinaryChromosome(List<Integer> representation) { + super(representation); + } + + /** + * Constructor. + * @param representation array of {0,1} values representing the chromosome + */ + public BinaryChromosome(Integer[] representation) { + super(representation); + } + + /** + * {@inheritDoc} + */ + @Override + protected void checkValidity(List<Integer> chromosomeRepresentation) throws InvalidRepresentationException { + for (int i : chromosomeRepresentation) { + if (i < 0 || i >1) + throw new InvalidRepresentationException("Elements can be only 0 or 1."); + } + } + + /** + * Returns a representation of a random binary array of length <code>length</code>. + * @param length length of the array + * @return a random binary array of length <code>length</code> + */ + public static List<Integer> randomBinaryRepresentation(int length) { + // random binary list + List<Integer> rList= new ArrayList<Integer> (length); + for (int j=0; j<length; j++) { + rList.add(GeneticAlgorithm.getRandomGenerator().nextInt(2)); + } + return rList; + } + + /** + * {@inheritDoc} + */ + @Override + protected boolean isSame(Chromosome another) { + // type check + if (! (another instanceof BinaryChromosome)) + return false; + BinaryChromosome anotherBc = (BinaryChromosome) another; + // size check + if (getLength() != anotherBc.getLength()) + return false; + + for (int i=0; i< getRepresentation().size(); i++) { + if (!(getRepresentation().get(i).equals(anotherBc.getRepresentation().get(i)))) + return false; + } + // all is ok + return true; + } +} diff --git a/src/main/java/org/apache/commons/math/genetics/BinaryMutation.java b/src/main/java/org/apache/commons/math/genetics/BinaryMutation.java new file mode 100644 index 0000000..f762f89 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/BinaryMutation.java @@ -0,0 +1,52 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.List; + +/** + * Mutation for {@link BinaryChromosome}s. Randomly changes one gene. + * + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + * @since 2.0 + */ +public class BinaryMutation implements MutationPolicy { + + /** + * Mutate the given chromosome. Randomly changes one gene. + * @param original the original chromosome. + * @return the mutated chromomsome. + */ + public Chromosome mutate(Chromosome original) { + if (!(original instanceof BinaryChromosome)) { + throw new IllegalArgumentException("Binary mutation works on BinaryChromosome only."); + } + + BinaryChromosome origChrom = (BinaryChromosome) original; + List<Integer> newRepr = new ArrayList<Integer>(origChrom.getRepresentation()); + + // randomly select a gene + int geneIndex = GeneticAlgorithm.getRandomGenerator().nextInt(origChrom.getLength()); + // and change it + newRepr.set(geneIndex, origChrom.getRepresentation().get(geneIndex) == 0 ? 1 : 0); + + Chromosome newChrom = origChrom.newFixedLengthChromosome(newRepr); + return newChrom; + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/Chromosome.java b/src/main/java/org/apache/commons/math/genetics/Chromosome.java new file mode 100644 index 0000000..5641a5b --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/Chromosome.java @@ -0,0 +1,111 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Individual in a population. Chromosomes are compared based on their fitness. + * + * The chromosomes are IMMUTABLE, and so their fitness is also immutable and + * therefore it can be cached. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public abstract class Chromosome implements Comparable<Chromosome>,Fitness { + + /** + * Cached value of the fitness of this chromosome. + */ + private double fitness = Double.MIN_VALUE; + + /** + * Access the fitness of this chromosome. The bigger the fitness, the better + * the chromosome. + * + * Computation of fitness is usually very time-consuming task, therefore the + * fitness is cached. + * + * @return the fitness. + */ + public double getFitness() { + if (this.fitness == Double.MIN_VALUE) { + // no cache - compute the fitness + this.fitness = fitness(); + } + return this.fitness; + } + + /** + * Compares two chromosomes based on their fitness. The bigger the fitness, + * the better the chromosome. + * + * @param another another chromosome to compare + * @return + * <ul> + * <li>-1 if <code>another</code> is better than <code>this</code></li> + * <li>1 if <code>another</code> is worse than <code>this</code></li> + * <li>0 if the two chromosomes have the same fitness</li> + * </ul> + */ + public int compareTo(Chromosome another) { + return ((Double)this.getFitness()).compareTo(another.getFitness()); + } + + /** + * Returns <code>true<code> iff <code>another</code> has the same + * representation and therefore the same fitness. By default, it returns + * false -- override it in your implementation if you need it. + * @param another chromosome to compare + * @return true if <code>another</code> is equivalent to this chromosome + */ + protected boolean isSame(Chromosome another) { + return false; + } + + /** + * Searches the <code>population</code> for another chromosome with the same + * representation. If such chromosome is found, it is returned, if no such + * chromosome exists, returns <code>null</code>. + * + * @param population + * Population to search + * @return Chromosome with the same representation, or <code>null</code> if + * no such chromosome exists. + */ + protected Chromosome findSameChromosome(Population population) { + for (Chromosome anotherChr : population) { + if (this.isSame(anotherChr)) + return anotherChr; + } + return null; + } + + /** + * Searches the population for a chromosome representing the same solution, + * and if it finds one, updates the fitness to its value. + * + * @param population + * Population to search + */ + public void searchForFitnessUpdate(Population population) { + Chromosome sameChromosome = findSameChromosome(population); + if (sameChromosome != null) { + fitness = sameChromosome.getFitness(); + } + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/ChromosomePair.java b/src/main/java/org/apache/commons/math/genetics/ChromosomePair.java new file mode 100644 index 0000000..82b048f --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/ChromosomePair.java @@ -0,0 +1,69 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * A pair of {@link Chromosome} objects. + * @since 2.0 + * + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public class ChromosomePair { + /** the first chromosome in the pair. */ + private final Chromosome first; + + /** the second chromosome in the pair. */ + private final Chromosome second; + + /** + * Create a chromosome pair. + * + * @param c1 the first chromosome. + * @param c2 the second chromosome. + */ + public ChromosomePair(final Chromosome c1, final Chromosome c2) { + super(); + first = c1; + second = c2; + } + + /** + * Access the first chromosome. + * + * @return the first chromosome. + */ + public Chromosome getFirst() { + return first; + } + + /** + * Access the second chromosome. + * + * @return the second chromosome. + */ + public Chromosome getSecond() { + return second; + } + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return String.format("(%s,%s)", getFirst(), getSecond()); + } +} diff --git a/src/main/java/org/apache/commons/math/genetics/CrossoverPolicy.java b/src/main/java/org/apache/commons/math/genetics/CrossoverPolicy.java new file mode 100644 index 0000000..8742dac --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/CrossoverPolicy.java @@ -0,0 +1,35 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Policy used to create a pair of new chromosomes by performing a crossover + * operation on a source pair of chromosomes. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public interface CrossoverPolicy { + /** + * Perform a crossover operation on the given chromosomes. + * + * @param first the first chromosome. + * @param second the second chromosome. + * @return the pair of new chromosomes that resulted from the crossover. + */ + ChromosomePair crossover(Chromosome first, Chromosome second); +} diff --git a/src/main/java/org/apache/commons/math/genetics/ElitisticListPopulation.java b/src/main/java/org/apache/commons/math/genetics/ElitisticListPopulation.java new file mode 100644 index 0000000..045632a --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/ElitisticListPopulation.java @@ -0,0 +1,110 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.Collections; +import java.util.List; + +import org.apache.commons.math.util.FastMath; + +/** + * Population of chromosomes which uses elitism (certain percentace of the best + * chromosomes is directly copied to the next generation). + * + * @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $ + * @since 2.0 + */ +public class ElitisticListPopulation extends ListPopulation { + + /** percentage of chromosomes copied to the next generation */ + private double elitismRate = 0.9; + + /** + * Creates a new ElitisticListPopulation instance. + * + * @param chromosomes + * list of chromosomes in the population + * @param populationLimit + * maximal size of the population + * @param elitismRate + * how many best chromosomes will be directly transferred to the + * next generation [in %] + */ + public ElitisticListPopulation(List<Chromosome> chromosomes, int populationLimit, double elitismRate) { + super(chromosomes, populationLimit); + this.elitismRate = elitismRate; + } + + /** + * Creates a new ListPopulation instance and initializes its inner + * chromosome list. + * + * @param populationLimit maximal size of the population + * @param elitismRate + * how many best chromosomes will be directly transferred to the + * next generation [in %] + */ + public ElitisticListPopulation(int populationLimit, double elitismRate) { + super(populationLimit); + this.elitismRate = elitismRate; + } + + /** + * Start the population for the next generation. The + * <code>{@link #elitismRate}<code> percents of the best + * chromosomes are directly copied to the next generation. + * + * @return the beginnings of the next generation. + */ + public Population nextGeneration() { + // initialize a new generation with the same parameters + ElitisticListPopulation nextGeneration = new ElitisticListPopulation(this.getPopulationLimit(), this.getElitismRate()); + + List<Chromosome> oldChromosomes = this.getChromosomes(); + Collections.sort(oldChromosomes); + + // index of the last "not good enough" chromosome + int boundIndex = (int) FastMath.ceil((1.0 - this.getElitismRate()) * oldChromosomes.size()); + for (int i=boundIndex; i<oldChromosomes.size(); i++) { + nextGeneration.addChromosome(oldChromosomes.get(i)); + } + return nextGeneration; + } + + /** + * Sets the elitism rate, i.e. how many best chromosomes will be directly + * transferred to the next generation [in %]. + * + * @param elitismRate + * how many best chromosomes will be directly transferred to the + * next generation [in %] + */ + public void setElitismRate(double elitismRate) { + if (elitismRate < 0 || elitismRate > 1) + throw new IllegalArgumentException("Elitism rate has to be in [0,1]"); + this.elitismRate = elitismRate; + } + + /** + * Access the elitism rate. + * @return the elitism rate + */ + public double getElitismRate() { + return this.elitismRate; + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/Fitness.java b/src/main/java/org/apache/commons/math/genetics/Fitness.java new file mode 100644 index 0000000..40d674c --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/Fitness.java @@ -0,0 +1,35 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Fitness of a chromosome. + * + * @version $Revision: 811786 $ $Date: 2009-09-06 11:36:08 +0200 (dim. 06 sept. 2009) $ + * @since 2.0 + */ +public interface Fitness { + + /** + * Compute the fitness. This is usually very time-consuming, so the value + * should be cached. + * + * @return fitness + */ + double fitness(); + +} diff --git a/src/main/java/org/apache/commons/math/genetics/FixedGenerationCount.java b/src/main/java/org/apache/commons/math/genetics/FixedGenerationCount.java new file mode 100644 index 0000000..337c5c0 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/FixedGenerationCount.java @@ -0,0 +1,70 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Stops after a fixed number of generations. Each time + * {@link #isSatisfied(Population)} is invoked, a generation counter is + * incremented. Once the counter reaches the configured + * <code>maxGenerations</code> value, {@link #isSatisfied(Population)} returns + * true. + * + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + * @since 2.0 + */ +public class FixedGenerationCount implements StoppingCondition { + /** Number of generations that have passed */ + private int numGenerations = 0; + + /** Maximum number of generations (stopping criteria) */ + private final int maxGenerations; + + /** + * Create a new FixedGenerationCount instance. + * + * @param maxGenerations number of generations to evolve + */ + public FixedGenerationCount(int maxGenerations) { + if (maxGenerations <= 0) + throw new IllegalArgumentException("The number of generations has to be >= 0"); + this.maxGenerations = maxGenerations; + } + + /** + * Determine whether or not the given number of generations have passed. + * Increments the number of generations counter if the maximum has not + * been reached. + * + * @param population ignored (no impact on result) + * @return <code>true</code> IFF the maximum number of generations has been exceeded + */ + public boolean isSatisfied(Population population) { + if (this.numGenerations < this.maxGenerations) { + numGenerations++; + return false; + } + return true; + } + + /** + * @return the number of generations that have passed + */ + public int getNumGenerations() { + return numGenerations; + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/GeneticAlgorithm.java b/src/main/java/org/apache/commons/math/genetics/GeneticAlgorithm.java new file mode 100644 index 0000000..fc666ac --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/GeneticAlgorithm.java @@ -0,0 +1,228 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import org.apache.commons.math.random.RandomGenerator; +import org.apache.commons.math.random.JDKRandomGenerator; + +/** + * Implementation of a genetic algorithm. All factors that govern the operation + * of the algorithm can be configured for a specific problem. + * + * @since 2.0 + * @version $Revision: 925812 $ $Date: 2010-03-21 16:49:31 +0100 (dim. 21 mars 2010) $ + */ +public class GeneticAlgorithm { + + /** + * Static random number generator shared by GA implementation classes. + * Set the randomGenerator seed to get reproducible results. + * Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative + * to the default JDK-provided PRNG. + */ + //@GuardedBy("this") + private static RandomGenerator randomGenerator = new JDKRandomGenerator(); + + /** the crossover policy used by the algorithm. */ + private final CrossoverPolicy crossoverPolicy; + + /** the rate of crossover for the algorithm. */ + private final double crossoverRate; + + /** the mutation policy used by the algorithm. */ + private final MutationPolicy mutationPolicy; + + /** the rate of mutation for the algorithm. */ + private final double mutationRate; + + /** the selection policy used by the algorithm. */ + private final SelectionPolicy selectionPolicy; + + /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */ + private int generationsEvolved = 0; + + /** + * @param crossoverPolicy The {@link CrossoverPolicy} + * @param crossoverRate The crossover rate as a percentage (0-1 inclusive) + * @param mutationPolicy The {@link MutationPolicy} + * @param mutationRate The mutation rate as a percentage (0-1 inclusive) + * @param selectionPolicy The {@link SelectionPolicy} + */ + public GeneticAlgorithm( + CrossoverPolicy crossoverPolicy, double crossoverRate, + MutationPolicy mutationPolicy, double mutationRate, + SelectionPolicy selectionPolicy) { + if (crossoverRate < 0 || crossoverRate > 1) { + throw new IllegalArgumentException("crossoverRate must be between 0 and 1"); + } + if (mutationRate < 0 || mutationRate > 1) { + throw new IllegalArgumentException("mutationRate must be between 0 and 1"); + } + this.crossoverPolicy = crossoverPolicy; + this.crossoverRate = crossoverRate; + this.mutationPolicy = mutationPolicy; + this.mutationRate = mutationRate; + this.selectionPolicy = selectionPolicy; + } + + /** + * Set the (static) random generator. + * + * @param random random generator + */ + public static synchronized void setRandomGenerator(RandomGenerator random) { + randomGenerator = random; + } + + /** + * Returns the (static) random generator. + * + * @return the static random generator shared by GA implementation classes + */ + public static synchronized RandomGenerator getRandomGenerator() { + return randomGenerator; + } + + /** + * Evolve the given population. Evolution stops when the stopping condition + * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved} + * property with the number of generations evolved before the StoppingCondition + * is satisfied. + * + * @param initial the initial, seed population. + * @param condition the stopping condition used to stop evolution. + * @return the population that satisfies the stopping condition. + */ + public Population evolve(Population initial, StoppingCondition condition) { + Population current = initial; + generationsEvolved = 0; + while (!condition.isSatisfied(current)) { + current = nextGeneration(current); + generationsEvolved++; + } + return current; + } + + /** + * <p>Evolve the given population into the next generation.</p> + * <p><ol> + * <li>Get nextGeneration population to fill from <code>current</code> + * generation, using its nextGeneration method</li> + * <li>Loop until new generation is filled:</li> + * <ul><li>Apply configured SelectionPolicy to select a pair of parents + * from <code>current</code></li> + * <li>With probability = {@link #getCrossoverRate()}, apply + * configured {@link CrossoverPolicy} to parents</li> + * <li>With probability = {@link #getMutationRate()}, apply + * configured {@link MutationPolicy} to each of the offspring</li> + * <li>Add offspring individually to nextGeneration, + * space permitting</li> + * </ul> + * <li>Return nextGeneration</li> + * </ol> + * </p> + * + * @param current the current population. + * @return the population for the next generation. + */ + public Population nextGeneration(Population current) { + Population nextGeneration = current.nextGeneration(); + + RandomGenerator randGen = getRandomGenerator(); + + while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { + // select parent chromosomes + ChromosomePair pair = getSelectionPolicy().select(current); + + // crossover? + if (randGen.nextDouble() < getCrossoverRate()) { + // apply crossover policy to create two offspring + pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond()); + } + + // mutation? + if (randGen.nextDouble() < getMutationRate()) { + // apply mutation policy to the chromosomes + pair = new ChromosomePair( + getMutationPolicy().mutate(pair.getFirst()), + getMutationPolicy().mutate(pair.getSecond())); + } + + // add the first chromosome to the population + nextGeneration.addChromosome(pair.getFirst()); + // is there still a place for the second chromosome? + if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { + // add the second chromosome to the population + nextGeneration.addChromosome(pair.getSecond()); + } + } + + return nextGeneration; + } + + /** + * Returns the crossover policy. + * @return crossover policy + */ + public CrossoverPolicy getCrossoverPolicy() { + return crossoverPolicy; + } + + /** + * Returns the crossover rate. + * @return crossover rate + */ + public double getCrossoverRate() { + return crossoverRate; + } + + /** + * Returns the mutation policy. + * @return mutation policy + */ + public MutationPolicy getMutationPolicy() { + return mutationPolicy; + } + + /** + * Returns the mutation rate. + * @return mutation rate + */ + public double getMutationRate() { + return mutationRate; + } + + /** + * Returns the selection policy. + * @return selection policy + */ + public SelectionPolicy getSelectionPolicy() { + return selectionPolicy; + } + + /** + * Returns the number of generations evolved to + * reach {@link StoppingCondition} in the last run. + * + * @return number of generations evolved + * @since 2.1 + */ + public int getGenerationsEvolved() { + return generationsEvolved; + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/InvalidRepresentationException.java b/src/main/java/org/apache/commons/math/genetics/InvalidRepresentationException.java new file mode 100644 index 0000000..b60ded8 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/InvalidRepresentationException.java @@ -0,0 +1,63 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Exception indicating that the representation of a chromosome is not valid. + * + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + * @since 2.0 + */ +public class InvalidRepresentationException extends Exception { + + /** Serialization version id */ + private static final long serialVersionUID = 1L; + + /** + * Constructor + */ + public InvalidRepresentationException() { + super(); + } + + /** + * Construct an InvalidRepresentationException + * @param arg0 exception message + */ + public InvalidRepresentationException(String arg0) { + super(arg0); + } + + /** + * Construct an InvalidRepresentationException + * @param arg0 cause + */ + public InvalidRepresentationException(Throwable arg0) { + super(arg0); + } + + /** + * Construct an InvalidRepresentationException + * + * @param arg0 exception message + * @param arg1 cause + */ + public InvalidRepresentationException(String arg0, Throwable arg1) { + super(arg0, arg1); + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/ListPopulation.java b/src/main/java/org/apache/commons/math/genetics/ListPopulation.java new file mode 100644 index 0000000..e880b2c --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/ListPopulation.java @@ -0,0 +1,155 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +import org.apache.commons.math.exception.util.LocalizedFormats; +import org.apache.commons.math.exception.NotPositiveException; +import org.apache.commons.math.exception.NumberIsTooLargeException; + +/** + * Population of chromosomes represented by a {@link List}. + * + * @since 2.0 + * @version $Revision: 983921 $ $Date: 2010-08-10 12:46:06 +0200 (mar. 10 août 2010) $ + */ +public abstract class ListPopulation implements Population { + + /** List of chromosomes */ + private List<Chromosome> chromosomes; + + /** maximial size of the population */ + private int populationLimit; + + + /** + * Creates a new ListPopulation instance. + * + * @param chromosomes list of chromosomes in the population + * @param populationLimit maximal size of the population + */ + public ListPopulation (List<Chromosome> chromosomes, int populationLimit) { + if (chromosomes.size() > populationLimit) { + throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, + chromosomes.size(), populationLimit, false); + } + if (populationLimit < 0) { + throw new NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE, populationLimit); + } + + this.chromosomes = chromosomes; + this.populationLimit = populationLimit; + } + + /** + * Creates a new ListPopulation instance and initializes its inner + * chromosome list. + * + * @param populationLimit maximal size of the population + */ + public ListPopulation (int populationLimit) { + if (populationLimit < 0) { + throw new NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE, populationLimit); + } + this.populationLimit = populationLimit; + this.chromosomes = new ArrayList<Chromosome>(populationLimit); + } + + /** + * Sets the list of chromosomes. + * @param chromosomes the list of chromosomes + */ + public void setChromosomes(List<Chromosome> chromosomes) { + this.chromosomes = chromosomes; + } + + /** + * Access the list of chromosomes. + * @return the list of chromosomes + */ + public List<Chromosome> getChromosomes() { + return chromosomes; + } + + /** + * Add the given chromosome to the population. + * @param chromosome the chromosome to add. + */ + public void addChromosome(Chromosome chromosome) { + this.chromosomes.add(chromosome); + } + + /** + * Access the fittest chromosome in this population. + * @return the fittest chromosome. + */ + public Chromosome getFittestChromosome() { + // best so far + Chromosome bestChromosome = this.chromosomes.get(0); + for (Chromosome chromosome : this.chromosomes) { + if (chromosome.compareTo(bestChromosome) > 0) { + // better chromosome found + bestChromosome = chromosome; + } + } + return bestChromosome; + } + + /** + * Access the maximum population size. + * @return the maximum population size. + */ + public int getPopulationLimit() { + return this.populationLimit; + } + + /** + * Sets the maximal population size. + * @param populationLimit maximal population size. + */ + public void setPopulationLimit(int populationLimit) { + this.populationLimit = populationLimit; + } + + /** + * Access the current population size. + * @return the current population size. + */ + public int getPopulationSize() { + return this.chromosomes.size(); + } + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return this.chromosomes.toString(); + } + + /** + * Chromosome list iterator + * + * @return chromosome iterator + */ + public Iterator<Chromosome> iterator() { + return chromosomes.iterator(); + } +} diff --git a/src/main/java/org/apache/commons/math/genetics/MutationPolicy.java b/src/main/java/org/apache/commons/math/genetics/MutationPolicy.java new file mode 100644 index 0000000..9753db7 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/MutationPolicy.java @@ -0,0 +1,33 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Algorithm used to mutate a chrommosome. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public interface MutationPolicy { + + /** + * Mutate the given chromosome. + * @param original the original chromosome. + * @return the mutated chromomsome. + */ + Chromosome mutate(Chromosome original); +} diff --git a/src/main/java/org/apache/commons/math/genetics/OnePointCrossover.java b/src/main/java/org/apache/commons/math/genetics/OnePointCrossover.java new file mode 100644 index 0000000..f5f6ffd --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/OnePointCrossover.java @@ -0,0 +1,117 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.List; + + +/** + * One point crossover policy. A random crossover point is selected and the + * first part from each parent is copied to the corresponding child, and the + * second parts are copied crosswise. + * + * Example: + * <pre> + * -C- denotes a crossover point + * -C- -C- + * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1) + * \------------/ \-----/ \------------/ \-----/ + * || (*) || (**) + * VV (**) VV (*) + * /------------\ /-----\ /------------\ /-----\ + * c1 = (1 0 1 0 0 1 | 1 1 1) X p2 = (0 1 1 0 1 0 | 0 1 1) + * </pre> + * + * This policy works only on {@link AbstractListChromosome}, and therefore it + * is parametrized by T. Moreover, the chromosomes must have same lengths. + * + * @param <T> generic type of the {@link AbstractListChromosome}s for crossover + * @since 2.0 + * @version $Revision: 903046 $ $Date: 2010-01-26 03:07:26 +0100 (mar. 26 janv. 2010) $ + * + */ +public class OnePointCrossover<T> implements CrossoverPolicy { + + /** + * Performs one point crossover. A random crossover point is selected and the + * first part from each parent is copied to the corresponding child, and the + * second parts are copied crosswise. + * + * Example: + * -C- denotes a crossover point + * -C- -C- + * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1) + * \------------/ \-----/ \------------/ \-----/ + * || (*) || (**) + * VV (**) VV (*) + * /------------\ /-----\ /------------\ /-----\ + * c1 = (1 0 1 0 0 1 | 1 1 1) X p2 = (0 1 1 0 1 0 | 0 1 1) + * + * @param first first parent (p1) + * @param second second parent (p2) + * @return pair of two children (c1,c2) + */ + @SuppressWarnings("unchecked") // OK because of instanceof checks + public ChromosomePair crossover(Chromosome first, Chromosome second) { + if (! (first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { + throw new IllegalArgumentException("One point crossover works on FixedLengthChromosomes only."); + } + return crossover((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second); + } + + + /** + * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover. + * + * @param first the first chromosome. + * @param second the second chromosome. + * @return the pair of new chromosomes that resulted from the crossover. + */ + private ChromosomePair crossover(AbstractListChromosome<T> first, AbstractListChromosome<T> second) { + int length = first.getLength(); + if (length != second.getLength()) + throw new IllegalArgumentException("Both chromosomes must have same lengths."); + + // array representations of the parents + List<T> parent1Rep = first.getRepresentation(); + List<T> parent2Rep = second.getRepresentation(); + // and of the children + ArrayList<T> child1Rep = new ArrayList<T> (first.getLength()); + ArrayList<T> child2Rep = new ArrayList<T> (second.getLength()); + + // select a crossover point at random (0 and length makes no sense) + int crossoverIndex = 1 + (GeneticAlgorithm.getRandomGenerator().nextInt(length-2)); + + // copy the first part + for (int i = 0; i < crossoverIndex; i++) { + child1Rep.add(parent1Rep.get(i)); + child2Rep.add(parent2Rep.get(i)); + } + // and switch the second part + for (int i = crossoverIndex; i < length; i++) { + child1Rep.add(parent2Rep.get(i)); + child2Rep.add(parent1Rep.get(i)); + } + + return new ChromosomePair( + first.newFixedLengthChromosome(child1Rep), + second.newFixedLengthChromosome(child2Rep) + ); + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/PermutationChromosome.java b/src/main/java/org/apache/commons/math/genetics/PermutationChromosome.java new file mode 100644 index 0000000..676b5dc --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/PermutationChromosome.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.List; + +/** + * Interface indicating that the chromosome represents a permutation of objects. + * + * @param <T> + * type of the permuted objects + * @since 2.0 + * @version $Revision: 811786 $ $Date: 2009-09-06 11:36:08 +0200 (dim. 06 sept. 2009) $ + */ +public interface PermutationChromosome<T> { + + /** + * Permutes the <code>sequence</code> of objects of type T according to the + * permutation this chromosome represents. For example, if this chromosome + * represents a permutation (3,0,1,2), and the unpermuted sequence is + * (a,b,c,d), this yields (d,a,b,c). + * + * @param sequence + * the unpermuted (original) sequence of objects + * @return permutation of <code>sequence</code> represented by this + * permutation + */ + List<T> decode(List<T> sequence); + +} diff --git a/src/main/java/org/apache/commons/math/genetics/Population.java b/src/main/java/org/apache/commons/math/genetics/Population.java new file mode 100644 index 0000000..3fc758a --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/Population.java @@ -0,0 +1,55 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * A collection of chromosomes that facilitates generational evolution. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public interface Population extends Iterable<Chromosome> { + /** + * Access the current population size. + * @return the current population size. + */ + int getPopulationSize(); + + /** + * Access the maximum population size. + * @return the maximum population size. + */ + int getPopulationLimit(); + + /** + * Start the population for the next generation. + * @return the beginnings of the next generation. + */ + Population nextGeneration(); + + /** + * Add the given chromosome to the population. + * @param chromosome the chromosome to add. + */ + void addChromosome(Chromosome chromosome); + + /** + * Access the fittest chromosome in this population. + * @return the fittest chromosome. + */ + Chromosome getFittestChromosome(); +} diff --git a/src/main/java/org/apache/commons/math/genetics/RandomKey.java b/src/main/java/org/apache/commons/math/genetics/RandomKey.java new file mode 100644 index 0000000..1cd28d3 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/RandomKey.java @@ -0,0 +1,290 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +/** + * <p> + * Random Key chromosome is used for permutation representation. It is a vector + * of a fixed length of real numbers in [0,1] interval. The index of the i-th + * smallest value in the vector represents an i-th member of the permutation. + * </p> + * + * <p> + * For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the + * permutation of indices (3,0,1,2). If the original (unpermuted) sequence would + * be (a,b,c,d), this would mean the sequence (d,a,b,c). + * </p> + * + * <p> + * With this representation, common operators like n-point crossover can be + * used, because any such chromosome represents a valid permutation. + * </p> + * + * <p> + * Since the chromosome (and thus its arrayRepresentation) is immutable, the + * array representation is sorted only once in the constructor. + * </p> + * + * <p> + * For details, see: + * <ul> + * <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and + * optimization. ORSA Journal on Computing 6 (1994) 154–160</li> + * <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms. + * Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag, + * Heidelberg (2002)</li> + * </ul> + * </p> + * + * @param <T> + * type of the permuted objects + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> { + + /** + * Cache of sorted representation (unmodifiable). + */ + private final List<Double> sortedRepresentation; + + /** + * Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable). + */ + private final List<Integer> baseSeqPermutation; + + /** + * Constructor. + * + * @param representation list of [0,1] values representing the permutation + */ + public RandomKey(List<Double> representation) { + super(representation); + // store the sorted representation + List<Double> sortedRepr = new ArrayList<Double> (getRepresentation()); + Collections.sort(sortedRepr); + sortedRepresentation = Collections.unmodifiableList(sortedRepr); + // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods + baseSeqPermutation = Collections.unmodifiableList( + decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation) + ); + } + + /** + * Constructor. + * + * @param representation array of [0,1] values representing the permutation + */ + public RandomKey(Double[] representation) { + this(Arrays.asList(representation)); + } + + /** + * {@inheritDoc} + */ + public List<T> decode(List<T> sequence) { + return decodeGeneric(sequence, getRepresentation(), sortedRepresentation); + } + + /** + * Decodes a permutation represented by <code>representation</code> and + * returns a (generic) list with the permuted values. + * + * @param <S> generic type of the sequence values + * @param sequence the unpermuted sequence + * @param representation representation of the permutation ([0,1] vector) + * @param sortedRepr sorted <code>representation</code> + * @return list with the sequence values permuted according to the representation + */ + private static <S> List<S> decodeGeneric(List<S> sequence, List<Double> representation, List<Double> sortedRepr) { + int l = sequence.size(); + + if (representation.size() != l) { + throw new IllegalArgumentException(String.format("Length of sequence for decoding (%s) has to be equal to the length of the RandomKey (%s)", l, representation.size())); + } + if (representation.size() != sortedRepr.size()) { + throw new IllegalArgumentException(String.format("Representation and sortedRepr must have same sizes, %d != %d", representation.size(), sortedRepr.size())); + } + + List<Double> reprCopy = new ArrayList<Double> (representation);// do not modify the orig. representation + + // now find the indices in the original repr and use them for permuting + List<S> res = new ArrayList<S> (l); + for (int i=0; i<l; i++) { + int index = reprCopy.indexOf(sortedRepr.get(i)); + res.add(sequence.get(index)); + reprCopy.set(index, null); + } + return res; + } + + /** + * Returns <code>true</code> iff <code>another</code> is a RandomKey and + * encodes the same permutation. + * + * @param another chromosome to compare + * @return true iff chromosomes encode the same permutation + */ + @Override + protected boolean isSame(Chromosome another) { + // type check + if (! (another instanceof RandomKey<?>)) + return false; + RandomKey<?> anotherRk = (RandomKey<?>) another; + // size check + if (getLength() != anotherRk.getLength()) + return false; + + // two different representations can still encode the same permutation + // the ordering is what counts + List<Integer> thisPerm = this.baseSeqPermutation; + List<Integer> anotherPerm = anotherRk.baseSeqPermutation; + + for (int i=0; i<getLength(); i++) { + if (thisPerm.get(i) != anotherPerm.get(i)) + return false; + } + // the permutations are the same + return true; + } + + /** + * {@inheritDoc} + */ + @Override + protected void checkValidity(java.util.List<Double> chromosomeRepresentation) throws InvalidRepresentationException { + for (double val : chromosomeRepresentation) { + if (val < 0 || val > 1) { + throw new InvalidRepresentationException("Values of representation must be in [0,1] interval"); + } + } + } + + + /** + * Generates a representation corresponding to a random permutation of + * length l which can be passed to the RandomKey constructor. + * + * @param l + * length of the permutation + * @return representation of a random permutation + */ + public static final List<Double> randomPermutation(int l) { + List<Double> repr = new ArrayList<Double>(l); + for (int i=0; i<l; i++) { + repr.add(GeneticAlgorithm.getRandomGenerator().nextDouble()); + } + return repr; + } + + /** + * Generates a representation corresponding to an identity permutation of + * length l which can be passed to the RandomKey constructor. + * + * @param l + * length of the permutation + * @return representation of an identity permutation + */ + public static final List<Double> identityPermutation(int l) { + List<Double> repr = new ArrayList<Double>(l); + for (int i=0; i<l; i++) { + repr.add((double)i/l); + } + return repr; + } + + /** + * Generates a representation of a permutation corresponding to the + * <code>data</code> sorted by <code>comparator</code>. The + * <code>data</code> is not modified during the process. + * + * This is useful if you want to inject some permutations to the initial + * population. + * + * @param <S> type of the data + * @param data list of data determining the order + * @param comparator how the data will be compared + * @return list representation of the permutation corresponding to the parameters + */ + public static <S> List<Double> comparatorPermutation(List<S> data, Comparator<S> comparator) { + List<S> sortedData = new ArrayList<S> (data); + Collections.sort(sortedData, comparator); + + return inducedPermutation(data, sortedData); + } + + /** + * Generates a representation of a permutation corresponding to a + * permutation which yields <code>permutedData</code> when applied to + * <code>originalData</code>. + * + * This method can be viewed as an inverse to {@link #decode(List)}. + * + * @param <S> type of the data + * @param originalData the original, unpermuted data + * @param permutedData the data, somehow permuted + * @return representation of a permutation corresponding to the permutation <code>originalData -> permutedData</code> + * @throws IllegalArgumentException iff the <code>permutedData</code> and <code>originalData</code> contains different data + */ + public static <S> List<Double> inducedPermutation(List<S> originalData, List<S> permutedData) throws IllegalArgumentException { + if (originalData.size() != permutedData.size()) { + throw new IllegalArgumentException("originalData and permutedData must have same length"); + } + int l = originalData.size(); + + List<S> origDataCopy = new ArrayList<S> (originalData); + + Double[] res = new Double[l]; + for (int i=0; i<l; i++) { + int index = origDataCopy.indexOf(permutedData.get(i)); + if (index == -1) { + throw new IllegalArgumentException("originalData and permutedData must contain the same objects."); + } + res[index] = (double) i / l; + origDataCopy.set(index, null); + } + return Arrays.asList(res); + } + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation); + } + + /** + * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1). + * + * @param l length of list to generate + * @return list of integers from 0 to l-1 + */ + private static List<Integer> baseSequence(int l) { + List<Integer> baseSequence = new ArrayList<Integer> (l); + for (int i=0; i<l; i++) { + baseSequence.add(i); + } + return baseSequence; + } +} diff --git a/src/main/java/org/apache/commons/math/genetics/RandomKeyMutation.java b/src/main/java/org/apache/commons/math/genetics/RandomKeyMutation.java new file mode 100644 index 0000000..792eef2 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/RandomKeyMutation.java @@ -0,0 +1,57 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.List; + +import org.apache.commons.math.MathRuntimeException; +import org.apache.commons.math.exception.util.LocalizedFormats; + +/** + * Mutation operator for {@link RandomKey}s. Changes a randomly chosen element + * of the array representation to a random value uniformly distributed in [0,1]. + * + * @since 2.0 + * @version $Revision: 983921 $ $Date: 2010-08-10 12:46:06 +0200 (mar. 10 août 2010) $ + */ +public class RandomKeyMutation implements MutationPolicy { + + /** + * {@inheritDoc} + * + * @throws IllegalArgumentException if <code>original</code> is not a + * {@link RandomKey} instance + */ + public Chromosome mutate(Chromosome original) { + if (!(original instanceof RandomKey<?>)) { + throw MathRuntimeException.createIllegalArgumentException( + LocalizedFormats.RANDOMKEY_MUTATION_WRONG_CLASS, + original.getClass().getSimpleName()); + } + + RandomKey<?> originalRk = (RandomKey<?>) original; + List<Double> repr = originalRk.getRepresentation(); + int rInd = GeneticAlgorithm.getRandomGenerator().nextInt(repr.size()); + + List<Double> newRepr = new ArrayList<Double> (repr); + newRepr.set(rInd, GeneticAlgorithm.getRandomGenerator().nextDouble()); + + return originalRk.newFixedLengthChromosome(newRepr); + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/SelectionPolicy.java b/src/main/java/org/apache/commons/math/genetics/SelectionPolicy.java new file mode 100644 index 0000000..4cf6768 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/SelectionPolicy.java @@ -0,0 +1,32 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Algorithm used to select a chromosome pair from a population. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public interface SelectionPolicy { + /** + * Select two chromosomes from the population. + * @param population the population from which the chromosomes are choosen. + * @return the selected chromosomes. + */ + ChromosomePair select(Population population); +} diff --git a/src/main/java/org/apache/commons/math/genetics/StoppingCondition.java b/src/main/java/org/apache/commons/math/genetics/StoppingCondition.java new file mode 100644 index 0000000..0253ce9 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/StoppingCondition.java @@ -0,0 +1,35 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +/** + * Algorithm used to determine when to stop evolution. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public interface StoppingCondition { + /** + * Determine whether or not the given population satisfies the stopping + * condition. + * + * @param population the population to test. + * @return <code>true</code> if this stopping condition is met by the + * given population. <code>false</code> otherwise. + */ + boolean isSatisfied(Population population); +} diff --git a/src/main/java/org/apache/commons/math/genetics/TournamentSelection.java b/src/main/java/org/apache/commons/math/genetics/TournamentSelection.java new file mode 100644 index 0000000..f1a091f --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/TournamentSelection.java @@ -0,0 +1,114 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.genetics; + +import java.util.ArrayList; +import java.util.List; + +/** + * Tournament selection scheme. Each of the two selected chromosomes is selected + * based on n-ary tournament -- this is done by drawing {@link #arity} random + * chromosomes without replacement from the population, and then selecting the + * fittest chromosome among them. + * + * @since 2.0 + * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ + */ +public class TournamentSelection implements SelectionPolicy { + + /** number of chromosomes included in the tournament selections */ + private int arity; + + /** + * Creates a new TournamentSelection instance. + * + * @param arity + * how many chromosomes will be drawn to the tournament + */ + public TournamentSelection(int arity) { + this.arity = arity; + } + + /** + * Select two chromosomes from the population. Each of the two selected + * chromosomes is selected based on n-ary tournament -- this is done by + * drawing {@link #arity} random chromosomes without replacement from the + * population, and then selecting the fittest chromosome among them. + * + * @param population + * the population from which the chromosomes are choosen. + * @return the selected chromosomes. + */ + public ChromosomePair select(Population population) { + return new ChromosomePair( + tournament((ListPopulation) population), + tournament((ListPopulation)population) + ); + } + + /** + * Helper for {@link #select(Population)}. Draw {@link #arity} random + * chromosomes without replacement from the population, and then select the + * fittest chromosome among them. + * + * @param population + * the population from which the chromosomes are choosen. + * @return the selected chromosome. + */ + private Chromosome tournament(ListPopulation population) { + if (population.getPopulationSize() < this.arity) + throw new IllegalArgumentException("Tournament arity cannot be bigger than population size."); + // auxiliary population + ListPopulation tournamentPopulation = new ListPopulation(this.arity) { + public Population nextGeneration() { + // not useful here + return null; + } + }; + + // create a copy of the chromosome list + List<Chromosome> chromosomes = new ArrayList<Chromosome> (population.getChromosomes()); + for (int i=0; i<this.arity; i++) { + // select a random individual and add it to the tournament + int rind = GeneticAlgorithm.getRandomGenerator().nextInt(chromosomes.size()); + tournamentPopulation.addChromosome(chromosomes.get(rind)); + // do not select it again + chromosomes.remove(rind); + } + // the winner takes it all + return tournamentPopulation.getFittestChromosome(); + } + + /** + * Gets the arity (number of chromosomes drawn to the tournament). + * + * @return arity of the tournament + */ + public int getArity() { + return arity; + } + + /** + * Sets the arity (number of chromosomes drawn to the tournament). + * + * @param arity arity of the tournament + */ + public void setArity(int arity) { + this.arity = arity; + } + +} diff --git a/src/main/java/org/apache/commons/math/genetics/package.html b/src/main/java/org/apache/commons/math/genetics/package.html new file mode 100644 index 0000000..adcd5a9 --- /dev/null +++ b/src/main/java/org/apache/commons/math/genetics/package.html @@ -0,0 +1,24 @@ +<html> +<!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + --> + <!-- $Revision: 784604 $ --> +<body> +<p> +This package provides Genetic Algorithms components and implementations. +</p> +</body> +</html> |