OrderedCrossover.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.Collections;
  20. import java.util.HashSet;
  21. import java.util.List;
  22. import java.util.Set;

  23. import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
  24. import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
  25. import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
  26. import org.apache.commons.rng.UniformRandomProvider;
  27. import org.apache.commons.math4.core.jdkmath.JdkMath;

  28. /**
  29.  * Order 1 Crossover [OX1] builds offspring from <b>ordered</b> chromosomes by copying a
  30.  * consecutive slice from one parent, and filling up the remaining genes from the other
  31.  * parent as they appear.
  32.  * <p>
  33.  * This policy works by applying the following rules:
  34.  * <ol>
  35.  *   <li>select a random slice of consecutive genes from parent 1</li>
  36.  *   <li>copy the slice to child 1 and mark out the genes in parent 2</li>
  37.  *   <li>starting from the right side of the slice, copy genes from parent 2 as they
  38.  *       appear to child 1 if they are not yet marked out.</li>
  39.  * </ol>
  40.  * <p>
  41.  * Example (random sublist from index 3 to 7, underlined):
  42.  * <pre>
  43.  * p1 = (8 4 7 3 6 2 5 1 9 0)   X   c1 = (0 4 7 3 6 2 5 1 8 9)
  44.  *             ---------                        ---------
  45.  * p2 = (0 1 2 3 4 5 6 7 8 9)   X   c2 = (8 1 2 3 4 5 6 7 9 0)
  46.  * </pre>
  47.  * <p>
  48.  * This policy works only on {@link AbstractListChromosome}, and therefore it
  49.  * is parameterized by T. Moreover, the chromosomes must have same lengths.
  50.  *
  51.  * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx">
  52.  * Order 1 Crossover Operator</a>
  53.  *
  54.  * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
  55.  * @since 3.1
  56.  */
  57. public class OrderedCrossover<T> implements CrossoverPolicy {

  58.     /**
  59.      * {@inheritDoc}
  60.      *
  61.      * @throws MathIllegalArgumentException iff one of the chromosomes is
  62.      *   not an instance of {@link AbstractListChromosome}
  63.      * @throws DimensionMismatchException if the length of the two chromosomes is different
  64.      */
  65.     @Override
  66.     @SuppressWarnings("unchecked")
  67.     public ChromosomePair crossover(final Chromosome first, final Chromosome second)
  68.         throws DimensionMismatchException, MathIllegalArgumentException {

  69.         if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
  70.             throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
  71.         }
  72.         return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
  73.     }

  74.     /**
  75.      * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
  76.      *
  77.      * @param first the first chromosome
  78.      * @param second the second chromosome
  79.      * @return the pair of new chromosomes that resulted from the crossover
  80.      * @throws DimensionMismatchException if the length of the two chromosomes is different
  81.      */
  82.     protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second)
  83.         throws DimensionMismatchException {

  84.         final int length = first.getLength();
  85.         if (length != second.getLength()) {
  86.             throw new DimensionMismatchException(second.getLength(), length);
  87.         }

  88.         // array representations of the parents
  89.         final List<T> parent1Rep = first.getRepresentation();
  90.         final List<T> parent2Rep = second.getRepresentation();
  91.         // and of the children
  92.         final List<T> child1 = new ArrayList<>(length);
  93.         final List<T> child2 = new ArrayList<>(length);
  94.         // sets of already inserted items for quick access
  95.         final Set<T> child1Set = new HashSet<>(length);
  96.         final Set<T> child2Set = new HashSet<>(length);

  97.         final UniformRandomProvider random = GeneticAlgorithm.getRandomGenerator();
  98.         // choose random points, making sure that lb < ub.
  99.         int a = random.nextInt(length);
  100.         int b;
  101.         do {
  102.             b = random.nextInt(length);
  103.         } while (a == b);
  104.         // determine the lower and upper bounds
  105.         final int lb = JdkMath.min(a, b);
  106.         final int ub = JdkMath.max(a, b);

  107.         // add the subLists that are between lb and ub
  108.         child1.addAll(parent1Rep.subList(lb, ub + 1));
  109.         child1Set.addAll(child1);
  110.         child2.addAll(parent2Rep.subList(lb, ub + 1));
  111.         child2Set.addAll(child2);

  112.         // iterate over every item in the parents
  113.         for (int i = 1; i <= length; i++) {
  114.             final int idx = (ub + i) % length;

  115.             // retrieve the current item in each parent
  116.             final T item1 = parent1Rep.get(idx);
  117.             final T item2 = parent2Rep.get(idx);

  118.             // if the first child already contains the item in the second parent add it
  119.             if (!child1Set.contains(item2)) {
  120.                 child1.add(item2);
  121.                 child1Set.add(item2);
  122.             }

  123.             // if the second child already contains the item in the first parent add it
  124.             if (!child2Set.contains(item1)) {
  125.                 child2.add(item1);
  126.                 child2Set.add(item1);
  127.             }
  128.         }

  129.         // rotate so that the original slice is in the same place as in the parents.
  130.         Collections.rotate(child1, lb);
  131.         Collections.rotate(child2, lb);

  132.         return new ChromosomePair(first.newFixedLengthChromosome(child1),
  133.                                   second.newFixedLengthChromosome(child2));
  134.     }
  135. }