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.math4.genetics;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.math4.exception.DimensionMismatchException;
023import org.apache.commons.math4.exception.MathIllegalArgumentException;
024import org.apache.commons.math4.exception.NotStrictlyPositiveException;
025import org.apache.commons.math4.exception.NumberIsTooLargeException;
026import org.apache.commons.math4.exception.util.LocalizedFormats;
027import org.apache.commons.rng.UniformRandomProvider;
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    @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}