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/06/14 22:37:29 UTC
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
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} < {@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