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.math4.legacy.genetics;
18
19 import java.util.ArrayList;
20 import java.util.Collections;
21 import java.util.HashSet;
22 import java.util.List;
23 import java.util.Set;
24
25 import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
26 import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
27 import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
28 import org.apache.commons.rng.UniformRandomProvider;
29 import org.apache.commons.math4.core.jdkmath.JdkMath;
30
31 /**
32 * Order 1 Crossover [OX1] builds offspring from <b>ordered</b> chromosomes by copying a
33 * consecutive slice from one parent, and filling up the remaining genes from the other
34 * parent as they appear.
35 * <p>
36 * This policy works by applying the following rules:
37 * <ol>
38 * <li>select a random slice of consecutive genes from parent 1</li>
39 * <li>copy the slice to child 1 and mark out the genes in parent 2</li>
40 * <li>starting from the right side of the slice, copy genes from parent 2 as they
41 * appear to child 1 if they are not yet marked out.</li>
42 * </ol>
43 * <p>
44 * Example (random sublist from index 3 to 7, underlined):
45 * <pre>
46 * p1 = (8 4 7 3 6 2 5 1 9 0) X c1 = (0 4 7 3 6 2 5 1 8 9)
47 * --------- ---------
48 * p2 = (0 1 2 3 4 5 6 7 8 9) X c2 = (8 1 2 3 4 5 6 7 9 0)
49 * </pre>
50 * <p>
51 * This policy works only on {@link AbstractListChromosome}, and therefore it
52 * is parameterized by T. Moreover, the chromosomes must have same lengths.
53 *
54 * @see <a href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx">
55 * Order 1 Crossover Operator</a>
56 *
57 * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
58 * @since 3.1
59 */
60 public class OrderedCrossover<T> implements CrossoverPolicy {
61
62 /**
63 * {@inheritDoc}
64 *
65 * @throws MathIllegalArgumentException iff one of the chromosomes is
66 * not an instance of {@link AbstractListChromosome}
67 * @throws DimensionMismatchException if the length of the two chromosomes is different
68 */
69 @Override
70 @SuppressWarnings("unchecked")
71 public ChromosomePair crossover(final Chromosome first, final Chromosome second)
72 throws DimensionMismatchException, MathIllegalArgumentException {
73
74 if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
75 throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
76 }
77 return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
78 }
79
80 /**
81 * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
82 *
83 * @param first the first chromosome
84 * @param second the second chromosome
85 * @return the pair of new chromosomes that resulted from the crossover
86 * @throws DimensionMismatchException if the length of the two chromosomes is different
87 */
88 protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second)
89 throws DimensionMismatchException {
90
91 final int length = first.getLength();
92 if (length != second.getLength()) {
93 throw new DimensionMismatchException(second.getLength(), length);
94 }
95
96 // array representations of the parents
97 final List<T> parent1Rep = first.getRepresentation();
98 final List<T> parent2Rep = second.getRepresentation();
99 // 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 }