001 /*
002 * Java Genetic Algorithm Library (jenetics-3.0.0).
003 * Copyright (c) 2007-2014 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@gmx.at)
019 */
020 package org.jenetics;
021
022 import static java.lang.Math.pow;
023 import static java.lang.String.format;
024 import static org.jenetics.internal.math.random.indexes;
025
026 import org.jenetics.internal.util.Equality;
027 import org.jenetics.internal.util.Hash;
028 import org.jenetics.internal.util.IntRef;
029
030 import org.jenetics.util.MSeq;
031 import org.jenetics.util.RandomRegistry;
032
033 /**
034 * This class is for mutating a chromosomes of an given population. There are
035 * two distinct roles mutation plays
036 * <ul>
037 * <li>Exploring the search space. By making small moves mutation allows a
038 * population to explore the search space. This exploration is often slow
039 * compared to crossover, but in problems where crossover is disruptive this
040 * can be an important way to explore the landscape.
041 * </li>
042 * <li>Maintaining diversity. Mutation prevents a population from
043 * correlating. Even if most of the search is being performed by crossover,
044 * mutation can be vital to provide the diversity which crossover needs.
045 * </li>
046 * </ul>
047 *
048 * <p>
049 * The mutation probability is the parameter that must be optimized. The optimal
050 * value of the mutation rate depends on the role mutation plays. If mutation is
051 * the only source of exploration (if there is no crossover) then the mutation
052 * rate should be set so that a reasonable neighborhood of solutions is explored.
053 * </p>
054 * The mutation probability <i>P(m)</i> is the probability that a specific gene
055 * over the whole population is mutated. The number of available genes of an
056 * population is
057 * <p>
058 * <img src="doc-files/mutator-N_G.gif" alt="N_P N_{g}=N_P \sum_{i=0}^{N_{G}-1}N_{C[i]}" >
059 * </p>
060 * where <i>N<sub>P</sub></i> is the population size, <i>N<sub>g</sub></i> the
061 * number of genes of a genotype. So the (average) number of genes
062 * mutated by the mutation is
063 * <p>
064 * <img src="doc-files/mutator-mean_m.gif" alt="\hat{\mu}=N_{P}N_{g}\cdot P(m)" >
065 * </p>
066 *
067 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
068 * @since 1.0
069 * @version 3.0 — <em>$Date: 2014-12-28 $</em>
070 */
071 public class Mutator<
072 G extends Gene<?, G>,
073 C extends Comparable<? super C>
074 >
075 extends AbstractAlterer<G, C>
076 {
077
078 /**
079 * Construct a Mutation object which a given mutation probability.
080 *
081 * @param probability Mutation probability. The given probability is
082 * divided by the number of chromosomes of the genotype to form
083 * the concrete mutation probability.
084 * @throws IllegalArgumentException if the {@code probability} is not in the
085 * valid range of {@code [0, 1]}..
086 */
087 public Mutator(final double probability) {
088 super(probability);
089 }
090
091 /**
092 * Default constructor, with probability = 0.01.
093 */
094 public Mutator() {
095 this(0.01);
096 }
097
098 /**
099 * Concrete implementation of the alter method.
100 */
101 @Override
102 public int alter(
103 final Population<G, C> population,
104 final long generation
105 ) {
106 assert(population != null) : "Not null is guaranteed from base class.";
107
108 final double p = pow(_probability, 1.0/3.0);
109 final IntRef alterations = new IntRef(0);
110
111 indexes(RandomRegistry.getRandom(), population.size(), p).forEach(i -> {
112 final Phenotype<G, C> pt = population.get(i);
113
114 final Genotype<G> gt = pt.getGenotype();
115 final Genotype<G> mgt = mutate(gt, p, alterations);
116
117 final Phenotype<G, C> mpt = pt.newInstance(mgt, generation);
118 population.set(i, mpt);
119 });
120
121 return alterations.value;
122 }
123
124 private Genotype<G> mutate(
125 final Genotype<G> genotype,
126 final double p,
127 final IntRef alterations
128 ) {
129 final MSeq<Chromosome<G>> chromosomes = genotype.toSeq().copy();
130
131 alterations.value +=
132 indexes(RandomRegistry.getRandom(), genotype.length(), p)
133 .map(i -> mutate(chromosomes, i, p))
134 .sum();
135
136 return genotype.newInstance(chromosomes.toISeq());
137 }
138
139 private int mutate(final MSeq<Chromosome<G>> c, final int i, final double p) {
140 final Chromosome<G> chromosome = c.get(i);
141 final MSeq<G> genes = chromosome.toSeq().copy();
142
143 final int mutations = mutate(genes, p);
144 if (mutations > 0) {
145 c.set(i, chromosome.newInstance(genes.toISeq()));
146 }
147 return mutations;
148 }
149
150 /**
151 * <p>
152 * Template method which gives an (re)implementation of the mutation class
153 * the possibility to perform its own mutation operation, based on a
154 * writable gene array and the gene mutation probability <i>p</i>.
155 *
156 * @param genes the genes to mutate.
157 * @param p the gene mutation probability.
158 * @return the number of performed mutations
159 */
160 protected int mutate(final MSeq<G> genes, final double p) {
161 return (int)indexes(RandomRegistry.getRandom(), genes.length(), p)
162 .peek(i -> genes.set(i, genes.get(i).newInstance()))
163 .count();
164 }
165
166 @Override
167 public int hashCode() {
168 return Hash.of(getClass()).and(super.hashCode()).value();
169 }
170
171 @Override
172 public boolean equals(final Object obj) {
173 return Equality.of(this, obj).test(super::equals);
174 }
175
176 @Override
177 public String toString() {
178 return format("%s[p=%f]", getClass().getSimpleName(), _probability);
179 }
180
181 }
|