commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject 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/
Date Sun, 14 Jun 2009 19:04:34 GMT
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



Mime
View raw message