commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1369637 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/genetics/CycleCrossover.java test/java/org/apache/commons/math3/genetics/CycleCrossoverTest.java
Date Sun, 05 Aug 2012 18:46:54 GMT
Author: tn
Date: Sun Aug  5 18:46:54 2012
New Revision: 1369637

URL: http://svn.apache.org/viewvc?rev=1369637&view=rev
Log:
[MATH-777] Added CycleCrossover policy.

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

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java?rev=1369637&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java
(added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/CycleCrossover.java
Sun Aug  5 18:46:54 2012
@@ -0,0 +1,160 @@
+package org.apache.commons.math3.genetics;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.util.LocalizedFormats;
+
+/**
+ * Cycle Crossover [CX] builds offspring from <b>ordered</b> chromosomes by identifying
cycles
+ * between two parent chromosomes. To form the children, the cycles are copied from the
+ * respective parents.
+ * <p>
+ * To form a cycle the following procedure is applied:
+ * <ol>
+ *   <li>start with the first gene of parent 1</li>
+ *   <li>look at the gene at the same position of parent 2</li>
+ *   <li>go to the position with the same gene in parent 1</li>
+ *   <li>add this gene index to the cycle</li>
+ *   <li>repeat the steps 2-5 until we arrive at the starting gene of this cycle</li>
+ * </ol>
+ * The indices that form a cycle are then used to form the children in alternating order,
i.e.
+ * in cycle 1, the genes of parent 1 are copied to child 1, while in cycle 2 the genes of
parent 1
+ * are copied to child 2, and so forth ...
+ * </p>
+ *
+ * Example (zero-start cycle):
+ * <pre>
+ * p1 = (8 4 7 3 6 2 5 1 9 0)    X   c1 = (8 1 2 3 4 5 6 7 9 0)
+ * p2 = (0 1 2 3 4 5 6 7 8 9)    X   c2 = (0 4 7 3 6 2 5 1 8 9)
+ *
+ * cycle 1: 8 0 9
+ * cycle 2: 4 1 7 2 5 6
+ * cycle 3: 3
+ * </pre>
+ *
+ * This policy works only on {@link AbstractListChromosome}, and therefore it
+ * is parameterized by T. Moreover, the chromosomes must have same lengths.
+ *
+ * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/CycleCrossoverOperator.aspx"
+ * Cycle Crossover Operator</a>
+ *
+ * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
+ * @since 3.1
+ * @version $Id$
+ */
+public class CycleCrossover<T> implements CrossoverPolicy {
+
+    /** If the start index shall be chosen randomly. */
+    private final boolean randomStart;
+
+    /**
+     * Creates a new {@link CycleCrossover} policy.
+     */
+    public CycleCrossover() {
+        this(false);
+    }
+
+    /**
+     * Creates a new {@link CycleCrossover} policy using the given {@code randomStart} behavior.
+     *
+     * @param randomStart whether the start index shall be chosen randomly or be set to 0
+     */
+    public CycleCrossover(final boolean randomStart) {
+        this.randomStart = randomStart;
+    }
+
+    /**
+     * Returns whether the starting index is chosen randomly or set to zero.
+     *
+     * @return {@code true} if the starting index is chosen randomly, {@code false} otherwise
+     */
+    public boolean isRandomStart() {
+        return randomStart;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @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
+     */
+    protected 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: do a crossover copy to simplify the later processing
+        final List<T> child1Rep = new ArrayList<T>(second.getRepresentation());
+        final List<T> child2Rep = new ArrayList<T>(first.getRepresentation());
+
+        // the set of all visited indices so far
+        final Set<Integer> visitedIndices = new HashSet<Integer>(length);
+        // the indices of the current cycle
+        final List<Integer> indices = new ArrayList<Integer>(length);
+
+        // determine the starting index
+        int idx = randomStart ? GeneticAlgorithm.getRandomGenerator().nextInt(length) : 0;
+        int cycle = 1;
+
+        while (visitedIndices.size() < length) {
+            indices.add(idx);
+
+            T item = parent2Rep.get(idx);
+            idx = parent1Rep.indexOf(item);
+
+            while (idx != indices.get(0)) {
+                // add that index to the cycle indices
+                indices.add(idx);
+                // get the item in the second parent at that index
+                item = parent2Rep.get(idx);
+                // get the index of that item in the first parent
+                idx = parent1Rep.indexOf(item);
+            }
+
+            // for even cycles: swap the child elements on the indices found in this cycle
+            if (cycle++ % 2 != 0) {
+                for (int i : indices) {
+                    T tmp = child1Rep.get(i);
+                    child1Rep.set(i, child2Rep.get(i));
+                    child2Rep.set(i, tmp);
+                }
+            }
+
+            visitedIndices.addAll(indices);
+            // find next starting index: last one + 1 until we find an unvisited index
+            idx = (indices.get(0) + 1) % length;
+            while (visitedIndices.contains(idx) && visitedIndices.size() < length)
{
+                idx++;
+                if (idx >= length) {
+                    idx = 0;
+                }
+            }
+            indices.clear();
+        }
+
+        return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
+                                  second.newFixedLengthChromosome(child2Rep));
+    }
+}

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

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

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

Added: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/CycleCrossoverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/CycleCrossoverTest.java?rev=1369637&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/CycleCrossoverTest.java
(added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/CycleCrossoverTest.java
Sun Aug  5 18:46:54 2012
@@ -0,0 +1,133 @@
+package org.apache.commons.math3.genetics;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class CycleCrossoverTest {
+    
+    @Test
+    public void testCrossoverExample() {
+        // taken from http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/CycleCrossoverOperator.aspx
+        final Integer[] p1 = new Integer[] { 8, 4, 7, 3, 6, 2, 5, 1, 9, 0 };
+        final Integer[] p2 = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+        final DummyListChromosome p1c = new DummyListChromosome(p1);
+        final DummyListChromosome p2c = new DummyListChromosome(p2);
+
+        final CrossoverPolicy cp = new CycleCrossover<Integer>();
+        final ChromosomePair pair = cp.crossover(p1c, p2c);
+
+        final Integer[] c1 = ((DummyListChromosome) pair.getFirst()).getRepresentation().toArray(new
Integer[p1.length]);
+        final Integer[] c2 = ((DummyListChromosome) pair.getSecond()).getRepresentation().toArray(new
Integer[p2.length]);
+
+        final Integer[] c1e = new Integer[] { 8, 1, 2, 3, 4, 5, 6, 7, 9, 0 };
+        final Integer[] c2e = new Integer[] { 0, 4, 7, 3, 6, 2, 5, 1, 8, 9 };
+
+        Assert.assertArrayEquals(c1e, c1);
+        Assert.assertArrayEquals(c2e, c2);
+    }
+
+    @Test
+    public void testCrossoverExample2() {
+        // taken from http://www.scribd.com/doc/54206412/32/Cycle-crossover
+        final Integer[] p1 = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+        final Integer[] p2 = new Integer[] { 9, 3, 7, 8, 2, 6, 5, 1, 4};
+        final DummyListChromosome p1c = new DummyListChromosome(p1);
+        final DummyListChromosome p2c = new DummyListChromosome(p2);
+
+        final CrossoverPolicy cp = new CycleCrossover<Integer>();
+        final ChromosomePair pair = cp.crossover(p1c, p2c);
+
+        final Integer[] c1 = ((DummyListChromosome) pair.getFirst()).getRepresentation().toArray(new
Integer[p1.length]);
+        final Integer[] c2 = ((DummyListChromosome) pair.getSecond()).getRepresentation().toArray(new
Integer[p2.length]);
+
+        final Integer[] c1e = new Integer[] { 1, 3, 7, 4, 2, 6, 5, 8, 9 };
+        final Integer[] c2e = new Integer[] { 9, 2, 3, 8, 5, 6, 7, 1, 4 };
+
+        Assert.assertArrayEquals(c1e, c1);
+        Assert.assertArrayEquals(c2e, c2);
+    }
+
+    @Test
+    public void testCrossover() {
+        final Integer[] p1 = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+        final Integer[] p2 = new Integer[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
+        final DummyListChromosome p1c = new DummyListChromosome(p1);
+        final DummyListChromosome p2c = new DummyListChromosome(p2);
+
+        final CrossoverPolicy cp = new CycleCrossover<Integer>(true);
+
+        for (int i = 0; i < 20; i++) {
+            final ChromosomePair pair = cp.crossover(p1c, p2c);
+
+            final Integer[] c1 = ((DummyListChromosome) pair.getFirst()).getRepresentation().toArray(new
Integer[p1.length]);
+            final Integer[] c2 = ((DummyListChromosome) pair.getSecond()).getRepresentation().toArray(new
Integer[p2.length]);
+
+            int index = 0;
+            // Determine if it is in the same spot as in the first parent, if 
+            // not it comes from the second parent.
+            for (final Integer j : c1) {
+                if (!p1[index].equals(j)) {
+                    Assert.assertEquals(j, p2[index]);
+                } else {
+                    Assert.assertEquals(j, p1[index]);
+                }
+                index++;
+            }
+
+            // Same as above only for the second parent.
+            index = 0;
+            for (final Integer k : c2) {
+                if (p2[index] != k) {
+                    Assert.assertEquals(k, p1[index]);
+                } else {
+                    Assert.assertEquals(k, p2[index]);
+                }
+                index++;
+            }
+        }
+    }
+
+    @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 CycleCrossover<Integer>();
+        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 CycleCrossover<Integer>();
+        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 CycleCrossover<Integer>();
+        cp.crossover(p1c, p2c);
+    }
+}

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

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

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



Mime
View raw message