weightedrouletteselector.java

用java语言写的遗传算法库

/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licencing information please see the file license.txt included with JGAP
 * or have a look at the top of class org.jgap.Chromosome which representatively
 * includes the JGAP license policy applicable for any file delivered with JGAP.
 */
package org.jgap.impl;

import java.math.*;
import java.util.*;
import org.jgap.*;

/**
 * A basic implementation of NaturalSelector that models a roulette wheel.
 * When a Chromosome is added, it gets a number of "slots" on the wheel equal
 * to its fitness value. When the select method is invoked, the wheel is
 * "spun" and the Chromosome occupying the spot on which it lands is selected.
 * Then the wheel is spun again and again until the requested number of
 * Chromosomes have been selected. Since Chromosomes with higher fitness
 * values get more slots on the wheel, there's a higher statistical probability
 * that they'll be chosen, but it's not guaranteed.
 *
 * @author Neil Rotstan
 * @author Klaus Meffert
 * @since 1.0
 */
public class WeightedRouletteSelector
    extends NaturalSelector {
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.16 $";

  //delta for distinguishing whether a value is to be interpreted as zero
  private static final double DELTA = 0.000001d;

  private static final BigDecimal ZERO_BIG_DECIMAL = new BigDecimal(0.0d);

  /**
   * Represents the "roulette wheel." Each key in the Map is a Chromosome
   * and each value is an instance of the SlotCounter inner class, which
   * keeps track of how many slots on the wheel each Chromosome is occupying.
   */
  private Map m_wheel = new HashMap();

  /**
   * Keeps track of the total number of slots that are in use on the
   * roulette wheel. This is equal to the combined fitness values of
   * all Chromosome instances that have been added to this wheel.
   */
  private double m_totalNumberOfUsedSlots;

  /**
   * An internal pool in which discarded SlotCounter instances can be stored
   * so that they can be reused over and over again, thus saving memory
   * and the overhead of constructing new ones each time.
   */
  private Pool m_counterPool = new Pool();

  /**
   * Allows or disallows doublette chromosomes to be added to the selector
   */
  private boolean m_doublettesAllowed;

  /**
   * @author Klaus Meffert
   * @since 2.0 (prior: existent thru super class)
   */
  public WeightedRouletteSelector() {
    m_doublettesAllowed = true;
  }

  /**
   * Add a Chromosome instance to this selector's working pool of Chromosomes.
   *
   * @param a_chromosomeToAdd The specimen to add to the pool.
   *
   * @author Neil Rotstan
   * @author Klaus Meffert
   * @since 1.0
   */
  protected synchronized void add(Chromosome a_chromosomeToAdd) {
    // The "roulette wheel" is represented by a Map. Each key is a
    // Chromosome and each value is an instance of the SlotCounter inner
    // class. The counter keeps track of the total number of slots that
    // each chromosome is occupying on the wheel (which is equal to the
    // combined total of their fitness values). If the Chromosome is
    // already in the Map, then we just increment its number of slots
    // by its fitness value. Otherwise we add it to the Map.
    // -----------------------------------------------------------------
    SlotCounter counter = (SlotCounter) m_wheel.get(a_chromosomeToAdd);
    if (counter != null) {
      // The Chromosome is already in the map.
      // -------------------------------------
      counter.increment();
    }
    else {
      // We need to add this Chromosome and an associated SlotCounter
      // to the map. First, we reset the Chromosome's
      // isSelectedForNextGeneration flag to false. Later, if the
      // Chromosome is actually selected to move on to the next
      // generation population by the select() method, then it will
      // be set to true.
      // ------------------------------------------------------------
      a_chromosomeToAdd.setIsSelectedForNextGeneration(false);
      // We're going to need a SlotCounter. See if we can get one
      // from the pool. If not, construct a new one.
      // --------------------------------------------------------
      counter = (SlotCounter) m_counterPool.acquirePooledObject();
      if (counter == null) {
        counter = new SlotCounter();
      }
      counter.reset(a_chromosomeToAdd.getFitnessValue());
      m_wheel.put(a_chromosomeToAdd, counter);
    }
  }

  /**
   * Select a given number of Chromosomes from the pool that will move on
   * to the next generation population. This selection should be guided by
   * the fitness values, but fitness should be treated as a statistical
   * probability of survival, not as the sole determining factor. In other
   * words, Chromosomes with higher fitness values should be more likely to
   * be selected than those with lower fitness values, but it should not be
   * guaranteed.
   *
   * @param a_howManyToSelect The number of Chromosomes to select.
   * @param a_from_pop the population the Chromosomes will be selected from.
   * @param a_to_pop the population the Chromosomes will be added to.
   *
   * @author Neil Rotstan
   * @author Klaus Meffert
   * @since 1.0
   */
  public synchronized void select(int a_howManyToSelect, Population a_from_pop,
                                  Population a_to_pop) {
    if (a_from_pop != null) {
      for (int i = 0; i < a_from_pop.size(); i++) {
        add(a_from_pop.getChromosome(i));
      }
    }

    RandomGenerator generator = Genotype.getConfiguration().getRandomGenerator();
    scaleFitnessValues();
    // Build three arrays from the key/value pairs in the wheel map: one
    // that contains the fitness values for each chromosome, one that
    // contains the total number of occupied slots on the wheel for each
    // chromosome, and one that contains the chromosomes themselves. The
    // array indices are used to associate the values of the three arrays
    // together (eg, if a chromosome is at index 5, then its fitness value
    // and counter values are also at index 5 of their respective arrays).
    // -------------------------------------------------------------------
    Set entries = m_wheel.entrySet();
    int numberOfEntries = entries.size();
    double[] fitnessValues = new double[numberOfEntries];
    double[] counterValues = new double[numberOfEntries];
    Chromosome[] chromosomes = new Chromosome[numberOfEntries];
    m_totalNumberOfUsedSlots = 0.0;
    Iterator entryIterator = entries.iterator();
    for (int i = 0; i < numberOfEntries; i++) {
      Map.Entry chromosomeEntry = (Map.Entry) entryIterator.next();
      Chromosome currentChromosome =
          (Chromosome) chromosomeEntry.getKey();
      SlotCounter currentCounter =
          (SlotCounter) chromosomeEntry.getValue();
      fitnessValues[i] = currentCounter.getFitnessValue();
      counterValues[i] = currentCounter.getFitnessValue() *
          currentCounter.getCounterValue();
      chromosomes[i] = currentChromosome;
      // We're also keeping track of the total number of slots,
      // which is the sum of all the counter values.
      // ------------------------------------------------------
      m_totalNumberOfUsedSlots += counterValues[i];
    }
    if (a_howManyToSelect > numberOfEntries && !getDoubletteChromosomesAllowed()) {
      a_howManyToSelect = numberOfEntries;
    }
    // To select each chromosome, we just "spin" the wheel and grab
    // whichever chromosome it lands on.
    // ------------------------------------------------------------
    Chromosome selectedChromosome;
    for (int i = 0; i < a_howManyToSelect; i++) {
      selectedChromosome = spinWheel(generator, fitnessValues, counterValues,
                                     chromosomes);
      selectedChromosome.setIsSelectedForNextGeneration(true);
      a_to_pop.addChromosome(selectedChromosome);
    }
  }

  /**
   * This method "spins" the wheel and returns the Chromosome that is
   * "landed upon." Each time a chromosome is selected, one instance of it
   * is removed from the wheel so that it cannot be selected again.
   *
   * @param a_generator The random number generator to be used during the
   *                    spinning process.
   * @param a_fitnessValues An array of fitness values of the respective
   *                        Chromosomes.
   * @param a_counterValues An array of total counter values of the
   *                        respective Chromosomes.
   * @param a_chromosomes The respective Chromosome instances from which
   *                      selection is to occur.
   * @return selected Chromosome from the roulette wheel
   *
   * @author Neil Rotstan
   * @author Klaus Meffert
   * @since 1.0
   */
  private Chromosome spinWheel(RandomGenerator a_generator,
                               double[] a_fitnessValues,
                               double[] a_counterValues,
                               Chromosome[] a_chromosomes) {
    // Randomly choose a slot on the wheel.
    // ------------------------------------
    double selectedSlot =
        Math.abs(a_generator.nextDouble() * m_totalNumberOfUsedSlots);
    if (selectedSlot > m_totalNumberOfUsedSlots) {
      selectedSlot = m_totalNumberOfUsedSlots;
    }
    // Loop through the wheel until we find our selected slot. Here's
    // how this works: we have three arrays, one with the fitness values
    // of the chromosomes, one with the total number of slots on the
    // wheel that each chromosome occupies (its counter value), and
    // one with the chromosomes themselves. The array indices associate
    // each of the three together (eg, if a chromosome is at index 5,