KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgap > impl > SwappingMutationOperator


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
15 /**
16  * Swaps the genes instead of mutating them. This kind of operator is
17  * required by Traveling Salesman Problem.
18  *
19  * See J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht.
20  * <i>Genetic algorithms for the traveling salesman problem</i>.
21  * In Proceedings of the Second International Conference on Genetic Algorithms.
22  * Lawrence Eribaum Associates, Mahwah, NJ, 1985.
23  * and also <a HREF="http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html">
24  * Sushil J. Louis & Gong Li</a> }
25  *
26  * @author Audrius Meskauskas
27  * @author <font size=-1>Neil Rotstan, Klaus Meffert (reused code
28  * from {@link org.jgap.impl.MutationOperator MutationOperator})</font>
29  * @since 2.0
30  */

31 public class SwappingMutationOperator
32     extends MutationOperator {
33   /** String containing the CVS revision. Read out via reflection!*/
34   private final static String JavaDoc CVS_REVISION = "$Revision: 1.18 $";
35
36   private int m_startOffset = 1;
37
38   /**
39    * Constructs a new instance of this operator.<p>
40    * Attention: The configuration used is the one set with the static method
41    * Genotype.setConfiguration.
42    * @throws InvalidConfigurationException
43    *
44    * @author Klaus Meffert
45    */

46   public SwappingMutationOperator()
47       throws InvalidConfigurationException {
48     super();
49   }
50
51   /**
52    * @param a_config the configuration to use
53    * @throws InvalidConfigurationException
54    *
55    * @author Klaus Meffert
56    * @since 3.0
57    */

58   public SwappingMutationOperator(final Configuration a_config)
59       throws InvalidConfigurationException {
60     super(a_config);
61   }
62
63   /**
64    * Constructs a new instance of this operator with a specified
65    * mutation rate calculator, which results in dynamic mutation being turned
66    * on.
67    * @param a_config the configuration to use
68    * @param a_mutationRateCalculator calculator for dynamic mutation rate
69    * computation
70    * @throws InvalidConfigurationException
71    *
72    * @author Klaus Meffert
73    * @since 3.0 (previously: without a_config)
74    */

75   public SwappingMutationOperator(final Configuration a_config,
76                                   final IUniversalRateCalculator
77                                   a_mutationRateCalculator)
78       throws InvalidConfigurationException {
79     super(a_config, a_mutationRateCalculator);
80   }
81
82   /**
83    * Constructs a new instance of this MutationOperator with the given
84    * mutation rate.
85    *
86    * @param a_config the configuration to use
87    * @param a_desiredMutationRate desired rate of mutation, expressed as
88    * the denominator of the 1 / X fraction. For example, 1000 would result
89    * in 1/1000 genes being mutated on average. A mutation rate of zero disables
90    * mutation entirely
91    * @throws InvalidConfigurationException
92    *
93    * @author Klaus Meffert
94    * @since 3.0 (previously: without a_config)
95    */

96   public SwappingMutationOperator(final Configuration a_config,
97                                   final int a_desiredMutationRate)
98       throws InvalidConfigurationException {
99     super(a_config, a_desiredMutationRate);
100   }
101
102   /**
103    * @param a_population the population of chromosomes from the current
104    * evolution prior to exposure to any genetic operators. Chromosomes in this
105    * array should not be modified. Please, notice, that the call in
106    * Genotype.evolve() to the implementations of GeneticOperator overgoes this
107    * due to performance issues
108    * @param a_candidateChromosomes the pool of chromosomes that have been
109    * selected for the next evolved population
110    *
111    * @author Audrius Meskauskas
112    * @author Klaus Meffert
113    * @since 2.0
114    */

115   public void operate(final Population a_population,
116                       List a_candidateChromosomes) {
117     // this was a private variable, now it is local reference.
118
final IUniversalRateCalculator m_mutationRateCalc = getMutationRateCalc();
119     // If the mutation rate is set to zero and dynamic mutation rate is
120
// disabled, then we don't perform any mutation.
121
// ----------------------------------------------------------------
122
if (getMutationRate() == 0 && m_mutationRateCalc == null) {
123       return;
124     }
125     // Determine the mutation rate. If dynamic rate is enabled, then
126
// calculate it based upon the number of genes in the chromosome.
127
// Otherwise, go with the mutation rate set upon construction.
128
// --------------------------------------------------------------
129
int currentRate;
130     if (m_mutationRateCalc != null) {
131       currentRate = m_mutationRateCalc.calculateCurrentRate();
132     }
133     else {
134       currentRate = getMutationRate();
135     }
136     RandomGenerator generator = getConfiguration().getRandomGenerator();
137     // It would be inefficient to create copies of each Chromosome just
138
// to decide whether to mutate them. Instead, we only make a copy
139
// once we've positively decided to perform a mutation.
140
// ----------------------------------------------------------------
141
int size = a_population.size();
142     for (int i = 0; i < size; i++) {
143       IChromosome x = a_population.getChromosome(i);
144       // This returns null if not mutated:
145
IChromosome xm = operate(x, currentRate, generator);
146       if (xm != null) {
147         a_candidateChromosomes.add(xm);
148       }
149     }
150   }
151
152   /**
153    * Operate on the given chromosome with the given mutation rate.
154    * @param a_x chromosome to operate
155    * @param a_rate mutation rate
156    * @param a_generator random generator to use (must not be null)
157    * @return mutated chromosome of null if no mutation has occured.
158    *
159    * @author Audrius Meskauskas
160    * @since 2.0
161    */

162   protected IChromosome operate(final IChromosome a_x, final int a_rate,
163                                 final RandomGenerator a_generator) {
164     IChromosome chromosome = null;
165     // ----------------------------------------
166
for (int j = m_startOffset; j < a_x.size(); j++) {
167       // Ensure probability of 1/currentRate for applying mutation.
168
// ----------------------------------------------------------
169
if (a_generator.nextInt(a_rate) == 0) {
170         if (chromosome == null) {
171           chromosome = (IChromosome) a_x.clone();
172         }
173         Gene[] genes = chromosome.getGenes();
174         Gene[] mutated = operate(a_generator, j, genes);
175         // setGenes is not required for this operator, but it may
176
// be needed for the derived operators.
177
// ------------------------------------------------------
178
try {
179           chromosome.setGenes(mutated);
180         }
181         catch (InvalidConfigurationException cex) {
182           throw new Error JavaDoc("Gene type not allowed by constraint checker", cex);
183         }
184       }
185     }
186     return chromosome;
187   }
188
189   /**
190    * Operate on the given array of genes. This method is only called
191    * when it is already clear that the mutation must occur under the given
192    * mutation rate
193    * @param a_generator a random number generator that may be needed to
194    * perform a mutation
195    * @param a_target_gene an index of gene in the chromosome that will mutate
196    * @param a_genes the array of all genes in the chromosome
197    * @return the mutated gene array
198    *
199    * @author Audrius Meskauskas
200    * @since 2.0
201    */

202   protected Gene[] operate(final RandomGenerator a_generator,
203                            final int a_target_gene, final Gene[] a_genes) {
204     // swap this gene with the other one now:
205
// mutateGene(genes[j], generator);
206
// -------------------------------------
207
int other = m_startOffset
208         + a_generator.nextInt(a_genes.length - m_startOffset);
209     Gene t = a_genes[a_target_gene];
210     a_genes[a_target_gene] = a_genes[other];
211     a_genes[other] = t;
212     return a_genes;
213   }
214
215   /**
216    * Sets a number of genes at the start of chromosome, that are
217    * excluded from the swapping. In the Salesman task, the first city
218    * in the list should (where the salesman leaves from) probably should
219    * not change as it is part of the list. The default value is 1.
220    *
221    * @param a_offset the offset to set
222    *
223    * @author Audrius Meskauskas
224    * @since 2.0
225    */

226   public void setStartOffset(final int a_offset) {
227     m_startOffset = a_offset;
228   }
229
230   /**
231    * Gets a number of genes at the start of chromosome, that are
232    * excluded from the swapping. In the Salesman task, the first city
233    * in the list should (where the salesman leaves from) probably should
234    * not change as it is part of the list. The default value is 1.
235    *
236    * @return the start offset
237    *
238    * @author Audrius Meskauskas
239    * @since 2.0
240    */

241   public int getStartOffset() {
242     return m_startOffset;
243   }
244 }
245
Popular Tags