You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ps...@apache.org on 2009/06/14 21:04:34 UTC
svn commit: r784604 [1/2] - in /commons/proper/math/trunk/src:
java/org/apache/commons/math/genetics/ site/xdoc/
test/org/apache/commons/math/genetics/
Author: psteitz
Date: Sun Jun 14 19:04:32 2009
New Revision: 784604
URL: http://svn.apache.org/viewvc?rev=784604&view=rev
Log:
Added Genetic Algorithm implementation.
JIRA: MATH-207
Contributed by David Stefka
Added:
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/AbstractListChromosome.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryChromosome.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryMutation.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ElitisticListPopulation.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/FixedGenerationCount.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/InvalidRepresentationException.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ListPopulation.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/OnePointCrossover.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/PermutationChromosome.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKey.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKeyMutation.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/TournamentSelection.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryChromosomeTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryMutationTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ChromosomeTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyBinaryChromosome.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyRandomKey.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ElitisticListPopulationTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FitnessCachingTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FixedGenerationCountTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestBinary.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestPermutations.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ListPopulationTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/OnePointCrossoverTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyMutationTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyTest.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/TournamentSelectionTest.java (with props)
Modified:
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/package.html
commons/proper/math/trunk/src/site/xdoc/changes.xml
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/AbstractListChromosome.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/AbstractListChromosome.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/AbstractListChromosome.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/AbstractListChromosome.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,104 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Chromosome represented by an immutable list of a fixed length.
+ *
+ * @param <T> type of the representation list
+ * @version $Revision:$ $Date:$
+ * @since 2.0
+ */
+public abstract class AbstractListChromosome<T> extends Chromosome {
+
+ /** List representing the chromosome */
+ private final List<T> representation;
+
+ /**
+ * Constructor.
+ * @param representation inner representation of the chromosome
+ */
+ public AbstractListChromosome(final List<T> representation) {
+ try {
+ checkValidity(representation);
+ } catch (InvalidRepresentationException e) {
+ throw new IllegalArgumentException(String.format("Invalid representation for %s", getClass().getSimpleName()), e);
+ }
+ this.representation = Collections.unmodifiableList(new ArrayList<T> (representation));
+ }
+
+ /**
+ * Constructor.
+ * @param representation inner representation of the chromosome
+ */
+ public AbstractListChromosome(final T[] representation) {
+ this(Arrays.asList(representation));
+ }
+
+ /**
+ *
+ * Asserts that <code>representation</code> can represent a valid chromosome.
+ * @param representation representation of the chromosome
+ * @throws InvalidRepresentationException iff the <code>representation</code> can not represent
+ * a valid chromosome
+ */
+ protected abstract void checkValidity(List<T> representation) throws InvalidRepresentationException;
+
+ /**
+ * Returns the (immutable) inner representation of the chromosome.
+ * @return the representation of the chromosome
+ */
+ protected List<T> getRepresentation() {
+ return representation;
+ }
+
+ /**
+ * Returns the length of the chromosome.
+ * @return the length of the chromosome
+ */
+ public int getLength() {
+ return getRepresentation().size();
+ }
+
+ /**
+ * Creates a new instance of the same class as <code>this</code> is, with a
+ * given <code>arrayRepresentation</code>. This is needed in crossover and
+ * mutation operators, where we need a new instance of the same class, but
+ * with different array representation.
+ *
+ * Usually, this method just calls a constructor of the class.
+ *
+ * @param representation
+ * 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> representation);
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ return String.format("(f=%s %s)", getFitness(), getRepresentation());
+ }
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/AbstractListChromosome.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryChromosome.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryChromosome.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryChromosome.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryChromosome.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,92 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+
+/**
+ * Chromosome represented by a vector of 0s and 1s.
+ *
+ * @version $Revision:$ $Date:$
+ * @since 2.0
+ */
+public abstract class BinaryChromosome extends AbstractListChromosome<Integer> {
+
+ /**
+ * Constructor.
+ * @param representation list of {0,1} values representing the chromosome
+ */
+ public BinaryChromosome(List<Integer> representation) {
+ super(representation);
+ }
+
+ /**
+ * Constructor.
+ * @param representation array of {0,1} values representing the chromosome
+ */
+ public BinaryChromosome(Integer[] representation) {
+ super(representation);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ protected void checkValidity(List<Integer> representation) throws InvalidRepresentationException {
+ for (int i : representation) {
+ if (i < 0 || i >1)
+ throw new InvalidRepresentationException("Elements can be only 0 or 1.");
+ }
+ }
+
+ /**
+ * Returns a representation of a random binary array of length <code>length</code>.
+ * @param length length of the array
+ * @return a random binary array of length <code>length</code>
+ */
+ public static List<Integer> randomBinaryRepresentation(int length) {
+ // random binary list
+ List<Integer> rList= new ArrayList<Integer> (length);
+ for (int j=0; j<length; j++) {
+ rList.add(GeneticAlgorithm.getRandomGenerator().nextInt(2));
+ }
+ return rList;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ protected boolean isSame(Chromosome another) {
+ // type check
+ if (! (another instanceof BinaryChromosome))
+ return false;
+ BinaryChromosome anotherBc = (BinaryChromosome) another;
+ // size check
+ if (getLength() != anotherBc.getLength())
+ return false;
+
+ for (int i=0; i< getRepresentation().size(); i++) {
+ if (!(getRepresentation().get(i).equals(anotherBc.getRepresentation().get(i))))
+ return false;
+ }
+ // all is ok
+ return true;
+ }
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryChromosome.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryMutation.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryMutation.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryMutation.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryMutation.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,52 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Mutation for {@link BinaryChromosome}s. Randomly changes one gene.
+ *
+ * @version $Revision:$ $Date:$
+ * @since 2.0
+ */
+public class BinaryMutation implements MutationPolicy {
+
+ /**
+ * Mutate the given chromosome. Randomly changes one gene.
+ * @param original the original chromosome.
+ * @return the mutated chromomsome.
+ */
+ public Chromosome mutate(Chromosome original) {
+ if (!(original instanceof BinaryChromosome)) {
+ throw new IllegalArgumentException("Binary mutation works on BinaryChromosome only.");
+ }
+
+ BinaryChromosome origChrom = (BinaryChromosome) original;
+ List<Integer> newRepr = new ArrayList<Integer>(origChrom.getRepresentation());
+
+ // randomly select a gene
+ int geneIndex = GeneticAlgorithm.getRandomGenerator().nextInt(origChrom.getLength());
+ // and change it
+ newRepr.set(geneIndex, origChrom.getRepresentation().get(geneIndex) == 0 ? 1 : 0);
+
+ Chromosome newChrom = origChrom.newFixedLengthChromosome(newRepr);
+ return newChrom;
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/BinaryMutation.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java Sun Jun 14 19:04:32 2009
@@ -18,13 +18,94 @@
/**
* Individual in a population. Chromosomes are compared based on their fitness.
- * @version $Revision$ $Date$
+ *
+ * The chromosomes are IMMUTABLE, and so their fitness is also immutable and
+ * therefore it can be cached.
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
*/
-public interface Chromosome {
+public abstract class Chromosome implements Comparable<Chromosome>,Fitness {
+
/**
- * Access the fitness of this chromosome.
+ * Cached value of the fitness of this chromosome.
+ */
+ private double fitness = Double.MIN_VALUE;
+
+ /**
+ * Access the fitness of this chromosome. The bigger the fitness, the better
+ * the chromosome.
+ *
+ * Computation of fitness is usually very time-consuming task, therefore the
+ * fitness is cached.
*
* @return the fitness.
*/
- Fitness getFitness();
+ public double getFitness() {
+ if (this.fitness == Double.MIN_VALUE) {
+ // no cache - compute the fitness
+ this.fitness = fitness();
+ }
+ return this.fitness;
+ }
+
+ /**
+ * Compares two chromosomes based on their fitness. The bigger the fitness,
+ * the better the chromosome.
+ *
+ * @param another another chromosome to compare
+ * @return
+ * <ul>
+ * <li>-1 if <code>another</code> is better than <code>this</code></li>
+ * <li>1 if <code>another</code> is worse than <code>this</code></li>
+ * <li>0 if the two chromosomes have the same fitness</li>
+ * </ul>
+ */
+ public int compareTo(Chromosome another) {
+ return ((Double)this.getFitness()).compareTo(another.getFitness());
+ }
+
+ /**
+ * Returns <code>true<code> iff <code>another</code> has the same
+ * representation and therefore the same fitness. By default, it returns
+ * false -- override it in your implementation if you need it.
+ * @param another chromosome to compare
+ * @return true if <code>another</code> is equivalent to this chromosome
+ */
+ protected boolean isSame(Chromosome another) {
+ return false;
+ }
+
+ /**
+ * Searches the <code>population</code> for another chromosome with the same
+ * representation. If such chromosome is found, it is returned, if no such
+ * chromosome exists, returns <code>null</code>.
+ *
+ * @param population
+ * Population to search
+ * @return Chromosome with the same representation, or <code>null</code> if
+ * no such chromosome exists.
+ */
+ protected Chromosome findSameChromosome(Population population) {
+ for (Chromosome anotherChr : population) {
+ if (this.isSame(anotherChr))
+ return anotherChr;
+ }
+ return null;
+ }
+
+ /**
+ * Searches the population for a chromosome representing the same solution,
+ * and if it finds one, updates the fitness to its value.
+ *
+ * @param population
+ * Population to search
+ */
+ public void searchForFitnessUpdate(Population population) {
+ Chromosome sameChromosome = findSameChromosome(population);
+ if (sameChromosome != null) {
+ fitness = sameChromosome.getFitness();
+ }
+ }
+
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java Sun Jun 14 19:04:32 2009
@@ -18,14 +18,16 @@
/**
* A pair of {@link Chromosome} objects.
+ * @since 2.0
+ *
* @version $Revision$ $Date$
*/
public class ChromosomePair {
/** the first chromosome in the pair. */
- private Chromosome first;
+ private final Chromosome first;
/** the second chromosome in the pair. */
- private Chromosome second;
+ private final Chromosome second;
/**
* Create a chromosome pair.
@@ -33,7 +35,7 @@
* @param c1 the first chromosome.
* @param c2 the second chromosome.
*/
- public ChromosomePair(Chromosome c1, Chromosome c2) {
+ public ChromosomePair(final Chromosome c1, final Chromosome c2) {
super();
first = c1;
second = c2;
@@ -56,4 +58,12 @@
public Chromosome getSecond() {
return second;
}
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ return String.format("(%s,%s)", getFirst(), getSecond());
+ }
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java Sun Jun 14 19:04:32 2009
@@ -19,6 +19,8 @@
/**
* Policy used to create a pair of new chromosomes by performing a crossover
* operation on a source pair of chromosomes.
+ *
+ * @since 2.0
* @version $Revision$ $Date$
*/
public interface CrossoverPolicy {
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ElitisticListPopulation.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ElitisticListPopulation.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ElitisticListPopulation.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ElitisticListPopulation.java Sun Jun 14 19:04:32 2009
@@ -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.math.genetics;
+
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Population of chromosomes which uses elitism (certain percentace of the best
+ * chromosomes is directly copied to the next generation).
+ *
+ * @version $Revision:$ $Date:$
+ * @since 2.0
+ */
+public class ElitisticListPopulation extends ListPopulation {
+
+ /** percentage of chromosomes copied to the next generation */
+ private double elitismRate = 0.9;
+
+ /**
+ * Creates a new ElitisticListPopulation instance.
+ *
+ * @param chromosomes
+ * list of chromosomes in the population
+ * @param populationLimit
+ * maximal size of the population
+ * @param elitismRate
+ * how many best chromosomes will be directly transferred to the
+ * next generation [in %]
+ */
+ public ElitisticListPopulation(List<Chromosome> chromosomes, int populationLimit, double elitismRate) {
+ super(chromosomes, populationLimit);
+ this.elitismRate = elitismRate;
+ }
+
+ /**
+ * Creates a new ListPopulation instance and initializes its inner
+ * chromosome list.
+ *
+ * @param populationLimit maximal size of the population
+ * @param elitismRate
+ * how many best chromosomes will be directly transferred to the
+ * next generation [in %]
+ */
+ public ElitisticListPopulation(int populationLimit, double elitismRate) {
+ super(populationLimit);
+ this.elitismRate = elitismRate;
+ }
+
+ /**
+ * Start the population for the next generation. The
+ * <code>{@link #elitismRate}<code> percents of the best
+ * chromosomes are directly copied to the next generation.
+ *
+ * @return the beginnings of the next generation.
+ */
+ public Population nextGeneration() {
+ // initialize a new generation with the same parameters
+ ElitisticListPopulation nextGeneration = new ElitisticListPopulation(this.getPopulationLimit(), this.getElitismRate());
+
+ List<Chromosome> oldChromosomes = this.getChromosomes();
+ Collections.sort(oldChromosomes);
+
+ // index of the last "not good enough" chromosome
+ int boundIndex = (int) Math.ceil((1.0 - this.getElitismRate()) * oldChromosomes.size());
+ for (int i=boundIndex; i<oldChromosomes.size(); i++) {
+ nextGeneration.addChromosome(oldChromosomes.get(i));
+ }
+ return nextGeneration;
+ }
+
+ /**
+ * Sets the elitism rate, i.e. how many best chromosomes will be directly
+ * transferred to the next generation [in %].
+ *
+ * @param elitismRate
+ * how many best chromosomes will be directly transferred to the
+ * next generation [in %]
+ */
+ public void setElitismRate(double elitismRate) {
+ if (elitismRate < 0 || elitismRate > 1)
+ throw new IllegalArgumentException("Elitism rate has to be in [0,1]");
+ this.elitismRate = elitismRate;
+ }
+
+ /**
+ * Access the elitism rate.
+ * @return the elitism rate
+ */
+ public double getElitismRate() {
+ return this.elitismRate;
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ElitisticListPopulation.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java Sun Jun 14 19:04:32 2009
@@ -17,9 +17,17 @@
package org.apache.commons.math.genetics;
/**
- * Interface used to compare chromosomes.
- * @version $Revision$ $Date$
+ * Fitness of a chromosome.
+ *
+ * @version $Revision:$ $Date:$
* @since 2.0
*/
-public interface Fitness extends Comparable<Fitness> {
+public interface Fitness {
+ /**
+ * Compute the fitness. This is usually very time-consuming, so the value
+ * should be cached.
+ *
+ * @return fitness
+ */
+ public double fitness();
}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/FixedGenerationCount.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/FixedGenerationCount.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/FixedGenerationCount.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/FixedGenerationCount.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,70 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+/**
+ * Stops after a fixed number of generations. Each time
+ * {@link #isSatisfied(Population)} is invoked, a generation counter is
+ * incremented. Once the counter reaches the configured
+ * <code>maxGenerations</code> value, {@link #isSatisfied(Population)} returns
+ * true.
+ *
+ * @version $Revision:$ $Date:$
+ * @since 2.0
+ */
+public class FixedGenerationCount implements StoppingCondition {
+ /** Number of generations that have passed */
+ private int numGenerations = 0;
+
+ /** Maximum number of generations (stopping criteria) */
+ private final int maxGenerations;
+
+ /**
+ * Create a new FixedGenerationCount instance.
+ *
+ * @param maxGenerations number of generations to evolve
+ */
+ public FixedGenerationCount(int maxGenerations) {
+ if (maxGenerations <= 0)
+ throw new IllegalArgumentException("The number of generations has to be >= 0");
+ this.maxGenerations = maxGenerations;
+ }
+
+ /**
+ * Determine whether or not the given number of generations have passed.
+ * Increments the number of generations counter if the maximum has not
+ * been reached.
+ *
+ * @param population ignored (no impact on result)
+ * @return <code>true</code> IFF the maximum number of generations has been exceeded
+ */
+ public boolean isSatisfied(Population population) {
+ if (this.numGenerations < this.maxGenerations) {
+ numGenerations++;
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * @return the number of generations that have passed
+ */
+ public int getNumGenerations() {
+ return numGenerations;
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/FixedGenerationCount.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java Sun Jun 14 19:04:32 2009
@@ -16,28 +16,83 @@
*/
package org.apache.commons.math.genetics;
+import org.apache.commons.math.random.RandomGenerator;
+import org.apache.commons.math.random.JDKRandomGenerator;
+
/**
* Implementation of a genetic algorithm. All factors that govern the operation
* of the algorithm can be configured for a specific problem.
- *
- * @version $Revision$ $Date$
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
*/
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.
+ */
+ private static RandomGenerator randomGenerator = new JDKRandomGenerator();
+
+ /**
+ * Set the (static) random generator.
+ *
+ * @param random random generator
+ */
+ public synchronized static void setRandomGenerator(RandomGenerator random) {
+ randomGenerator = random;
+ }
+
+ /**
+ * Returns the (static) random generator.
+ *
+ * @return the static random generator shared by GA implementation classes
+ */
+ public synchronized static RandomGenerator getRandomGenerator() {
+ return randomGenerator;
+ }
+
/** the crossover policy used by the algorithm. */
- private CrossoverPolicy crossoverPolicy;
+ protected final CrossoverPolicy crossoverPolicy;
/** the rate of crossover for the algorithm. */
- private double crossoverRate;
+ protected final double crossoverRate;
/** the mutation policy used by the algorithm. */
- private MutationPolicy mutationPolicy;
+ protected final MutationPolicy mutationPolicy;
/** the rate of mutation for the algorithm. */
- private double mutationRate;
+ protected final double mutationRate;
/** the selection policy used by the algorithm. */
- private SelectionPolicy selectionPolicy;
-
+ protected final SelectionPolicy selectionPolicy;
+
+ /**
+ * @param crossoverPolicy The {@link CrossoverPolicy}
+ * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)
+ * @param mutationPolicy The {@link MutationPolicy}
+ * @param mutationRate The mutation rate as a percentage (0-1 inclusive)
+ * @param selectionPolicy The {@link selectionPolicy}
+ */
+ public GeneticAlgorithm(
+ CrossoverPolicy crossoverPolicy, double crossoverRate,
+ MutationPolicy mutationPolicy, double mutationRate,
+ SelectionPolicy selectionPolicy) {
+ if (crossoverRate < 0 || crossoverRate > 1) {
+ throw new IllegalArgumentException("crossoverRate must be between 0 and 1");
+ }
+ if (mutationRate < 0 || mutationRate > 1) {
+ throw new IllegalArgumentException("mutationRate must be between 0 and 1");
+ }
+ this.crossoverPolicy = crossoverPolicy;
+ this.crossoverRate = crossoverRate;
+ this.mutationPolicy = mutationPolicy;
+ this.mutationRate = mutationRate;
+ this.selectionPolicy = selectionPolicy;
+ }
+
/**
* Evolve the given population. Evolution stops when the stopping condition
* is satisfied.
@@ -55,51 +110,6 @@
}
/**
- * Access the crossover policy.
- *
- * @return the crossover policy.
- */
- private CrossoverPolicy getCrossoverPolicy() {
- return crossoverPolicy;
- }
-
- /**
- * Access the crossover rate.
- *
- * @return the crossover rate.
- */
- private double getCrossoverRate() {
- return crossoverRate;
- }
-
- /**
- * Access the mutation policy.
- *
- * @return the mutation policy.
- */
- private MutationPolicy getMutationPolicy() {
- return mutationPolicy;
- }
-
- /**
- * Access the mutation rate.
- *
- * @return the mutation rate.
- */
- private double getMutationRate() {
- return mutationRate;
- }
-
- /**
- * Access the selection policy.
- *
- * @return the selection policy.
- */
- private SelectionPolicy getSelectionPolicy() {
- return selectionPolicy;
- }
-
- /**
* <p>Evolve the given population into the next generation.</p>
* <p><ol>
* <li>Get nextGeneration population to fill from <code>current</code>
@@ -118,89 +128,80 @@
* </ol>
* </p>
*
- *
* @param current the current population.
* @return the population for the next generation.
*/
- private Population nextGeneration(Population current) {
+ public Population nextGeneration(Population current) {
Population nextGeneration = current.nextGeneration();
- while (nextGeneration.getPopulationSize() < nextGeneration
- .getPopulationLimit()) {
+ while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
// select parent chromosomes
ChromosomePair pair = getSelectionPolicy().select(current);
// crossover?
- if (Math.random() < getCrossoverRate()) {
+ if (randomGenerator.nextDouble() < getCrossoverRate()) {
// apply crossover policy to create two offspring
- pair = getCrossoverPolicy().crossover(pair.getFirst(),
- pair.getSecond());
+ pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond());
}
// mutation?
- if (Math.random() < getMutationRate()) {
+ if (randomGenerator.nextDouble() < getMutationRate()) {
// apply mutation policy to the chromosomes
pair = new ChromosomePair(
- getMutationPolicy().mutate(pair.getFirst()),
- getMutationPolicy().mutate(pair.getSecond())
- );
+ 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()) {
+ if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) {
// add the second chromosome to the population
nextGeneration.addChromosome(pair.getSecond());
}
}
return nextGeneration;
- }
-
+ }
+
/**
- * Modify the crossover policy.
- *
- * @param value the new crossover policy.
+ * Returns the crossover policy.
+ * @return crossover policy
*/
- public void setCrossoverPolicy(CrossoverPolicy value) {
- this.crossoverPolicy = value;
+ public CrossoverPolicy getCrossoverPolicy() {
+ return crossoverPolicy;
}
/**
- * Modify the crossover rate.
- *
- * @param value the new crossover rate.
+ * Returns the crossover rate.
+ * @return crossover rate
*/
- public void setCrossoverRate(double value) {
- this.crossoverRate = value;
+ public double getCrossoverRate() {
+ return crossoverRate;
}
/**
- * Modify the mutation policy.
- *
- * @param value the new mutation policy.
+ * Returns the mutation policy.
+ * @return mutation policy
*/
- public void setMutationPolicy(MutationPolicy value) {
- this.mutationPolicy = value;
+ public MutationPolicy getMutationPolicy() {
+ return mutationPolicy;
}
/**
- * Modify the mutation rate.
- *
- * @param value the new mutation rate.
+ * Returns the mutation rate.
+ * @return mutation rate
*/
- public void setMutationRate(double value) {
- this.mutationRate = value;
+ public double getMutationRate() {
+ return mutationRate;
}
/**
- * Modify the selection policy.
- *
- * @param value the new selection policy.
+ * Returns the selection policy.
+ * @return selection policy
*/
- public void setSelectionPolicy(SelectionPolicy value) {
- this.selectionPolicy = value;
+ public SelectionPolicy getSelectionPolicy() {
+ return selectionPolicy;
}
+
}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/InvalidRepresentationException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/InvalidRepresentationException.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/InvalidRepresentationException.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/InvalidRepresentationException.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,63 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+/**
+ * Exception indicating that the representation of a chromosome is not valid.
+ *
+ * @version $Revision:$ $Date:$
+ * @since 2.0
+ */
+public class InvalidRepresentationException extends Exception {
+
+ /** Serialization version id */
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Constructor
+ */
+ public InvalidRepresentationException() {
+ super();
+ }
+
+ /**
+ * Construct an InvalidRepresentationException
+ * @param arg0 exception message
+ */
+ public InvalidRepresentationException(String arg0) {
+ super(arg0);
+ }
+
+ /**
+ * Construct an InvalidRepresentationException
+ * @param arg0 cause
+ */
+ public InvalidRepresentationException(Throwable arg0) {
+ super(arg0);
+ }
+
+ /**
+ * Construct an InvalidRepresentationException
+ *
+ * @param arg0 exception message
+ * @param arg1 cause
+ */
+ public InvalidRepresentationException(String arg0, Throwable arg1) {
+ super(arg0, arg1);
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/InvalidRepresentationException.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ListPopulation.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ListPopulation.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ListPopulation.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ListPopulation.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,150 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * Population of chromosomes represented by a {@link List}.
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
+ */
+public abstract class ListPopulation implements Population {
+
+ /** List of chromosomes */
+ private List<Chromosome> chromosomes;
+
+ /** maximial size of the population */
+ private int populationLimit;
+
+
+ /**
+ * Creates a new ListPopulation instance.
+ *
+ * @param chromosomes list of chromosomes in the population
+ * @param populationLimit maximal size of the population
+ */
+ public ListPopulation (List<Chromosome> chromosomes, int populationLimit) {
+ if (chromosomes.size() > populationLimit) {
+ throw new IllegalArgumentException("List of chromosomes bigger than maxPopulationSize.");
+ }
+ if (populationLimit < 0) {
+ throw new IllegalArgumentException("Population limit has to be >= 0");
+ }
+
+ this.chromosomes = chromosomes;
+ this.populationLimit = populationLimit;
+ }
+
+ /**
+ * Creates a new ListPopulation instance and initializes its inner
+ * chromosome list.
+ *
+ * @param populationLimit maximal size of the population
+ */
+ public ListPopulation (int populationLimit) {
+ if (populationLimit < 0) {
+ throw new IllegalArgumentException("Population limit has to be >= 0");
+ }
+ this.populationLimit = populationLimit;
+ this.chromosomes = new ArrayList<Chromosome>(populationLimit);
+ }
+
+ /**
+ * Sets the list of chromosomes.
+ * @param chromosomes the list of chromosomes
+ */
+ public void setChromosomes(List<Chromosome> chromosomes) {
+ this.chromosomes = chromosomes;
+ }
+
+ /**
+ * Access the list of chromosomes.
+ * @return the list of chromosomes
+ */
+ public List<Chromosome> getChromosomes() {
+ return chromosomes;
+ }
+
+ /**
+ * Add the given chromosome to the population.
+ * @param chromosome the chromosome to add.
+ */
+ public void addChromosome(Chromosome chromosome) {
+ this.chromosomes.add(chromosome);
+ }
+
+ /**
+ * Access the fittest chromosome in this population.
+ * @return the fittest chromosome.
+ */
+ public Chromosome getFittestChromosome() {
+ // best so far
+ Chromosome bestChromosome = this.chromosomes.get(0);
+ for (Chromosome chromosome : this.chromosomes) {
+ if (chromosome.compareTo(bestChromosome) > 0) {
+ // better chromosome found
+ bestChromosome = chromosome;
+ }
+ }
+ return bestChromosome;
+ }
+
+ /**
+ * Access the maximum population size.
+ * @return the maximum population size.
+ */
+ public int getPopulationLimit() {
+ return this.populationLimit;
+ }
+
+ /**
+ * Sets the maximal population size.
+ * @param populationLimit maximal population size.
+ */
+ public void setPopulationLimit(int populationLimit) {
+ this.populationLimit = populationLimit;
+ }
+
+ /**
+ * Access the current population size.
+ * @return the current population size.
+ */
+ public int getPopulationSize() {
+ return this.chromosomes.size();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ return this.chromosomes.toString();
+ }
+
+ /**
+ * Chromosome list iterator
+ *
+ * @return chromosome iterator
+ */
+ public Iterator<Chromosome> iterator() {
+ return chromosomes.iterator();
+ }
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ListPopulation.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java Sun Jun 14 19:04:32 2009
@@ -18,6 +18,8 @@
/**
* Algorithm used to mutate a chrommosome.
+ *
+ * @since 2.0
* @version $Revision$ $Date$
*/
public interface MutationPolicy {
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/OnePointCrossover.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/OnePointCrossover.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/OnePointCrossover.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/OnePointCrossover.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+
+/**
+ * One point crossover policy. A random crossover point is selected and the
+ * first part from each parent is copied to the corresponding child, and the
+ * second parts are copied crosswise.
+ *
+ * Example:
+ * <pre>
+ * -C- denotes a crossover point
+ * -C- -C-
+ * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1)
+ * \------------/ \-----/ \------------/ \-----/
+ * || (*) || (**)
+ * VV (**) VV (*)
+ * /------------\ /-----\ /------------\ /-----\
+ * c1 = (1 0 1 0 0 1 | 1 1 1) X p2 = (0 1 1 0 1 0 | 0 1 1)
+ * </pre>
+ *
+ * This policy works only on {@link AbstractListChromosome}, and therefore it
+ * is parametrized by T. Moreover, the chromosomes must have same lengths.
+ *
+ * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
+ * @since 2.0
+ * @version $Revision:$ $Date:$
+ *
+ */
+public class OnePointCrossover<T> implements CrossoverPolicy {
+
+ /**
+ * Performs one point crossover. A random crossover point is selected and the
+ * first part from each parent is copied to the corresponding child, and the
+ * second parts are copied crosswise.
+ *
+ * Example:
+ * -C- denotes a crossover point
+ * -C- -C-
+ * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1)
+ * \------------/ \-----/ \------------/ \-----/
+ * || (*) || (**)
+ * VV (**) VV (*)
+ * /------------\ /-----\ /------------\ /-----\
+ * c1 = (1 0 1 0 0 1 | 1 1 1) X p2 = (0 1 1 0 1 0 | 0 1 1)
+ *
+ * @param first first parent (p1)
+ * @param second second parent (p2)
+ * @return pair of two children (c1,c2)
+ */
+ @SuppressWarnings("unchecked")
+ public ChromosomePair crossover(Chromosome first, Chromosome second) {
+ if (! (first instanceof AbstractListChromosome && second instanceof AbstractListChromosome)) {
+ throw new IllegalArgumentException("One point crossover works on FixedLengthChromosomes only.");
+ }
+ return crossover((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
+ }
+
+
+ /**
+ * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
+ *
+ * @param first the first chromosome.
+ * @param second the second chromosome.
+ * @return the pair of new chromosomes that resulted from the crossover.
+ */
+ private ChromosomePair crossover(AbstractListChromosome<T> first, AbstractListChromosome<T> second) {
+ int length = first.getLength();
+ if (length != second.getLength())
+ throw new IllegalArgumentException("Both chromosomes must have same lengths.");
+
+ // array representations of the parents
+ List<T> parent1Rep = first.getRepresentation();
+ List<T> parent2Rep = second.getRepresentation();
+ // and of the children
+ ArrayList<T> child1Rep = new ArrayList<T> (first.getLength());
+ ArrayList<T> child2Rep = new ArrayList<T> (second.getLength());
+
+ // select a crossover point at random (0 and length makes no sense)
+ int crossoverIndex = 1 + (GeneticAlgorithm.getRandomGenerator().nextInt(length-2));
+
+ // copy the first part
+ for (int i = 0; i < crossoverIndex; i++) {
+ child1Rep.add(parent1Rep.get(i));
+ child2Rep.add(parent2Rep.get(i));
+ }
+ // and switch the second part
+ for (int i = crossoverIndex; i < length; i++) {
+ child1Rep.add(parent2Rep.get(i));
+ child2Rep.add(parent1Rep.get(i));
+ }
+
+ return new ChromosomePair(
+ first.newFixedLengthChromosome(child1Rep),
+ second.newFixedLengthChromosome(child2Rep)
+ );
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/OnePointCrossover.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/PermutationChromosome.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/PermutationChromosome.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/PermutationChromosome.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/PermutationChromosome.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.List;
+
+/**
+ * Interface indicating that the chromosome represents a permutation of objects.
+ *
+ * @param <T>
+ * type of the permuted objects
+ * @since 2.0
+ * @version $Revision:$ $Date:$
+ */
+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
+ */
+ public List<T> decode(List<T> sequence);
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/PermutationChromosome.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java Sun Jun 14 19:04:32 2009
@@ -18,9 +18,11 @@
/**
* A collection of chromosomes that facilitates generational evolution.
- * @version $Revision$ $Date$
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
*/
-public interface Population {
+public interface Population extends Iterable<Chromosome> {
/**
* Access the current population size.
* @return the current population size.
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKey.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKey.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKey.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKey.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,290 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * <p>
+ * Random Key chromosome is used for permutation representation. It is a vector
+ * of a fixed length of real numbers in [0,1] interval. The index of the i-th
+ * smallest value in the vector represents an i-th member of the permutation.
+ * </p>
+ *
+ * <p>
+ * For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the
+ * permutation of indices (3,0,1,2). If the original (unpermuted) sequence would
+ * be (a,b,c,d), this would mean the sequence (d,a,b,c).
+ * </p>
+ *
+ * <p>
+ * With this representation, common operators like n-point crossover can be
+ * used, because any such chromosome represents a valid permutation.
+ * </p>
+ *
+ * <p>
+ * Since the chromosome (and thus its arrayRepresentation) is immutable, the
+ * array representation is sorted only once in the constructor.
+ * </p>
+ *
+ * <p>
+ * For details, see:
+ * <ul>
+ * <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and
+ * optimization. ORSA Journal on Computing 6 (1994) 154â160</li>
+ * <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms.
+ * Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag,
+ * Heidelberg (2002)</li>
+ * </ul>
+ * </p>
+ *
+ * @param <T>
+ * type of the permuted objects
+ * @since 2.0
+ * @version $Revision:$ $Date:$
+ */
+public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> {
+
+ /**
+ * Cache of sorted representation (unmodifiable).
+ */
+ private final List<Double> sortedRepresentation;
+
+ /**
+ * Base sequence [0,1,...,n-1], permuted accorting to the representation (unmodifiable).
+ */
+ private final List<Integer> baseSeqPermutation;
+
+ /**
+ * Constructor.
+ *
+ * @param representation list of [0,1] values representing the permutation
+ */
+ public RandomKey(List<Double> representation) {
+ super(representation);
+ // store the sorted representation
+ List<Double> sortedRepr = new ArrayList<Double> (getRepresentation());
+ Collections.sort(sortedRepr);
+ sortedRepresentation = Collections.unmodifiableList(sortedRepr);
+ // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods
+ baseSeqPermutation = Collections.unmodifiableList(
+ decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation)
+ );
+ }
+
+ /**
+ * Constructor.
+ *
+ * @param representation array of [0,1] values representing the permutation
+ */
+ public RandomKey(Double[] representation) {
+ this(Arrays.asList(representation));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public List<T> decode(List<T> sequence) {
+ return decodeGeneric(sequence, getRepresentation(), sortedRepresentation);
+ }
+
+ /**
+ * Decodes a permutation represented by <code>representation</code> and
+ * returns a (generic) list with the permuted values.
+ *
+ * @param <S> generic type of the sequence values
+ * @param sequence the unpermuted sequence
+ * @param representation representation of the permutation ([0,1] vector)
+ * @param sortedRepr sorted <code>representation</code>
+ * @return list with the sequence values permuted according to the representation
+ */
+ private static <S> List<S> decodeGeneric(List<S> sequence, List<Double> representation, List<Double> sortedRepr) {
+ int l = sequence.size();
+
+ if (representation.size() != l) {
+ throw new IllegalArgumentException(String.format("Length of sequence for decoding (%s) has to be equal to the length of the RandomKey (%s)", l, representation.size()));
+ }
+ if (representation.size() != sortedRepr.size()) {
+ throw new IllegalArgumentException(String.format("Representation and sortedRepr must have same sizes, %d != %d", representation.size(), sortedRepr.size()));
+ }
+
+ List<Double> reprCopy = new ArrayList<Double> (representation);// do not modify the orig. representation
+
+ // now find the indices in the original repr and use them for permuting
+ List<S> res = new ArrayList<S> (l);
+ for (int i=0; i<l; i++) {
+ int index = reprCopy.indexOf(sortedRepr.get(i));
+ res.add(sequence.get(index));
+ reprCopy.set(index, null);
+ }
+ return res;
+ }
+
+ /**
+ * Returns <code>true</code> iff <code>another</code> is a RandomKey and
+ * encodes the same permutation.
+ *
+ * @param another chromosome to compare
+ * @return true iff chromosomes encode the same permutation
+ */
+ @Override
+ protected boolean isSame(Chromosome another) {
+ // type check
+ if (! (another instanceof RandomKey))
+ return false;
+ RandomKey<?> anotherRk = (RandomKey<?>) another;
+ // size check
+ if (getLength() != anotherRk.getLength())
+ return false;
+
+ // two different representations can still encode the same permutation
+ // the ordering is what counts
+ List<Integer> thisPerm = this.baseSeqPermutation;
+ List<Integer> anotherPerm = anotherRk.baseSeqPermutation;
+
+ for (int i=0; i<getLength(); i++) {
+ if (thisPerm.get(i) != anotherPerm.get(i))
+ return false;
+ }
+ // the permutations are the same
+ return true;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ protected void checkValidity(java.util.List<Double> representation) throws InvalidRepresentationException {
+ for (double val : representation) {
+ if (val < 0 || val > 1) {
+ throw new InvalidRepresentationException("Values of representation must be in [0,1] interval");
+ }
+ }
+ };
+
+
+ /**
+ * Generates a representation corresponding to a random permutation of
+ * length l which can be passed to the RandomKey constructor.
+ *
+ * @param l
+ * length of the permutation
+ * @return representation of a random permutation
+ */
+ public static final List<Double> randomPermutation(int l) {
+ List<Double> repr = new ArrayList<Double>(l);
+ for (int i=0; i<l; i++) {
+ repr.add(GeneticAlgorithm.getRandomGenerator().nextDouble());
+ }
+ return repr;
+ }
+
+ /**
+ * Generates a representation corresponding to an identity permutation of
+ * length l which can be passed to the RandomKey constructor.
+ *
+ * @param l
+ * length of the permutation
+ * @return representation of an identity permutation
+ */
+ public static final List<Double> identityPermutation(int l) {
+ List<Double> repr = new ArrayList<Double>(l);
+ for (int i=0; i<l; i++) {
+ repr.add((double)i/l);
+ }
+ return repr;
+ }
+
+ /**
+ * Generates a representation of a permutation corresponding to the
+ * <code>data</code> sorted by <code>comparator</code>. The
+ * <code>data</code> is not modified during the process.
+ *
+ * This is useful if you want to inject some permutations to the initial
+ * population.
+ *
+ * @param <S> type of the data
+ * @param data list of data determining the order
+ * @param comparator how the data will be compared
+ * @return list representation of the permutation corresponding to the parameters
+ */
+ public static <S> List<Double> comparatorPermutation(List<S> data, Comparator<S> comparator) {
+ List<S> sortedData = new ArrayList<S> (data);
+ Collections.sort(sortedData, comparator);
+
+ return inducedPermutation(data, sortedData);
+ }
+
+ /**
+ * Generates a representation of a permutation corresponding to a
+ * permutation which yields <code>permutedData</code> when applied to
+ * <code>originalData</code>.
+ *
+ * This method can be viewed as an inverse to {@link #decode(List)}.
+ *
+ * @param <S> type of the data
+ * @param originalData the original, unpermuted data
+ * @param permutedData the data, somehow permuted
+ * @return representation of a permutation corresponding to the permutation <code>originalData -> permutedData</code>
+ * @throws IllegalArgumentException iff the <code>permutedData</code> and <code>originalData</code> contains different data
+ */
+ public static <S> List<Double> inducedPermutation(List<S> originalData, List<S> permutedData) throws IllegalArgumentException {
+ if (originalData.size() != permutedData.size()) {
+ throw new IllegalArgumentException("originalData and permutedData must have same length");
+ }
+ int l = originalData.size();
+
+ List<S> origDataCopy = new ArrayList<S> (originalData);
+
+ Double[] res = new Double[l];
+ for (int i=0; i<l; i++) {
+ int index = origDataCopy.indexOf(permutedData.get(i));
+ if (index == -1) {
+ throw new IllegalArgumentException("originalData and permutedData must contain the same objects.");
+ }
+ res[index] = (double) i / l;
+ origDataCopy.set(index, null);
+ }
+ return Arrays.asList(res);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation);
+ }
+
+ /**
+ * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).
+ *
+ * @param l length of list to generate
+ * @return list of integers from 0 to l-1
+ */
+ private static List<Integer> baseSequence(int l) {
+ List<Integer> baseSequence = new ArrayList<Integer> (l);
+ for (int i=0; i<l; i++) {
+ baseSequence.add(i);
+ }
+ return baseSequence;
+ }
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKey.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKeyMutation.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKeyMutation.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKeyMutation.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKeyMutation.java Sun Jun 14 19:04:32 2009
@@ -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.math.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.math.MathRuntimeException;
+
+/**
+ * Mutation operator for {@link RandomKey}s. Changes a randomly chosen element
+ * of the array representation to a random value uniformly distributed in [0,1].
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
+ */
+public class RandomKeyMutation implements MutationPolicy {
+
+ /**
+ * {@inheritDoc}
+ *
+ * @throws IllegalArgumentException if <code>original</code> is not a
+ * {@link RandomKeys} instance
+ */
+ public Chromosome mutate(Chromosome original) {
+ if (!(original instanceof RandomKey)) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "RandomKeyMutation works only with RandomKeys, got " +
+ 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);
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/RandomKeyMutation.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java Sun Jun 14 19:04:32 2009
@@ -18,7 +18,9 @@
/**
* Algorithm used to select a chromosome pair from a population.
- * @version $Revision$ $Date$
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
*/
public interface SelectionPolicy {
/**
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java Sun Jun 14 19:04:32 2009
@@ -18,7 +18,9 @@
/**
* Algorithm used to determine when to stop evolution.
- * @version $Revision$ $Date$
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
*/
public interface StoppingCondition {
/**
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/TournamentSelection.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/TournamentSelection.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/TournamentSelection.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/TournamentSelection.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,114 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Tournament selection scheme. Each of the two selected chromosomes is selected
+ * based on n-ary tournament -- this is done by drawing {@link #arity} random
+ * chromosomes without replacement from the population, and then selecting the
+ * fittest chromosome among them.
+ *
+ * @since 2.0
+ * @version $Revision:$ $Date:$
+ */
+public class TournamentSelection implements SelectionPolicy {
+
+ /** number of chromosomes included in the tournament selections */
+ private int arity;
+
+ /**
+ * Creates a new TournamentSelection instance.
+ *
+ * @param arity
+ * how many chromosomes will be drawn to the tournament
+ */
+ public TournamentSelection(int arity) {
+ this.arity = arity;
+ }
+
+ /**
+ * Select two chromosomes from the population. Each of the two selected
+ * chromosomes is selected based on n-ary tournament -- this is done by
+ * drawing {@link #arity} random chromosomes without replacement from the
+ * population, and then selecting the fittest chromosome among them.
+ *
+ * @param population
+ * the population from which the chromosomes are choosen.
+ * @return the selected chromosomes.
+ */
+ public ChromosomePair select(Population population) {
+ return new ChromosomePair(
+ tournament((ListPopulation) population),
+ tournament((ListPopulation)population)
+ );
+ }
+
+ /**
+ * Helper for {@link #select(Population)}. Draw {@link #arity} random
+ * chromosomes without replacement from the population, and then select the
+ * fittest chromosome among them.
+ *
+ * @param population
+ * the population from which the chromosomes are choosen.
+ * @return the selected chromosome.
+ */
+ private Chromosome tournament(ListPopulation population) {
+ if (population.getPopulationSize() < this.arity)
+ throw new IllegalArgumentException("Tournament arity cannot be bigger than population size.");
+ // auxiliary population
+ ListPopulation tournamentPopulation = new ListPopulation(this.arity) {
+ public Population nextGeneration() {
+ // not useful here
+ return null;
+ }
+ };
+
+ // create a copy of the chromosome list
+ List<Chromosome> chromosomes = new ArrayList<Chromosome> (population.getChromosomes());
+ for (int i=0; i<this.arity; i++) {
+ // select a random individual and add it to the tournament
+ int rind = GeneticAlgorithm.getRandomGenerator().nextInt(chromosomes.size());
+ tournamentPopulation.addChromosome(chromosomes.get(rind));
+ // do not select it again
+ chromosomes.remove(rind);
+ }
+ // the winner takes it all
+ return tournamentPopulation.getFittestChromosome();
+ }
+
+ /**
+ * Gets the arity (number of chromosomes drawn to the tournament).
+ *
+ * @return arity of the tournament
+ */
+ public int getArity() {
+ return arity;
+ }
+
+ /**
+ * Sets the arity (number of chromosomes drawn to the tournament).
+ *
+ * @param arity arity of the tournament
+ */
+ public void setArity(int arity) {
+ this.arity = arity;
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/TournamentSelection.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/package.html
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/package.html?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/package.html (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/package.html Sun Jun 14 19:04:32 2009
@@ -18,7 +18,7 @@
<!-- $Revision$ -->
<body>
<p>
-This package provides basic genetic algorithms components.
+This package provides Genetic Algorithms components and implementations.
</p>
</body>
</html>
Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=784604&r1=784603&r2=784604&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Sun Jun 14 19:04:32 2009
@@ -39,6 +39,9 @@
</properties>
<body>
<release version="2.0" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-207" due-to="David Stefka">
+ Added Genetic Algorithm implementation.
+ </action>
<action dev="luc" type="fix" issue="MATH-274" >
Fixed detection of not positive definite matrices in Cholesky decomposition
</action>
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryChromosomeTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryChromosomeTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryChromosomeTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryChromosomeTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,67 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import org.junit.Test;
+
+public class BinaryChromosomeTest {
+
+ @Test
+ public void testInvalidConstructor() {
+ Integer[][] reprs = new Integer[][] {
+ new Integer[] {0,1,0,1,2},
+ new Integer[] {0,1,0,1,-1}
+ };
+
+ for (Integer[] repr : reprs) {
+ try {
+ new DummyBinaryChromosome(repr);
+ fail("Exception not caught");
+ } catch (IllegalArgumentException e) {
+
+ }
+ }
+ }
+
+ @Test
+ public void testRandomConstructor() {
+ for (int i=0; i<20; i++) {
+ new DummyBinaryChromosome(BinaryChromosome.randomBinaryRepresentation(10));
+ }
+ }
+
+ @Test
+ public void testIsSame() {
+ Chromosome c1 = new DummyBinaryChromosome(new Integer[] {0,1,0,1,0,1});
+ Chromosome c2 = new DummyBinaryChromosome(new Integer[] {0,1,1,0,1});
+ Chromosome c3 = new DummyBinaryChromosome(new Integer[] {0,1,0,1,0,1,1});
+ Chromosome c4 = new DummyBinaryChromosome(new Integer[] {1,1,0,1,0,1});
+ Chromosome c5 = new DummyBinaryChromosome(new Integer[] {0,1,0,1,0,0});
+ Chromosome c6 = new DummyBinaryChromosome(new Integer[] {0,1,0,1,0,1});
+
+ assertFalse(c1.isSame(c2));
+ assertFalse(c1.isSame(c3));
+ assertFalse(c1.isSame(c4));
+ assertFalse(c1.isSame(c5));
+ assertTrue(c1.isSame(c6));
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryChromosomeTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryMutationTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryMutationTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryMutationTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryMutationTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.genetics;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+
+public class BinaryMutationTest {
+
+ @Test
+ public void testMutate() {
+ BinaryMutation mutation = new BinaryMutation();
+
+ // stochastic testing :)
+ for (int i=0; i<20; i++) {
+ DummyBinaryChromosome original = new DummyBinaryChromosome(BinaryChromosome.randomBinaryRepresentation(10));
+ DummyBinaryChromosome mutated = (DummyBinaryChromosome) mutation.mutate(original);
+
+ // one gene should be different
+ int numDifferent = 0;
+ for (int j=0; j<original.getRepresentation().size(); j++) {
+ if (original.getRepresentation().get(j) != mutated.getRepresentation().get(j))
+ numDifferent++;
+ }
+ assertEquals(1, numDifferent);
+ }
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/BinaryMutationTest.java
------------------------------------------------------------------------------
svn:eol-style = native