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.math4.legacy.genetics;
18  
19  import java.util.ArrayList;
20  import java.util.List;
21  
22  import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
23  import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
24  import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException;
25  import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException;
26  import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
27  import org.apache.commons.rng.UniformRandomProvider;
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     @Override
107     @SuppressWarnings("unchecked") // OK because of instanceof checks
108     public ChromosomePair crossover(final Chromosome first, final Chromosome second)
109         throws DimensionMismatchException, MathIllegalArgumentException {
110 
111         if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
112             throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
113         }
114         return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
115     }
116 
117     /**
118      * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
119      *
120      * @param first the first chromosome
121      * @param second the second chromosome
122      * @return the pair of new chromosomes that resulted from the crossover
123      * @throws DimensionMismatchException if the length of the two chromosomes is different
124      * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for the actual chromosomes
125      */
126     private ChromosomePair mate(final AbstractListChromosome<T> first,
127                                 final AbstractListChromosome<T> second)
128         throws DimensionMismatchException, NumberIsTooLargeException {
129 
130         final int length = first.getLength();
131         if (length != second.getLength()) {
132             throw new DimensionMismatchException(second.getLength(), length);
133         }
134         if (crossoverPoints >= length) {
135             throw new NumberIsTooLargeException(crossoverPoints, length, false);
136         }
137 
138         // array representations of the parents
139         final List<T> parent1Rep = first.getRepresentation();
140         final List<T> parent2Rep = second.getRepresentation();
141         // and of the children
142         final List<T> child1Rep = new ArrayList<>(length);
143         final List<T> child2Rep = new ArrayList<>(length);
144 
145         final UniformRandomProvider random = GeneticAlgorithm.getRandomGenerator();
146 
147         List<T> c1 = child1Rep;
148         List<T> c2 = child2Rep;
149 
150         int remainingPoints = crossoverPoints;
151         int lastIndex = 0;
152         for (int i = 0; i < crossoverPoints; i++, remainingPoints--) {
153             // select the next crossover point at random
154             final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex - remainingPoints);
155 
156             // copy the current segment
157             for (int j = lastIndex; j < crossoverIndex; j++) {
158                 c1.add(parent1Rep.get(j));
159                 c2.add(parent2Rep.get(j));
160             }
161 
162             // swap the children for the next segment
163             List<T> tmp = c1;
164             c1 = c2;
165             c2 = tmp;
166 
167             lastIndex = crossoverIndex;
168         }
169 
170         // copy the last segment
171         for (int j = lastIndex; j < length; j++) {
172             c1.add(parent1Rep.get(j));
173             c2.add(parent2Rep.get(j));
174         }
175 
176         return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
177                                   second.newFixedLengthChromosome(child2Rep));
178     }
179 }