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 agents.anac.y2019.harddealer.math3.genetics;
|
---|
18 |
|
---|
19 | import java.util.ArrayList;
|
---|
20 | import java.util.List;
|
---|
21 |
|
---|
22 | import agents.anac.y2019.harddealer.math3.exception.DimensionMismatchException;
|
---|
23 | import agents.anac.y2019.harddealer.math3.exception.MathIllegalArgumentException;
|
---|
24 | import agents.anac.y2019.harddealer.math3.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 | @SuppressWarnings("unchecked") // OK because of instanceof checks
|
---|
78 | public ChromosomePair crossover(final Chromosome first, final Chromosome second)
|
---|
79 | throws DimensionMismatchException, MathIllegalArgumentException {
|
---|
80 |
|
---|
81 | if (! (first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
|
---|
82 | throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
|
---|
83 | }
|
---|
84 | return crossover((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
|
---|
85 | }
|
---|
86 |
|
---|
87 |
|
---|
88 | /**
|
---|
89 | * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
|
---|
90 | *
|
---|
91 | * @param first the first chromosome.
|
---|
92 | * @param second the second chromosome.
|
---|
93 | * @return the pair of new chromosomes that resulted from the crossover.
|
---|
94 | * @throws DimensionMismatchException if the length of the two chromosomes is different
|
---|
95 | */
|
---|
96 | private ChromosomePair crossover(final AbstractListChromosome<T> first,
|
---|
97 | final AbstractListChromosome<T> second) throws DimensionMismatchException {
|
---|
98 | final int length = first.getLength();
|
---|
99 | if (length != second.getLength()) {
|
---|
100 | throw new DimensionMismatchException(second.getLength(), length);
|
---|
101 | }
|
---|
102 |
|
---|
103 | // array representations of the parents
|
---|
104 | final List<T> parent1Rep = first.getRepresentation();
|
---|
105 | final List<T> parent2Rep = second.getRepresentation();
|
---|
106 | // and of the children
|
---|
107 | final List<T> child1Rep = new ArrayList<T>(length);
|
---|
108 | final List<T> child2Rep = new ArrayList<T>(length);
|
---|
109 |
|
---|
110 | // select a crossover point at random (0 and length makes no sense)
|
---|
111 | final int crossoverIndex = 1 + (GeneticAlgorithm.getRandomGenerator().nextInt(length-2));
|
---|
112 |
|
---|
113 | // copy the first part
|
---|
114 | for (int i = 0; i < crossoverIndex; i++) {
|
---|
115 | child1Rep.add(parent1Rep.get(i));
|
---|
116 | child2Rep.add(parent2Rep.get(i));
|
---|
117 | }
|
---|
118 | // and switch the second part
|
---|
119 | for (int i = crossoverIndex; i < length; i++) {
|
---|
120 | child1Rep.add(parent2Rep.get(i));
|
---|
121 | child2Rep.add(parent1Rep.get(i));
|
---|
122 | }
|
---|
123 |
|
---|
124 | return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
|
---|
125 | second.newFixedLengthChromosome(child2Rep));
|
---|
126 | }
|
---|
127 |
|
---|
128 | }
|
---|