001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *      http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016package io.jenetics;
017
018import io.jenetics.internal.math.Subsets;
019import io.jenetics.util.BaseSeq;
020import io.jenetics.util.MSeq;
021import io.jenetics.util.RandomRegistry;
022import io.jenetics.util.Seq;
023
024/**
025 * The {@code UniformOderBasedCrossover} guarantees that all {@link Gene}s
026 * are found exactly once in each chromosome. No gene is duplicated by this
027 * crossover. This crossover can be applied usefully in the TSP or other
028 * permutation problem encodings. Permutation encoding is useful for all
029 * problems where fitness only depends on the ordering of the genes within
030 * the chromosome. This is the case in many combinatorial optimization problems.
031 * Other crossover operators for combinatorial optimization are:
032 * <ul>
033 *     <li>order crossover</li>
034 *     <li>cycle crossover</li>
035 *     <li>edge recombination crossover</li>
036 *     <li>edge assembly crossover</li>
037 *     <li>partially matched crossover</li>
038 * </ul>
039 * <p>
040 * Within the uniform order-based crossover, a set of positions are chosen
041 * randomly. The genes at the positions are reordered in the order they occur in
042 * the other parent.
043 * <pre>
044 *    C1 = 0123456789
045 *    C2 = 9876543210
046 *    Positions = 2, 4, 5, 7, 8
047 * </pre>
048 *  The values at the positions are removed
049 * <pre>
050 *    C1 = 01_3__6__9
051 *    C2 = 9__6__3_10
052 *    Order of removed values in C1 = 2, 4, 5, 7, 8
053 *    Order of removed values in C2 = 8, 7, 5, 4, 2
054 * </pre>
055 * The removed values are added in the order they occur in the other chromosome
056 * <pre>
057 *    C1 = 0183756429
058 *    C2 = 9246573810
059 * </pre>
060 *
061 * @see <a href="https://doi.org/10.1007/978-3-030-42227-1_12">
062 *     Elements of evolutionary algorithms. Computational intelligence:
063 *     A methodological introduction (pp. 255–285).</a>
064 * @see PermutationChromosome
065 *
066 * @author <a href="mailto:feichtenschlager10@gmail.com">Paul Feichtenschlager</a>
067 * @version 8.0
068 * @since 8.0
069 */
070public class UniformOderBasedCrossover<T, C extends Comparable<? super C>>
071        extends Crossover<EnumGene<T>, C>
072{
073
074        /**
075         * Create a new UniformOrderBasedCrossover instance
076         *
077         * @param probability the recombination probability as defined in
078         *        {@link Crossover#Crossover(double)}. This is the probability that
079         *        a given individual is selected for crossover.
080         * @throws IllegalArgumentException if the probability is not in the
081         *         valid range of {@code [0, 1]}
082         */
083        public UniformOderBasedCrossover(double probability) {
084            super(probability);
085        }
086
087        /**
088         * Applies uniform order-based crossover to two sequences. A set of positions
089         * is chosen, the genes at those positions are reordered as they occur in
090         * the other sequence.
091         *
092         * @param that first sequence
093         * @param other second sequence
094         * @throws IllegalArgumentException if the two input sequences have a
095         *         different length
096         */
097        @Override
098        protected int crossover(
099                final MSeq<EnumGene<T>> that,
100                final MSeq<EnumGene<T>> other
101        ) {
102                if (that.length() != other.length()) {
103                        throw new IllegalArgumentException(
104                                "Required chromosomes with same length: %d != %d"
105                                        .formatted(that.length(), other.length())
106                        );
107                }
108
109                if (that.length() >= 2) {
110                        final var random = RandomRegistry.random();
111                        final var positions = Subsets.next(
112                                random, that.length(), that.length()/2
113                        );
114
115                        final var removed1 = selectAt(positions, that);
116                        final var removed2 = selectAt(positions, other);
117
118                        final var reordered1 = reorder(removed1, other);
119                        final var reordered2 = reorder(removed2, that);
120
121                        exchange(positions, reordered1, that);
122                        exchange(positions, reordered2, other);
123
124                        return positions.length;
125                } else {
126                        return 0;
127                }
128        }
129
130        private static <T> void
131        exchange(final int[] indexes, final BaseSeq<T> ordered, final MSeq<T> seq) {
132                for (int i = 0; i < indexes.length; ++i) {
133                        seq.set(indexes[i], ordered.get(i));
134                }
135        }
136
137        private static <T> Seq<T> reorder(final Seq<T> removed, final Seq<T> seq) {
138            return removed.stream()
139                        .map(seq::lastIndexOf)
140                        .sorted(Integer::compareTo)
141                        .map(seq::get)
142                        .collect(Seq.toSeq());
143        }
144
145        private static <T> Seq<T> selectAt(final int[] indexes, final BaseSeq<T> seq) {
146                final var selected = MSeq. <T>ofLength(indexes.length);
147                for (int i = 0; i < indexes.length; ++i) {
148                        selected.set(i, seq.get(indexes[i]));
149                }
150                return selected;
151        }
152
153}