View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math3.genetics;
18  
19  import java.util.ArrayList;
20  import java.util.HashSet;
21  import java.util.List;
22  import java.util.Set;
23  
24  import org.apache.commons.math3.exception.DimensionMismatchException;
25  import org.apache.commons.math3.exception.MathIllegalArgumentException;
26  import org.apache.commons.math3.exception.util.LocalizedFormats;
27  
28  /**
29   * Cycle Crossover [CX] builds offspring from <b>ordered</b> chromosomes by identifying cycles
30   * between two parent chromosomes. To form the children, the cycles are copied from the
31   * respective parents.
32   * <p>
33   * To form a cycle the following procedure is applied:
34   * <ol>
35   *   <li>start with the first gene of parent 1</li>
36   *   <li>look at the gene at the same position of parent 2</li>
37   *   <li>go to the position with the same gene in parent 1</li>
38   *   <li>add this gene index to the cycle</li>
39   *   <li>repeat the steps 2-5 until we arrive at the starting gene of this cycle</li>
40   * </ol>
41   * The indices that form a cycle are then used to form the children in alternating order, i.e.
42   * in cycle 1, the genes of parent 1 are copied to child 1, while in cycle 2 the genes of parent 1
43   * are copied to child 2, and so forth ...
44   * </p>
45   *
46   * Example (zero-start cycle):
47   * <pre>
48   * p1 = (8 4 7 3 6 2 5 1 9 0)    X   c1 = (8 1 2 3 4 5 6 7 9 0)
49   * p2 = (0 1 2 3 4 5 6 7 8 9)    X   c2 = (0 4 7 3 6 2 5 1 8 9)
50   *
51   * cycle 1: 8 0 9
52   * cycle 2: 4 1 7 2 5 6
53   * cycle 3: 3
54   * </pre>
55   *
56   * This policy works only on {@link AbstractListChromosome}, and therefore it
57   * is parameterized by T. Moreover, the chromosomes must have same lengths.
58   *
59   * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/CycleCrossoverOperator.aspx">
60   * Cycle Crossover Operator</a>
61   *
62   * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
63   * @since 3.1
64   * @version $Id: CycleCrossover.java 1385297 2012-09-16 16:05:57Z tn $
65   */
66  public class CycleCrossover<T> implements CrossoverPolicy {
67  
68      /** If the start index shall be chosen randomly. */
69      private final boolean randomStart;
70  
71      /**
72       * Creates a new {@link CycleCrossover} policy.
73       */
74      public CycleCrossover() {
75          this(false);
76      }
77  
78      /**
79       * Creates a new {@link CycleCrossover} policy using the given {@code randomStart} behavior.
80       *
81       * @param randomStart whether the start index shall be chosen randomly or be set to 0
82       */
83      public CycleCrossover(final boolean randomStart) {
84          this.randomStart = randomStart;
85      }
86  
87      /**
88       * Returns whether the starting index is chosen randomly or set to zero.
89       *
90       * @return {@code true} if the starting index is chosen randomly, {@code false} otherwise
91       */
92      public boolean isRandomStart() {
93          return randomStart;
94      }
95  
96      /**
97       * {@inheritDoc}
98       *
99       * @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 }