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 */
017package org.apache.commons.math3.genetics;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.math3.exception.DimensionMismatchException;
023import org.apache.commons.math3.exception.MathIllegalArgumentException;
024import org.apache.commons.math3.exception.NotStrictlyPositiveException;
025import org.apache.commons.math3.exception.NumberIsTooLargeException;
026import org.apache.commons.math3.exception.util.LocalizedFormats;
027import 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 */
052public class NPointCrossover<T> implements CrossoverPolicy {
053
054    /** The number of crossover points. */
055    private final int crossoverPoints;
056
057    /**
058     * Creates a new {@link NPointCrossover} policy using the given number of points.
059     * <p>
060     * <b>Note</b>: the number of crossover points must be &lt; <code>chromosome length - 1</code>.
061     * This condition can only be checked at runtime, as the chromosome length is not known in advance.
062     *
063     * @param crossoverPoints the number of crossover points
064     * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive
065     */
066    public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException {
067        if (crossoverPoints <= 0) {
068            throw new NotStrictlyPositiveException(crossoverPoints);
069        }
070        this.crossoverPoints = crossoverPoints;
071    }
072
073    /**
074     * Returns the number of crossover points used by this {@link CrossoverPolicy}.
075     *
076     * @return the number of crossover points
077     */
078    public int getCrossoverPoints() {
079        return crossoverPoints;
080    }
081
082    /**
083     * Performs a N-point crossover. N random crossover points are selected and are used
084     * to divide the parent chromosomes into segments. The segments are copied in alternate
085     * order from the two parents to the corresponding child chromosomes.
086     *
087     * Example (2-point crossover):
088     * <pre>
089     * -C- denotes a crossover point
090     *           -C-       -C-                         -C-        -C-
091     * p1 = (1 0  | 1 0 0 1 | 0 1 1)    X    p2 = (0 1  | 1 0 1 0  | 1 1 1)
092     *      \----/ \-------/ \-----/              \----/ \--------/ \-----/
093     *        ||      (*)       ||                  ||      (**)       ||
094     *        VV      (**)      VV                  VV      (*)        VV
095     *      /----\ /--------\ /-----\             /----\ /--------\ /-----\
096     * c1 = (1 0  | 1 0 1 0  | 0 1 1)    X   c2 = (0 1  | 1 0 0 1  | 0 1 1)
097     * </pre>
098     *
099     * @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}