MutationOperator


1   /*
2    * This file is part of JGAP.
3    *
4    * JGAP offers a dual license model containing the LGPL as well as the MPL.
5    *
6    * For licencing information please see the file license.txt included with JGAP
7    * or have a look at the top of class org.jgap.Chromosome which representatively
8    * includes the JGAP license policy applicable for any file delivered with JGAP.
9    */
10  package org.jgap.impl;
11  
12  import java.util.*;
13  import org.jgap.*;
14  import org.jgap.data.config.*;
15  
16  /**
17   * The mutation operator runs through the genes in each of the Chromosomes
18   * in the population and mutates them in statistical accordance to the
19   * given mutation rate. Mutated Chromosomes are then added to the list of
20   * candidate Chromosomes destined for the natural selection process.
21   * <p>
22   * This MutationOperator supports both fixed and dynamic mutation rates.
23   * A fixed rate is one specified at construction time by the user. A dynamic
24   * rate is determined by this class if no fixed rate is provided, and is
25   * calculated based on the size of the Chromosomes in the population. Details
26   * are specified in the DefaultMutationRateCalculator class.
27   *
28   * @author Neil Rotstan
29   * @author Klaus Meffert
30   * @since 1.0
31   */
32  public class MutationOperator
33      extends BaseGeneticOperator implements Configurable {
34    /** String containing the CVS revision. Read out via reflection!*/
35    private final static String   CVS_REVISION = "$Revision: 1.42 $";
36  
37    /**
38     * Calculator for dynamically determining the mutation rate. If set to
39     * null the value of m_mutationRate will be used. Replaces the previously used
40     * boolean m_dynamicMutationRate.
41     */
42    private IUniversalRateCalculator m_mutationRateCalc;
43  
44    private MutationOperatorConfigurable m_config = new
45        MutationOperatorConfigurable();
46  
47    /**
48     * Constructs a new instance of this MutationOperator without a specified
49     * mutation rate, which results in dynamic mutation being turned on. This
50     * means that the mutation rate will be automatically determined by this
51     * operator based upon the number of genes present in the chromosomes.<p>
52     * Attention: The configuration used is the one set with the static method
53     * Genotype.setConfiguration.
54     * @throws InvalidConfigurationException
55     *
56     * @author Neil Rotstan
57     * @author Klaus Meffert
58     * @since 1.0
59     */
60    public MutationOperator()
61        throws InvalidConfigurationException {
62      this(Genotype.getStaticConfiguration());
63    }
64  
65    /**
66     * @param a_conf the configuration to use
67     * @throws InvalidConfigurationException
68     *
69     * @author Klaus Meffert
70     * @since 3.0
71     */
72    public MutationOperator(final Configuration a_conf)
73        throws InvalidConfigurationException {
74      super(a_conf);
75      setMutationRateCalc(new DefaultMutationRateCalculator(a_conf));
76    }
77  
78    /**
79     * Constructs a new instance of this MutationOperator with a specified
80     * mutation rate calculator, which results in dynamic mutation being turned
81     * on.
82     * @param a_config the configuration to use
83     * @param a_mutationRateCalculator calculator for dynamic mutation rate
84     * computation
85     * @throws InvalidConfigurationException
86     *
87     * @author Klaus Meffert
88     * @since 1.1
89     */
90    public MutationOperator(final Configuration a_config,
91                            final IUniversalRateCalculator
92                            a_mutationRateCalculator)
93        throws InvalidConfigurationException {
94      super(a_config);
95      setMutationRateCalc(a_mutationRateCalculator);
96    }
97  
98    /**
99     * Constructs a new instance of this MutationOperator with the given
100    * mutation rate.
101    *
102    * @param a_config the configuration to use
103    * @param a_desiredMutationRate desired rate of mutation, expressed as
104    * the denominator of the 1 / X fraction. For example, 1000 would result
105    * in 1/1000 genes being mutated on average. A mutation rate of zero disables
106    * mutation entirely
107    * @throws InvalidConfigurationException
108    *
109    * @author Neil Rotstan
110    * @since 1.1
111    */
112   public MutationOperator(final Configuration a_config,
113                           final int a_desiredMutationRate)
114       throws InvalidConfigurationException {
115     super(a_config);
116     m_config.m_mutationRate = a_desiredMutationRate;
117     setMutationRateCalc(null);
118   }
119 
120   /**
121    * @param a_population the population of chromosomes from the current
122    * evolution prior to exposure to any genetic operators. Chromosomes in this
123    * array should not be modified. Please, notice, that the call in
124    * Genotype.evolve() to the implementations of GeneticOperator overgoes this
125    * due to performance issues
126    * @param a_candidateChromosomes the pool of chromosomes that have been
127    * mutated
128    *
129    * @author Neil Rotstan
130    * @author Klaus Meffert
131    * @since 1.0
132    */
133   public void operate(final Population a_population,
134                       final List a_candidateChromosomes) {
135     if (a_population == null || a_candidateChromosomes == null) {
136       // Population or candidate chromosomes list empty:
137       // nothing to do.
138       // -----------------------------------------------
139       return;
140     }
141     if (m_config.m_mutationRate == 0 && m_mutationRateCalc == null) {
142       // If the mutation rate is set to zero and dynamic mutation rate is
143       // disabled, then we don't perform any mutation.
144       // ----------------------------------------------------------------
145       return;
146     }
147     // Determine the mutation rate. If dynamic rate is enabled, then
148     // calculate it using the IUniversalRateCalculator instance.
149     // Otherwise, go with the mutation rate set upon construction.
150     // -------------------------------------------------------------
151     boolean mutate = false;
152     RandomGenerator generator = getConfiguration().getRandomGenerator();
153     // It would be inefficient to create copies of each Chromosome just
154     // to decide whether to mutate them. Instead, we only make a copy
155     // once we've positively decided to perform a mutation.
156     // ----------------------------------------------------------------
157     int size = Math.min(getConfiguration().getPopulationSize(),
158                         a_population.size());
159     IGeneticOperatorConstraint constraint = getConfiguration().
160         getJGAPFactory().getGeneticOperatorConstraint();
161     for (int i = 0; i < size; i++) {
162       IChromosome chrom = a_population.getChromosome(i);
163       Gene[] genes = chrom.getGenes();
164       IChromosome copyOfChromosome = null;
165       // For each Chromosome in the population...
166       // ----------------------------------------
167       for (int j = 0; j < genes.length; j++) {
168         if (m_mutationRateCalc != null) {
169           // If it's a dynamic mutation rate then let the calculator decide
170           // whether the current gene should be mutated.
171           // --------------------------------------------------------------
172           mutate = m_mutationRateCalc.toBePermutated(chrom, j);
173         }
174         else {
175           // Non-dynamic, so just mutate based on the the current rate.
176           // In fact we use a rate of 1/m_mutationRate.
177           // ----------------------------------------------------------
178           mutate = (generator.nextInt(m_config.m_mutationRate) == 0);
179         }
180         if (mutate) {
181           // Verify that crossover allowed.
182           // ------------------------------
183           /**@todo move to base class, refactor*/
184           if (constraint != null) {
185             List v = new Vector();
186             v.add(chrom);
187             if (!constraint.isValid(a_population, v, this)) {
188               continue;
189             }
190           }
191           // Now that we want to actually modify the Chromosome,
192           // let's make a copy of it (if we haven't already) and
193           // add it to the candidate chromosomes so that it will
194           // be considered for natural selection during the next
195           // phase of evolution. Then we'll set the gene's value
196           // to a random value as the implementation of our
197           // "mutation" of the gene.
198           // ---------------------------------------------------
199           if (copyOfChromosome == null) {
200             // ...take a copy of it...
201             // -----------------------
202             copyOfChromosome = (IChromosome) chrom.clone();
203             // ...add it to the candidate pool...
204             // ----------------------------------
205             a_candidateChromosomes.add(copyOfChromosome);
206             // ...then mutate all its genes...
207             // -------------------------------
208             genes = copyOfChromosome.getGenes();
209           }
210           // Process all atomic elements in the gene. For a StringGene this
211           // would be as many elements as the string is long , for an
212           // IntegerGene, it is always one element.
213           // --------------------------------------------------------------
214           if (genes[j] instanceof ICompositeGene) {
215             ICompositeGene compositeGene = (ICompositeGene) genes[j];
216             for (int k = 0; k < compositeGene.size(); k++) {
217               mutateGene(compositeGene.geneAt(k), generator);
218             }
219           }
220           else {
221             mutateGene(genes[j], generator);
222           }
223         }
224       }
225     }
226   }
227 
228   /**
229    * Helper: mutate all atomic elements of a gene
230    * @param a_gene the gene to be mutated
231    * @param a_generator the generator delivering amount of mutation
232    *
233    * @author Klaus Meffert
234    * @since 1.1
235    */
236   private void mutateGene(final Gene a_gene, final RandomGenerator a_generator) {
237     for (int k = 0; k < a_gene.size(); k++) {
238       // Retrieve value between 0 and 1 (not included) from generator.
239       // Then map this value to range -1 and 1 (-1 included, 1 not).
240       // -------------------------------------------------------------
241       double percentage = -1 + a_generator.nextDouble() * 2;
242       // Mutate atomic element by calculated percentage.
243       // -----------------------------------------------
244       a_gene.applyMutation(k, percentage);
245     }
246   }
247 
248   /**
249    * @return the MutationRateCalculator used
250    *
251    * @author Klaus Meffert
252    * @since 1.1
253    */
254   public IUniversalRateCalculator getMutationRateCalc() {
255     return m_mutationRateCalc;
256   }
257 
258   /**
259    * Sets the MutationRateCalculator to be used for determining the strength of
260    * mutation.
261    * @param a_mutationRateCalc MutationRateCalculator
262    *
263    * @author Klaus Meffert
264    * @since 1.1
265    */
266   public void setMutationRateCalc(final IUniversalRateCalculator
267                                   a_mutationRateCalc) {
268     m_mutationRateCalc = a_mutationRateCalc;
269     if (m_mutationRateCalc != null) {
270       m_config.m_mutationRate = 0;
271     }
272   }
273 
274   /**
275    * Compares this GeneticOperator against the specified object. The result is
276    * true if and the argument is an instance of this class and is equal wrt the
277    * data.
278    *
279    * @param a_other the object to compare against
280    * @return true: if the objects are the same, false otherwise
281    *
282    * @author Klaus Meffert
283    * @since 2.6
284    */
285   public boolean equals(final Object   a_other) {
286     try {
287       return compareTo(a_other) == 0;
288     } catch (ClassCastException   cex) {
289       return false;
290     }
291   }
292 
293   /**
294    * Compares the given GeneticOperator to this GeneticOperator.
295    *
296    * @param a_other the instance against which to compare this instance
297    * @return a negative number if this instance is "less than" the given
298    * instance, zero if they are equal to each other, and a positive number if
299    * this is "greater than" the given instance
300    *
301    * @author Klaus Meffert
302    * @since 2.6
303    */
304   public int compareTo(Object   a_other) {
305     if (a_other == null) {
306       return 1;
307     }
308     MutationOperator op = (MutationOperator) a_other;
309     if (m_mutationRateCalc == null) {
310       if (op.m_mutationRateCalc != null) {
311         return -1;
312       }
313     }
314     else {
315       if (op.m_mutationRateCalc == null) {
316         return 1;
317       }
318       else {
319       }
320     }
321     if (m_config.m_mutationRate != op.m_config.m_mutationRate) {
322       if (m_config.m_mutationRate > op.m_config.m_mutationRate) {
323         return 1;
324       }
325       else {
326         return -1;
327       }
328     }
329     // Everything is equal. Return zero.
330     // ---------------------------------
331     return 0;
332   }
333 
334   public int getMutationRate() {
335     return m_config.m_mutationRate;
336   }
337 
338   class MutationOperatorConfigurable
339       implements java.io.Serializable   {
340     /**
341      * The current mutation rate used by this MutationOperator, expressed as
342      * the denominator in the 1 / X ratio. For example, X = 1000 would
343      * mean that, on average, 1 / 1000 genes would be mutated. A value of zero
344      * disables mutation entirely.
345      */
346     public int m_mutationRate;
347   }
348 }
349
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags