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