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   * @version $Id: NPointCrossover.java 1385297 2012-09-16 16:05:57Z tn $
52   */
53  public class NPointCrossover<T> implements CrossoverPolicy {
54  
55      /** The number of crossover points. */
56      private final int crossoverPoints;
57  
58      /**
59       * Creates a new {@link NPointCrossover} policy using the given number of points.
60       * <p>
61       * <b>Note</b>: the number of crossover points must be &lt; <code>chromosome length - 1</code>.
62       * This condition can only be checked at runtime, as the chromosome length is not known in advance.
63       *
64       * @param crossoverPoints the number of crossover points
65       * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive
66       */
67      public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException {
68          if (crossoverPoints <= 0) {
69              throw new NotStrictlyPositiveException(crossoverPoints);
70          }
71          this.crossoverPoints = crossoverPoints;
72      }
73  
74      /**
75       * Returns the number of crossover points used by this {@link CrossoverPolicy}.
76       *
77       * @return the number of crossover points
78       */
79      public int getCrossoverPoints() {
80          return crossoverPoints;
81      }
82  
83      /**
84       * Performs a N-point crossover. N random crossover points are selected and are used
85       * to divide the parent chromosomes into segments. The segments are copied in alternate
86       * order from the two parents to the corresponding child chromosomes.
87       *
88       * Example (2-point crossover):
89       * <pre>
90       * -C- denotes a crossover point
91       *           -C-       -C-                         -C-        -C-
92       * p1 = (1 0  | 1 0 0 1 | 0 1 1)    X    p2 = (0 1  | 1 0 1 0  | 1 1 1)
93       *      \----/ \-------/ \-----/              \----/ \--------/ \-----/
94       *        ||      (*)       ||                  ||      (**)       ||
95       *        VV      (**)      VV                  VV      (*)        VV
96       *      /----\ /--------\ /-----\             /----\ /--------\ /-----\
97       * c1 = (1 0  | 1 0 1 0  | 0 1 1)    X   c2 = (0 1  | 1 0 0 1  | 0 1 1)
98       * </pre>
99       *
100      * @param first first parent (p1)
101      * @param second second parent (p2)
102      * @return pair of two children (c1,c2)
103      * @throws MathIllegalArgumentException iff one of the chromosomes is
104      *   not an instance of {@link AbstractListChromosome}
105      * @throws DimensionMismatchException if the length of the two chromosomes is different
106      */
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 ArrayList<T> child1Rep = new ArrayList<T>(first.getLength());
143         final ArrayList<T> child2Rep = new ArrayList<T>(second.getLength());
144 
145         final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
146 
147         ArrayList<T> c1 = child1Rep;
148         ArrayList<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             ArrayList<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 }