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.List;
21  
22  import org.apache.commons.math3.exception.DimensionMismatchException;
23  import org.apache.commons.math3.exception.MathIllegalArgumentException;
24  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
25  import org.apache.commons.math3.exception.NumberIsTooLargeException;
26  import org.apache.commons.math3.exception.util.LocalizedFormats;
27  import org.apache.commons.math3.random.RandomGenerator;
28  
29  /**
30   * N-point crossover policy. For each iteration a random crossover point is
31   * selected and the first part from each parent is copied to the corresponding
32   * child, and the second parts are copied crosswise.
33   *
34   * Example (2-point crossover):
35   * <pre>
36   * -C- denotes a crossover point
37   *           -C-       -C-                         -C-        -C-
38   * p1 = (1 0  | 1 0 0 1 | 0 1 1)    X    p2 = (0 1  | 1 0 1 0  | 1 1 1)
39   *      \----/ \-------/ \-----/              \----/ \--------/ \-----/
40   *        ||      (*)       ||                  ||      (**)       ||
41   *        VV      (**)      VV                  VV      (*)        VV
42   *      /----\ /--------\ /-----\             /----\ /--------\ /-----\
43   * c1 = (1 0  | 1 0 1 0  | 0 1 1)    X   c2 = (0 1  | 1 0 0 1  | 0 1 1)
44   * </pre>
45   *
46   * This policy works only on {@link AbstractListChromosome}, and therefore it
47   * is parameterized by T. Moreover, the chromosomes must have same lengths.
48   *
49   * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
50   * @since 3.1
51   */
52  public class NPointCrossover<T> implements CrossoverPolicy {
53  
54      /** The number of crossover points. */
55      private final int crossoverPoints;
56  
57      /**
58       * Creates a new {@link NPointCrossover} policy using the given number of points.
59       * <p>
60       * <b>Note</b>: the number of crossover points must be &lt; <code>chromosome length - 1</code>.
61       * This condition can only be checked at runtime, as the chromosome length is not known in advance.
62       *
63       * @param crossoverPoints the number of crossover points
64       * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive
65       */
66      public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException {
67          if (crossoverPoints <= 0) {
68              throw new NotStrictlyPositiveException(crossoverPoints);
69          }
70          this.crossoverPoints = crossoverPoints;
71      }
72  
73      /**
74       * Returns the number of crossover points used by this {@link CrossoverPolicy}.
75       *
76       * @return the number of crossover points
77       */
78      public int getCrossoverPoints() {
79          return crossoverPoints;
80      }
81  
82      /**
83       * Performs a N-point crossover. N random crossover points are selected and are used
84       * to divide the parent chromosomes into segments. The segments are copied in alternate
85       * order from the two parents to the corresponding child chromosomes.
86       *
87       * Example (2-point crossover):
88       * <pre>
89       * -C- denotes a crossover point
90       *           -C-       -C-                         -C-        -C-
91       * p1 = (1 0  | 1 0 0 1 | 0 1 1)    X    p2 = (0 1  | 1 0 1 0  | 1 1 1)
92       *      \----/ \-------/ \-----/              \----/ \--------/ \-----/
93       *        ||      (*)       ||                  ||      (**)       ||
94       *        VV      (**)      VV                  VV      (*)        VV
95       *      /----\ /--------\ /-----\             /----\ /--------\ /-----\
96       * c1 = (1 0  | 1 0 1 0  | 0 1 1)    X   c2 = (0 1  | 1 0 0 1  | 0 1 1)
97       * </pre>
98       *
99       * @param first first parent (p1)
100      * @param second second parent (p2)
101      * @return pair of two children (c1,c2)
102      * @throws MathIllegalArgumentException iff one of the chromosomes is
103      *   not an instance of {@link AbstractListChromosome}
104      * @throws DimensionMismatchException if the length of the two chromosomes is different
105      */
106     @SuppressWarnings("unchecked") // OK because of instanceof checks
107     public ChromosomePair crossover(final Chromosome first, final Chromosome second)
108         throws DimensionMismatchException, MathIllegalArgumentException {
109 
110         if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
111             throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
112         }
113         return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
114     }
115 
116     /**
117      * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
118      *
119      * @param first the first chromosome
120      * @param second the second chromosome
121      * @return the pair of new chromosomes that resulted from the crossover
122      * @throws DimensionMismatchException if the length of the two chromosomes is different
123      * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for the actual chromosomes
124      */
125     private ChromosomePair mate(final AbstractListChromosome<T> first,
126                                 final AbstractListChromosome<T> second)
127         throws DimensionMismatchException, NumberIsTooLargeException {
128 
129         final int length = first.getLength();
130         if (length != second.getLength()) {
131             throw new DimensionMismatchException(second.getLength(), length);
132         }
133         if (crossoverPoints >= length) {
134             throw new NumberIsTooLargeException(crossoverPoints, length, false);
135         }
136 
137         // array representations of the parents
138         final List<T> parent1Rep = first.getRepresentation();
139         final List<T> parent2Rep = second.getRepresentation();
140         // and of the children
141         final List<T> child1Rep = new ArrayList<T>(length);
142         final List<T> child2Rep = new ArrayList<T>(length);
143 
144         final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
145 
146         List<T> c1 = child1Rep;
147         List<T> c2 = child2Rep;
148 
149         int remainingPoints = crossoverPoints;
150         int lastIndex = 0;
151         for (int i = 0; i < crossoverPoints; i++, remainingPoints--) {
152             // select the next crossover point at random
153             final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex - remainingPoints);
154 
155             // copy the current segment
156             for (int j = lastIndex; j < crossoverIndex; j++) {
157                 c1.add(parent1Rep.get(j));
158                 c2.add(parent2Rep.get(j));
159             }
160 
161             // swap the children for the next segment
162             List<T> tmp = c1;
163             c1 = c2;
164             c2 = tmp;
165 
166             lastIndex = crossoverIndex;
167         }
168 
169         // copy the last segment
170         for (int j = lastIndex; j < length; j++) {
171             c1.add(parent1Rep.get(j));
172             c2.add(parent2Rep.get(j));
173         }
174 
175         return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
176                                   second.newFixedLengthChromosome(child2Rep));
177     }
178 }