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.OutOfRangeException;
25 import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
26 import org.apache.commons.rng.UniformRandomProvider;
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 choosing 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 @Override
86 @SuppressWarnings("unchecked")
87 public ChromosomePair crossover(final Chromosome first, final Chromosome second)
88 throws DimensionMismatchException, MathIllegalArgumentException {
89
90 if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
91 throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
92 }
93 return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
94 }
95
96 /**
97 * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
98 *
99 * @param first the first chromosome
100 * @param second the second chromosome
101 * @return the pair of new chromosomes that resulted from the crossover
102 * @throws DimensionMismatchException if the length of the two chromosomes is different
103 */
104 private ChromosomePair mate(final AbstractListChromosome<T> first,
105 final AbstractListChromosome<T> second) throws DimensionMismatchException {
106 final int length = first.getLength();
107 if (length != second.getLength()) {
108 throw new DimensionMismatchException(second.getLength(), length);
109 }
110
111 // array representations of the parents
112 final List<T> parent1Rep = first.getRepresentation();
113 final List<T> parent2Rep = second.getRepresentation();
114 // and of the children
115 final List<T> child1Rep = new ArrayList<>(length);
116 final List<T> child2Rep = new ArrayList<>(length);
117
118 final UniformRandomProvider random = GeneticAlgorithm.getRandomGenerator();
119
120 for (int index = 0; index < length; index++) {
121
122 if (random.nextDouble() < ratio) {
123 // swap the bits -> take other parent
124 child1Rep.add(parent2Rep.get(index));
125 child2Rep.add(parent1Rep.get(index));
126 } else {
127 child1Rep.add(parent1Rep.get(index));
128 child2Rep.add(parent2Rep.get(index));
129 }
130 }
131
132 return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
133 second.newFixedLengthChromosome(child2Rep));
134 }
135 }