001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licensing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package org.jgap.impl;
011:
012: import java.util.*;
013:
014: import org.jgap.*;
015: import org.jgap.data.config.*;
016:
017: /**
018: * The mutation operator runs through the genes in each of the Chromosomes
019: * in the population and mutates them in statistical accordance to the
020: * given mutation rate. Mutated Chromosomes are then added to the list of
021: * candidate Chromosomes destined for the natural selection process.
022: *
023: * This MutationOperator supports both fixed and dynamic mutation rates.
024: * A fixed rate is one specified at construction time by the user. A dynamic
025: * rate is determined by this class if no fixed rate is provided, and is
026: * calculated based on the size of the Chromosomes in the population. Details
027: * are specified in the DefaultMutationRateCalculator class.
028: *
029: * @author Neil Rotstan
030: * @author Klaus Meffert
031: * @since 1.0
032: */
033: public class MutationOperator extends BaseGeneticOperator implements
034: Configurable {
035: /** String containing the CVS revision. Read out via reflection!*/
036: private final static String CVS_REVISION = "$Revision: 1.44 $";
037:
038: /**
039: * Calculator for dynamically determining the mutation rate. If set to
040: * null the value of m_mutationRate will be used. Replaces the previously used
041: * boolean m_dynamicMutationRate.
042: */
043: private IUniversalRateCalculator m_mutationRateCalc;
044:
045: private MutationOperatorConfigurable m_config = new MutationOperatorConfigurable();
046:
047: /**
048: * Constructs a new instance of this MutationOperator without a specified
049: * mutation rate, which results in dynamic mutation being turned on. This
050: * means that the mutation rate will be automatically determined by this
051: * operator based upon the number of genes present in the chromosomes.
052: * <p>
053: * Attention: The configuration used is the one set with the static method
054: * Genotype.setConfiguration.
055: *
056: * @throws InvalidConfigurationException
057: *
058: * @author Neil Rotstan
059: * @author Klaus Meffert
060: * @since 1.0
061: */
062: public MutationOperator() throws InvalidConfigurationException {
063: this (Genotype.getStaticConfiguration());
064: }
065:
066: /**
067: * @param a_conf the configuration to use
068: * @throws InvalidConfigurationException
069: *
070: * @author Klaus Meffert
071: * @since 3.0
072: */
073: public MutationOperator(final Configuration a_conf)
074: throws InvalidConfigurationException {
075: super (a_conf);
076: setMutationRateCalc(new DefaultMutationRateCalculator(a_conf));
077: }
078:
079: /**
080: * Constructs a new instance of this MutationOperator with a specified
081: * mutation rate calculator, which results in dynamic mutation being turned
082: * on.
083: * @param a_config the configuration to use
084: * @param a_mutationRateCalculator calculator for dynamic mutation rate
085: * computation
086: * @throws InvalidConfigurationException
087: *
088: * @author Klaus Meffert
089: * @since 1.1
090: */
091: public MutationOperator(final Configuration a_config,
092: final IUniversalRateCalculator a_mutationRateCalculator)
093: throws InvalidConfigurationException {
094: super (a_config);
095: setMutationRateCalc(a_mutationRateCalculator);
096: }
097:
098: /**
099: * 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()
153: .getRandomGenerator();
154: // It would be inefficient to create copies of each Chromosome just
155: // to decide whether to mutate them. Instead, we only make a copy
156: // once we've positively decided to perform a mutation.
157: // ----------------------------------------------------------------
158: int size = Math.min(getConfiguration().getPopulationSize(),
159: a_population.size());
160: IGeneticOperatorConstraint constraint = getConfiguration()
161: .getJGAPFactory().getGeneticOperatorConstraint();
162: for (int i = 0; i < size; i++) {
163: IChromosome chrom = a_population.getChromosome(i);
164: Gene[] genes = chrom.getGenes();
165: IChromosome copyOfChromosome = null;
166: // For each Chromosome in the population...
167: // ----------------------------------------
168: for (int j = 0; j < genes.length; j++) {
169: if (m_mutationRateCalc != null) {
170: // If it's a dynamic mutation rate then let the calculator decide
171: // whether the current gene should be mutated.
172: // --------------------------------------------------------------
173: mutate = m_mutationRateCalc
174: .toBePermutated(chrom, j);
175: } else {
176: // Non-dynamic, so just mutate based on the the current rate.
177: // In fact we use a rate of 1/m_mutationRate.
178: // ----------------------------------------------------------
179: mutate = (generator
180: .nextInt(m_config.m_mutationRate) == 0);
181: }
182: if (mutate) {
183: // Verify that crossover allowed.
184: // ------------------------------
185: /**@todo move to base class, refactor*/
186: if (constraint != null) {
187: List v = new Vector();
188: v.add(chrom);
189: if (!constraint.isValid(a_population, v, this )) {
190: continue;
191: }
192: }
193: // Now that we want to actually modify the Chromosome,
194: // let's make a copy of it (if we haven't already) and
195: // add it to the candidate chromosomes so that it will
196: // be considered for natural selection during the next
197: // phase of evolution. Then we'll set the gene's value
198: // to a random value as the implementation of our
199: // "mutation" of the gene.
200: // ---------------------------------------------------
201: if (copyOfChromosome == null) {
202: // ...take a copy of it...
203: // -----------------------
204: copyOfChromosome = (IChromosome) chrom.clone();
205: // ...add it to the candidate pool...
206: // ----------------------------------
207: a_candidateChromosomes.add(copyOfChromosome);
208: // ...then mutate all its genes...
209: // -------------------------------
210: genes = copyOfChromosome.getGenes();
211: }
212: // Process all atomic elements in the gene. For a StringGene this
213: // would be as many elements as the string is long , for an
214: // IntegerGene, it is always one element.
215: // --------------------------------------------------------------
216: if (genes[j] instanceof ICompositeGene) {
217: ICompositeGene compositeGene = (ICompositeGene) genes[j];
218: for (int k = 0; k < compositeGene.size(); k++) {
219: mutateGene(compositeGene.geneAt(k),
220: generator);
221: }
222: } else {
223: mutateGene(genes[j], generator);
224: }
225: }
226: }
227: }
228: }
229:
230: /**
231: * Helper: mutate all atomic elements of a gene.
232: *
233: * @param a_gene the gene to be mutated
234: * @param a_generator the generator delivering amount of mutation
235: *
236: * @author Klaus Meffert
237: * @since 1.1
238: */
239: private void mutateGene(final Gene a_gene,
240: final RandomGenerator a_generator) {
241: for (int k = 0; k < a_gene.size(); k++) {
242: // Retrieve value between 0 and 1 (not included) from generator.
243: // Then map this value to range -1 and 1 (-1 included, 1 not).
244: // -------------------------------------------------------------
245: double percentage = -1 + a_generator.nextDouble() * 2;
246: // Mutate atomic element by calculated percentage.
247: // -----------------------------------------------
248: a_gene.applyMutation(k, percentage);
249: }
250: }
251:
252: /**
253: * @return the MutationRateCalculator used
254: *
255: * @author Klaus Meffert
256: * @since 1.1
257: */
258: public IUniversalRateCalculator getMutationRateCalc() {
259: return m_mutationRateCalc;
260: }
261:
262: /**
263: * Sets the MutationRateCalculator to be used for determining the strength of
264: * mutation.
265: *
266: * @param a_mutationRateCalc MutationRateCalculator
267: *
268: * @author Klaus Meffert
269: * @since 1.1
270: */
271: public void setMutationRateCalc(
272: final IUniversalRateCalculator a_mutationRateCalc) {
273: m_mutationRateCalc = a_mutationRateCalc;
274: if (m_mutationRateCalc != null) {
275: m_config.m_mutationRate = 0;
276: }
277: }
278:
279: /**
280: *
281: * @param a_mutationRate new rate of mutation, expressed as
282: * the denominator of the 1 / X fraction. For example, 1000 would result
283: * in 1/1000 genes being mutated on average. A mutation rate of zero disables
284: * mutation entirely
285: *
286: * @author Klaus Meffert
287: * @since 3.2.2
288: */
289: public void setMutationRate(int a_mutationRate) {
290: m_config.m_mutationRate = a_mutationRate;
291: setMutationRateCalc(null);
292: }
293:
294: /**
295: * Compares this GeneticOperator against the specified object. The result is
296: * true if and the argument is an instance of this class and is equal wrt the
297: * data.
298: *
299: * @param a_other the object to compare against
300: * @return true: if the objects are the same, false otherwise
301: *
302: * @author Klaus Meffert
303: * @since 2.6
304: */
305: public boolean equals(final Object a_other) {
306: try {
307: return compareTo(a_other) == 0;
308: } catch (ClassCastException cex) {
309: return false;
310: }
311: }
312:
313: /**
314: * Compares the given GeneticOperator to this GeneticOperator.
315: *
316: * @param a_other the instance against which to compare this instance
317: * @return a negative number if this instance is "less than" the given
318: * instance, zero if they are equal to each other, and a positive number if
319: * this is "greater than" the given instance
320: *
321: * @author Klaus Meffert
322: * @since 2.6
323: */
324: public int compareTo(Object a_other) {
325: if (a_other == null) {
326: return 1;
327: }
328: MutationOperator op = (MutationOperator) a_other;
329: if (m_mutationRateCalc == null) {
330: if (op.m_mutationRateCalc != null) {
331: return -1;
332: }
333: } else {
334: if (op.m_mutationRateCalc == null) {
335: return 1;
336: } else {
337: }
338: }
339: if (m_config.m_mutationRate != op.m_config.m_mutationRate) {
340: if (m_config.m_mutationRate > op.m_config.m_mutationRate) {
341: return 1;
342: } else {
343: return -1;
344: }
345: }
346: // Everything is equal. Return zero.
347: // ---------------------------------
348: return 0;
349: }
350:
351: public int getMutationRate() {
352: return m_config.m_mutationRate;
353: }
354:
355: class MutationOperatorConfigurable implements java.io.Serializable {
356: /**
357: * The current mutation rate used by this MutationOperator, expressed as
358: * the denominator in the 1 / X ratio. For example, X = 1000 would
359: * mean that, on average, 1 / 1000 genes would be mutated. A value of zero
360: * disables mutation entirely.
361: */
362: public int m_mutationRate;
363: }
364: }
|