http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java b/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java deleted file mode 100644 index a426bc2..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java +++ /dev/null @@ -1,117 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.Collections; -import java.util.List; - -import org.apache.commons.math3.exception.NotPositiveException; -import org.apache.commons.math3.exception.NullArgumentException; -import org.apache.commons.math3.exception.NumberIsTooLargeException; -import org.apache.commons.math3.exception.OutOfRangeException; -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.util.FastMath; - -/** - * Population of chromosomes which uses elitism (certain percentage of the best - * chromosomes is directly copied to the next generation). - * - * @since 2.0 - */ -public class ElitisticListPopulation extends ListPopulation { - - /** percentage of chromosomes copied to the next generation */ - private double elitismRate = 0.9; - - /** - * Creates a new {@link 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 %] - * @throws NullArgumentException if the list of chromosomes is {@code null} - * @throws NotPositiveException if the population limit is not a positive number (< 1) - * @throws NumberIsTooLargeException if the list of chromosomes exceeds the population limit - * @throws OutOfRangeException if the elitism rate is outside the [0, 1] range - */ - public ElitisticListPopulation(final List<Chromosome> chromosomes, final int populationLimit, - final double elitismRate) - throws NullArgumentException, NotPositiveException, NumberIsTooLargeException, OutOfRangeException { - - super(chromosomes, populationLimit); - setElitismRate(elitismRate); - } - - /** - * Creates a new {@link ElitisticListPopulation} 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 %] - * @throws NotPositiveException if the population limit is not a positive number (< 1) - * @throws OutOfRangeException if the elitism rate is outside the [0, 1] range - */ - public ElitisticListPopulation(final int populationLimit, final double elitismRate) - throws NotPositiveException, OutOfRangeException { - - super(populationLimit); - setElitismRate(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(getPopulationLimit(), getElitismRate()); - - final List<Chromosome> oldChromosomes = getChromosomeList(); - Collections.sort(oldChromosomes); - - // index of the last "not good enough" chromosome - int boundIndex = (int) FastMath.ceil((1.0 - 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 %] - * @throws OutOfRangeException if the elitism rate is outside the [0, 1] range - */ - public void setElitismRate(final double elitismRate) throws OutOfRangeException { - if (elitismRate < 0 || elitismRate > 1) { - throw new OutOfRangeException(LocalizedFormats.ELITISM_RATE, elitismRate, 0, 1); - } - this.elitismRate = elitismRate; - } - - /** - * Access the elitism rate. - * @return the elitism rate - */ - public double getElitismRate() { - return this.elitismRate; - } - -}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/Fitness.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/Fitness.java b/src/main/java/org/apache/commons/math3/genetics/Fitness.java deleted file mode 100644 index 40d6192..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/Fitness.java +++ /dev/null @@ -1,32 +0,0 @@ -/* - * 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.math3.genetics; - -/** - * Fitness of a chromosome. - * - * @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(); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java b/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java deleted file mode 100644 index 3879a8c..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java +++ /dev/null @@ -1,77 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.concurrent.TimeUnit; - -import org.apache.commons.math3.exception.NumberIsTooSmallException; - -/** - * Stops after a fixed amount of time has elapsed. - * <p> - * The first time {@link #isSatisfied(Population)} is invoked, the end time of the evolution is determined based on the - * provided <code>maxTime</code> value. Once the elapsed time reaches the configured <code>maxTime</code> value, - * {@link #isSatisfied(Population)} returns true. - * - * @since 3.1 - */ -public class FixedElapsedTime implements StoppingCondition { - /** Maximum allowed time period (in nanoseconds). */ - private final long maxTimePeriod; - - /** The predetermined termination time (stopping condition). */ - private long endTime = -1; - - /** - * Create a new {@link FixedElapsedTime} instance. - * - * @param maxTime maximum number of seconds generations are allowed to evolve - * @throws NumberIsTooSmallException if the provided time is < 0 - */ - public FixedElapsedTime(final long maxTime) throws NumberIsTooSmallException { - this(maxTime, TimeUnit.SECONDS); - } - - /** - * Create a new {@link FixedElapsedTime} instance. - * - * @param maxTime maximum time generations are allowed to evolve - * @param unit {@link TimeUnit} of the maxTime argument - * @throws NumberIsTooSmallException if the provided time is < 0 - */ - public FixedElapsedTime(final long maxTime, final TimeUnit unit) throws NumberIsTooSmallException { - if (maxTime < 0) { - throw new NumberIsTooSmallException(maxTime, 0, true); - } - maxTimePeriod = unit.toNanos(maxTime); - } - - /** - * Determine whether or not the maximum allowed time has passed. - * The termination time is determined after the first generation. - * - * @param population ignored (no impact on result) - * @return <code>true</code> IFF the maximum allowed time period has elapsed - */ - public boolean isSatisfied(final Population population) { - if (endTime < 0) { - endTime = System.nanoTime() + maxTimePeriod; - } - - return System.nanoTime() >= endTime; - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java b/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java deleted file mode 100644 index 64362fc..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java +++ /dev/null @@ -1,71 +0,0 @@ -/* - * 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.math3.genetics; - -import org.apache.commons.math3.exception.NumberIsTooSmallException; - -/** - * 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. - * - * @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 - * @throws NumberIsTooSmallException if the number of generations is < 1 - */ - public FixedGenerationCount(final int maxGenerations) throws NumberIsTooSmallException { - if (maxGenerations <= 0) { - throw new NumberIsTooSmallException(maxGenerations, 1, true); - } - 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(final Population population) { - if (this.numGenerations < this.maxGenerations) { - numGenerations++; - return false; - } - return true; - } - - /** - * Returns the number of generations that have already passed. - * @return the number of generations that have passed - */ - public int getNumGenerations() { - return numGenerations; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java b/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java deleted file mode 100644 index 2f3d684..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java +++ /dev/null @@ -1,233 +0,0 @@ -/* - * 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.math3.genetics; - -import org.apache.commons.math3.exception.OutOfRangeException; -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.random.RandomGenerator; -import org.apache.commons.math3.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 - */ -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; - - /** - * Create a new genetic algorithm. - * @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} - * @throws OutOfRangeException if the crossover or mutation rate is outside the [0, 1] range - */ - public GeneticAlgorithm(final CrossoverPolicy crossoverPolicy, - final double crossoverRate, - final MutationPolicy mutationPolicy, - final double mutationRate, - final SelectionPolicy selectionPolicy) throws OutOfRangeException { - - if (crossoverRate < 0 || crossoverRate > 1) { - throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, - crossoverRate, 0, 1); - } - if (mutationRate < 0 || mutationRate > 1) { - throw new OutOfRangeException(LocalizedFormats.MUTATION_RATE, - mutationRate, 0, 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(final 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(final Population initial, final StoppingCondition condition) { - Population current = initial; - generationsEvolved = 0; - while (!condition.isSatisfied(current)) { - current = nextGeneration(current); - generationsEvolved++; - } - return current; - } - - /** - * Evolve the given population into the next generation. - * <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> - * - * @param current the current population. - * @return the population for the next generation. - */ - public Population nextGeneration(final 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; - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java b/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java deleted file mode 100644 index 7ca3a9a..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java +++ /dev/null @@ -1,42 +0,0 @@ -/* - * 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.math3.genetics; - -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.util.Localizable; - -/** - * Exception indicating that the representation of a chromosome is not valid. - * - * @since 2.0 - */ -public class InvalidRepresentationException extends MathIllegalArgumentException { - - /** Serialization version id */ - private static final long serialVersionUID = 1L; - - /** - * Construct an InvalidRepresentationException with a specialized message. - * - * @param pattern Message pattern. - * @param args Arguments. - */ - public InvalidRepresentationException(Localizable pattern, Object ... args) { - super(pattern, args); - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java b/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java deleted file mode 100644 index ce45234..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java +++ /dev/null @@ -1,222 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.Iterator; -import java.util.List; - -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.exception.NotPositiveException; -import org.apache.commons.math3.exception.NullArgumentException; -import org.apache.commons.math3.exception.NumberIsTooLargeException; -import org.apache.commons.math3.exception.NumberIsTooSmallException; - -/** - * Population of chromosomes represented by a {@link List}. - * - * @since 2.0 - */ -public abstract class ListPopulation implements Population { - - /** List of chromosomes */ - private List<Chromosome> chromosomes; - - /** maximal size of the population */ - private int populationLimit; - - /** - * Creates a new ListPopulation instance and initializes its inner chromosome list. - * - * @param populationLimit maximal size of the population - * @throws NotPositiveException if the population limit is not a positive number (< 1) - */ - public ListPopulation(final int populationLimit) throws NotPositiveException { - this(Collections.<Chromosome> emptyList(), populationLimit); - } - - /** - * Creates a new ListPopulation instance. - * <p> - * Note: the chromosomes of the specified list are added to the population. - * - * @param chromosomes list of chromosomes to be added to the population - * @param populationLimit maximal size of the population - * @throws NullArgumentException if the list of chromosomes is {@code null} - * @throws NotPositiveException if the population limit is not a positive number (< 1) - * @throws NumberIsTooLargeException if the list of chromosomes exceeds the population limit - */ - public ListPopulation(final List<Chromosome> chromosomes, final int populationLimit) - throws NullArgumentException, NotPositiveException, NumberIsTooLargeException { - - if (chromosomes == null) { - throw new NullArgumentException(); - } - if (populationLimit <= 0) { - throw new NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE, populationLimit); - } - if (chromosomes.size() > populationLimit) { - throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, - chromosomes.size(), populationLimit, false); - } - this.populationLimit = populationLimit; - this.chromosomes = new ArrayList<Chromosome>(populationLimit); - this.chromosomes.addAll(chromosomes); - } - - /** - * Sets the list of chromosomes. - * <p> - * Note: this method removed all existing chromosomes in the population and adds all chromosomes - * of the specified list to the population. - * - * @param chromosomes the list of chromosomes - * @throws NullArgumentException if the list of chromosomes is {@code null} - * @throws NumberIsTooLargeException if the list of chromosomes exceeds the population limit - * @deprecated use {@link #addChromosomes(Collection)} instead - */ - @Deprecated - public void setChromosomes(final List<Chromosome> chromosomes) - throws NullArgumentException, NumberIsTooLargeException { - - if (chromosomes == null) { - throw new NullArgumentException(); - } - if (chromosomes.size() > populationLimit) { - throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, - chromosomes.size(), populationLimit, false); - } - this.chromosomes.clear(); - this.chromosomes.addAll(chromosomes); - } - - /** - * Add a {@link Collection} of chromosomes to this {@link Population}. - * @param chromosomeColl a {@link Collection} of chromosomes - * @throws NumberIsTooLargeException if the population would exceed the population limit when - * adding this chromosome - * @since 3.1 - */ - public void addChromosomes(final Collection<Chromosome> chromosomeColl) throws NumberIsTooLargeException { - if (chromosomes.size() + chromosomeColl.size() > populationLimit) { - throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, - chromosomes.size(), populationLimit, false); - } - this.chromosomes.addAll(chromosomeColl); - } - - /** - * Returns an unmodifiable list of the chromosomes in this population. - * @return the unmodifiable list of chromosomes - */ - public List<Chromosome> getChromosomes() { - return Collections.unmodifiableList(chromosomes); - } - - /** - * Access the list of chromosomes. - * @return the list of chromosomes - * @since 3.1 - */ - protected List<Chromosome> getChromosomeList() { - return chromosomes; - } - - /** - * Add the given chromosome to the population. - * - * @param chromosome the chromosome to add. - * @throws NumberIsTooLargeException if the population would exceed the {@code populationLimit} after - * adding this chromosome - */ - public void addChromosome(final Chromosome chromosome) throws NumberIsTooLargeException { - if (chromosomes.size() >= populationLimit) { - throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, - chromosomes.size(), populationLimit, false); - } - 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. - * @throws NotPositiveException if the population limit is not a positive number (< 1) - * @throws NumberIsTooSmallException if the new population size is smaller than the current number - * of chromosomes in the population - */ - public void setPopulationLimit(final int populationLimit) throws NotPositiveException, NumberIsTooSmallException { - if (populationLimit <= 0) { - throw new NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE, populationLimit); - } - if (populationLimit < chromosomes.size()) { - throw new NumberIsTooSmallException(populationLimit, chromosomes.size(), true); - } - 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(); - } - - /** - * Returns an iterator over the unmodifiable list of chromosomes. - * <p>Any call to {@link Iterator#remove()} will result in a {@link UnsupportedOperationException}.</p> - * - * @return chromosome iterator - */ - public Iterator<Chromosome> iterator() { - return getChromosomes().iterator(); - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java b/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java deleted file mode 100644 index b981881..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java +++ /dev/null @@ -1,35 +0,0 @@ -/* - * 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.math3.genetics; - -import org.apache.commons.math3.exception.MathIllegalArgumentException; - -/** - * Algorithm used to mutate a chromosome. - * - * @since 2.0 - */ -public interface MutationPolicy { - - /** - * Mutate the given chromosome. - * @param original the original chromosome. - * @return the mutated chromosome. - * @throws MathIllegalArgumentException if the given chromosome is not compatible with this {@link MutationPolicy} - */ - Chromosome mutate(Chromosome original) throws MathIllegalArgumentException; -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java b/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java deleted file mode 100644 index a1a7d99..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java +++ /dev/null @@ -1,178 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.List; - -import org.apache.commons.math3.exception.DimensionMismatchException; -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.NotStrictlyPositiveException; -import org.apache.commons.math3.exception.NumberIsTooLargeException; -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.random.RandomGenerator; - -/** - * N-point crossover policy. For each iteration 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 (2-point crossover): - * <pre> - * -C- denotes a crossover point - * -C- -C- -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 VV (*) VV - * /----\ /--------\ /-----\ /----\ /--------\ /-----\ - * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1) - * </pre> - * - * This policy works only on {@link AbstractListChromosome}, and therefore it - * is parameterized by T. Moreover, the chromosomes must have same lengths. - * - * @param <T> generic type of the {@link AbstractListChromosome}s for crossover - * @since 3.1 - */ -public class NPointCrossover<T> implements CrossoverPolicy { - - /** The number of crossover points. */ - private final int crossoverPoints; - - /** - * Creates a new {@link NPointCrossover} policy using the given number of points. - * <p> - * <b>Note</b>: the number of crossover points must be < <code>chromosome length - 1</code>. - * This condition can only be checked at runtime, as the chromosome length is not known in advance. - * - * @param crossoverPoints the number of crossover points - * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive - */ - public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException { - if (crossoverPoints <= 0) { - throw new NotStrictlyPositiveException(crossoverPoints); - } - this.crossoverPoints = crossoverPoints; - } - - /** - * Returns the number of crossover points used by this {@link CrossoverPolicy}. - * - * @return the number of crossover points - */ - public int getCrossoverPoints() { - return crossoverPoints; - } - - /** - * Performs a N-point crossover. N random crossover points are selected and are used - * to divide the parent chromosomes into segments. The segments are copied in alternate - * order from the two parents to the corresponding child chromosomes. - * - * Example (2-point crossover): - * <pre> - * -C- denotes a crossover point - * -C- -C- -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 VV (*) VV - * /----\ /--------\ /-----\ /----\ /--------\ /-----\ - * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1) - * </pre> - * - * @param first first parent (p1) - * @param second second parent (p2) - * @return pair of two children (c1,c2) - * @throws MathIllegalArgumentException iff one of the chromosomes is - * not an instance of {@link AbstractListChromosome} - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - @SuppressWarnings("unchecked") // OK because of instanceof checks - public ChromosomePair crossover(final Chromosome first, final Chromosome second) - throws DimensionMismatchException, MathIllegalArgumentException { - - if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { - throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME); - } - return mate((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 - * @throws DimensionMismatchException if the length of the two chromosomes is different - * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for the actual chromosomes - */ - private ChromosomePair mate(final AbstractListChromosome<T> first, - final AbstractListChromosome<T> second) - throws DimensionMismatchException, NumberIsTooLargeException { - - final int length = first.getLength(); - if (length != second.getLength()) { - throw new DimensionMismatchException(second.getLength(), length); - } - if (crossoverPoints >= length) { - throw new NumberIsTooLargeException(crossoverPoints, length, false); - } - - // array representations of the parents - final List<T> parent1Rep = first.getRepresentation(); - final List<T> parent2Rep = second.getRepresentation(); - // and of the children - final List<T> child1Rep = new ArrayList<T>(length); - final List<T> child2Rep = new ArrayList<T>(length); - - final RandomGenerator random = GeneticAlgorithm.getRandomGenerator(); - - List<T> c1 = child1Rep; - List<T> c2 = child2Rep; - - int remainingPoints = crossoverPoints; - int lastIndex = 0; - for (int i = 0; i < crossoverPoints; i++, remainingPoints--) { - // select the next crossover point at random - final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex - remainingPoints); - - // copy the current segment - for (int j = lastIndex; j < crossoverIndex; j++) { - c1.add(parent1Rep.get(j)); - c2.add(parent2Rep.get(j)); - } - - // swap the children for the next segment - List<T> tmp = c1; - c1 = c2; - c2 = tmp; - - lastIndex = crossoverIndex; - } - - // copy the last segment - for (int j = lastIndex; j < length; j++) { - c1.add(parent1Rep.get(j)); - c2.add(parent2Rep.get(j)); - } - - return new ChromosomePair(first.newFixedLengthChromosome(child1Rep), - second.newFixedLengthChromosome(child2Rep)); - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java b/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java deleted file mode 100644 index b1ea47b..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java +++ /dev/null @@ -1,128 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.List; - -import org.apache.commons.math3.exception.DimensionMismatchException; -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.util.LocalizedFormats; - - -/** - * 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 c2 = (0 1 1 0 1 0 | 0 1 1) - * </pre> - * - * This policy works only on {@link AbstractListChromosome}, and therefore it - * is parameterized by T. Moreover, the chromosomes must have same lengths. - * - * @param <T> generic type of the {@link AbstractListChromosome}s for crossover - * @since 2.0 - * - */ -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: - * <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 c2 = (0 1 1 0 1 0 | 0 1 1) - * </pre> - * - * @param first first parent (p1) - * @param second second parent (p2) - * @return pair of two children (c1,c2) - * @throws MathIllegalArgumentException iff one of the chromosomes is - * not an instance of {@link AbstractListChromosome} - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - @SuppressWarnings("unchecked") // OK because of instanceof checks - public ChromosomePair crossover(final Chromosome first, final Chromosome second) - throws DimensionMismatchException, MathIllegalArgumentException { - - if (! (first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { - throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME); - } - 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. - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - private ChromosomePair crossover(final AbstractListChromosome<T> first, - final AbstractListChromosome<T> second) throws DimensionMismatchException { - final int length = first.getLength(); - if (length != second.getLength()) { - throw new DimensionMismatchException(second.getLength(), length); - } - - // array representations of the parents - final List<T> parent1Rep = first.getRepresentation(); - final List<T> parent2Rep = second.getRepresentation(); - // and of the children - final List<T> child1Rep = new ArrayList<T>(length); - final List<T> child2Rep = new ArrayList<T>(length); - - // select a crossover point at random (0 and length makes no sense) - final 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)); - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java b/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java deleted file mode 100644 index e796f53..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java +++ /dev/null @@ -1,150 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.Collections; -import java.util.HashSet; -import java.util.List; -import java.util.Set; - -import org.apache.commons.math3.exception.DimensionMismatchException; -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.util.LocalizedFormats; -import org.apache.commons.math3.random.RandomGenerator; -import org.apache.commons.math3.util.FastMath; - -/** - * Order 1 Crossover [OX1] builds offspring from <b>ordered</b> chromosomes by copying a - * consecutive slice from one parent, and filling up the remaining genes from the other - * parent as they appear. - * <p> - * This policy works by applying the following rules: - * <ol> - * <li>select a random slice of consecutive genes from parent 1</li> - * <li>copy the slice to child 1 and mark out the genes in parent 2</li> - * <li>starting from the right side of the slice, copy genes from parent 2 as they - * appear to child 1 if they are not yet marked out.</li> - * </ol> - * <p> - * Example (random sublist from index 3 to 7, underlined): - * <pre> - * p1 = (8 4 7 3 6 2 5 1 9 0) X c1 = (0 4 7 3 6 2 5 1 8 9) - * --------- --------- - * p2 = (0 1 2 3 4 5 6 7 8 9) X c2 = (8 1 2 3 4 5 6 7 9 0) - * </pre> - * <p> - * This policy works only on {@link AbstractListChromosome}, and therefore it - * is parameterized by T. Moreover, the chromosomes must have same lengths. - * - * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx";> - * Order 1 Crossover Operator</a> - * - * @param <T> generic type of the {@link AbstractListChromosome}s for crossover - * @since 3.1 - */ -public class OrderedCrossover<T> implements CrossoverPolicy { - - /** - * {@inheritDoc} - * - * @throws MathIllegalArgumentException iff one of the chromosomes is - * not an instance of {@link AbstractListChromosome} - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - @SuppressWarnings("unchecked") - public ChromosomePair crossover(final Chromosome first, final Chromosome second) - throws DimensionMismatchException, MathIllegalArgumentException { - - if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { - throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME); - } - return mate((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 - * @throws DimensionMismatchException if the length of the two chromosomes is different - */ - protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second) - throws DimensionMismatchException { - - final int length = first.getLength(); - if (length != second.getLength()) { - throw new DimensionMismatchException(second.getLength(), length); - } - - // array representations of the parents - final List<T> parent1Rep = first.getRepresentation(); - final List<T> parent2Rep = second.getRepresentation(); - // and of the children - final List<T> child1 = new ArrayList<T>(length); - final List<T> child2 = new ArrayList<T>(length); - // sets of already inserted items for quick access - final Set<T> child1Set = new HashSet<T>(length); - final Set<T> child2Set = new HashSet<T>(length); - - final RandomGenerator random = GeneticAlgorithm.getRandomGenerator(); - // choose random points, making sure that lb < ub. - int a = random.nextInt(length); - int b; - do { - b = random.nextInt(length); - } while (a == b); - // determine the lower and upper bounds - final int lb = FastMath.min(a, b); - final int ub = FastMath.max(a, b); - - // add the subLists that are between lb and ub - child1.addAll(parent1Rep.subList(lb, ub + 1)); - child1Set.addAll(child1); - child2.addAll(parent2Rep.subList(lb, ub + 1)); - child2Set.addAll(child2); - - // iterate over every item in the parents - for (int i = 1; i <= length; i++) { - final int idx = (ub + i) % length; - - // retrieve the current item in each parent - final T item1 = parent1Rep.get(idx); - final T item2 = parent2Rep.get(idx); - - // if the first child already contains the item in the second parent add it - if (!child1Set.contains(item2)) { - child1.add(item2); - child1Set.add(item2); - } - - // if the second child already contains the item in the first parent add it - if (!child2Set.contains(item1)) { - child2.add(item1); - child2Set.add(item1); - } - } - - // rotate so that the original slice is in the same place as in the parents. - Collections.rotate(child1, lb); - Collections.rotate(child2, lb); - - return new ChromosomePair(first.newFixedLengthChromosome(child1), - second.newFixedLengthChromosome(child2)); - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java b/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java deleted file mode 100644 index d02cf2c..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java +++ /dev/null @@ -1,40 +0,0 @@ -/* - * 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.math3.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 - */ -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); - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/Population.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/Population.java b/src/main/java/org/apache/commons/math3/genetics/Population.java deleted file mode 100644 index 8cc6d8b..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/Population.java +++ /dev/null @@ -1,59 +0,0 @@ -/* - * 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.math3.genetics; - -import org.apache.commons.math3.exception.NumberIsTooLargeException; - - -/** - * A collection of chromosomes that facilitates generational evolution. - * - * @since 2.0 - */ -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. - * @throws NumberIsTooLargeException if the population would exceed the population limit when adding - * this chromosome - */ - void addChromosome(Chromosome chromosome) throws NumberIsTooLargeException; - - /** - * Access the fittest chromosome in this population. - * @return the fittest chromosome. - */ - Chromosome getFittestChromosome(); -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/RandomKey.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/RandomKey.java b/src/main/java/org/apache/commons/math3/genetics/RandomKey.java deleted file mode 100644 index 52db4a7..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/RandomKey.java +++ /dev/null @@ -1,298 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.Comparator; -import java.util.List; - -import org.apache.commons.math3.exception.DimensionMismatchException; -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.util.LocalizedFormats; - -/** - * 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> - * 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> - * With this representation, common operators like n-point crossover can be - * used, because any such chromosome represents a valid permutation. - * <p> - * Since the chromosome (and thus its arrayRepresentation) is immutable, the - * array representation is sorted only once in the constructor. - * <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> - * - * @param <T> type of the permuted objects - * @since 2.0 - */ -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 according to the representation (unmodifiable). - */ - private final List<Integer> baseSeqPermutation; - - /** - * Constructor. - * - * @param representation list of [0,1] values representing the permutation - * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome - */ - public RandomKey(final List<Double> representation) throws InvalidRepresentationException { - 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 - * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome - */ - public RandomKey(final Double[] representation) throws InvalidRepresentationException { - this(Arrays.asList(representation)); - } - - /** - * {@inheritDoc} - */ - public List<T> decode(final 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 - * @throws DimensionMismatchException iff the length of the <code>sequence</code>, - * <code>representation</code> or <code>sortedRepr</code> lists are not equal - */ - private static <S> List<S> decodeGeneric(final List<S> sequence, List<Double> representation, - final List<Double> sortedRepr) - throws DimensionMismatchException { - - int l = sequence.size(); - - // the size of the three lists must be equal - if (representation.size() != l) { - throw new DimensionMismatchException(representation.size(), l); - } - if (sortedRepr.size() != l) { - throw new DimensionMismatchException(sortedRepr.size(), l); - } - - // do not modify the original representation - List<Double> reprCopy = new ArrayList<Double> (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(final 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(final List<Double> chromosomeRepresentation) - throws InvalidRepresentationException { - - for (double val : chromosomeRepresentation) { - if (val < 0 || val > 1) { - throw new InvalidRepresentationException(LocalizedFormats.OUT_OF_RANGE_SIMPLE, - val, 0, 1); - } - } - } - - - /** - * 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(final 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(final 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(final List<S> data, - final 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 DimensionMismatchException iff the length of <code>originalData</code> - * and <code>permutedData</code> lists are not equal - * @throws MathIllegalArgumentException iff the <code>permutedData</code> and - * <code>originalData</code> lists contain different data - */ - public static <S> List<Double> inducedPermutation(final List<S> originalData, - final List<S> permutedData) - throws DimensionMismatchException, MathIllegalArgumentException { - - if (originalData.size() != permutedData.size()) { - throw new DimensionMismatchException(permutedData.size(), originalData.size()); - } - 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 MathIllegalArgumentException(LocalizedFormats.DIFFERENT_ORIG_AND_PERMUTED_DATA); - } - res[index] = (double) i / l; - origDataCopy.set(index, null); - } - return Arrays.asList(res); - } - - @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(final int l) { - List<Integer> baseSequence = new ArrayList<Integer> (l); - for (int i=0; i<l; i++) { - baseSequence.add(i); - } - return baseSequence; - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/RandomKeyMutation.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/RandomKeyMutation.java b/src/main/java/org/apache/commons/math3/genetics/RandomKeyMutation.java deleted file mode 100644 index 9fb16fb..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/RandomKeyMutation.java +++ /dev/null @@ -1,54 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.List; - -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.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 - */ -public class RandomKeyMutation implements MutationPolicy { - - /** - * {@inheritDoc} - * - * @throws MathIllegalArgumentException if <code>original</code> is not a {@link RandomKey} instance - */ - public Chromosome mutate(final Chromosome original) throws MathIllegalArgumentException { - if (!(original instanceof RandomKey<?>)) { - throw new MathIllegalArgumentException(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); - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java b/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java deleted file mode 100644 index 5240f75..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java +++ /dev/null @@ -1,34 +0,0 @@ -/* - * 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.math3.genetics; - -import org.apache.commons.math3.exception.MathIllegalArgumentException; - -/** - * Algorithm used to select a chromosome pair from a population. - * - * @since 2.0 - */ -public interface SelectionPolicy { - /** - * Select two chromosomes from the population. - * @param population the population from which the chromosomes are choosen. - * @return the selected chromosomes. - * @throws MathIllegalArgumentException if the population is not compatible with this {@link SelectionPolicy} - */ - ChromosomePair select(Population population) throws MathIllegalArgumentException; -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.java b/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.java deleted file mode 100644 index 0e21628..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.java +++ /dev/null @@ -1,33 +0,0 @@ -/* - * 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.math3.genetics; - -/** - * Algorithm used to determine when to stop evolution. - * - * @since 2.0 - */ -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); -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java b/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java deleted file mode 100644 index 95051ee..0000000 --- a/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java +++ /dev/null @@ -1,114 +0,0 @@ -/* - * 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.math3.genetics; - -import java.util.ArrayList; -import java.util.List; - -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.util.LocalizedFormats; - -/** - * 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 - */ -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(final 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 chosen. - * @return the selected chromosomes. - * @throws MathIllegalArgumentException if the tournament arity is bigger than the population size - */ - public ChromosomePair select(final Population population) throws MathIllegalArgumentException { - 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 chosen. - * @return the selected chromosome. - * @throws MathIllegalArgumentException if the tournament arity is bigger than the population size - */ - private Chromosome tournament(final ListPopulation population) throws MathIllegalArgumentException { - if (population.getPopulationSize() < this.arity) { - throw new MathIllegalArgumentException(LocalizedFormats.TOO_LARGE_TOURNAMENT_ARITY, - arity, population.getPopulationSize()); - } - // 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(final int arity) { - this.arity = arity; - } - -}
