001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.math3.genetics;
018    
019    import java.util.ArrayList;
020    import java.util.List;
021    
022    import org.apache.commons.math3.exception.DimensionMismatchException;
023    import org.apache.commons.math3.exception.MathIllegalArgumentException;
024    import org.apache.commons.math3.exception.OutOfRangeException;
025    import org.apache.commons.math3.exception.util.LocalizedFormats;
026    import org.apache.commons.math3.random.RandomGenerator;
027    
028    /**
029     * Perform Uniform Crossover [UX] on the specified chromosomes. A fixed mixing
030     * ratio is used to combine genes from the first and second parents, e.g. using a
031     * ratio of 0.5 would result in approximately 50% of genes coming from each
032     * parent. This is typically a poor method of crossover, but empirical evidence
033     * suggests that it is more exploratory and results in a larger part of the
034     * problem space being searched.
035     * <p>
036     * This crossover policy evaluates each gene of the parent chromosomes by chosing a
037     * uniform random number {@code p} in the range [0, 1]. If {@code p} &lt; {@code ratio},
038     * the parent genes are swapped. This means with a ratio of 0.7, 30% of the genes from the
039     * first parent and 70% from the second parent will be selected for the first offspring (and
040     * vice versa for the second offspring).
041     * <p>
042     * This policy works only on {@link AbstractListChromosome}, and therefore it
043     * is parameterized by T. Moreover, the chromosomes must have same lengths.
044     *
045     * @see <a href="http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29">Crossover techniques (Wikipedia)</a>
046     * @see <a href="http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php">Crossover (Obitko.com)</a>
047     * @see <a href="http://www.tomaszgwiazda.com/uniformX.htm">Uniform crossover</a>
048     * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
049     * @since 3.1
050     * @version $Id: UniformCrossover.java 1385297 2012-09-16 16:05:57Z tn $
051     */
052    public class UniformCrossover<T> implements CrossoverPolicy {
053    
054        /** The mixing ratio. */
055        private final double ratio;
056    
057        /**
058         * Creates a new {@link UniformCrossover} policy using the given mixing ratio.
059         *
060         * @param ratio the mixing ratio
061         * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range
062         */
063        public UniformCrossover(final double ratio) throws OutOfRangeException {
064            if (ratio < 0.0d || ratio > 1.0d) {
065                throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d);
066            }
067            this.ratio = ratio;
068        }
069    
070        /**
071         * Returns the mixing ratio used by this {@link CrossoverPolicy}.
072         *
073         * @return the mixing ratio
074         */
075        public double getRatio() {
076            return ratio;
077        }
078    
079        /**
080         * {@inheritDoc}
081         *
082         * @throws MathIllegalArgumentException iff one of the chromosomes is
083         *   not an instance of {@link AbstractListChromosome}
084         * @throws DimensionMismatchException if the length of the two chromosomes is different
085         */
086        @SuppressWarnings("unchecked")
087        public ChromosomePair crossover(final Chromosome first, final Chromosome second)
088            throws DimensionMismatchException, MathIllegalArgumentException {
089    
090            if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) {
091                throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME);
092            }
093            return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
094        }
095    
096        /**
097         * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
098         *
099         * @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>(first.getLength());
116            final List<T> child2Rep = new ArrayList<T>(second.getLength());
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    }