001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.genetics;
018
019 import java.util.ArrayList;
020 import java.util.List;
021
022 import org.apache.commons.math3.exception.DimensionMismatchException;
023 import org.apache.commons.math3.exception.MathIllegalArgumentException;
024 import org.apache.commons.math3.exception.NotStrictlyPositiveException;
025 import org.apache.commons.math3.exception.NumberIsTooLargeException;
026 import org.apache.commons.math3.exception.util.LocalizedFormats;
027 import org.apache.commons.math3.random.RandomGenerator;
028
029 /**
030 * N-point crossover policy. For each iteration a random crossover point is
031 * selected and the first part from each parent is copied to the corresponding
032 * child, and the second parts are copied crosswise.
033 *
034 * Example (2-point crossover):
035 * <pre>
036 * -C- denotes a crossover point
037 * -C- -C- -C- -C-
038 * p1 = (1 0 | 1 0 0 1 | 0 1 1) X p2 = (0 1 | 1 0 1 0 | 1 1 1)
039 * \----/ \-------/ \-----/ \----/ \--------/ \-----/
040 * || (*) || || (**) ||
041 * VV (**) VV VV (*) VV
042 * /----\ /--------\ /-----\ /----\ /--------\ /-----\
043 * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1)
044 * </pre>
045 *
046 * This policy works only on {@link AbstractListChromosome}, and therefore it
047 * is parameterized by T. Moreover, the chromosomes must have same lengths.
048 *
049 * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
050 * @since 3.1
051 * @version $Id: NPointCrossover.java 1385297 2012-09-16 16:05:57Z tn $
052 */
053 public class NPointCrossover<T> implements CrossoverPolicy {
054
055 /** The number of crossover points. */
056 private final int crossoverPoints;
057
058 /**
059 * Creates a new {@link NPointCrossover} policy using the given number of points.
060 * <p>
061 * <b>Note</b>: the number of crossover points must be < <code>chromosome length - 1</code>.
062 * This condition can only be checked at runtime, as the chromosome length is not known in advance.
063 *
064 * @param crossoverPoints the number of crossover points
065 * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive
066 */
067 public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException {
068 if (crossoverPoints <= 0) {
069 throw new NotStrictlyPositiveException(crossoverPoints);
070 }
071 this.crossoverPoints = crossoverPoints;
072 }
073
074 /**
075 * Returns the number of crossover points used by this {@link CrossoverPolicy}.
076 *
077 * @return the number of crossover points
078 */
079 public int getCrossoverPoints() {
080 return crossoverPoints;
081 }
082
083 /**
084 * Performs a N-point crossover. N random crossover points are selected and are used
085 * to divide the parent chromosomes into segments. The segments are copied in alternate
086 * order from the two parents to the corresponding child chromosomes.
087 *
088 * Example (2-point crossover):
089 * <pre>
090 * -C- denotes a crossover point
091 * -C- -C- -C- -C-
092 * p1 = (1 0 | 1 0 0 1 | 0 1 1) X p2 = (0 1 | 1 0 1 0 | 1 1 1)
093 * \----/ \-------/ \-----/ \----/ \--------/ \-----/
094 * || (*) || || (**) ||
095 * VV (**) VV VV (*) VV
096 * /----\ /--------\ /-----\ /----\ /--------\ /-----\
097 * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1)
098 * </pre>
099 *
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 }