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 */
017package org.apache.commons.math4.legacy.genetics;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
023import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
024import org.apache.commons.math4.legacy.exception.OutOfRangeException;
025import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
026import org.apache.commons.rng.UniformRandomProvider;
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 choosing 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 */
051public class UniformCrossover<T> implements CrossoverPolicy {
052
053    /** The mixing ratio. */
054    private final double ratio;
055
056    /**
057     * Creates a new {@link UniformCrossover} policy using the given mixing ratio.
058     *
059     * @param ratio the mixing ratio
060     * @throws OutOfRangeException if the mixing ratio is outside the [0, 1] range
061     */
062    public UniformCrossover(final double ratio) throws OutOfRangeException {
063        if (ratio < 0.0d || ratio > 1.0d) {
064            throw new OutOfRangeException(LocalizedFormats.CROSSOVER_RATE, ratio, 0.0d, 1.0d);
065        }
066        this.ratio = ratio;
067    }
068
069    /**
070     * Returns the mixing ratio used by this {@link CrossoverPolicy}.
071     *
072     * @return the mixing ratio
073     */
074    public double getRatio() {
075        return ratio;
076    }
077
078    /**
079     * {@inheritDoc}
080     *
081     * @throws MathIllegalArgumentException iff one of the chromosomes is
082     *   not an instance of {@link AbstractListChromosome}
083     * @throws DimensionMismatchException if the length of the two chromosomes is different
084     */
085    @Override
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<>(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}