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