KickJava   Java API By Example, From Geeks To Geeks.

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


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  * The crossover operator randomly selects two Chromosomes from the
17  * population and "mates" them by randomly picking a gene and then
18  * swapping that gene and all subsequent genes between the two
19  * Chromosomes. The two modified Chromosomes are then added to the
20  * list of candidate Chromosomes.
21  *
22  * This CrossoverOperator supports both fixed and dynamic crossover rates.
23  * A fixed rate is one specified at construction time by the user. This
24  * operation is performed 1/m_crossoverRate as many times as there are
25  * Chromosomes in the population. A dynamic rate is one determined by
26  * this class if no fixed rate is provided.
27  *
28  * @author Neil Rotstan
29  * @author Klaus Meffert
30  * @author Chris Knowles
31  * @since 1.0
32  */

33 public class CrossoverOperator
34     extends BaseGeneticOperator implements Comparable JavaDoc {
35   /** String containing the CVS revision. Read out via reflection!*/
36   private final static String JavaDoc CVS_REVISION = "$Revision: 1.32 $";
37
38   /**
39    * The current crossover rate used by this crossover operator.
40    */

41   private int m_crossoverRate;
42
43   /**
44    * Calculator for dynamically determining the crossover rate. If set to
45    * null the value of m_crossoverRate will be used instead.
46    */

47   private IUniversalRateCalculator m_crossoverRateCalc;
48
49   /**
50    * Constructs a new instance of this CrossoverOperator without a specified
51    * crossover rate, this results in dynamic crossover rate being turned off.
52    * This means that the crossover rate will be fixed at populationsize/2.<p>
53    * Attention: The configuration used is the one set with the static method
54    * Genotype.setConfiguration.
55    * @throws InvalidConfigurationException
56    *
57    * @author Chris Knowles
58    * @since 2.0
59    */

60   public CrossoverOperator()
61       throws InvalidConfigurationException {
62     super(Genotype.getStaticConfiguration());
63     //set the default crossoverRate to be populationsize/2
64
m_crossoverRate = 2;
65     setCrossoverRateCalc(null);
66   }
67
68   /**
69    * Constructs a new instance of this CrossoverOperator without a specified
70    * crossover rate, this results in dynamic crossover rate being turned off.
71    * This means that the crossover rate will be fixed at populationsize/2.
72    *
73    * @param a_configuration the configuration to use
74    * @throws InvalidConfigurationException
75    *
76    * @author Klaus Meffert
77    * @since 3.0
78    */

79   public CrossoverOperator(final Configuration a_configuration)
80       throws InvalidConfigurationException {
81     super(a_configuration);
82     // Set the default crossoverRate to be populationsize/2.
83
// -----------------------------------------------------
84
m_crossoverRate = 2;
85     setCrossoverRateCalc(null);
86   }
87
88   /**
89    * Constructs a new instance of this CrossoverOperator with a specified
90    * crossover rate calculator, which results in dynamic crossover being turned
91    * on.
92    *
93    * @param a_configuration the configuration to use
94    * @param a_crossoverRateCalculator calculator for dynamic crossover rate
95    * computation
96    * @throws InvalidConfigurationException
97    *
98    * @author Chris Knowles
99    * @author Klaus Meffert
100    * @since 3.0 (since 2.0 without a_configuration)
101    */

102   public CrossoverOperator(final Configuration a_configuration,
103                            final IUniversalRateCalculator
104                            a_crossoverRateCalculator)
105       throws InvalidConfigurationException {
106     super(a_configuration);
107     setCrossoverRateCalc(a_crossoverRateCalculator);
108   }
109
110   /**
111    * Constructs a new instance of this CrossoverOperator with the given
112    * crossover rate.
113    *
114    * @param a_configuration the configuration to use
115    * @param a_desiredCrossoverRate the desired rate of crossover
116    * @throws InvalidConfigurationException
117    *
118    * @author Chris Knowles
119    * @author Klaus Meffert
120    * @since 3.0 (since 2.0 without a_configuration)
121    */

122   public CrossoverOperator(final Configuration a_configuration,
123                            final int a_desiredCrossoverRate)
124       throws InvalidConfigurationException {
125     super(a_configuration);
126     if (a_desiredCrossoverRate < 1) {
127       throw new IllegalArgumentException JavaDoc("Crossover rate must be greater zero");
128     }
129     m_crossoverRate = a_desiredCrossoverRate;
130     setCrossoverRateCalc(null);
131   }
132
133   /**
134    * @author Neil Rotstan
135    * @author Klaus Meffert
136    * @since 2.0 (earlier versions referenced the Configuration object)
137    */

138   public void operate(final Population a_population,
139                       final List a_candidateChromosomes) {
140     // Work out the number of crossovers that should be performed.
141
// -----------------------------------------------------------
142
int size = Math.min(getConfiguration().getPopulationSize(),
143                         a_population.size());
144     int numCrossovers = 0;
145     if (m_crossoverRateCalc == null) {
146       numCrossovers = size / m_crossoverRate;
147     }
148     else {
149       numCrossovers = size / m_crossoverRateCalc.calculateCurrentRate();
150     }
151     RandomGenerator generator = getConfiguration().getRandomGenerator();
152     IGeneticOperatorConstraint constraint = getConfiguration().
153         getJGAPFactory().getGeneticOperatorConstraint();
154     // For each crossover, grab two random chromosomes, pick a random
155
// locus (gene location), and then swap that gene and all genes
156
// to the "right" (those with greater loci) of that gene between
157
// the two chromosomes.
158
// --------------------------------------------------------------
159
int index1, index2;
160     for (int i = 0; i < numCrossovers; i++) {
161       index1 = generator.nextInt(size);
162       index2 = generator.nextInt(size);
163       IChromosome chrom1 = a_population.getChromosome(index1);
164       IChromosome chrom2 = a_population.getChromosome(index2);
165       // Verify that crossover allowed.
166
// ------------------------------
167
if (constraint != null) {
168         List v = new Vector();
169         v.add(chrom1);
170         v.add(chrom2);
171         if (!constraint.isValid(a_population, v, this)) {
172           continue;
173         }
174       }
175       // Clone the chromosomes.
176
// ----------------------
177
IChromosome firstMate = (IChromosome) chrom1.clone();
178       IChromosome secondMate = (IChromosome) chrom2.clone();
179       doCrossover(firstMate, secondMate, a_candidateChromosomes, generator);
180     }
181   }
182
183   private void doCrossover(IChromosome firstMate, IChromosome secondMate,
184                            List a_candidateChromosomes,
185                            RandomGenerator generator) {
186     Gene[] firstGenes = firstMate.getGenes();
187     Gene[] secondGenes = secondMate.getGenes();
188     int locus = generator.nextInt(firstGenes.length);
189     // Swap the genes.
190
// ---------------
191
Gene gene1;
192     Gene gene2;
193     Object JavaDoc firstAllele;
194     for (int j = locus; j < firstGenes.length; j++) {
195       // Make a distinction for ICompositeGene for the first gene.
196
// ---------------------------------------------------------
197
if (firstGenes[j] instanceof ICompositeGene) {
198         // Randomly determine gene to be considered.
199
// -----------------------------------------
200
int index1 = generator.nextInt(firstGenes[j].size());
201         gene1 = ( (ICompositeGene) firstGenes[j]).geneAt(index1);
202       }
203       else {
204         gene1 = firstGenes[j];
205       }
206       // Make a distinction for CompositeGene for the second gene.
207
// ---------------------------------------------------------
208
if (secondGenes[j] instanceof ICompositeGene) {
209         // Randomly determine gene to be considered.
210
// -----------------------------------------
211
int index2 = generator.nextInt(secondGenes[j].size());
212         gene2 = ( (ICompositeGene) secondGenes[j]).geneAt(index2);
213       }
214       else {
215         gene2 = secondGenes[j];
216       }
217       firstAllele = gene1.getAllele();
218       gene1.setAllele(gene2.getAllele());
219       gene2.setAllele(firstAllele);
220     }
221     // Add the modified chromosomes to the candidate pool so that
222
// they'll be considered for natural selection during the next
223
// phase of evolution.
224
// -----------------------------------------------------------
225
a_candidateChromosomes.add(firstMate);
226     a_candidateChromosomes.add(secondMate);
227   }
228
229   /**
230    * Sets the crossover rate calculator.
231    *
232    * @param a_crossoverRateCalculator the new calculator
233    *
234    * @author Chris Knowles
235    * @since 2.0
236    */

237   private void setCrossoverRateCalc(final IUniversalRateCalculator
238                                     a_crossoverRateCalculator) {
239     m_crossoverRateCalc = a_crossoverRateCalculator;
240   }
241
242   /**
243    * Compares the given GeneticOperator to this GeneticOperator.
244    *
245    * @param a_other the instance against which to compare this instance
246    * @return a negative number if this instance is "less than" the given
247    * instance, zero if they are equal to each other, and a positive number if
248    * this is "greater than" the given instance
249    *
250    * @author Klaus Meffert
251    * @since 2.6
252    */

253   public int compareTo(final Object JavaDoc a_other) {
254     /**@todo consider Configuration*/
255     if (a_other == null) {
256       return 1;
257     }
258     CrossoverOperator op = (CrossoverOperator) a_other;
259     if (m_crossoverRateCalc == null) {
260       if (op.m_crossoverRateCalc != null) {
261         return -1;
262       }
263     }
264     else {
265       if (op.m_crossoverRateCalc == null) {
266         return 1;
267       }
268     }
269     if (m_crossoverRate != op.m_crossoverRate) {
270       if (m_crossoverRate > op.m_crossoverRate) {
271         return 1;
272       }
273       else {
274         return -1;
275       }
276     }
277     // Everything is equal. Return zero.
278
// ---------------------------------
279
return 0;
280   }
281 }
282
Popular Tags