001 /*
002 * Java Genetic Algorithm Library (jenetics-8.0.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 */
020 package io.jenetics;
021
022 import static java.lang.Math.pow;
023 import static java.lang.String.format;
024
025 import java.util.random.RandomGenerator;
026
027 import io.jenetics.internal.math.Probabilities;
028 import io.jenetics.util.ISeq;
029 import io.jenetics.util.RandomRegistry;
030 import 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 */
070 public 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 }
|