diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/genetics')
27 files changed, 2810 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/genetics/AbstractListChromosome.java b/src/main/java/org/apache/commons/math3/genetics/AbstractListChromosome.java new file mode 100644 index 0000000..60d09c7 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/AbstractListChromosome.java @@ -0,0 +1,119 @@ +/* + * 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.List; + +/** + * Chromosome represented by an immutable list of a fixed length. + * + * @param <T> type of the representation list + * @since 2.0 + */ +public abstract class AbstractListChromosome<T> extends Chromosome { + + /** List representing the chromosome */ + private final List<T> representation; + + /** + * Constructor, copying the input representation. + * + * @param representation inner representation of the chromosome + * @throws InvalidRepresentationException iff the <code>representation</code> can not represent + * a valid chromosome + */ + public AbstractListChromosome(final List<T> representation) + throws InvalidRepresentationException { + this(representation, true); + } + + /** + * Constructor, copying the input representation. + * + * @param representation inner representation of the chromosome + * @throws InvalidRepresentationException iff the <code>representation</code> can not represent + * a valid chromosome + */ + public AbstractListChromosome(final T[] representation) throws InvalidRepresentationException { + this(Arrays.asList(representation)); + } + + /** + * Constructor. + * + * @param representation inner representation of the chromosome + * @param copyList if {@code true}, the representation will be copied, otherwise it will be + * referenced. + * @since 3.3 + */ + public AbstractListChromosome(final List<T> representation, final boolean copyList) { + checkValidity(representation); + this.representation = + Collections.unmodifiableList( + copyList ? new ArrayList<T>(representation) : 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. + * + * <p>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/math3/genetics/BinaryChromosome.java b/src/main/java/org/apache/commons/math3/genetics/BinaryChromosome.java new file mode 100644 index 0000000..6874ddc --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/BinaryChromosome.java @@ -0,0 +1,100 @@ +/* + * 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.util.LocalizedFormats; + +import java.util.ArrayList; +import java.util.List; + +/** + * Chromosome represented by a vector of 0s and 1s. + * + * @since 2.0 + */ +public abstract class BinaryChromosome extends AbstractListChromosome<Integer> { + + /** + * Constructor. + * + * @param representation list of {0,1} values representing the chromosome + * @throws InvalidRepresentationException iff the <code>representation</code> can not represent + * a valid chromosome + */ + public BinaryChromosome(List<Integer> representation) throws InvalidRepresentationException { + super(representation); + } + + /** + * Constructor. + * + * @param representation array of {0,1} values representing the chromosome + * @throws InvalidRepresentationException iff the <code>representation</code> can not represent + * a valid chromosome + */ + public BinaryChromosome(Integer[] representation) throws InvalidRepresentationException { + super(representation); + } + + /** {@inheritDoc} */ + @Override + protected void checkValidity(List<Integer> chromosomeRepresentation) + throws InvalidRepresentationException { + for (int i : chromosomeRepresentation) { + if (i < 0 || i > 1) { + throw new InvalidRepresentationException(LocalizedFormats.INVALID_BINARY_DIGIT, i); + } + } + } + + /** + * 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/math3/genetics/BinaryMutation.java b/src/main/java/org/apache/commons/math3/genetics/BinaryMutation.java new file mode 100644 index 0000000..9372b13 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/BinaryMutation.java @@ -0,0 +1,56 @@ +/* + * 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.LocalizedFormats; + +import java.util.ArrayList; +import java.util.List; + +/** + * Mutation for {@link BinaryChromosome}s. Randomly changes one gene. + * + * @since 2.0 + */ +public class BinaryMutation implements MutationPolicy { + + /** + * Mutate the given chromosome. Randomly changes one gene. + * + * @param original the original chromosome. + * @return the mutated chromosome. + * @throws MathIllegalArgumentException if <code>original</code> is not an instance of {@link + * BinaryChromosome}. + */ + public Chromosome mutate(Chromosome original) throws MathIllegalArgumentException { + if (!(original instanceof BinaryChromosome)) { + throw new MathIllegalArgumentException(LocalizedFormats.INVALID_BINARY_CHROMOSOME); + } + + 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/math3/genetics/Chromosome.java b/src/main/java/org/apache/commons/math3/genetics/Chromosome.java new file mode 100644 index 0000000..532a726 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/Chromosome.java @@ -0,0 +1,108 @@ +/* + * 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; + +/** + * Individual in a population. Chromosomes are compared based on their fitness. + * + * <p>The chromosomes are IMMUTABLE, and so their fitness is also immutable and therefore it can be + * cached. + * + * @since 2.0 + */ +public abstract class Chromosome implements Comparable<Chromosome>, Fitness { + /** Value assigned when no fitness has been computed yet. */ + private static final double NO_FITNESS = Double.NEGATIVE_INFINITY; + + /** Cached value of the fitness of this chromosome. */ + private double fitness = NO_FITNESS; + + /** + * Access the fitness of this chromosome. The bigger the fitness, the better the chromosome. + * + * <p>Computation of fitness is usually very time-consuming task, therefore the fitness is + * cached. + * + * @return the fitness + */ + public double getFitness() { + if (this.fitness == NO_FITNESS) { + // 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>1 if <code>another</code> is worse than <code>this</code> + * <li>0 if the two chromosomes have the same fitness + * </ul> + */ + public int compareTo(final Chromosome another) { + return Double.compare(getFitness(), 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(final 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(final 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(final Population population) { + Chromosome sameChromosome = findSameChromosome(population); + if (sameChromosome != null) { + fitness = sameChromosome.getFitness(); + } + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/ChromosomePair.java b/src/main/java/org/apache/commons/math3/genetics/ChromosomePair.java new file mode 100644 index 0000000..e47c1b7 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/ChromosomePair.java @@ -0,0 +1,66 @@ +/* + * 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; + +/** + * A pair of {@link Chromosome} objects. + * + * @since 2.0 + */ +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/math3/genetics/CrossoverPolicy.java b/src/main/java/org/apache/commons/math3/genetics/CrossoverPolicy.java new file mode 100644 index 0000000..d959044 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/CrossoverPolicy.java @@ -0,0 +1,40 @@ +/* + * 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; + +/** + * Policy used to create a pair of new chromosomes by performing a crossover operation on a source + * pair of chromosomes. + * + * @since 2.0 + */ +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. + * @throws MathIllegalArgumentException if the given chromosomes are not compatible with this + * {@link CrossoverPolicy} + */ + ChromosomePair crossover(Chromosome first, Chromosome second) + throws MathIllegalArgumentException; +} diff --git a/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java b/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java new file mode 100644 index 0000000..e07e47c --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java @@ -0,0 +1,185 @@ +/* + * 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.DimensionMismatchException; +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** + * Cycle Crossover [CX] builds offspring from <b>ordered</b> chromosomes by identifying cycles + * between two parent chromosomes. To form the children, the cycles are copied from the respective + * parents. + * + * <p>To form a cycle the following procedure is applied: + * + * <ol> + * <li>start with the first gene of parent 1 + * <li>look at the gene at the same position of parent 2 + * <li>go to the position with the same gene in parent 1 + * <li>add this gene index to the cycle + * <li>repeat the steps 2-5 until we arrive at the starting gene of this cycle + * </ol> + * + * The indices that form a cycle are then used to form the children in alternating order, i.e. in + * cycle 1, the genes of parent 1 are copied to child 1, while in cycle 2 the genes of parent 1 are + * copied to child 2, and so forth ... Example (zero-start cycle): + * + * <pre> + * p1 = (8 4 7 3 6 2 5 1 9 0) X c1 = (8 1 2 3 4 5 6 7 9 0) + * p2 = (0 1 2 3 4 5 6 7 8 9) X c2 = (0 4 7 3 6 2 5 1 8 9) + * + * cycle 1: 8 0 9 + * cycle 2: 4 1 7 2 5 6 + * cycle 3: 3 + * </pre> + * + * 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/CycleCrossoverOperator.aspx"> + * Cycle Crossover Operator</a> + * @param <T> generic type of the {@link AbstractListChromosome}s for crossover + * @since 3.1 + */ +public class CycleCrossover<T> implements CrossoverPolicy { + + /** If the start index shall be chosen randomly. */ + private final boolean randomStart; + + /** Creates a new {@link CycleCrossover} policy. */ + public CycleCrossover() { + this(false); + } + + /** + * Creates a new {@link CycleCrossover} policy using the given {@code randomStart} behavior. + * + * @param randomStart whether the start index shall be chosen randomly or be set to 0 + */ + public CycleCrossover(final boolean randomStart) { + this.randomStart = randomStart; + } + + /** + * Returns whether the starting index is chosen randomly or set to zero. + * + * @return {@code true} if the starting index is chosen randomly, {@code false} otherwise + */ + public boolean isRandomStart() { + return randomStart; + } + + /** + * {@inheritDoc} + * + * @throws MathIllegalArgumentException if the chromosomes are 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: do a crossover copy to simplify the later processing + final List<T> child1Rep = new ArrayList<T>(second.getRepresentation()); + final List<T> child2Rep = new ArrayList<T>(first.getRepresentation()); + + // the set of all visited indices so far + final Set<Integer> visitedIndices = new HashSet<Integer>(length); + // the indices of the current cycle + final List<Integer> indices = new ArrayList<Integer>(length); + + // determine the starting index + int idx = randomStart ? GeneticAlgorithm.getRandomGenerator().nextInt(length) : 0; + int cycle = 1; + + while (visitedIndices.size() < length) { + indices.add(idx); + + T item = parent2Rep.get(idx); + idx = parent1Rep.indexOf(item); + + while (idx != indices.get(0)) { + // add that index to the cycle indices + indices.add(idx); + // get the item in the second parent at that index + item = parent2Rep.get(idx); + // get the index of that item in the first parent + idx = parent1Rep.indexOf(item); + } + + // for even cycles: swap the child elements on the indices found in this cycle + if (cycle++ % 2 != 0) { + for (int i : indices) { + T tmp = child1Rep.get(i); + child1Rep.set(i, child2Rep.get(i)); + child2Rep.set(i, tmp); + } + } + + visitedIndices.addAll(indices); + // find next starting index: last one + 1 until we find an unvisited index + idx = (indices.get(0) + 1) % length; + while (visitedIndices.contains(idx) && visitedIndices.size() < length) { + idx++; + if (idx >= length) { + idx = 0; + } + } + indices.clear(); + } + + return new ChromosomePair( + first.newFixedLengthChromosome(child1Rep), + second.newFixedLengthChromosome(child2Rep)); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java b/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java new file mode 100644 index 0000000..0e7009d --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/ElitisticListPopulation.java @@ -0,0 +1,125 @@ +/* + * 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.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; + +import java.util.Collections; +import java.util.List; + +/** + * 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; + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/Fitness.java b/src/main/java/org/apache/commons/math3/genetics/Fitness.java new file mode 100644 index 0000000..66f8d56 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/Fitness.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.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(); +} diff --git a/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java b/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java new file mode 100644 index 0000000..af63094 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/FixedElapsedTime.java @@ -0,0 +1,78 @@ +/* + * 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; + +import java.util.concurrent.TimeUnit; + +/** + * 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; + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java b/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java new file mode 100644 index 0000000..d7d2088 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/FixedGenerationCount.java @@ -0,0 +1,71 @@ +/* + * 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; + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java b/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java new file mode 100644 index 0000000..e0f1127 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/GeneticAlgorithm.java @@ -0,0 +1,240 @@ +/* + * 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.JDKRandomGenerator; +import org.apache.commons.math3.random.RandomGenerator; + +/** + * 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>Loop until new generation is filled: + * <ul> + * <li>Apply configured SelectionPolicy to select a pair of parents from <code>current + * </code> + * <li>With probability = {@link #getCrossoverRate()}, apply configured {@link + * CrossoverPolicy} to parents + * <li>With probability = {@link #getMutationRate()}, apply configured {@link + * MutationPolicy} to each of the offspring + * <li>Add offspring individually to nextGeneration, space permitting + * </ul> + * <li>Return nextGeneration + * </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; + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java b/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java new file mode 100644 index 0000000..33bc90c --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/InvalidRepresentationException.java @@ -0,0 +1,41 @@ +/* + * 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); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java b/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java new file mode 100644 index 0000000..b2023d6 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/ListPopulation.java @@ -0,0 +1,245 @@ +/* + * 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.NotPositiveException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.exception.NumberIsTooLargeException; +import org.apache.commons.math3.exception.NumberIsTooSmallException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; + +/** + * 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 removes 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}. + * + * @return chromosome iterator + */ + public Iterator<Chromosome> iterator() { + return getChromosomes().iterator(); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java b/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java new file mode 100644 index 0000000..ded2ec6 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/MutationPolicy.java @@ -0,0 +1,37 @@ +/* + * 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; +} diff --git a/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java b/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java new file mode 100644 index 0000000..f78997e --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java @@ -0,0 +1,187 @@ +/* + * 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.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; + +import java.util.ArrayList; +import java.util.List; + +/** + * 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. + * + * <p>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. + * + * <p>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)); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java b/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java new file mode 100644 index 0000000..9514771 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/OnePointCrossover.java @@ -0,0 +1,128 @@ +/* + * 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.DimensionMismatchException; +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +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. + * + * <p>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. + * + * <p>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)); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java b/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java new file mode 100644 index 0000000..eeb62ed --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java @@ -0,0 +1,154 @@ +/* + * 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.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; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** + * 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>copy the slice to child 1 and mark out the genes in parent 2 + * <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. + * </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)); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java b/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java new file mode 100644 index 0000000..0857733 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/PermutationChromosome.java @@ -0,0 +1,38 @@ +/* + * 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); +} diff --git a/src/main/java/org/apache/commons/math3/genetics/Population.java b/src/main/java/org/apache/commons/math3/genetics/Population.java new file mode 100644 index 0000000..25b6c2a --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/Population.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.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(); +} diff --git a/src/main/java/org/apache/commons/math3/genetics/RandomKey.java b/src/main/java/org/apache/commons/math3/genetics/RandomKey.java new file mode 100644 index 0000000..b33eaec --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/RandomKey.java @@ -0,0 +1,296 @@ +/* + * 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.DimensionMismatchException; +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +/** + * 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>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms. Volume 104 of + * Studies in Fuzziness and Soft Computing. Physica-Verlag, Heidelberg (2002) + * </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. + * + * <p>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>. + * + * <p>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); + } + + /** {@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(final 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/math3/genetics/RandomKeyMutation.java b/src/main/java/org/apache/commons/math3/genetics/RandomKeyMutation.java new file mode 100644 index 0000000..6d1512a --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/RandomKeyMutation.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.math3.genetics; + +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +import java.util.ArrayList; +import java.util.List; + +/** + * 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); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java b/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java new file mode 100644 index 0000000..c19c922 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/SelectionPolicy.java @@ -0,0 +1,36 @@ +/* + * 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; +} diff --git a/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.java b/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.java new file mode 100644 index 0000000..06eb2ad --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/StoppingCondition.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.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); +} diff --git a/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java b/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java new file mode 100644 index 0000000..2a9d9d7 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/TournamentSelection.java @@ -0,0 +1,119 @@ +/* + * 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.LocalizedFormats; + +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 + */ +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) { + /** {@inheritDoc} */ + 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; + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java b/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java new file mode 100644 index 0000000..c11450a --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java @@ -0,0 +1,140 @@ +/* + * 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.DimensionMismatchException; +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.OutOfRangeException; +import org.apache.commons.math3.exception.util.LocalizedFormats; +import org.apache.commons.math3.random.RandomGenerator; + +import java.util.ArrayList; +import java.util.List; + +/** + * Perform Uniform Crossover [UX] on the specified chromosomes. A fixed mixing ratio is used to + * combine genes from the first and second parents, e.g. using a ratio of 0.5 would result in + * approximately 50% of genes coming from each parent. This is typically a poor method of crossover, + * but empirical evidence suggests that it is more exploratory and results in a larger part of the + * problem space being searched. + * + * <p>This crossover policy evaluates each gene of the parent chromosomes by chosing a uniform + * random number {@code p} in the range [0, 1]. If {@code p} < {@code ratio}, the parent genes + * are swapped. This means with a ratio of 0.7, 30% of the genes from the first parent and 70% from + * the second parent will be selected for the first offspring (and vice versa for the second + * offspring). + * + * <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://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29">Crossover + * techniques (Wikipedia)</a> + * @see <a + * href="http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php">Crossover + * (Obitko.com)</a> + * @see <a href="http://www.tomaszgwiazda.com/uniformX.htm">Uniform crossover</a> + * @param <T> generic type of the {@link AbstractListChromosome}s for crossover + * @since 3.1 + */ +public class UniformCrossover<T> implements CrossoverPolicy { + + /** The mixing ratio. */ + private final double ratio; + + /** + * Creates a new {@link UniformCrossover} policy using the given mixing ratio. + * + * @param ratio the mixing ratio + * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range + */ + public UniformCrossover(final double ratio) throws OutOfRangeException { + if (ratio < 0.0d || ratio > 1.0d) { + throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d); + } + this.ratio = ratio; + } + + /** + * Returns the mixing ratio used by this {@link CrossoverPolicy}. + * + * @return the mixing ratio + */ + public double getRatio() { + return ratio; + } + + /** + * {@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 + */ + private 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> child1Rep = new ArrayList<T>(length); + final List<T> child2Rep = new ArrayList<T>(length); + + final RandomGenerator random = GeneticAlgorithm.getRandomGenerator(); + + for (int index = 0; index < length; index++) { + + if (random.nextDouble() < ratio) { + // swap the bits -> take other parent + child1Rep.add(parent2Rep.get(index)); + child2Rep.add(parent1Rep.get(index)); + } else { + child1Rep.add(parent1Rep.get(index)); + child2Rep.add(parent2Rep.get(index)); + } + } + + return new ChromosomePair( + first.newFixedLengthChromosome(child1Rep), + second.newFixedLengthChromosome(child2Rep)); + } +} diff --git a/src/main/java/org/apache/commons/math3/genetics/package-info.java b/src/main/java/org/apache/commons/math3/genetics/package-info.java new file mode 100644 index 0000000..32109e8 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/genetics/package-info.java @@ -0,0 +1,18 @@ +/* + * 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. + */ +/** This package provides Genetic Algorithms components and implementations. */ +package org.apache.commons.math3.genetics; |