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.HashSet;
021    import java.util.List;
022    import java.util.Set;
023    
024    import org.apache.commons.math3.exception.DimensionMismatchException;
025    import org.apache.commons.math3.exception.MathIllegalArgumentException;
026    import org.apache.commons.math3.exception.util.LocalizedFormats;
027    
028    /**
029     * Cycle Crossover [CX] builds offspring from <b>ordered</b> chromosomes by identifying cycles
030     * between two parent chromosomes. To form the children, the cycles are copied from the
031     * respective parents.
032     * <p>
033     * To form a cycle the following procedure is applied:
034     * <ol>
035     *   <li>start with the first gene of parent 1</li>
036     *   <li>look at the gene at the same position of parent 2</li>
037     *   <li>go to the position with the same gene in parent 1</li>
038     *   <li>add this gene index to the cycle</li>
039     *   <li>repeat the steps 2-5 until we arrive at the starting gene of this cycle</li>
040     * </ol>
041     * The indices that form a cycle are then used to form the children in alternating order, i.e.
042     * in cycle 1, the genes of parent 1 are copied to child 1, while in cycle 2 the genes of parent 1
043     * are copied to child 2, and so forth ...
044     * </p>
045     *
046     * Example (zero-start cycle):
047     * <pre>
048     * p1 = (8 4 7 3 6 2 5 1 9 0)    X   c1 = (8 1 2 3 4 5 6 7 9 0)
049     * p2 = (0 1 2 3 4 5 6 7 8 9)    X   c2 = (0 4 7 3 6 2 5 1 8 9)
050     *
051     * cycle 1: 8 0 9
052     * cycle 2: 4 1 7 2 5 6
053     * cycle 3: 3
054     * </pre>
055     *
056     * This policy works only on {@link AbstractListChromosome}, and therefore it
057     * is parameterized by T. Moreover, the chromosomes must have same lengths.
058     *
059     * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/CycleCrossoverOperator.aspx">
060     * Cycle Crossover Operator</a>
061     *
062     * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
063     * @since 3.1
064     * @version $Id: CycleCrossover.java 1385297 2012-09-16 16:05:57Z tn $
065     */
066    public class CycleCrossover<T> implements CrossoverPolicy {
067    
068        /** If the start index shall be chosen randomly. */
069        private final boolean randomStart;
070    
071        /**
072         * Creates a new {@link CycleCrossover} policy.
073         */
074        public CycleCrossover() {
075            this(false);
076        }
077    
078        /**
079         * Creates a new {@link CycleCrossover} policy using the given {@code randomStart} behavior.
080         *
081         * @param randomStart whether the start index shall be chosen randomly or be set to 0
082         */
083        public CycleCrossover(final boolean randomStart) {
084            this.randomStart = randomStart;
085        }
086    
087        /**
088         * Returns whether the starting index is chosen randomly or set to zero.
089         *
090         * @return {@code true} if the starting index is chosen randomly, {@code false} otherwise
091         */
092        public boolean isRandomStart() {
093            return randomStart;
094        }
095    
096        /**
097         * {@inheritDoc}
098         *
099         * @throws MathIllegalArgumentException if the chromosomes are not an instance of {@link AbstractListChromosome}
100         * @throws DimensionMismatchException if the length of the two chromosomes is different
101         */
102        @SuppressWarnings("unchecked")
103        public ChromosomePair crossover(final Chromosome first, final Chromosome second)
104            throws DimensionMismatchException, MathIllegalArgumentException {
105    
106            if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
107                throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
108            }
109            return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
110        }
111    
112        /**
113         * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
114         *
115         * @param first the first chromosome
116         * @param second the second chromosome
117         * @return the pair of new chromosomes that resulted from the crossover
118         * @throws DimensionMismatchException if the length of the two chromosomes is different
119         */
120        protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second)
121            throws DimensionMismatchException {
122    
123            final int length = first.getLength();
124            if (length != second.getLength()) {
125                throw new DimensionMismatchException(second.getLength(), length);
126            }
127    
128            // array representations of the parents
129            final List<T> parent1Rep = first.getRepresentation();
130            final List<T> parent2Rep = second.getRepresentation();
131            // and of the children: do a crossover copy to simplify the later processing
132            final List<T> child1Rep = new ArrayList<T>(second.getRepresentation());
133            final List<T> child2Rep = new ArrayList<T>(first.getRepresentation());
134    
135            // the set of all visited indices so far
136            final Set<Integer> visitedIndices = new HashSet<Integer>(length);
137            // the indices of the current cycle
138            final List<Integer> indices = new ArrayList<Integer>(length);
139    
140            // determine the starting index
141            int idx = randomStart ? GeneticAlgorithm.getRandomGenerator().nextInt(length) : 0;
142            int cycle = 1;
143    
144            while (visitedIndices.size() < length) {
145                indices.add(idx);
146    
147                T item = parent2Rep.get(idx);
148                idx = parent1Rep.indexOf(item);
149    
150                while (idx != indices.get(0)) {
151                    // add that index to the cycle indices
152                    indices.add(idx);
153                    // get the item in the second parent at that index
154                    item = parent2Rep.get(idx);
155                    // get the index of that item in the first parent
156                    idx = parent1Rep.indexOf(item);
157                }
158    
159                // for even cycles: swap the child elements on the indices found in this cycle
160                if (cycle++ % 2 != 0) {
161                    for (int i : indices) {
162                        T tmp = child1Rep.get(i);
163                        child1Rep.set(i, child2Rep.get(i));
164                        child2Rep.set(i, tmp);
165                    }
166                }
167    
168                visitedIndices.addAll(indices);
169                // find next starting index: last one + 1 until we find an unvisited index
170                idx = (indices.get(0) + 1) % length;
171                while (visitedIndices.contains(idx) && visitedIndices.size() < length) {
172                    idx++;
173                    if (idx >= length) {
174                        idx = 0;
175                    }
176                }
177                indices.clear();
178            }
179    
180            return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
181                                      second.newFixedLengthChromosome(child2Rep));
182        }
183    }