commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1350391 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/genetics/UniformCrossover.java test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
Date Thu, 14 Jun 2012 20:37:29 GMT
Author: tn
Date: Thu Jun 14 20:37:29 2012
New Revision: 1350391

URL: http://svn.apache.org/viewvc?rev=1350391&view=rev
Log:
[MATH-777] Added UniformCrossover policy. Thanks for Reid Hochstedler.

Added:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
  (with props)
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
  (with props)

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java?rev=1350391&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
(added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
Thu Jun 14 20:37:29 2012
@@ -0,0 +1,130 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math3.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.OutOfRangeException;
+import org.apache.commons.math3.exception.util.LocalizedFormats;
+import org.apache.commons.math3.random.RandomGenerator;
+
+/**
+ * Perform Uniform Crossover [UX] on the specified chromosomes. A fixed mixing
+ * ratio is used to combine genes from the first and second parents, e.g. using a
+ * ratio of 0.5 would result in approximately 50% of genes coming from each
+ * parent. This is typically a poor method of crossover, but empirical evidence
+ * suggests that it is more exploratory and results in a larger part of the
+ * problem space being searched.
+ *
+ * <p>This crossover policy evaluates each gene of the parent chromosomes by chosing
a
+ * uniform random number {@code p} in the range [0, 1]. If {@code p} &lt; {@code ratio},
+ * the parent genes are swapped. This means with a ratio of 0.7, 30% of the genes from the
+ * first parent and 70% from the second parent will be selected for the first offspring (and
+ * vice versa for the second offspring).</p>
+ *
+ * <p>This policy works only on {@link AbstractListChromosome}, and therefore it
+ * is parameterized by T. Moreover, the chromosomes must have same lengths.
+ * </p>
+ *
+ * @see <a href="http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29">Crossover
techniques (Wikipedia)</a>
+ * @see <a href="http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php">Crossover
(Obitko.com)</a>
+ * @see <a href="http://www.tomaszgwiazda.com/uniformX.htm">Uniform crossover</a>
+ * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
+ * @since 3.1
+ * @version $Id$
+ */
+public class UniformCrossover<T> implements CrossoverPolicy {
+
+    /** The mixing ratio. */
+    private final double ratio;
+
+    /**
+     * Creates a new {@link UniformCrossover} policy using the given mixing ratio.
+     *
+     * @param ratio the mixing ratio
+     * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range
+     */
+    public UniformCrossover(final double ratio) {
+        if (ratio < 0.0d || ratio > 1.0d) {
+            throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d);
+        }
+        this.ratio = ratio;
+    }
+
+    /**
+     * Returns the mixing ratio used by this {@link CrossoverPolicy}.
+     *
+     * @return the mixing ratio
+     */
+    public double getRatio() {
+        return ratio;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public ChromosomePair crossover(final Chromosome first, final Chromosome second) {
+        if (!(first instanceof AbstractListChromosome<?> && second instanceof
AbstractListChromosome<?>)) {
+            throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
+        }
+        return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>)
second);
+    }
+
+    /**
+     * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
+     *
+     * @param first the first chromosome
+     * @param second the second chromosome
+     * @return the pair of new chromosomes that resulted from the crossover
+     * @throws DimensionMismatchException if the length of the two chromosomes is different
+     */
+    private ChromosomePair mate(final AbstractListChromosome<T> first,
+                                final AbstractListChromosome<T> second) {
+        final int length = first.getLength();
+        if (length != second.getLength()) {
+            throw new DimensionMismatchException(second.getLength(), length);
+        }
+
+        // array representations of the parents
+        final List<T> parent1Rep = first.getRepresentation();
+        final List<T> parent2Rep = second.getRepresentation();
+        // and of the children
+        final List<T> child1Rep = new ArrayList<T>(first.getLength());
+        final List<T> child2Rep = new ArrayList<T>(second.getLength());
+
+        final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
+
+        for (int index = 0; index < length; index++) {
+
+            if (random.nextDouble() < ratio) {
+                // swap the bits -> take other parent
+                child1Rep.add(parent2Rep.get(index));
+                child2Rep.add(parent1Rep.get(index));
+            } else {
+                child1Rep.add(parent1Rep.get(index));
+                child2Rep.add(parent2Rep.get(index));
+            }
+        }
+
+        return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
+                                  second.newFixedLengthChromosome(child2Rep));
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/UniformCrossover.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java?rev=1350391&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
(added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
Thu Jun 14 20:37:29 2012
@@ -0,0 +1,131 @@
+package org.apache.commons.math3.genetics;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import junit.framework.Assert;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.OutOfRangeException;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+public class UniformCrossoverTest {
+    private static final int LEN = 10000;
+    private static final List<Integer> p1 = new ArrayList<Integer>(LEN);
+    private static final List<Integer> p2 = new ArrayList<Integer>(LEN);
+
+    @BeforeClass
+    public static void setUpBeforeClass() {
+        for (int i = 0; i < LEN; i++) {
+            p1.add(0);
+            p2.add(1);
+        }
+    }
+
+    @Test(expected = OutOfRangeException.class)
+    public void testRatioTooLow() {
+        new UniformCrossover<Integer>(-0.5d);
+    }
+    
+    @Test(expected = OutOfRangeException.class)
+    public void testRatioTooHigh() {
+        new UniformCrossover<Integer>(1.5d);
+    }
+    
+    @Test
+    public void testCrossover() {
+        // test crossover with different ratios
+        performCrossover(0.5);
+        performCrossover(0.7);
+        performCrossover(0.2);        
+    }
+    
+    private void performCrossover(double ratio) {
+        final DummyBinaryChromosome p1c = new DummyBinaryChromosome(p1);
+        final DummyBinaryChromosome p2c = new DummyBinaryChromosome(p2);
+
+        final CrossoverPolicy cp = new UniformCrossover<Integer>(ratio);
+
+        // make a number of rounds
+        for (int i = 0; i < 20; i++) {
+            final ChromosomePair pair = cp.crossover(p1c, p2c);
+
+            final List<Integer> c1 = ((DummyBinaryChromosome) pair.getFirst()).getRepresentation();
+            final List<Integer> c2 = ((DummyBinaryChromosome) pair.getSecond()).getRepresentation();
+
+            int from1 = 0;
+            int from2 = 0;
+
+            // check first child
+            for (int val : c1) {
+                if (val == 0) {
+                    from1++;
+                } else {
+                    from2++;
+                }
+            }
+
+            Assert.assertEquals(1.0 - ratio, Double.valueOf((double) from1 / LEN), 0.1);
+            Assert.assertEquals(ratio, Double.valueOf((double) from2 / LEN), 0.1);
+
+            from1 = 0;
+            from2 = 0;
+
+            // check second child
+            for (int val : c2) {
+                if (val == 0) {
+                    from1++;
+                } else {
+                    from2++;
+                }
+            }
+
+            Assert.assertEquals(ratio, Double.valueOf((double) from1 / LEN), 0.1);
+            Assert.assertEquals(1.0 - ratio, Double.valueOf((double) from2 / LEN), 0.1);
+        }
+    }
+    
+    @Test(expected = DimensionMismatchException.class)
+    public void testCrossoverDimensionMismatchException(){
+        final Integer[] p1 = new Integer[] {1,0,1,0,0,1,0,1,1};
+        final Integer[] p2 = new Integer[] {0,1,1,0,1};
+
+        final BinaryChromosome p1c = new DummyBinaryChromosome(p1);
+        final BinaryChromosome p2c = new DummyBinaryChromosome(p2);
+
+        final CrossoverPolicy cp = new UniformCrossover<Integer>(0.5d);
+        cp.crossover(p1c, p2c);
+    }
+    
+    @Test(expected = MathIllegalArgumentException.class)
+    public void testCrossoverInvalidFixedLengthChromosomeFirst() {
+        final Integer[] p1 = new Integer[] {1,0,1,0,0,1,0,1,1};
+        final BinaryChromosome p1c = new DummyBinaryChromosome(p1);
+        final Chromosome p2c = new Chromosome() {
+            public double fitness() {
+                // Not important
+                return 0;
+            }
+        };
+
+        final CrossoverPolicy cp = new UniformCrossover<Integer>(0.5d);
+        cp.crossover(p1c, p2c);
+    }
+    
+    @Test(expected = MathIllegalArgumentException.class)
+    public void testCrossoverInvalidFixedLengthChromosomeSecond() {
+        final Integer[] p1 = new Integer[] {1,0,1,0,0,1,0,1,1};
+        final BinaryChromosome p2c = new DummyBinaryChromosome(p1);
+        final Chromosome p1c = new Chromosome() {
+            public double fitness() {
+                // Not important
+                return 0;
+            }
+        };
+
+        final CrossoverPolicy cp = new UniformCrossover<Integer>(0.5d);
+        cp.crossover(p1c, p2c);
+    }
+}

Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/UniformCrossoverTest.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message