Mutator.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-3.8.0).
003  * Copyright (c) 2007-2017 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
070  */
071 public class Mutator<
072     extends Gene<?, G>,
073     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 }