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 shift mutation applies mutation between two randomly chosen points. A
029 * random value between the two points splits the sequences of genes between the
030 * positions. The second sequence is then shifted in front of the first one.
031 * This mutation operator can be used for combinatorial problems, where no
032 * duplicated genes within a chromosome are allowed, e.g., for the TSP.
033 * <p>
034 *      <img src="doc-files/ShiftMutator.svg" width="450"
035 *           alt="Shift mutator" >
036 *
037 * @see <a href="https://doi.org/10.1007/978-3-030-42227-1_12">
038 *     Elements of evolutionary algorithms. Computational intelligence:
039 *     A methodological introduction (pp. 255–285).</a>
040 * @see Mutator
041 *
042 * @author <a href="mailto:feichtenschlager10@gmail.com">Paul Feichtenschlager</a>
043 * @version 8.0
044 * @since 8.0
045 */
046public class ShiftMutator<
047        G extends Gene<?, G>,
048        C extends Comparable<? super C>
049>
050        extends Mutator<G, C>
051{
052
053        /**
054         * This class defines the {@link Chromosome} shift indexes.
055         * <p>
056         *      <img src="doc-files/ShiftMutator.svg" width="450"
057         *           alt="Shift mutator" >
058         *
059         * @param a the start index of the shift range (inclusively)
060         * @param b the end index (exclusively) of the first shift range and the
061         *        start index (inclusively) of the second shift range
062         * @param c the end index (exclusively) of the second shift range
063         */
064        public record Range(int a, int b, int c) {
065
066                /**
067                 * Create a new shift range with the given parameters
068                 *
069                 * @throws IllegalArgumentException if the indexes are smaller than zero
070                 *         or overlapping
071                 */
072                public Range {
073                        if (a < 0 || b < 0 || c < 0 || a >= b || b >= c) {
074                                throw new IllegalArgumentException(
075                                        "Invalid shift range [%d, %d, %d].".formatted(a, b, c)
076                                );
077                        }
078                }
079
080                /**
081                 * Performs the <em>shifting</em> of the elements of the given
082                 * {@code sequence}.
083                 *
084                 * @param seq the elements which will be shifted
085                 * @param <G> the shifted element type
086                 * @throws NullPointerException if the given {@code sequence} is
087                 *         {@code null}
088                 */
089                <G> void shift(final MSeq<G> seq) {
090                        if (seq.length() < c) {
091                                throw new IllegalArgumentException(
092                                        "Sequence to short for given range: [length=%d, %s]."
093                                                .formatted(seq.length(), this)
094                                );
095                        }
096
097                        final var temp = seq.subSeq(a, b).copy();
098
099                        final var length1 = b - a;
100                        final var length2 = c - b;
101                        for (int i = 0; i < length2; ++i) {
102                                seq.set(a + i, seq.get(b + i));
103                        }
104                        for (int i = 0; i < length1; ++i) {
105                                seq.set(a + length2 + i, temp.get(i));
106                        }
107                }
108
109        }
110
111        /**
112         * Functional interface for creating random shift ranges objects for
113         * shifting sequences of a given length.
114         */
115        @FunctionalInterface
116        public interface RangeRandom {
117
118                /**
119                 * Random shift range generator, which creates shifter with uniformly
120                 * distributed shifting points. Both the length and the shift indexes
121                 * are chosen uniformly.
122                 */
123                RangeRandom UNIFORM = (random, length) -> {
124                        if (length <= 1) {
125                                throw new IllegalArgumentException(
126                                        "Length must be greater then 1, but was %d."
127                                                .formatted(length)
128                                );
129                        }
130
131                        final int[] points = Subsets.next(random, length + 1, 3);
132                        return new Range(points[0], points[1], points[2]);
133                };
134
135                /**
136                 * Create a new <em>random</em> shift range for shifting sequences with a
137                 * given {@code length}.
138                 *
139                 * @param random the random generator to be used for creating a new
140                 *        shifter
141                 * @param length the length of the sequence to be shifted
142                 * @return a new <em>randomly</em> created shifter
143                 */
144                Range newRange(final RandomGenerator random, final int length);
145
146                /**
147                 * Create a new random shift range generator, which uses the given
148                 * distributions for creating the shift points.
149                 *
150                 * @param lengthSampler the sampler used for creating the shifted gene
151                 *        count
152                 * @param indexSampler the sampler used for creating the shift indexes
153                 * @return a new random shift generator with the given parameters
154                 */
155                static RangeRandom of(
156                        final Sampler lengthSampler,
157                        final Sampler indexSampler
158                ) {
159                        requireNonNull(lengthSampler);
160                        requireNonNull(indexSampler);
161
162                        return (random, size) -> {
163                                if (size <= 1) {
164                                        throw new IllegalArgumentException(
165                                                "Length must be greater then 1, but was %d."
166                                                        .formatted(size)
167                                        );
168                                }
169
170                                final int lng = lengthSampler.sample(random, IntRange.of(2, size));
171                                final int a = indexSampler.sample(random, IntRange.of(0, size - lng));
172                                final int b = indexSampler.sample(random, IntRange.of(a + 1, lng - 1));
173                                final int c = a + lng;
174
175                                return new Range(a, b, c);
176                        };
177                }
178
179                /**
180                 * Create a new random shift range generator, which uses the given
181                 * distributions for creating the shift points. The shift indexes are
182                 * uniformly distributed.
183                 *
184                 * @see #of(Sampler, Sampler)
185                 *
186                 * @param lengthSampler the sampler used for creating the shifted gene
187                 *        count
188                 * @return a new random shift generator with the given parameters
189                 */
190                static RangeRandom of(final Sampler lengthSampler) {
191                        return of(lengthSampler, Sampler.UNIFORM);
192                }
193
194        }
195
196        private final RangeRandom _random;
197
198        /**
199         * Constructs an alterer with a given shifter-random and recombination
200         * probability.
201         *
202         * @param probability the crossover probability.
203         * @param random the {@link Range} generator.
204         * @throws IllegalArgumentException if the {@code probability} is not in the
205         *          valid range of {@code [0, 1]}.
206         */
207        public ShiftMutator(final RangeRandom random, final double probability) {
208                super(probability);
209                _random = requireNonNull(random);
210        }
211
212        /**
213         * Constructs an alterer with a given shifter-random.
214         *
215         * @param random the {@link Range} generator.
216         * @throws IllegalArgumentException if the {@code probability} is not in the
217         *          valid range of {@code [0, 1]}.
218         */
219        public ShiftMutator(final RangeRandom random) {
220                this(random, DEFAULT_ALTER_PROBABILITY);
221        }
222
223        /**
224         * Constructs an alterer with a given recombination probability.
225         *
226         * @param probability the crossover probability.
227         * @throws IllegalArgumentException if the {@code probability} is not in the
228         *          valid range of {@code [0, 1]}.
229         */
230        public ShiftMutator(final double probability) {
231                this(RangeRandom.UNIFORM, probability);
232        }
233
234        /**
235         * Default constructor, with default mutation probability
236         * ({@link AbstractAlterer#DEFAULT_ALTER_PROBABILITY}).
237         */
238        public ShiftMutator() {
239                this(DEFAULT_ALTER_PROBABILITY);
240        }
241
242        /**
243         * Splits the values between two points into two sequences and shifts the
244         * second one in front of the first one.
245         */
246        @Override
247        protected MutatorResult<Chromosome<G>> mutate(
248                final Chromosome<G> chromosome,
249                final double p,
250                final RandomGenerator random
251        ) {
252                final MutatorResult<Chromosome<G>> result;
253
254                if (chromosome.length() > 1) {
255                        final var genes = MSeq.of(chromosome);
256                        final var range = _random.newRange(random, chromosome.length());
257
258                        range.shift(genes);
259
260                        result = new MutatorResult<>(
261                                chromosome.newInstance(genes.toISeq()),
262                                range.c - range.a
263                        );
264                } else {
265                        result = new MutatorResult<>(chromosome, 0);
266                }
267
268                return result;
269        }
270
271}