001/* 002 * Java Genetic Algorithm Library (jenetics-8.3.0). 003 * Copyright (c) 2007-2025 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 * @param <G> the gene type 067 * @param <C> the allele type 068 * 069 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 070 * @since 1.0 071 * @version 4.0 072 */ 073public class Mutator< 074 G extends Gene<?, G>, 075 C extends Comparable<? super C> 076> 077 extends AbstractAlterer<G, C> 078{ 079 080 /** 081 * Construct a Mutation object which a given mutation probability. 082 * 083 * @param probability Mutation probability. The given probability is 084 * divided by the number of chromosomes of the genotype to form 085 * the concrete mutation probability. 086 * @throws IllegalArgumentException if the {@code probability} is not in the 087 * valid range of {@code [0, 1]}. 088 */ 089 public Mutator(final double probability) { 090 super(probability); 091 } 092 093 /** 094 * Default constructor, with probability = 0.01. 095 */ 096 public Mutator() { 097 this(0.01); 098 } 099 100 /** 101 * Concrete implementation of the alter method. It uses the following 102 * mutation methods: {@link #mutate(Phenotype, long, double, RandomGenerator)}, 103 * {@link #mutate(Genotype, double, RandomGenerator)}, 104 * {@link #mutate(Chromosome, double, RandomGenerator)}, 105 * {@link #mutate(Gene, RandomGenerator)}, 106 * in this specific order. 107 * 108 * @see #mutate(Phenotype, long, double, RandomGenerator) 109 * @see #mutate(Genotype, double, RandomGenerator) 110 * @see #mutate(Chromosome, double, RandomGenerator) 111 * @see #mutate(Gene, RandomGenerator) 112 */ 113 @Override 114 public AltererResult<G, C> alter( 115 final Seq<Phenotype<G, C>> population, 116 final long generation 117 ) { 118 assert population != null : "Not null is guaranteed from base class."; 119 120 final var random = RandomRegistry.random(); 121 final double p = pow(_probability, 1.0/3.0); 122 final int P = Probabilities.toInt(p); 123 124 final Seq<MutatorResult<Phenotype<G, C>>> result = population 125 .map(pt -> random.nextInt() < P 126 ? mutate(pt, generation, p, random) 127 : new MutatorResult<>(pt, 0)); 128 129 return new AltererResult<>( 130 result.map(MutatorResult::result).asISeq(), 131 result.stream().mapToInt(MutatorResult::mutations).sum() 132 ); 133 } 134 135 /** 136 * Mutates the given phenotype. 137 * 138 * @see #mutate(Genotype, double, RandomGenerator) 139 * @see #mutate(Chromosome, double, RandomGenerator) 140 * @see #mutate(Gene, RandomGenerator) 141 * 142 * @param phenotype the phenotype to mutate 143 * @param generation the actual generation 144 * @param p the mutation probability for the underlying genetic objects 145 * @param random the random engine used for the phenotype mutation 146 * @return the mutation result 147 */ 148 protected MutatorResult<Phenotype<G, C>> mutate( 149 final Phenotype<G, C> phenotype, 150 final long generation, 151 final double p, 152 final RandomGenerator random 153 ) { 154 return mutate(phenotype.genotype(), p, random) 155 .map(gt -> Phenotype.of(gt, generation)); 156 } 157 158 /** 159 * Mutates the given genotype. 160 * 161 * @see #mutate(Chromosome, double, RandomGenerator) 162 * @see #mutate(Gene, RandomGenerator) 163 * 164 * @param genotype the genotype to mutate 165 * @param p the mutation probability for the underlying genetic objects 166 * @param random the random engine used for the genotype mutation 167 * @return the mutation result 168 */ 169 protected MutatorResult<Genotype<G>> mutate( 170 final Genotype<G> genotype, 171 final double p, 172 final RandomGenerator random 173 ) { 174 final int P = Probabilities.toInt(p); 175 final ISeq<MutatorResult<Chromosome<G>>> result = genotype.stream() 176 .map(gt -> random.nextInt() < P 177 ? mutate(gt, p, random) 178 : new MutatorResult<>(gt, 0)) 179 .collect(ISeq.toISeq()); 180 181 return new MutatorResult<>( 182 Genotype.of(result.map(MutatorResult::result)), 183 result.stream().mapToInt(MutatorResult::mutations).sum() 184 ); 185 } 186 187 /** 188 * Mutates the given chromosome. 189 * 190 * @see #mutate(Gene, RandomGenerator) 191 * 192 * @param chromosome the chromosome to mutate 193 * @param p the mutation probability for the underlying genetic objects 194 * @param random the random engine used for the genotype mutation 195 * @return the mutation result 196 */ 197 protected MutatorResult<Chromosome<G>> mutate( 198 final Chromosome<G> chromosome, 199 final double p, 200 final RandomGenerator random 201 ) { 202 final int P = Probabilities.toInt(p); 203 final ISeq<MutatorResult<G>> result = chromosome.stream() 204 .map(gene -> random.nextInt() < P 205 ? new MutatorResult<>(mutate(gene, random), 1) 206 : new MutatorResult<>(gene, 0)) 207 .collect(ISeq.toISeq()); 208 209 return new MutatorResult<>( 210 chromosome.newInstance(result.map(MutatorResult::result)), 211 result.stream().mapToInt(MutatorResult::mutations).sum() 212 ); 213 } 214 215 /** 216 * Mutates the given gene. 217 * 218 * @param gene the gene to mutate 219 * @param random the random engine used for the genotype mutation 220 * @return the mutation result 221 */ 222 protected G mutate(final G gene, final RandomGenerator random) { 223 return gene.newInstance(); 224 } 225 226 @Override 227 public String toString() { 228 return format("%s[p=%f]", getClass().getSimpleName(), _probability); 229 } 230 231}