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}