001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * 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 * Author:
018 *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
019 */
020package io.jenetics;
021
022import static java.lang.Math.pow;
023import static java.lang.String.format;
024
025import java.util.random.RandomGenerator;
026
027import io.jenetics.internal.math.Probabilities;
028import io.jenetics.util.ISeq;
029import io.jenetics.util.RandomRegistry;
030import io.jenetics.util.Seq;
031
032/**
033 * This class is for mutating the chromosomes of a given population. There are
034 * two distinct roles mutation plays
035 * <ul>
036 *     <li>Exploring the search space. By making small moves mutation allows a
037 *     population to explore the search space. This exploration is often slow
038 *     compared to crossover, but in problems where crossover is disruptive this
039 *     can be an important way to explore the landscape.
040 *     </li>
041 *     <li>Maintaining diversity. Mutation prevents a population from
042 *     correlating. Even if most of the search is being performed by crossover,
043 *     mutation can be vital to provide the diversity which crossover needs.
044 *     </li>
045 * </ul>
046 *
047 * <p>
048 * The mutation probability is the parameter that must be optimized. The optimal
049 * value of the mutation rate depends on the role mutation plays. If mutation is
050 * the only source of exploration (if there is no crossover) then the mutation
051 * rate should be set so that a reasonable neighborhood of solutions is explored.
052 * </p>
053 * The mutation probability <i>P(m)</i> is the probability that a specific gene
054 * over the whole population is mutated. The number of available genes of a
055 * population is
056 * <p>
057 * <img src="doc-files/mutator-N_G.svg" alt="N_P N_{g}=N_P \sum_{i=0}^{N_{G}-1}N_{C[i]}" >
058 * </p>
059 * where <i>N<sub>P</sub></i>  is the population size, <i>N<sub>g</sub></i> the
060 * number of genes of a genotype. So the (average) number of genes
061 * mutated by the mutation is
062 * <p>
063 * <img src="doc-files/mutator-mean_m.svg" alt="\hat{\mu}=N_{P}N_{g}\cdot P(m)" >
064 * </p>
065 *
066 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
067 * @since 1.0
068 * @version 4.0
069 */
070public class Mutator<
071        G extends Gene<?, G>,
072        C extends Comparable<? super C>
073>
074        extends AbstractAlterer<G, C>
075{
076
077        /**
078         * Construct a Mutation object which a given mutation probability.
079         *
080         * @param probability Mutation probability. The given probability is
081         *         divided by the number of chromosomes of the genotype to form
082         *         the concrete mutation probability.
083         * @throws IllegalArgumentException if the {@code probability} is not in the
084         *          valid range of {@code [0, 1]}.
085         */
086        public Mutator(final double probability) {
087                super(probability);
088        }
089
090        /**
091         * Default constructor, with probability = 0.01.
092         */
093        public Mutator() {
094                this(0.01);
095        }
096
097        /**
098         * Concrete implementation of the alter method. It uses the following
099         * mutation methods: {@link #mutate(Phenotype, long, double, RandomGenerator)},
100         * {@link #mutate(Genotype, double, RandomGenerator)},
101         * {@link #mutate(Chromosome, double, RandomGenerator)},
102         * {@link #mutate(Gene, RandomGenerator)},
103         * in this specific order.
104         *
105         * @see #mutate(Phenotype, long, double, RandomGenerator)
106         * @see #mutate(Genotype, double, RandomGenerator)
107         * @see #mutate(Chromosome, double, RandomGenerator)
108         * @see #mutate(Gene, RandomGenerator)
109         */
110        @Override
111        public AltererResult<G, C> alter(
112                final Seq<Phenotype<G, C>> population,
113                final long generation
114        ) {
115                assert population != null : "Not null is guaranteed from base class.";
116
117                final var random = RandomRegistry.random();
118                final double p = pow(_probability, 1.0/3.0);
119                final int P = Probabilities.toInt(p);
120
121                final Seq<MutatorResult<Phenotype<G, C>>> result = population
122                        .map(pt -> random.nextInt() < P
123                                ? mutate(pt, generation, p, random)
124                                : new MutatorResult<>(pt, 0));
125
126                return new AltererResult<>(
127                        result.map(MutatorResult::result).asISeq(),
128                        result.stream().mapToInt(MutatorResult::mutations).sum()
129                );
130        }
131
132        /**
133         * Mutates the given phenotype.
134         *
135         * @see #mutate(Genotype, double, RandomGenerator)
136         * @see #mutate(Chromosome, double, RandomGenerator)
137         * @see #mutate(Gene, RandomGenerator)
138         *
139         * @param phenotype the phenotype to mutate
140         * @param generation the actual generation
141         * @param p the mutation probability for the underlying genetic objects
142         * @param random the random engine used for the phenotype mutation
143         * @return the mutation result
144         */
145        protected MutatorResult<Phenotype<G, C>> mutate(
146                final Phenotype<G, C> phenotype,
147                final long generation,
148                final double p,
149                final RandomGenerator random
150        ) {
151                return mutate(phenotype.genotype(), p, random)
152                        .map(gt -> Phenotype.of(gt, generation));
153        }
154
155        /**
156         * Mutates the given genotype.
157         *
158         * @see #mutate(Chromosome, double, RandomGenerator)
159         * @see #mutate(Gene, RandomGenerator)
160         *
161         * @param genotype the genotype to mutate
162         * @param p the mutation probability for the underlying genetic objects
163         * @param random the random engine used for the genotype mutation
164         * @return the mutation result
165         */
166        protected MutatorResult<Genotype<G>> mutate(
167                final Genotype<G> genotype,
168                final double p,
169                final RandomGenerator random
170        ) {
171                final int P = Probabilities.toInt(p);
172                final ISeq<MutatorResult<Chromosome<G>>> result = genotype.stream()
173                        .map(gt -> random.nextInt() < P
174                                ? mutate(gt, p, random)
175                                : new MutatorResult<>(gt, 0))
176                        .collect(ISeq.toISeq());
177
178                return new MutatorResult<>(
179                        Genotype.of(result.map(MutatorResult::result)),
180                        result.stream().mapToInt(MutatorResult::mutations).sum()
181                );
182        }
183
184        /**
185         * Mutates the given chromosome.
186         *
187         * @see #mutate(Gene, RandomGenerator)
188         *
189         * @param chromosome the chromosome to mutate
190         * @param p the mutation probability for the underlying genetic objects
191         * @param random the random engine used for the genotype mutation
192         * @return the mutation result
193         */
194        protected MutatorResult<Chromosome<G>> mutate(
195                final Chromosome<G> chromosome,
196                final double p,
197                final RandomGenerator random
198        ) {
199                final int P = Probabilities.toInt(p);
200                final ISeq<MutatorResult<G>> result = chromosome.stream()
201                        .map(gene -> random.nextInt() < P
202                                ? new MutatorResult<>(mutate(gene, random), 1)
203                                : new MutatorResult<>(gene, 0))
204                        .collect(ISeq.toISeq());
205
206                return new MutatorResult<>(
207                        chromosome.newInstance(result.map(MutatorResult::result)),
208                        result.stream().mapToInt(MutatorResult::mutations).sum()
209                );
210        }
211
212        /**
213         * Mutates the given gene.
214         *
215         * @param gene the gene to mutate
216         * @param random the random engine used for the genotype mutation
217         * @return the mutation result
218         */
219        protected G mutate(final G gene, final RandomGenerator random) {
220                return gene.newInstance();
221        }
222
223        @Override
224        public String toString() {
225                return format("%s[p=%f]", getClass().getSimpleName(), _probability);
226        }
227
228}