WeightedRouletteSelector


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.math.*;
13  import java.util.*;
14  import org.jgap.*;
15  import org.jgap.util.*;
16  
17  /**
18   * A basic implementation of NaturalSelector that models a roulette wheel.
19   * When a Chromosome is added, it gets a number of "slots" on the wheel equal
20   * to its fitness value. When the select method is invoked, the wheel is
21   * "spun" and the Chromosome occupying the spot on which it lands is selected.
22   * Then the wheel is spun again and again until the requested number of
23   * Chromosomes have been selected. Since Chromosomes with higher fitness
24   * values get more slots on the wheel, there's a higher statistical probability
25   * that they'll be chosen, but it's not guaranteed.
26   *
27   * @author Neil Rotstan
28   * @author Klaus Meffert
29   * @since 1.0
30   */
31  public class WeightedRouletteSelector
32      extends NaturalSelector implements ICloneable {
33    /** String containing the CVS revision. Read out via reflection!*/
34    private final static String   CVS_REVISION = "$Revision: 1.35 $";
35  
36    //delta for distinguishing whether a value is to be interpreted as zero
37    private static final double DELTA = 0.000001d;
38  
39    private static final BigDecimal ZERO_BIG_DECIMAL = new BigDecimal(0.0d);
40  
41    /**
42     * Represents the "roulette wheel." Each key in the Map is a Chromosome
43     * and each value is an instance of the SlotCounter inner class, which
44     * keeps track of how many slots on the wheel each Chromosome is occupying.
45     */
46    private HashMap m_wheel = new HashMap();
47  
48    /**
49     * Keeps track of the total number of slots that are in use on the
50     * roulette wheel. This is equal to the combined fitness values of
51     * all Chromosome instances that have been added to this wheel.
52     */
53    private double m_totalNumberOfUsedSlots;
54  
55    /**
56     * An internal pool in which discarded SlotCounter instances can be stored
57     * so that they can be reused over and over again, thus saving memory
58     * and the overhead of constructing new ones each time.
59     */
60    private Pool m_counterPool = new Pool();
61  
62    private WeightedRouletteSelConfig m_config
63        = new WeightedRouletteSelConfig();
64  
65    /**
66     * Default constructor.<p>
67     * Attention: The configuration used is the one set with the static method
68     * Genotype.setConfiguration.
69     *
70     * @author Klaus Meffert
71     * @since 2.0
72     */
73    public WeightedRouletteSelector() {
74      this(Genotype.getStaticConfiguration());
75    }
76  
77    /**
78     * @param a_config the configuration to use
79     *
80     * @author Klaus Meffert
81     * @since 3.0
82     */
83    public WeightedRouletteSelector(Configuration a_config) {
84      super(a_config);
85      m_config.m_doublettesAllowed = false;
86    }
87  
88    /**
89     * Add a Chromosome instance to this selector's working pool of Chromosomes.
90     *
91     * @param a_chromosomeToAdd the chromosom to add to the pool
92     *
93     * @author Neil Rotstan
94     * @author Klaus Meffert
95     * @since 1.0
96     */
97    protected synchronized void add(final IChromosome a_chromosomeToAdd) {
98      // The "roulette wheel" is represented by a Map. Each key is a
99      // Chromosome and each value is an instance of the SlotCounter inner
100     // class. The counter keeps track of the total number of slots that
101     // each chromosome is occupying on the wheel (which is equal to the
102     // combined total of their fitness values). If the Chromosome is
103     // already in the Map, then we just increment its number of slots
104     // by its fitness value. Otherwise we add it to the Map.
105     // -----------------------------------------------------------------
106     SlotCounter counter = (SlotCounter) m_wheel.get(a_chromosomeToAdd);
107     if (counter != null) {
108       // The Chromosome is already in the map.
109       // -------------------------------------
110       counter.increment();
111     }
112     else {
113       // We need to add this Chromosome and an associated SlotCounter
114       // to the map. First, we reset the Chromosome's
115       // isSelectedForNextGeneration flag to false. Later, if the
116       // Chromosome is actually selected to move on to the next
117       // generation population by the select() method, then it will
118       // be set to true.
119       // ------------------------------------------------------------
120       a_chromosomeToAdd.setIsSelectedForNextGeneration(false);
121       // We're going to need a SlotCounter. See if we can get one
122       // from the pool. If not, construct a new one.
123       // --------------------------------------------------------
124       counter = (SlotCounter) m_counterPool.acquirePooledObject();
125       if (counter == null) {
126         counter = new SlotCounter();
127       }
128       counter.reset(a_chromosomeToAdd.getFitnessValue());
129       m_wheel.put(a_chromosomeToAdd, counter);
130     }
131   }
132 
133   /**
134    * Select a given number of Chromosomes from the pool that will move on
135    * to the next generation population. This selection should be guided by
136    * the fitness values, but fitness should be treated as a statistical
137    * probability of survival, not as the sole determining factor. In other
138    * words, Chromosomes with higher fitness values should be more likely to
139    * be selected than those with lower fitness values, but it should not be
140    * guaranteed.
141    *
142    * @param a_howManyToSelect the number of Chromosomes to select
143    * @param a_from_pop the population the Chromosomes will be selected from
144    * @param a_to_pop the population the Chromosomes will be added to
145    *
146    * @author Neil Rotstan
147    * @author Klaus Meffert
148    * @since 1.0
149    */
150   public synchronized void select(int a_howManyToSelect,
151                                   final Population a_from_pop,
152                                   Population a_to_pop) {
153     if (a_from_pop != null) {
154       int size = a_from_pop.size();
155       for (int i = 0; i < size; i++) {
156         add(a_from_pop.getChromosome(i));
157       }
158     }
159 
160     RandomGenerator generator = getConfiguration().getRandomGenerator();
161     scaleFitnessValues();
162     // Build three arrays from the key/value pairs in the wheel map: one
163     // that contains the fitness values for each chromosome, one that
164     // contains the total number of occupied slots on the wheel for each
165     // chromosome, and one that contains the chromosomes themselves. The
166     // array indices are used to associate the values of the three arrays
167     // together (eg, if a chromosome is at index 5, then its fitness value
168     // and counter values are also at index 5 of their respective arrays).
169     // -------------------------------------------------------------------
170     Set entries = m_wheel.entrySet();
171     int numberOfEntries = entries.size();
172     double[] fitnessValues = new double[numberOfEntries];
173     double[] counterValues = new double[numberOfEntries];
174     IChromosome[] chromosomes = new Chromosome[numberOfEntries];
175     m_totalNumberOfUsedSlots = 0.0d;
176     Iterator entryIterator = entries.iterator();
177     for (int i = 0; i < numberOfEntries; i++) {
178       Map.Entry chromosomeEntry = (Map.Entry) entryIterator.next();
179       IChromosome currentChromosome =
180           (IChromosome) chromosomeEntry.getKey();
181       SlotCounter currentCounter =
182           (SlotCounter) chromosomeEntry.getValue();
183       fitnessValues[i] = currentCounter.getFitnessValue();
184       counterValues[i] = fitnessValues[i] //currentCounter.getFitnessValue()
185           * currentCounter.getCounterValue();
186       chromosomes[i] = currentChromosome;
187       // We're also keeping track of the total number of slots,
188       // which is the sum of all the counter values.
189       // ------------------------------------------------------
190       m_totalNumberOfUsedSlots += counterValues[i];
191     }
192     if (a_howManyToSelect > numberOfEntries
193         && !getDoubletteChromosomesAllowed()) {
194       a_howManyToSelect = numberOfEntries;
195     }
196     // To select each chromosome, we just "spin" the wheel and grab
197     // whichever chromosome it lands on.
198     // ------------------------------------------------------------
199     IChromosome selectedChromosome;
200     for (int i = 0; i < a_howManyToSelect; i++) {
201       selectedChromosome = spinWheel(generator, fitnessValues, counterValues,
202                                      chromosomes);
203       selectedChromosome.setIsSelectedForNextGeneration(true);
204       a_to_pop.addChromosome(selectedChromosome);
205     }
206   }
207 
208   /**
209    * This method "spins" the wheel and returns the Chromosome that is
210    * "landed upon." Each time a chromosome is selected, one instance of it
211    * is removed from the wheel so that it cannot be selected again.
212    *
213    * @param a_generator the random number generator to be used during the
214    * spinning process
215    * @param a_fitnessValues an array of fitness values of the respective
216    * Chromosomes
217    * @param a_counterValues an array of total counter values of the
218    * respective Chromosomes
219    * @param a_chromosomes the respective Chromosome instances from which
220    * selection is to occur
221    * @return selected Chromosome from the roulette wheel
222    *
223    * @author Neil Rotstan
224    * @author Klaus Meffert
225    * @since 1.0
226    */
227   private IChromosome spinWheel(final RandomGenerator a_generator,
228                                final double[] a_fitnessValues,
229                                double[] a_counterValues,
230                                final IChromosome[] a_chromosomes) {
231     // Randomly choose a slot on the wheel.
232     // ------------------------------------
233     double selectedSlot =
234         a_generator.nextDouble() * m_totalNumberOfUsedSlots;
235     if (selectedSlot > m_totalNumberOfUsedSlots) {
236       selectedSlot = m_totalNumberOfUsedSlots;
237     }
238     // Loop through the wheel until we find our selected slot. Here's
239     // how this works: we have three arrays, one with the fitness values
240     // of the chromosomes, one with the total number of slots on the
241     // wheel that each chromosome occupies (its counter value), and
242     // one with the chromosomes themselves. The array indices associate
243     // each of the three together (eg, if a chromosome is at index 5,
244     // then its fitness value and counter value are also at index 5 of
245     // their respective arrays).
246     //
247     // We've already chosen a random slot number on the wheel from which
248     // we want to select the Chromosome. We loop through each of the
249     // array indices and, for each one, we add the number of occupied slots
250     // (the counter value) to an ongoing total until that total
251     // reaches or exceeds the chosen slot number. When that happenes,
252     // we've found the chromosome sitting in that slot and we return it.
253     // --------------------------------------------------------------------
254     double currentSlot = 0.0d;
255     FitnessEvaluator evaluator = getConfiguration().getFitnessEvaluator();
256     boolean isFitter2_1 = evaluator.isFitter(2, 1);
257     for (int i = 0; i < a_counterValues.length; i++) {
258       // Increment our ongoing total and see if we've landed on the
259       // selected slot.
260       // ----------------------------------------------------------
261       currentSlot += a_counterValues[i];
262       boolean found;
263       if (isFitter2_1) {
264         // Introduced DELTA to fix bug 1449651
265         found = selectedSlot - currentSlot <= DELTA;
266       }
267       else {
268         // Introduced DELTA to fix bug 1449651
269         found = currentSlot - selectedSlot <= DELTA;
270       }
271       if (found) {
272         // Remove one instance of the chromosome from the wheel by
273         // decrementing the slot counter by the fitness value resp.
274         // resetting the counter if doublette chromosomes are not
275         // allowed.
276         // -------------------------------------------------------
277          if ( !getDoubletteChromosomesAllowed() ) {
278            m_totalNumberOfUsedSlots -= a_counterValues[i];
279            a_counterValues[i] = 0;
280          }
281          else {
282            a_counterValues[i] -= a_fitnessValues[i];
283            m_totalNumberOfUsedSlots -= a_fitnessValues[i];
284          }
285         // Introduced DELTA to fix bug 1449651
286          if (Math.abs(m_totalNumberOfUsedSlots) < DELTA) {
287            m_totalNumberOfUsedSlots = 0.0d;
288          }
289         // Now return our selected Chromosome.
290         // -----------------------------------
291         return a_chromosomes[i];
292       }
293     }
294     // We have reached here because there were rounding errors when
295     // computing with doubles.
296     // ------------------------------------------------------------
297     return a_chromosomes[a_counterValues.length-1];
298   }
299 
300   /**
301    * Empty out the working pool of Chromosomes.
302    *
303    * @author Neil Rotstan
304    * @since 1.0
305    */
306   public synchronized void empty() {
307     // Put all of the old SlotCounters into the pool so that we can
308     // reuse them later instead of constructing new ones.
309     // ------------------------------------------------------------
310     m_counterPool.releaseAllObjects(m_wheel.values());
311     // Now clear the wheel and reset the internal state.
312     // -------------------------------------------------
313     m_wheel.clear();
314     m_totalNumberOfUsedSlots = 0;
315   }
316 
317   private void scaleFitnessValues() {
318     // First, add up all the fitness values. While we're doing this,
319     // keep track of the largest fitness value we encounter.
320     // -------------------------------------------------------------
321     double largestFitnessValue = 0.0;
322     BigDecimal totalFitness = ZERO_BIG_DECIMAL;
323     Iterator counterIterator = m_wheel.values().iterator();
324     while (counterIterator.hasNext()) {
325       SlotCounter counter = (SlotCounter) counterIterator.next();
326       if (counter.getFitnessValue() > largestFitnessValue) {
327         largestFitnessValue = counter.getFitnessValue();
328       }
329       BigDecimal counterFitness = new BigDecimal(counter.getFitnessValue());
330       totalFitness = totalFitness.add(counterFitness.multiply(
331           new BigDecimal(counter.getCounterValue())));
332     }
333     // Now divide the total fitness by the largest fitness value to
334     // compute the scaling factor.
335     // ------------------------------------------------------------
336     if (largestFitnessValue > 0.000000d
337         && totalFitness.floatValue() > 0.0000001d) {
338       double scalingFactor =
339           totalFitness.divide(new BigDecimal(largestFitnessValue),
340                               BigDecimal.ROUND_HALF_UP).doubleValue();
341       // Divide each of the fitness values by the scaling factor to
342       // scale them down.
343       // ----------------------------------------------------------
344       counterIterator = m_wheel.values().iterator();
345       while (counterIterator.hasNext()) {
346         SlotCounter counter = (SlotCounter) counterIterator.next();
347         counter.scaleFitnessValue(scalingFactor);
348       }
349     }
350   }
351 
352   /**
353    * @return always false as some Chromosome's could be returnd multiple times
354    *
355    * @author Klaus Meffert
356    * @since 2.0
357    */
358   public boolean returnsUniqueChromosomes() {
359     return false;
360   }
361 
362   /**
363    * Determines whether doublette chromosomes may be added to the selector or
364    * will be ignored.
365    * @param a_doublettesAllowed true: doublette chromosomes allowed to be
366    * added to the selector. FALSE: doublettes will be ignored and not added
367    *
368    * @author Klaus Meffert
369    * @since 2.0
370    */
371   public void setDoubletteChromosomesAllowed(final boolean a_doublettesAllowed) {
372     m_config.m_doublettesAllowed = a_doublettesAllowed;
373   }
374 
375   /**
376    * @return TRUE: doublette chromosomes allowed to be added to the selector
377    *
378    * @author Klaus Meffert
379    * @since 2.0
380    */
381   public boolean getDoubletteChromosomesAllowed() {
382     return m_config.m_doublettesAllowed;
383   }
384 
385   /**
386    * @return deep clone of this instance
387    *
388    * @author Klaus Meffert
389    * @since 3.2
390    */
391   public Object   clone() {
392     WeightedRouletteSelector result = new WeightedRouletteSelector(getConfiguration());
393     result.m_wheel = (HashMap)m_wheel.clone();
394     result.m_config = new WeightedRouletteSelConfig();
395     result.m_config.m_doublettesAllowed = m_config.m_doublettesAllowed;
396     return result;
397   }
398 
399   class WeightedRouletteSelConfig {
400     /**
401      * Allows or disallows doublette chromosomes to be added to the selector
402      */
403     public boolean m_doublettesAllowed;
404 
405   }
406 }
407 
408 /**
409  * Implements a counter that is used to keep track of the total number of
410  * slots that a single Chromosome is occupying in the roulette wheel. Since
411  * all equal copies of a chromosome have the same fitness value, the increment
412  * method always adds the fitness value of the chromosome. Following
413  * construction of this class, the reset() method must be invoked to provide
414  * the initial fitness value of the Chromosome for which this SlotCounter is
415  * to be associated. The reset() method may be reinvoked to begin counting
416  * slots for a new Chromosome.
417  *
418  * @author Neil Rotstan
419  * @since 1.0
420  */
421 class SlotCounter {
422   /**
423    * The fitness value of the Chromosome for which we are keeping count of
424    * roulette wheel slots. Although this value is constant for a Chromosome,
425    * it's not declared final here so that the slots can be reset and later
426    * reused for other Chromosomes, thus saving some memory and the overhead
427    * of constructing them from scratch.
428    */
429   private double m_fitnessValue;
430 
431   /**
432    * The current number of Chromosomes represented by this counter.
433    */
434   private int m_count;
435 
436   /**
437    * Resets the internal state of this SlotCounter instance so that it can
438    * be used to count slots for a new Chromosome.
439    *
440    * @param a_initialFitness the fitness value of the Chromosome for which
441    * this instance is acting as a counter
442    *
443    * @author Neil Rotstan
444    * @since 1.0
445    */
446   public void reset(final double a_initialFitness) {
447     m_fitnessValue = a_initialFitness;
448     m_count = 1;
449   }
450 
451   /**
452    * Retrieves the fitness value of the chromosome for which this instance
453    * is acting as a counter.
454    *
455    * @return the fitness value that was passed in at reset time
456    *
457    * @author Neil Rotstan
458    * @since 1.0
459    */
460   public double getFitnessValue() {
461     return m_fitnessValue;
462   }
463 
464   /**
465    * Increments the value of this counter by the fitness value that was
466    * passed in at reset time.
467    *
468    * @author Neil Rotstan
469    * @since 1.0
470    */
471   public void increment() {
472     m_count++;
473   }
474 
475   /**
476    * Retrieves the current value of this counter: ie, the number of slots
477    * on the roulette wheel that are currently occupied by the Chromosome
478    * associated with this SlotCounter instance.
479    *
480    * @return the current value of this counter
481    */
482   public int getCounterValue() {
483     return m_count;
484   }
485 
486   /**
487    * Scales this SlotCounter's fitness value by the given scaling factor.
488    *
489    * @param a_scalingFactor the factor by which the fitness value is to be
490    * scaled
491    *
492    * @author Neil Rotstan
493    * @since 1.0
494    */
495   public void scaleFitnessValue(final double a_scalingFactor) {
496     m_fitnessValue /= a_scalingFactor;
497   }
498 
499 }
500
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags