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.Collections;
|
---|
21 | import java.util.HashSet;
|
---|
22 | import java.util.List;
|
---|
23 | import java.util.Set;
|
---|
24 |
|
---|
25 | import agents.anac.y2019.harddealer.math3.exception.DimensionMismatchException;
|
---|
26 | import agents.anac.y2019.harddealer.math3.exception.MathIllegalArgumentException;
|
---|
27 | import agents.anac.y2019.harddealer.math3.exception.util.LocalizedFormats;
|
---|
28 | import agents.anac.y2019.harddealer.math3.random.RandomGenerator;
|
---|
29 | import agents.anac.y2019.harddealer.math3.util.FastMath;
|
---|
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 | @SuppressWarnings("unchecked")
|
---|
70 | public ChromosomePair crossover(final Chromosome first, final Chromosome second)
|
---|
71 | throws DimensionMismatchException, MathIllegalArgumentException {
|
---|
72 |
|
---|
73 | if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
|
---|
74 | throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
|
---|
75 | }
|
---|
76 | return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
|
---|
77 | }
|
---|
78 |
|
---|
79 | /**
|
---|
80 | * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
|
---|
81 | *
|
---|
82 | * @param first the first chromosome
|
---|
83 | * @param second the second chromosome
|
---|
84 | * @return the pair of new chromosomes that resulted from the crossover
|
---|
85 | * @throws DimensionMismatchException if the length of the two chromosomes is different
|
---|
86 | */
|
---|
87 | protected ChromosomePair mate(final AbstractListChromosome<T> first, final AbstractListChromosome<T> second)
|
---|
88 | throws DimensionMismatchException {
|
---|
89 |
|
---|
90 | final int length = first.getLength();
|
---|
91 | if (length != second.getLength()) {
|
---|
92 | throw new DimensionMismatchException(second.getLength(), length);
|
---|
93 | }
|
---|
94 |
|
---|
95 | // array representations of the parents
|
---|
96 | final List<T> parent1Rep = first.getRepresentation();
|
---|
97 | final List<T> parent2Rep = second.getRepresentation();
|
---|
98 | // and of the children
|
---|
99 | final List<T> child1 = new ArrayList<T>(length);
|
---|
100 | final List<T> child2 = new ArrayList<T>(length);
|
---|
101 | // sets of already inserted items for quick access
|
---|
102 | final Set<T> child1Set = new HashSet<T>(length);
|
---|
103 | final Set<T> child2Set = new HashSet<T>(length);
|
---|
104 |
|
---|
105 | final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
|
---|
106 | // choose random points, making sure that lb < ub.
|
---|
107 | int a = random.nextInt(length);
|
---|
108 | int b;
|
---|
109 | do {
|
---|
110 | b = random.nextInt(length);
|
---|
111 | } while (a == b);
|
---|
112 | // determine the lower and upper bounds
|
---|
113 | final int lb = FastMath.min(a, b);
|
---|
114 | final int ub = FastMath.max(a, b);
|
---|
115 |
|
---|
116 | // add the subLists that are between lb and ub
|
---|
117 | child1.addAll(parent1Rep.subList(lb, ub + 1));
|
---|
118 | child1Set.addAll(child1);
|
---|
119 | child2.addAll(parent2Rep.subList(lb, ub + 1));
|
---|
120 | child2Set.addAll(child2);
|
---|
121 |
|
---|
122 | // iterate over every item in the parents
|
---|
123 | for (int i = 1; i <= length; i++) {
|
---|
124 | final int idx = (ub + i) % length;
|
---|
125 |
|
---|
126 | // retrieve the current item in each parent
|
---|
127 | final T item1 = parent1Rep.get(idx);
|
---|
128 | final T item2 = parent2Rep.get(idx);
|
---|
129 |
|
---|
130 | // if the first child already contains the item in the second parent add it
|
---|
131 | if (!child1Set.contains(item2)) {
|
---|
132 | child1.add(item2);
|
---|
133 | child1Set.add(item2);
|
---|
134 | }
|
---|
135 |
|
---|
136 | // if the second child already contains the item in the first parent add it
|
---|
137 | if (!child2Set.contains(item1)) {
|
---|
138 | child2.add(item1);
|
---|
139 | child2Set.add(item1);
|
---|
140 | }
|
---|
141 | }
|
---|
142 |
|
---|
143 | // rotate so that the original slice is in the same place as in the parents.
|
---|
144 | Collections.rotate(child1, lb);
|
---|
145 | Collections.rotate(child2, lb);
|
---|
146 |
|
---|
147 | return new ChromosomePair(first.newFixedLengthChromosome(child1),
|
---|
148 | second.newFixedLengthChromosome(child2));
|
---|
149 | }
|
---|
150 | }
|
---|