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 static java.util.Objects.requireNonNull;
019
020import java.util.random.RandomGenerator;
021
022import io.jenetics.internal.math.Subsets;
023import io.jenetics.stat.Sampler;
024import io.jenetics.util.IntRange;
025import io.jenetics.util.MSeq;
026
027/**
028 * The shuffle mutation, changes the order of the genes between two randomly
029 * chosen positions. The genes between the positions are shuffled. This mutation
030 * operator can also be used for combinatorial problems, where no duplicated
031 * genes within a chromosome are allowed, e.g., for the TSP.
032 * <p>
033 *      <img src="doc-files/ShuffleMutator.svg" width="450"
034 *           alt="Shuffle mutator" >
035 *
036 * @see <a href="https://doi.org/10.1007/978-3-030-42227-1_12">
037 *     Elements of evolutionary algorithms. Computational intelligence:
038 *     A methodological introduction (pp. 255–285).</a>
039 * @see Mutator
040 *
041 * @author <a href="mailto:feichtenschlager10@gmail.com">Paul Feichtenschlager</a>
042 * @version 8.0
043 * @since 8.0
044 */
045public class ShuffleMutator<
046        G extends Gene<?, G>,
047        C extends Comparable<? super C>
048>
049        extends Mutator<G, C>
050{
051
052        /**
053         * Represents the chromosome range which will be shuffled
054         *
055         * @param a the start index (inclusively)
056         * @param b the end index (exclusively)
057         */
058        public record Range(int a, int b) {
059                public Range {
060                        if (a < 0 || b < 0 || b <= a) {
061                                throw new IllegalArgumentException(
062                                        "Invalid range: [%d, %d].".formatted(a, b)
063                                );
064                        }
065                }
066        }
067
068        /**
069         * Functional interface for creating random range objects for
070         * shuffling sequences of a given length.
071         */
072        @FunctionalInterface
073        public interface RangeRandom {
074
075                /**
076                 * Random range generator, which creates ranges with uniformly
077                 * distributed range indexes. Both the length and the shift indexes
078                 * are chosen uniformly.
079                 */
080                RangeRandom UNIFORM = (random, length) -> {
081                        if (length <= 1) {
082                                throw new IllegalArgumentException(
083                                        "Length must be greater then 1, but was %d."
084                                                .formatted(length)
085                                );
086                        }
087
088                        final int[] points = Subsets.next(random, length + 1, 2);
089                        return new Range(points[0], points[1]);
090                };
091
092                /**
093                 * Create a new <em>random</em> range for shuffling sequences with a
094                 * given {@code length}.
095                 *
096                 * @param random the random generator to be used for creating a new
097                 *        range
098                 * @param length the length of the sequence to be shuffled
099                 * @return a new <em>randomly</em> created shuffle range
100                 */
101                Range newRange(final RandomGenerator random, final int length);
102
103                /**
104                 * Create a new random range generator, which uses the given distributions
105                 * for creating the range points.
106                 *
107                 * @param lengthSampler the sampler used for creating the shifted gene
108                 *        count
109                 * @param indexSampler the sampler used for creating the shift indexes
110                 * @return a new random range generator with the given parameters
111                 */
112                static RangeRandom of(
113                        final Sampler lengthSampler,
114                        final Sampler indexSampler
115                ) {
116                        requireNonNull(lengthSampler);
117                        requireNonNull(indexSampler);
118
119                        return (random, size) -> {
120                                if (size <= 1) {
121                                        throw new IllegalArgumentException(
122                                                "Length must be greater then 1, but was %d."
123                                                        .formatted(size)
124                                        );
125                                }
126
127                                final int lng = lengthSampler.sample(random, IntRange.of(1, size));
128                                final int a = indexSampler.sample(random, IntRange.of(0, size - lng));
129                                final int b = a + lng;
130
131                                return new Range(a, b);
132                        };
133                }
134
135                /**
136                 * Create a new random range generator, which uses the given distributions
137                 * for creating the shift points. The shift indexes are uniformly
138                 * distributed.
139                 *
140                 * @see #of(Sampler, Sampler)
141                 *
142                 * @param lengthSampler the sampler used for creating the shifted gene
143                 *        count
144                 * @return a new random shift generator with the given parameters
145                 */
146                static RangeRandom of(final Sampler lengthSampler) {
147                        return of(lengthSampler, Sampler.UNIFORM);
148                }
149        }
150
151        private final RangeRandom _random;
152
153        /**
154         * Constructs an alterer with a given recombination probability and random
155         * range generator.
156         *
157         * @param probability the crossover probability.
158         * @param random the random range generator used by the mutator
159         * @throws IllegalArgumentException if the {@code probability} is not in the
160         *          valid range of {@code [0, 1]}.
161         */
162        public ShuffleMutator(final RangeRandom random, final double probability) {
163                super(probability);
164                _random = requireNonNull(random);
165        }
166
167        /**
168         * Constructs an alterer with a given recombination probability.
169         *
170         * @param probability the crossover probability.
171         * @throws IllegalArgumentException if the {@code probability} is not in the
172         *          valid range of {@code [0, 1]}.
173         */
174        public ShuffleMutator(final double probability) {
175                this(RangeRandom.UNIFORM, probability);
176        }
177
178        /**
179         * Default constructor, with default mutation probability
180         * ({@link AbstractAlterer#DEFAULT_ALTER_PROBABILITY}).
181         */
182        public ShuffleMutator() {
183                this(RangeRandom.UNIFORM, DEFAULT_ALTER_PROBABILITY);
184        }
185
186        /**
187         * Changes the order of the genes between two points randomly.
188         */
189        @Override
190        protected MutatorResult<Chromosome<G>> mutate(
191                final Chromosome<G> chromosome,
192                final double p,
193                final RandomGenerator random
194        ) {
195                final MutatorResult<Chromosome<G>> result;
196                if (chromosome.length() > 1) {
197                        final var genes = MSeq.of(chromosome);
198                        final var range = _random.newRange(random, chromosome.length());
199
200                        genes.subSeq(range.a, range.b).shuffle();
201
202                        result = new MutatorResult<>(
203                                chromosome.newInstance(genes.toISeq()),
204                                range.b - range.a
205                        );
206                } else {
207                        result = new MutatorResult<>(chromosome, 0);
208                }
209
210                return result;
211        }
212
213}