You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/08/05 22:03:28 UTC
svn commit: r1369658 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math3/genetics/OrderedCrossover.java
test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java
Author: tn
Date: Sun Aug 5 20:03:28 2012
New Revision: 1369658
URL: http://svn.apache.org/viewvc?rev=1369658&view=rev
Log:
[MATH-777] Added OrderedCrossover policy.
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java (with props)
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java (with props)
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java?rev=1369658&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java Sun Aug 5 20:03:28 2012
@@ -0,0 +1,128 @@
+package org.apache.commons.math3.genetics;
+
+import java.util.ArrayList;
+import java.util.Collections;
+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;
+import org.apache.commons.math3.random.RandomGenerator;
+import org.apache.commons.math3.util.FastMath;
+
+/**
+ * Order 1 Crossover [OX1] builds offspring from <b>ordered</b> chromosomes by copying a
+ * consecutive slice from one parent, and filling up the remaining genes from the other
+ * parent as they appear.
+ * <p>
+ * This policy works by applying the following rules:
+ * <ol>
+ * <li>select a random slice of consecutive genes from parent 1</li>
+ * <li>copy the slice to child 1 and mark out the genes in parent 2</li>
+ * <li>starting from the right side of the slice, copy genes from parent 2 as they
+ * appear to child 1 if they are not yet marked out.</li>
+ * </ol>
+ * </p>
+ *
+ * Example (random sublist from index 3 to 7, underlined):
+ * <pre>
+ * p1 = (8 4 7 3 6 2 5 1 9 0) X c1 = (0 4 7 3 6 2 5 1 8 9)
+ * --------- ---------
+ * p2 = (0 1 2 3 4 5 6 7 8 9) X c2 = (8 1 2 3 4 5 6 7 9 0)
+ * </pre>
+ *
+ * This policy works only on {@link AbstractListChromosome}, and therefore it
+ * is parameterized by T. Moreover, the chromosomes must have same lengths.
+ *
+ * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx"
+ * Order 1 Crossover Operator</a>
+ *
+ * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
+ * @since 3.1
+ * @version $Id$
+ */
+public class OrderedCrossover<T> implements CrossoverPolicy {
+
+ /**
+ * {@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
+ final List<T> child1 = new ArrayList<T>(length);
+ final List<T> child2 = new ArrayList<T>(length);
+ // sets of already inserted items for quick access
+ final Set<T> child1Set = new HashSet<T>(length);
+ final Set<T> child2Set = new HashSet<T>(length);
+
+ final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
+ // choose random points, making sure that lb < ub.
+ int a = random.nextInt(length);
+ int b;
+ do {
+ b = random.nextInt(length);
+ } while (a == b);
+ // determine the lower and upper bounds
+ final int lb = FastMath.min(a, b);
+ final int ub = FastMath.max(a, b);
+
+ // add the subLists that are between lb and ub
+ child1.addAll(parent1Rep.subList(lb, ub + 1));
+ child1Set.addAll(child1);
+ child2.addAll(parent2Rep.subList(lb, ub + 1));
+ child2Set.addAll(child2);
+
+ // iterate over every item in the parents
+ for (int i = 1; i <= length; i++) {
+ final int idx = (ub + i) % length;
+
+ // retrieve the current item in each parent
+ final T item1 = parent1Rep.get(idx);
+ final T item2 = parent2Rep.get(idx);
+
+ // if the first child already contains the item in the second parent add it
+ if (!child1Set.contains(item2)) {
+ child1.add(item2);
+ child1Set.add(item2);
+ }
+
+ // if the second child already contains the item in the first parent add it
+ if (!child2Set.contains(item1)) {
+ child2.add(item1);
+ child2Set.add(item1);
+ }
+ }
+
+ // rotate so that the original slice is in the same place as in the parents.
+ Collections.rotate(child1, lb);
+ Collections.rotate(child2, lb);
+
+ return new ChromosomePair(first.newFixedLengthChromosome(child1),
+ second.newFixedLengthChromosome(child2));
+ }
+}
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/OrderedCrossover.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java?rev=1369658&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java (added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java Sun Aug 5 20:03:28 2012
@@ -0,0 +1,86 @@
+package org.apache.commons.math3.genetics;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class OrderedCrossoverTest {
+
+ @Test
+ public void testCrossover() {
+ 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 OrderedCrossover<Integer>();
+
+ for (int i = 0; i < 20; i++) {
+ final Set<Integer> parentSet1 = new HashSet<Integer>(Arrays.asList(p1));
+ final Set<Integer> parentSet2 = new HashSet<Integer>(Arrays.asList(p2));
+
+ 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]);
+
+ Assert.assertNotSame(p1c, pair.getFirst());
+ Assert.assertNotSame(p2c, pair.getSecond());
+
+ // make sure that the children have exactly the same elements as their parents
+ for (int j = 0; j < c1.length; j++) {
+ Assert.assertTrue(parentSet1.contains(c1[j]));
+ parentSet1.remove(c1[j]);
+ Assert.assertTrue(parentSet2.contains(c2[j]));
+ parentSet2.remove(c2[j]);
+ }
+ }
+ }
+
+ @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 OrderedCrossover<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 OrderedCrossover<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 OrderedCrossover<Integer>();
+ cp.crossover(p1c, p2c);
+ }
+}
Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/OrderedCrossoverTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain