    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.Collections;
    021    import java.util.HashSet;
    022    import java.util.List;
    023    import java.util.Set;
    024
    025    import org.apache.commons.math3.exception.DimensionMismatchException;
    026    import org.apache.commons.math3.exception.MathIllegalArgumentException;
    027    import org.apache.commons.math3.exception.util.LocalizedFormats;
    028    import org.apache.commons.math3.random.RandomGenerator;
    029    import org.apache.commons.math3.util.FastMath;
    030
    031    /**
    032     * Order 1 Crossover [OX1] builds offspring from <b>ordered</b> chromosomes by copying a
    033     * consecutive slice from one parent, and filling up the remaining genes from the other
    034     * parent as they appear.
    035     * <p>
    036     * This policy works by applying the following rules:
    037     * <ol>
    038     *   <li>select a random slice of consecutive genes from parent 1</li>
    039     *   <li>copy the slice to child 1 and mark out the genes in parent 2</li>
    040     *   <li>starting from the right side of the slice, copy genes from parent 2 as they
    041     *       appear to child 1 if they are not yet marked out.</li>
    042     * </ol>
    043     * <p>
    044     * Example (random sublist from index 3 to 7, underlined):
    045     * <pre>
    046     * p1 = (8 4 7 3 6 2 5 1 9 0)   X   c1 = (0 4 7 3 6 2 5 1 8 9)
    047     *             ---------                        ---------
    048     * p2 = (0 1 2 3 4 5 6 7 8 9)   X   c2 = (8 1 2 3 4 5 6 7 9 0)
    049     * </pre>
    050     * <p>
    051     * This policy works only on {@link AbstractListChromosome}, and therefore it
    052     * is parameterized by T. Moreover, the chromosomes must have same lengths.
    053     *
    054     * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx">
    055     * Order 1 Crossover Operator</a>
    056     *
    057     * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
    058     * @since 3.1
    059     * @version $Id: OrderedCrossover.java 1385297 2012-09-16 16:05:57Z tn $
    060     */
    061    public class OrderedCrossover<T> implements CrossoverPolicy {
    062
    063        /**
    064         * {@inheritDoc}
    065         *
    066         * @throws MathIllegalArgumentException iff one of the chromosomes is
    067         *   not an instance of {@link AbstractListChromosome}
    068         * @throws DimensionMismatchException if the length of the two chromosomes is different
    069         */
    070        @SuppressWarnings("unchecked")
    071        public ChromosomePair crossover(final Chromosome first, final Chromosome second)
    072            throws DimensionMismatchException, MathIllegalArgumentException {
    073
    074            if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
    075                throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
    076            }
    077            return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
    078        }
    079
    080        /**
    081         * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
    082         *
    083         * @param first the first chromosome
    084         * @param second the second chromosome
    085         * @return the pair of new chromosomes that resulted from the crossover
    086         * @throws DimensionMismatchException if the length of the two chromosomes is different
    087         */
    088        protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second)
    089            throws DimensionMismatchException {
    090
    091            final int length = first.getLength();
    092            if (length != second.getLength()) {
    093                throw new DimensionMismatchException(second.getLength(), length);
    094            }
    095
    096            // array representations of the parents
    097            final List<T> parent1Rep = first.getRepresentation();
    098            final List<T> parent2Rep = second.getRepresentation();
    099            // and of the children
    100            final List<T> child1 = new ArrayList<T>(length);
    101            final List<T> child2 = new ArrayList<T>(length);
    102            // sets of already inserted items for quick access
    103            final Set<T> child1Set = new HashSet<T>(length);
    104            final Set<T> child2Set = new HashSet<T>(length);
    105
    106            final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
    107            // choose random points, making sure that lb < ub.
    108            int a = random.nextInt(length);
    109            int b;
    110            do {
    111                b = random.nextInt(length);
    112            } while (a == b);
    113            // determine the lower and upper bounds
    114            final int lb = FastMath.min(a, b);
    115            final int ub = FastMath.max(a, b);
    116
    117            // add the subLists that are between lb and ub
    118            child1.addAll(parent1Rep.subList(lb, ub + 1));
    119            child1Set.addAll(child1);
    120            child2.addAll(parent2Rep.subList(lb, ub + 1));
    121            child2Set.addAll(child2);
    122
    123            // iterate over every item in the parents
    124            for (int i = 1; i <= length; i++) {
    125                final int idx = (ub + i) % length;
    126
    127                // retrieve the current item in each parent
    128                final T item1 = parent1Rep.get(idx);
    129                final T item2 = parent2Rep.get(idx);
    130
    131                // if the first child already contains the item in the second parent add it
    132                if (!child1Set.contains(item2)) {
    133                    child1.add(item2);
    134                    child1Set.add(item2);
    135                }
    136
    137                // if the second child already contains the item in the first parent add it
    138                if (!child2Set.contains(item1)) {
    139                    child2.add(item1);
    140                    child2Set.add(item1);
    141                }
    142            }
    143
    144            // rotate so that the original slice is in the same place as in the parents.
    145            Collections.rotate(child1, lb);
    146            Collections.rotate(child2, lb);
    147
    148            return new ChromosomePair(first.newFixedLengthChromosome(child1),
    149                                      second.newFixedLengthChromosome(child2));
    150        }
    151    }