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.OutOfRangeException;
|
---|
25 | import agents.anac.y2019.harddealer.math3.exception.util.LocalizedFormats;
|
---|
26 | import agents.anac.y2019.harddealer.math3.random.RandomGenerator;
|
---|
27 |
|
---|
28 | /**
|
---|
29 | * Perform Uniform Crossover [UX] on the specified chromosomes. A fixed mixing
|
---|
30 | * ratio is used to combine genes from the first and second parents, e.g. using a
|
---|
31 | * ratio of 0.5 would result in approximately 50% of genes coming from each
|
---|
32 | * parent. This is typically a poor method of crossover, but empirical evidence
|
---|
33 | * suggests that it is more exploratory and results in a larger part of the
|
---|
34 | * problem space being searched.
|
---|
35 | * <p>
|
---|
36 | * This crossover policy evaluates each gene of the parent chromosomes by chosing a
|
---|
37 | * uniform random number {@code p} in the range [0, 1]. If {@code p} < {@code ratio},
|
---|
38 | * the parent genes are swapped. This means with a ratio of 0.7, 30% of the genes from the
|
---|
39 | * first parent and 70% from the second parent will be selected for the first offspring (and
|
---|
40 | * vice versa for the second offspring).
|
---|
41 | * <p>
|
---|
42 | * This policy works only on {@link AbstractListChromosome}, and therefore it
|
---|
43 | * is parameterized by T. Moreover, the chromosomes must have same lengths.
|
---|
44 | *
|
---|
45 | * @see <a href="http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29">Crossover techniques (Wikipedia)</a>
|
---|
46 | * @see <a href="http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php">Crossover (Obitko.com)</a>
|
---|
47 | * @see <a href="http://www.tomaszgwiazda.com/uniformX.htm">Uniform crossover</a>
|
---|
48 | * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
|
---|
49 | * @since 3.1
|
---|
50 | */
|
---|
51 | public class UniformCrossover<T> implements CrossoverPolicy {
|
---|
52 |
|
---|
53 | /** The mixing ratio. */
|
---|
54 | private final double ratio;
|
---|
55 |
|
---|
56 | /**
|
---|
57 | * Creates a new {@link UniformCrossover} policy using the given mixing ratio.
|
---|
58 | *
|
---|
59 | * @param ratio the mixing ratio
|
---|
60 | * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range
|
---|
61 | */
|
---|
62 | public UniformCrossover(final double ratio) throws OutOfRangeException {
|
---|
63 | if (ratio < 0.0d || ratio > 1.0d) {
|
---|
64 | throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d);
|
---|
65 | }
|
---|
66 | this.ratio = ratio;
|
---|
67 | }
|
---|
68 |
|
---|
69 | /**
|
---|
70 | * Returns the mixing ratio used by this {@link CrossoverPolicy}.
|
---|
71 | *
|
---|
72 | * @return the mixing ratio
|
---|
73 | */
|
---|
74 | public double getRatio() {
|
---|
75 | return ratio;
|
---|
76 | }
|
---|
77 |
|
---|
78 | /**
|
---|
79 | * {@inheritDoc}
|
---|
80 | *
|
---|
81 | * @throws MathIllegalArgumentException iff one of the chromosomes is
|
---|
82 | * not an instance of {@link AbstractListChromosome}
|
---|
83 | * @throws DimensionMismatchException if the length of the two chromosomes is different
|
---|
84 | */
|
---|
85 | @SuppressWarnings("unchecked")
|
---|
86 | public ChromosomePair crossover(final Chromosome first, final Chromosome second)
|
---|
87 | throws DimensionMismatchException, MathIllegalArgumentException {
|
---|
88 |
|
---|
89 | if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
|
---|
90 | throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
|
---|
91 | }
|
---|
92 | return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
|
---|
93 | }
|
---|
94 |
|
---|
95 | /**
|
---|
96 | * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
|
---|
97 | *
|
---|
98 | * @param first the first chromosome
|
---|
99 | * @param second the second chromosome
|
---|
100 | * @return the pair of new chromosomes that resulted from the crossover
|
---|
101 | * @throws DimensionMismatchException if the length of the two chromosomes is different
|
---|
102 | */
|
---|
103 | private ChromosomePair mate(final AbstractListChromosome<T> first,
|
---|
104 | final AbstractListChromosome<T> second) throws DimensionMismatchException {
|
---|
105 | final int length = first.getLength();
|
---|
106 | if (length != second.getLength()) {
|
---|
107 | throw new DimensionMismatchException(second.getLength(), length);
|
---|
108 | }
|
---|
109 |
|
---|
110 | // array representations of the parents
|
---|
111 | final List<T> parent1Rep = first.getRepresentation();
|
---|
112 | final List<T> parent2Rep = second.getRepresentation();
|
---|
113 | // and of the children
|
---|
114 | final List<T> child1Rep = new ArrayList<T>(length);
|
---|
115 | final List<T> child2Rep = new ArrayList<T>(length);
|
---|
116 |
|
---|
117 | final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();
|
---|
118 |
|
---|
119 | for (int index = 0; index < length; index++) {
|
---|
120 |
|
---|
121 | if (random.nextDouble() < ratio) {
|
---|
122 | // swap the bits -> take other parent
|
---|
123 | child1Rep.add(parent2Rep.get(index));
|
---|
124 | child2Rep.add(parent1Rep.get(index));
|
---|
125 | } else {
|
---|
126 | child1Rep.add(parent1Rep.get(index));
|
---|
127 | child2Rep.add(parent2Rep.get(index));
|
---|
128 | }
|
---|
129 | }
|
---|
130 |
|
---|
131 | return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
|
---|
132 | second.newFixedLengthChromosome(child2Rep));
|
---|
133 | }
|
---|
134 | }
|
---|