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 &lt; <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    }