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 }