View Javadoc
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.math3.genetics;
18  
19  import java.util.ArrayList;
20  import java.util.List;
21  
22  import org.apache.commons.math3.exception.DimensionMismatchException;
23  import org.apache.commons.math3.exception.MathIllegalArgumentException;
24  import org.apache.commons.math3.exception.OutOfRangeException;
25  import org.apache.commons.math3.exception.util.LocalizedFormats;
26  import org.apache.commons.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} &lt; {@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   * @version $Id: UniformCrossover.java 1551014 2013-12-15 10:56:49Z tn $
51   */
52  public class UniformCrossover<T> implements CrossoverPolicy {
53  
54      /** The mixing ratio. */
55      private final double ratio;
56  
57      /**
58       * Creates a new {@link UniformCrossover} policy using the given mixing ratio.
59       *
60       * @param ratio the mixing ratio
61       * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range
62       */
63      public UniformCrossover(final double ratio) throws OutOfRangeException {
64          if (ratio < 0.0d || ratio > 1.0d) {
65              throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d);
66          }
67          this.ratio = ratio;
68      }
69  
70      /**
71       * Returns the mixing ratio used by this {@link CrossoverPolicy}.
72       *
73       * @return the mixing ratio
74       */
75      public double getRatio() {
76          return ratio;
77      }
78  
79      /**
80       * {@inheritDoc}
81       *
82       * @throws MathIllegalArgumentException iff one of the chromosomes is
83       *   not an instance of {@link AbstractListChromosome}
84       * @throws DimensionMismatchException if the length of the two chromosomes is different
85       */
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<T>(length);
116         final List<T> child2Rep = new ArrayList<T>(length);
117 
118         final RandomGenerator 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 }