AveragingCrossoverOperator


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 averaging 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. This operation is performed half
21   * as many times as there are Chromosomes in the population.
22   * Additionally, the loci of crossing over are cached for each index, i.e.,
23   * after randomizing the loci for each index once, they don't change again
24   *
25   * @author Klaus Meffert
26   * @since 2.0
27   */
28  public class AveragingCrossoverOperator
29      extends BaseGeneticOperator {
30    /** String containing the CVS revision. Read out via reflection!*/
31    private final static String   CVS_REVISION = "$Revision: 1.26 $";
32  
33    /**
34     * Random generator for randomizing the loci for crossing over
35     */
36    private RandomGenerator m_crossoverGenerator;
37  
38    /**
39     * The current crossover rate used by this crossover operator.
40     */
41    private int m_crossoverRate;
42  
43    /**
44     * Cache for alreadycrandomized loci for crossing over
45     */
46    private Map m_loci;
47  
48    /**
49     * Calculator for dynamically determining the crossover rate. If set to
50     * null the value of m_crossoverRate will be used instead.
51     */
52    private IUniversalRateCalculator m_crossoverRateCalc;
53  
54    private void init() {
55      m_loci = new Hashtable();
56      m_crossoverRate = 2;
57    }
58  
59    /**
60     * Using the same random generator for randomizing the loci for crossing
61     * over as for selecting the genes to be crossed over.<p>
62     * Attention: The configuration used is the one set with the static method
63     * Genotype.setConfiguration.
64     *
65     * @author Klaus Meffert
66     * @since 2.0
67     */
68    public AveragingCrossoverOperator()
69        throws InvalidConfigurationException {
70      this(Genotype.getStaticConfiguration(), (RandomGenerator)null);
71    }
72  
73    /**
74     * Using the same random generator for randomizing the loci for crossing
75     * over as for selecting the genes to be crossed over.
76     * @param a_configuration the configuration to use
77     *
78     * @author Klaus Meffert
79     * @since 3.0
80     */
81    public AveragingCrossoverOperator(final Configuration a_configuration)
82        throws InvalidConfigurationException {
83      this(a_configuration, (RandomGenerator)null);
84    }
85  
86    /**
87     * Using a different random generator for randomizing the loci for
88     * crossing over than for selecting the genes to be crossed over
89     * @param a_configuration the configuration to use
90     * @param a_generatorForAveraging RandomGenerator to use
91     *
92     * @author Klaus Meffert
93     * @since 3.0 (since 2.0 without a_configuration)
94     */
95    public AveragingCrossoverOperator(final Configuration a_configuration,
96                                      final RandomGenerator
97                                      a_generatorForAveraging)
98        throws InvalidConfigurationException {
99      super(a_configuration);
100     init();
101     m_crossoverGenerator = a_generatorForAveraging;
102   }
103 
104   /**
105    * Constructs a new instance of this CrossoverOperator with a specified
106    * crossover rate calculator, which results in dynamic crossover being turned
107    * on.
108    * @param a_configuration the configuration to use
109    * @param a_crossoverRateCalculator calculator for dynamic crossover rate
110    * computation
111    *
112    * @author Klaus Meffert
113    * @since 3.0 (since 2.0 without a_configuration)
114    */
115   public AveragingCrossoverOperator(final Configuration a_configuration,
116                                     final IUniversalRateCalculator
117                                     a_crossoverRateCalculator)
118       throws InvalidConfigurationException {
119     super(a_configuration);
120     init();
121     setCrossoverRateCalc(a_crossoverRateCalculator);
122   }
123 
124   /**
125    * Sets the crossover rate calculator
126    * @param a_crossoverRateCalculator the new calculator
127    *
128    * @author Klaus Meffert
129    * @since 2.0
130    */
131   private void setCrossoverRateCalc(final IUniversalRateCalculator
132                                     a_crossoverRateCalculator) {
133     m_crossoverRateCalc = a_crossoverRateCalculator;
134   }
135 
136   /**
137    * Crossover that acts as a perturbed mean of two individuals.
138    * x_i = p*x1_i + (1-p)*x2_i
139    * p - uniform random value over [0,1].
140    * Averaging over line means p is same for every i,
141    * averaging over space if different p is chosen for each i.
142    * See CrossoverOperator for general description, also see feature request
143    * 708774
144    *
145    * @param a_population Chromosome[]
146    * @param a_candidateChromosomes List
147    *
148    * @author Klaus Meffert
149    * @since 2.0
150    */
151   public void operate(final Population a_population,
152                       final List a_candidateChromosomes) {
153     // Determine the number of crossovers that should be performed
154     int size = Math.min(getConfiguration().getPopulationSize(),
155                         a_population.size());
156     int numCrossovers = 0;
157     if (m_crossoverRateCalc == null) {
158       numCrossovers = size / m_crossoverRate;
159     }
160     else {
161       numCrossovers = size / m_crossoverRateCalc.calculateCurrentRate();
162     }
163     RandomGenerator generator = getConfiguration().getRandomGenerator();
164     if (m_crossoverGenerator == null) {
165       m_crossoverGenerator = generator;
166     }
167     // For each crossover, grab two random chromosomes, pick a random
168     // locus (gene location), and then swap that gene and all genes
169     // to the "right" (those with greater loci) of that gene between
170     // the two chromosomes.
171     // --------------------------------------------------------------
172     int index1, index2;
173     for (int i = 0; i < numCrossovers; i++) {
174       index1 = generator.nextInt(size);
175       index2 = generator.nextInt(size);
176       IChromosome firstMate = a_population.getChromosome(index1);
177       IChromosome secondMate = a_population.getChromosome(index2);
178       Gene[] firstGenes = firstMate.getGenes();
179       Gene[] secondGenes = secondMate.getGenes();
180       int locus = getLocus(m_crossoverGenerator, i, firstGenes.length);
181       // Swap the genes.
182       // ---------------
183       Gene gene1;
184       Gene gene2;
185       Object   firstAllele;
186       for (int j = locus; j < firstGenes.length; j++) {
187         // Make a distinction to ICompositeGene for the first gene
188         if (firstGenes[j] instanceof ICompositeGene) {
189           // Randomly determine gene to be considered
190           index1 = generator.nextInt(firstGenes[j].size());
191           gene1 = ( (ICompositeGene) firstGenes[j]).geneAt(index1);
192         }
193         else {
194           gene1 = firstGenes[j];
195         }
196         // Make a distinction to ICompositeGene fot the second gene
197         if (secondGenes[j] instanceof CompositeGene) {
198           // Randomly determine gene to be considered
199           index2 = generator.nextInt(secondGenes[j].size());
200           gene2 = ( (ICompositeGene) secondGenes[j]).geneAt(index2);
201         }
202         else {
203           gene2 = secondGenes[j];
204         }
205         firstAllele = gene1.getAllele();
206         gene1.setAllele(gene2.getAllele());
207         gene2.setAllele(firstAllele);
208       }
209       // Add the modified chromosomes to the candidate pool so that
210       // they'll be considered for natural selection during the next
211       // phase of evolution.
212       // -----------------------------------------------------------
213       a_candidateChromosomes.add(firstMate);
214       a_candidateChromosomes.add(secondMate);
215     }
216   }
217 
218   /**
219    * Returns the crossover location for a given index.
220    * For each index the crossover locatio  is the same, therefor it is cached!
221    *
222    * @param a_generator to generate random values the first time
223    * @param a_index the index of the crossover operation
224    * @param a_max upper boundary for random generator
225    *
226    * @return crossover location for a given index
227    *
228    * @author Klaus Meffert
229    * @since 2.0
230    */
231   protected int getLocus(final RandomGenerator a_generator, final int a_index,
232                          final int a_max) {
233     Integer   locus = (Integer  ) m_loci.get(new Integer  (a_index));
234     if (locus == null) {
235       locus = new Integer  (a_generator.nextInt(a_max));
236       m_loci.put(new Integer  (a_index), locus);
237     }
238     return locus.intValue();
239   }
240 
241   /**
242    * Compares this GeneticOperator against the specified object. The result is
243    * true if and the argument is an instance of this class and is equal wrt the
244    * data.
245    *
246    * @param a_other the object to compare against
247    * @return true: if the objects are the same, false otherwise
248    *
249    * @author Klaus Meffert
250    * @since 2.6
251    */
252   public boolean equals(final Object   a_other) {
253     try {
254       return compareTo(a_other) == 0;
255     }
256     catch (ClassCastException   cex) {
257       return false;
258     }
259   }
260 
261   /**
262    * Compares the given GeneticOperator to this GeneticOperator.
263    *
264    * @param a_other the instance against which to compare this instance
265    * @return a negative number if this instance is "less than" the given
266    * instance, zero if they are equal to each other, and a positive number if
267    * this is "greater than" the given instance
268    *
269    * @author Klaus Meffert
270    * @since 2.6
271    */
272   public int compareTo(final Object   a_other) {
273     if (a_other == null) {
274       return 1;
275     }
276     AveragingCrossoverOperator op = (AveragingCrossoverOperator) a_other;
277     if (m_crossoverRateCalc == null) {
278       if (op.m_crossoverRateCalc != null) {
279         return -1;
280       }
281     }
282     else {
283       if (op.m_crossoverRateCalc == null) {
284         return 1;
285       }
286     }
287     if (m_crossoverRate != op.m_crossoverRate) {
288       if (m_crossoverRate > op.m_crossoverRate) {
289         return 1;
290       }
291       else {
292         return -1;
293       }
294     }
295     // Everything is equal. Return zero.
296     // ---------------------------------
297     return 0;
298   }
299 
300   /**
301    * @param a_rate crossover rate to use by this crossover operator
302    * @author Klaus Meffert
303    * @since 2.6
304    */
305   public void setCrossoverRate(int a_rate) {
306     m_crossoverRate = a_rate;
307   }
308 }
309
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags