    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    }