View Javadoc

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.math3.genetics;
18  
19  import java.util.ArrayList;
20  import java.util.Collections;
21  import java.util.HashSet;
22  import java.util.List;
23  import java.util.Set;
24  
25  import org.apache.commons.math3.exception.DimensionMismatchException;
26  import org.apache.commons.math3.exception.MathIllegalArgumentException;
27  import org.apache.commons.math3.exception.util.LocalizedFormats;
28  import org.apache.commons.math3.random.RandomGenerator;
29  import org.apache.commons.math3.util.FastMath;
30  
31  /**
32   * Order 1 Crossover [OX1] builds offspring from <b>ordered</b> chromosomes by copying a
33   * consecutive slice from one parent, and filling up the remaining genes from the other
34   * parent as they appear.
35   * <p>
36   * This policy works by applying the following rules:
37   * <ol>
38   *   <li>select a random slice of consecutive genes from parent 1</li>
39   *   <li>copy the slice to child 1 and mark out the genes in parent 2</li>
40   *   <li>starting from the right side of the slice, copy genes from parent 2 as they
41   *       appear to child 1 if they are not yet marked out.</li>
42   * </ol>
43   * <p>
44   * Example (random sublist from index 3 to 7, underlined):
45   * <pre>
46   * p1 = (8 4 7 3 6 2 5 1 9 0)   X   c1 = (0 4 7 3 6 2 5 1 8 9)
47   *             ---------                        ---------
48   * p2 = (0 1 2 3 4 5 6 7 8 9)   X   c2 = (8 1 2 3 4 5 6 7 9 0)
49   * </pre>
50   * <p>
51   * This policy works only on {@link AbstractListChromosome}, and therefore it
52   * is parameterized by T. Moreover, the chromosomes must have same lengths.
53   *
54   * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx">
55   * Order 1 Crossover Operator</a>
56   *
57   * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
58   * @since 3.1
59   * @version $Id: OrderedCrossover.java 1385297 2012-09-16 16:05:57Z tn $
60   */
61  public class OrderedCrossover<T> implements CrossoverPolicy {
62  
63      /**
64       * {@inheritDoc}
65       *
66       * @throws MathIllegalArgumentException iff one of the chromosomes is
67       *   not an instance of {@link AbstractListChromosome}
68       * @throws DimensionMismatchException if the length of the two chromosomes is different
69       */
70      @SuppressWarnings("unchecked")
71      public ChromosomePair crossover(final Chromosome first, final Chromosome second)
72          throws DimensionMismatchException, MathIllegalArgumentException {
73  
74          if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
75              throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
76          }
77          return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
78      }
79  
80      /**
81       * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
82       *
83       * @param first the first chromosome
84       * @param second the second chromosome
85       * @return the pair of new chromosomes that resulted from the crossover
86       * @throws DimensionMismatchException if the length of the two chromosomes is different
87       */
88      protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second)
89          throws DimensionMismatchException {
90  
91          final int length = first.getLength();
92          if (length != second.getLength()) {
93              throw new DimensionMismatchException(second.getLength(), length);
94          }
95  
96          // array representations of the parents
97          final List<T> parent1Rep = first.getRepresentation();
98          final List<T> parent2Rep = second.getRepresentation();
99          // and of the children
100         final List<T> child1 = new ArrayList<T>(length);
101         final List<T> child2 = new ArrayList<T>(length);
102         // sets of already inserted items for quick access
103         final Set<T> child1Set = new HashSet<T>(length);
104         final Set<T> child2Set = new HashSet<T>(length);
105 
106         final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
107         // choose random points, making sure that lb < ub.
108         int a = random.nextInt(length);
109         int b;
110         do {
111             b = random.nextInt(length);
112         } while (a == b);
113         // determine the lower and upper bounds
114         final int lb = FastMath.min(a, b);
115         final int ub = FastMath.max(a, b);
116 
117         // add the subLists that are between lb and ub
118         child1.addAll(parent1Rep.subList(lb, ub + 1));
119         child1Set.addAll(child1);
120         child2.addAll(parent2Rep.subList(lb, ub + 1));
121         child2Set.addAll(child2);
122 
123         // iterate over every item in the parents
124         for (int i = 1; i <= length; i++) {
125             final int idx = (ub + i) % length;
126 
127             // retrieve the current item in each parent
128             final T item1 = parent1Rep.get(idx);
129             final T item2 = parent2Rep.get(idx);
130 
131             // if the first child already contains the item in the second parent add it
132             if (!child1Set.contains(item2)) {
133                 child1.add(item2);
134                 child1Set.add(item2);
135             }
136 
137             // if the second child already contains the item in the first parent add it
138             if (!child2Set.contains(item1)) {
139                 child2.add(item1);
140                 child2Set.add(item1);
141             }
142         }
143 
144         // rotate so that the original slice is in the same place as in the parents.
145         Collections.rotate(child1, lb);
146         Collections.rotate(child2, lb);
147 
148         return new ChromosomePair(first.newFixedLengthChromosome(child1),
149                                   second.newFixedLengthChromosome(child2));
150     }
151 }