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.List;
21
22 import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
23 import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
24 import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
25
26
27 /**
28 * One point crossover policy. A random crossover point is selected and the
29 * first part from each parent is copied to the corresponding child, and the
30 * second parts are copied crosswise.
31 *
32 * Example:
33 * <pre>
34 * -C- denotes a crossover point
35 * -C- -C-
36 * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1)
37 * \------------/ \-----/ \------------/ \-----/
38 * || (*) || (**)
39 * VV (**) VV (*)
40 * /------------\ /-----\ /------------\ /-----\
41 * c1 = (1 0 1 0 0 1 | 1 1 1) X c2 = (0 1 1 0 1 0 | 0 1 1)
42 * </pre>
43 *
44 * This policy works only on {@link AbstractListChromosome}, and therefore it
45 * is parameterized by T. Moreover, the chromosomes must have same lengths.
46 *
47 * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
48 * @since 2.0
49 *
50 */
51 public class OnePointCrossover<T> implements CrossoverPolicy {
52
53 /**
54 * Performs one point crossover. A random crossover point is selected and the
55 * first part from each parent is copied to the corresponding child, and the
56 * second parts are copied crosswise.
57 *
58 * Example:
59 * <pre>
60 * -C- denotes a crossover point
61 * -C- -C-
62 * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1)
63 * \------------/ \-----/ \------------/ \-----/
64 * || (*) || (**)
65 * VV (**) VV (*)
66 * /------------\ /-----\ /------------\ /-----\
67 * c1 = (1 0 1 0 0 1 | 1 1 1) X c2 = (0 1 1 0 1 0 | 0 1 1)
68 * </pre>
69 *
70 * @param first first parent (p1)
71 * @param second second parent (p2)
72 * @return pair of two children (c1,c2)
73 * @throws MathIllegalArgumentException iff one of the chromosomes is
74 * not an instance of {@link AbstractListChromosome}
75 * @throws DimensionMismatchException if the length of the two chromosomes is different
76 */
77 @Override
78 @SuppressWarnings("unchecked") // OK because of instanceof checks
79 public ChromosomePair crossover(final Chromosome first, final Chromosome second)
80 throws DimensionMismatchException, MathIllegalArgumentException {
81
82 if (! (first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
83 throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
84 }
85 return crossover((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
86 }
87
88
89 /**
90 * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
91 *
92 * @param first the first chromosome.
93 * @param second the second chromosome.
94 * @return the pair of new chromosomes that resulted from the crossover.
95 * @throws DimensionMismatchException if the length of the two chromosomes is different
96 */
97 private ChromosomePair crossover(final AbstractListChromosome<T> first,
98 final AbstractListChromosome<T> second) throws DimensionMismatchException {
99 final int length = first.getLength();
100 if (length != second.getLength()) {
101 throw new DimensionMismatchException(second.getLength(), length);
102 }
103
104 // array representations of the parents
105 final List<T> parent1Rep = first.getRepresentation();
106 final List<T> parent2Rep = second.getRepresentation();
107 // and of the children
108 final List<T> child1Rep = new ArrayList<>(length);
109 final List<T> child2Rep = new ArrayList<>(length);
110
111 // select a crossover point at random (0 and length makes no sense)
112 final int crossoverIndex = 1 + (GeneticAlgorithm.getRandomGenerator().nextInt(length-2));
113
114 // copy the first part
115 for (int i = 0; i < crossoverIndex; i++) {
116 child1Rep.add(parent1Rep.get(i));
117 child2Rep.add(parent2Rep.get(i));
118 }
119 // and switch the second part
120 for (int i = crossoverIndex; i < length; i++) {
121 child1Rep.add(parent2Rep.get(i));
122 child2Rep.add(parent1Rep.get(i));
123 }
124
125 return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
126 second.newFixedLengthChromosome(child2Rep));
127 }
128 }