commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1344030 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/genetics/NPointCrossover.java test/java/org/apache/commons/math3/genetics/NPointCrossoverTest.java
Date Tue, 29 May 2012 22:24:24 GMT
Author: tn
Date: Tue May 29 22:24:24 2012
New Revision: 1344030

URL: http://svn.apache.org/viewvc?rev=1344030&view=rev
Log:
[MATH-777] added NPointCrossover policy, thanks to Reid Hochstedler.

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

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java?rev=1344030&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java
(added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/genetics/NPointCrossover.java
Tue May 29 22:24:24 2012
@@ -0,0 +1,178 @@
+/*
+ * 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.NotStrictlyPositiveException;
+import org.apache.commons.math3.exception.NumberIsTooLargeException;
+import org.apache.commons.math3.exception.util.LocalizedFormats;
+import org.apache.commons.math3.random.RandomGenerator;
+
+/**
+ * N-point crossover policy. For each iteration 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 (2-point crossover):
+ * <pre>
+ * -C- denotes a crossover point
+ *           -C-       -C-                         -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                  VV      (*)        VV
+ *      /----\ /--------\ /-----\             /----\ /--------\ /-----\
+ * c1 = (1 0  | 1 0 1 0  | 0 1 1)    X   c2 = (0 1  | 1 0 0 1  | 0 1 1)
+ * </pre>
+ *
+ * This policy works only on {@link AbstractListChromosome}, and therefore it
+ * is parameterized by T. Moreover, the chromosomes must have same lengths.
+ *
+ * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
+ * @since 3.1
+ * @version $Id$
+ */
+public class NPointCrossover<T> implements CrossoverPolicy {
+
+    /** The number of crossover points. */
+    private final int crossoverPoints;
+
+    /**
+     * Creates a new {@link NPointCrossover} policy using the given number of points.
+     *
+     * <p><b>Note</b>: the number of crossover points must be &lt;
<code>chromosome length - 1</code>.
+     * This condition can only be checked at runtime, as the chromosome length is not known
in advance.
+     * </p>
+     *
+     * @param crossoverPoints the number of crossover points
+     * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not
+     * strictly positive
+     */
+    public NPointCrossover(final int crossoverPoints) {
+        if (crossoverPoints <= 0) {
+            throw new NotStrictlyPositiveException(crossoverPoints);
+        }
+        this.crossoverPoints = crossoverPoints;
+    }
+
+    /**
+     * Returns the number of crossover points used by this {@link CrossoverPolicy}.
+     *
+     * @return the number of crossover points
+     */
+    public int getCrossoverPoints() {
+        return crossoverPoints;
+    }
+
+    /**
+     * Performs a N-point crossover. N random crossover points are selected and are used
+     * to divide the parent chromosomes into segments. The segments are copied in alternate
+     * order from the two parents to the corresponding child chromosomes.
+     *
+     * Example (2-point crossover):
+     * <pre>
+     * -C- denotes a crossover point
+     *           -C-       -C-                         -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                  VV      (*)        VV
+     *      /----\ /--------\ /-----\             /----\ /--------\ /-----\
+     * c1 = (1 0  | 1 0 1 0  | 0 1 1)    X   c2 = (0 1  | 1 0 0 1  | 0 1 1)
+     * </pre>
+     *
+     * @param first first parent (p1)
+     * @param second second parent (p2)
+     * @return pair of two children (c1,c2)
+     * @throws MathIllegalArgumentException iff one of the chromosomes is
+     *         not an instance of {@link AbstractListChromosome}
+     * @throws DimensionMismatchException if the length of the two chromosomes is different
+     */
+    @SuppressWarnings("unchecked") // OK because of instanceof checks
+    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
+     * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for
the
+     * actual chromosomes
+     */
+    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);
+        }
+        if (crossoverPoints >= length) {
+            throw new NumberIsTooLargeException(crossoverPoints, length, false);
+        }
+
+        // array representations of the parents
+        final List<T> parent1Rep = first.getRepresentation();
+        final List<T> parent2Rep = second.getRepresentation();
+        // and of the children
+        final ArrayList<T> child1Rep = new ArrayList<T>(first.getLength());
+        final ArrayList<T> child2Rep = new ArrayList<T>(second.getLength());
+
+        final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
+
+        ArrayList<T> c1 = child1Rep;
+        ArrayList<T> c2 = child2Rep;
+
+        int remainingPoints = crossoverPoints;
+        int lastIndex = 0;
+        for (int i = 0; i < crossoverPoints; i++, remainingPoints--) {
+            // select the next crossover point at random
+            final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex
- remainingPoints);
+
+            // copy the current segment
+            for (int j = lastIndex; j < crossoverIndex; j++) {
+                c1.add(parent1Rep.get(j));
+                c2.add(parent2Rep.get(j));
+            }
+
+            // swap the children for the next segment
+            ArrayList<T> tmp = c1;
+            c1 = c2;
+            c2 = tmp;
+
+            lastIndex = crossoverIndex;
+        }
+
+        // copy the last segment
+        for (int j = lastIndex; j < length; j++) {
+            c1.add(parent1Rep.get(j));
+            c2.add(parent2Rep.get(j));
+        }
+
+        return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
+                                  second.newFixedLengthChromosome(child2Rep));
+    }
+}

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

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

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

Added: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/NPointCrossoverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/NPointCrossoverTest.java?rev=1344030&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/NPointCrossoverTest.java
(added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/NPointCrossoverTest.java
Tue May 29 22:24:24 2012
@@ -0,0 +1,113 @@
+package org.apache.commons.math3.genetics;
+
+import java.util.List;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.NumberIsTooLargeException;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class NPointCrossoverTest {
+
+    @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 NPointCrossover<Integer>(1);
+        cp.crossover(p1c,p2c);
+    }
+    
+    @Test(expected = NumberIsTooLargeException.class)
+    public void testNumberIsTooLargeException() {
+        final Integer[] p1 = new Integer[] {1,0,1,0,0,1,0,1,1};
+        final Integer[] p2 = new Integer[] {0,1,1,0,1,0,1,1,1};
+
+        final BinaryChromosome p1c = new DummyBinaryChromosome(p1);
+        final BinaryChromosome p2c = new DummyBinaryChromosome(p2);
+
+        final CrossoverPolicy cp = new NPointCrossover<Integer>(15);
+        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 NPointCrossover<Integer>(1);
+        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 NPointCrossover<Integer>(1);
+        cp.crossover(p1c,p2c);
+    }
+    
+    @Test
+    public void testCrossover() {
+        Integer[] p1 = new Integer[] {1,0,1,0,1,0,1,0,1};
+        Integer[] p2 = new Integer[] {0,1,0,1,0,1,0,1,0};
+
+        BinaryChromosome p1c = new DummyBinaryChromosome(p1);
+        BinaryChromosome p2c = new DummyBinaryChromosome(p2);
+
+        final int order = 3;
+        NPointCrossover<Integer> npc = new NPointCrossover<Integer>(order);
+
+        // the two parent chromosomes are different at each position, so it is easy to detect
+        // the number of crossovers that happened for each child
+        for (int i=0; i<20; i++) {
+            ChromosomePair pair = npc.crossover(p1c,p2c);
+
+            Integer[] c1 = new Integer[p1.length];
+            Integer[] c2 = new Integer[p2.length];
+
+            c1 = ((BinaryChromosome) pair.getFirst()).getRepresentation().toArray(c1);
+            c2 = ((BinaryChromosome) pair.getSecond()).getRepresentation().toArray(c2);
+
+            Assert.assertEquals(order, detectCrossoverPoints(p1c, p2c, (BinaryChromosome)
pair.getFirst()));
+            Assert.assertEquals(order, detectCrossoverPoints(p2c, p1c, (BinaryChromosome)
pair.getSecond()));            
+        }
+    }
+    
+    private int detectCrossoverPoints(BinaryChromosome p1, BinaryChromosome p2, BinaryChromosome
c) {
+        int crossovers = 0;
+        final int length = p1.getLength();
+
+        final List<Integer> p1Rep = p1.getRepresentation();
+        final List<Integer> p2Rep = p2.getRepresentation();
+        final List<Integer> cRep = c.getRepresentation();
+        
+        List<Integer> rep = p1Rep;
+        for (int i = 0; i < length; i++) {
+            if (rep.get(i) != cRep.get(i)) {
+                crossovers++;
+                rep = rep == p1Rep ? p2Rep : p1Rep;
+            }
+        }
+        
+        return crossovers;
+    }
+
+}

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

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

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



Mime
View raw message