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.legacy.genetics;
018
019import java.util.ArrayList;
020import java.util.Collections;
021import java.util.HashSet;
022import java.util.List;
023import java.util.Set;
024
025import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
026import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
027import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
028import org.apache.commons.rng.UniformRandomProvider;
029import org.apache.commons.math4.core.jdkmath.JdkMath;
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 */
060public class OrderedCrossover<T> implements CrossoverPolicy {
061
062    /**
063     * {@inheritDoc}
064     *
065     * @throws MathIllegalArgumentException iff one of the chromosomes is
066     *   not an instance of {@link AbstractListChromosome}
067     * @throws DimensionMismatchException if the length of the two chromosomes is different
068     */
069    @Override
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<>(length);
101        final List<T> child2 = new ArrayList<>(length);
102        // sets of already inserted items for quick access
103        final Set<T> child1Set = new HashSet<>(length);
104        final Set<T> child2Set = new HashSet<>(length);
105
106        final UniformRandomProvider 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 = JdkMath.min(a, b);
115        final int ub = JdkMath.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}