UniformCrossover.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.math4.legacy.genetics;

  18. import java.util.ArrayList;
  19. import java.util.List;

  20. import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
  21. import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
  22. import org.apache.commons.math4.legacy.exception.OutOfRangeException;
  23. import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
  24. import org.apache.commons.rng.UniformRandomProvider;

  25. /**
  26.  * Perform Uniform Crossover [UX] on the specified chromosomes. A fixed mixing
  27.  * ratio is used to combine genes from the first and second parents, e.g. using a
  28.  * ratio of 0.5 would result in approximately 50% of genes coming from each
  29.  * parent. This is typically a poor method of crossover, but empirical evidence
  30.  * suggests that it is more exploratory and results in a larger part of the
  31.  * problem space being searched.
  32.  * <p>
  33.  * This crossover policy evaluates each gene of the parent chromosomes by choosing a
  34.  * uniform random number {@code p} in the range [0, 1]. If {@code p} &lt; {@code ratio},
  35.  * the parent genes are swapped. This means with a ratio of 0.7, 30% of the genes from the
  36.  * first parent and 70% from the second parent will be selected for the first offspring (and
  37.  * vice versa for the second offspring).
  38.  * <p>
  39.  * This policy works only on {@link AbstractListChromosome}, and therefore it
  40.  * is parameterized by T. Moreover, the chromosomes must have same lengths.
  41.  *
  42.  * @see <a href="http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29">Crossover techniques (Wikipedia)</a>
  43.  * @see <a href="http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php">Crossover (Obitko.com)</a>
  44.  * @see <a href="http://www.tomaszgwiazda.com/uniformX.htm">Uniform crossover</a>
  45.  * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
  46.  * @since 3.1
  47.  */
  48. public class UniformCrossover<T> implements CrossoverPolicy {

  49.     /** The mixing ratio. */
  50.     private final double ratio;

  51.     /**
  52.      * Creates a new {@link UniformCrossover} policy using the given mixing ratio.
  53.      *
  54.      * @param ratio the mixing ratio
  55.      * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range
  56.      */
  57.     public UniformCrossover(final double ratio) throws OutOfRangeException {
  58.         if (ratio < 0.0d || ratio > 1.0d) {
  59.             throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d);
  60.         }
  61.         this.ratio = ratio;
  62.     }

  63.     /**
  64.      * Returns the mixing ratio used by this {@link CrossoverPolicy}.
  65.      *
  66.      * @return the mixing ratio
  67.      */
  68.     public double getRatio() {
  69.         return ratio;
  70.     }

  71.     /**
  72.      * {@inheritDoc}
  73.      *
  74.      * @throws MathIllegalArgumentException iff one of the chromosomes is
  75.      *   not an instance of {@link AbstractListChromosome}
  76.      * @throws DimensionMismatchException if the length of the two chromosomes is different
  77.      */
  78.     @Override
  79.     @SuppressWarnings("unchecked")
  80.     public ChromosomePair crossover(final Chromosome first, final Chromosome second)
  81.         throws DimensionMismatchException, MathIllegalArgumentException {

  82.         if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
  83.             throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
  84.         }
  85.         return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
  86.     }

  87.     /**
  88.      * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
  89.      *
  90.      * @param first the first chromosome
  91.      * @param second the second chromosome
  92.      * @return the pair of new chromosomes that resulted from the crossover
  93.      * @throws DimensionMismatchException if the length of the two chromosomes is different
  94.      */
  95.     private ChromosomePair mate(final AbstractListChromosome<T> first,
  96.                                 final AbstractListChromosome<T> second) throws DimensionMismatchException {
  97.         final int length = first.getLength();
  98.         if (length != second.getLength()) {
  99.             throw new DimensionMismatchException(second.getLength(), length);
  100.         }

  101.         // array representations of the parents
  102.         final List<T> parent1Rep = first.getRepresentation();
  103.         final List<T> parent2Rep = second.getRepresentation();
  104.         // and of the children
  105.         final List<T> child1Rep = new ArrayList<>(length);
  106.         final List<T> child2Rep = new ArrayList<>(length);

  107.         final UniformRandomProvider random = GeneticAlgorithm.getRandomGenerator();

  108.         for (int index = 0; index < length; index++) {

  109.             if (random.nextDouble() < ratio) {
  110.                 // swap the bits -> take other parent
  111.                 child1Rep.add(parent2Rep.get(index));
  112.                 child2Rep.add(parent1Rep.get(index));
  113.             } else {
  114.                 child1Rep.add(parent1Rep.get(index));
  115.                 child2Rep.add(parent2Rep.get(index));
  116.             }
  117.         }

  118.         return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
  119.                                   second.newFixedLengthChromosome(child2Rep));
  120.     }
  121. }