001 /*
002 * Java Genetic Algorithm Library (jenetics-5.1.0).
003 * Copyright (c) 2007-2019 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;
026
027 import io.jenetics.internal.math.probability;
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 a chromosomes of an 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 an
055 * population is
056 * <p>
057 * <img src="doc-files/mutator-N_G.gif" 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.gif" 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, Random)},
100 * {@link #mutate(Genotype, double, Random)},
101 * {@link #mutate(Chromosome, double, Random)}, {@link #mutate(Gene, Random)},
102 * in this specific order.
103 *
104 * @see #mutate(Phenotype, long, double, Random)
105 * @see #mutate(Genotype, double, Random)
106 * @see #mutate(Chromosome, double, Random)
107 * @see #mutate(Gene, Random)
108 */
109 @Override
110 public AltererResult<G, C> alter(
111 final Seq<Phenotype<G, C>> population,
112 final long generation
113 ) {
114 assert population != null : "Not null is guaranteed from base class.";
115
116 final Random random = RandomRegistry.getRandom();
117 final double p = pow(_probability, 1.0/3.0);
118 final int P = probability.toInt(p);
119
120 final Seq<MutatorResult<Phenotype<G, C>>> result = population
121 .map(pt -> random.nextInt() < P
122 ? mutate(pt, generation, p, random)
123 : MutatorResult.of(pt));
124
125 return AltererResult.of(
126 result.map(MutatorResult::getResult).asISeq(),
127 result.stream().mapToInt(MutatorResult::getMutations).sum()
128 );
129 }
130
131 /**
132 * Mutates the given phenotype.
133 *
134 * @see #mutate(Genotype, double, Random)
135 * @see #mutate(Chromosome, double, Random)
136 * @see #mutate(Gene, Random)
137 *
138 * @param phenotype the phenotype to mutate
139 * @param generation the actual generation
140 * @param p the mutation probability for the underlying genetic objects
141 * @param random the random engine used for the phenotype mutation
142 * @return the mutation result
143 */
144 protected MutatorResult<Phenotype<G, C>> mutate(
145 final Phenotype<G, C> phenotype,
146 final long generation,
147 final double p,
148 final Random random
149 ) {
150 return mutate(phenotype.getGenotype(), p, random)
151 .map(gt -> Phenotype.of(gt, generation));
152 }
153
154 /**
155 * Mutates the given genotype.
156 *
157 * @see #mutate(Chromosome, double, Random)
158 * @see #mutate(Gene, Random)
159 *
160 * @param genotype the genotype to mutate
161 * @param p the mutation probability for the underlying genetic objects
162 * @param random the random engine used for the genotype mutation
163 * @return the mutation result
164 */
165 protected MutatorResult<Genotype<G>> mutate(
166 final Genotype<G> genotype,
167 final double p,
168 final Random random
169 ) {
170 final int P = probability.toInt(p);
171 final ISeq<MutatorResult<Chromosome<G>>> result = genotype.toSeq()
172 .map(gt -> random.nextInt() < P
173 ? mutate(gt, p, random)
174 : MutatorResult.of(gt));
175
176 return MutatorResult.of(
177 Genotype.of(result.map(MutatorResult::getResult)),
178 result.stream().mapToInt(MutatorResult::getMutations).sum()
179 );
180 }
181
182 /**
183 * Mutates the given chromosome.
184 *
185 * @see #mutate(Gene, Random)
186 *
187 * @param chromosome the chromosome to mutate
188 * @param p the mutation probability for the underlying genetic objects
189 * @param random the random engine used for the genotype mutation
190 * @return the mutation result
191 */
192 protected MutatorResult<Chromosome<G>> mutate(
193 final Chromosome<G> chromosome,
194 final double p,
195 final Random random
196 ) {
197 final int P = probability.toInt(p);
198 final ISeq<MutatorResult<G>> result = chromosome.stream()
199 .map(gene -> random.nextInt() < P
200 ? MutatorResult.of(mutate(gene, random), 1)
201 : MutatorResult.of(gene))
202 .collect(ISeq.toISeq());
203
204 return MutatorResult.of(
205 chromosome.newInstance(result.map(MutatorResult::getResult)),
206 result.stream().mapToInt(MutatorResult::getMutations).sum()
207 );
208 }
209
210 /**
211 * Mutates the given gene.
212 *
213 * @param gene the gene to mutate
214 * @param random the random engine used for the genotype mutation
215 * @return the mutation result
216 */
217 protected G mutate(final G gene, final Random random) {
218 return gene.newInstance();
219 }
220
221 @Override
222 public String toString() {
223 return format("%s[p=%f]", getClass().getSimpleName(), _probability);
224 }
225
226 }
|