weightedrouletteselector.java

用java语言写的遗传算法库

    // then its fitness value and counter value are also at index 5 of
    // their respective arrays).
    //
    // We've already chosen a random slot number on the wheel from which
    // we want to select the Chromosome. We loop through each of the
    // array indices and, for each one, we add the number of occupied slots
    // (the counter value) to an ongoing total until that total
    // reaches or exceeds the chosen slot number. When that happenes,
    // we've found the chromosome sitting in that slot and we return it.
    // --------------------------------------------------------------------
    double currentSlot = 0.0;
    for (int i = 0; i < a_counterValues.length; i++) {
      // Increment our ongoing total and see if we've landed on the
      // selected slot.
      // ----------------------------------------------------------
      currentSlot += a_counterValues[i];
      if (currentSlot > selectedSlot - DELTA) {
        // Remove one instance of the chromosome from the wheel by
        // decrementing the slot counter by the fitness value.
        // --------------------------------------------------------
        a_counterValues[i] -= a_fitnessValues[i];
        m_totalNumberOfUsedSlots -= a_fitnessValues[i];
        // Now return our selected Chromosome
        // ----------------------------------
        return a_chromosomes[i];
      }
    }
    // If we have reached here, it means we have not found any chromosomes
    // to select and something is wrong with our logic. For some reason
    // the selected slot has exceeded the slots on our wheel. To help
    // with debugging, we tally up the total number of slots left on
    // the wheel and report it along with the chosen slot number that we
    // couldn't find.
    // -------------------------------------------------------------------
    long totalSlotsLeft = 0;
    for (int i = 0; i < a_counterValues.length; i++) {
      totalSlotsLeft += a_counterValues[i];
    }
    throw new RuntimeException("Logic Error. This code should never " +
                               "be reached. Please report this as a bug to the " +
                               "JGAP team: selected slot " + selectedSlot + " " +
                               "exceeded " + totalSlotsLeft +
                               " number of slots left. " +
                               "We thought there were " +
                               m_totalNumberOfUsedSlots +
                               " slots left.");
  }

  /**
   * Empty out the working pool of Chromosomes.
   *
   * @author Neil Rotstan
   * @since 1.0
   */
  public synchronized void empty() {
    // Put all of the old SlotCounters into the pool so that we can
    // reuse them later instead of constructing new ones.
    // ------------------------------------------------------------
    m_counterPool.releaseAllObjects(m_wheel.values());
    // Now clear the wheel and reset the internal state.
    // -------------------------------------------------
    m_wheel.clear();
    m_totalNumberOfUsedSlots = 0;
  }

  private void scaleFitnessValues() {
    // First, add up all the fitness values. While we're doing this,
    // keep track of the largest fitness value we encounter.
    // -------------------------------------------------------------
    double largestFitnessValue = 0.0;
    BigDecimal totalFitness = ZERO_BIG_DECIMAL;
    Iterator counterIterator = m_wheel.values().iterator();
    while (counterIterator.hasNext()) {
      SlotCounter counter = (SlotCounter) counterIterator.next();
      if (counter.getFitnessValue() > largestFitnessValue) {
        largestFitnessValue = counter.getFitnessValue();
      }
      BigDecimal counterFitness = new BigDecimal(counter.getFitnessValue());
      totalFitness = totalFitness.add(counterFitness.multiply(
          new BigDecimal(counter.getCounterValue())));
    }
    // Now divide the total fitness by the largest fitness value to
    // compute the scaling factor.
    // ------------------------------------------------------------
    if (largestFitnessValue > 0.000000d) {
      double scalingFactor =
          totalFitness.divide(new BigDecimal(largestFitnessValue),
                              BigDecimal.ROUND_HALF_UP).doubleValue();
      // Divide each of the fitness values by the scaling factor to
      // scale them down.
      // --------------------------------------------------------------
      counterIterator = m_wheel.values().iterator();
      while (counterIterator.hasNext()) {
        SlotCounter counter = (SlotCounter) counterIterator.next();
        counter.scaleFitnessValue(scalingFactor);
      }
    }
  }

  /**
   * @return always false as some Chromosome's could be returnd multiple times
   *
   * @author Klaus Meffert
   * @since 2.0
   */
  public boolean returnsUniqueChromosomes() {
    return false;
  }

  /**
   * Determines whether doublette chromosomes may be added to the selector or
   * will be ignored.
   * @param a_doublettesAllowed true: doublette chromosomes allowed to be
   *       added to the selector. FALSE: doublettes will be ignored and not
   *       added
   *
   * @author Klaus Meffert
   * @since 2.0
   */
  public void setDoubletteChromosomesAllowed(boolean a_doublettesAllowed) {
    m_doublettesAllowed = a_doublettesAllowed;
  }

  /**
   * @return TRUE: doublette chromosomes allowed to be added to the selector
   *
   * @author Klaus Meffert
   * @since 2.0
   */
  public boolean getDoubletteChromosomesAllowed() {
    return m_doublettesAllowed;
  }
}

/**
 * Implements a counter that is used to keep track of the total number of
 * slots that a single Chromosome is occupying in the roulette wheel. Since
 * all equal copies of a chromosome have the same fitness value, the increment
 * method always adds the fitness value of the chromosome. Following
 * construction of this class, the reset() method must be invoked to provide
 * the initial fitness value of the Chromosome for which this SlotCounter is
 * to be associated. The reset() method may be reinvoked to begin counting
 * slots for a new Chromosome.
 *
 * @author Neil Rotstan
 * @since 1.0
 */
class SlotCounter {
  /**
   * The fitness value of the Chromosome for which we are keeping count of
   * roulette wheel slots. Although this value is constant for a Chromosome,
   * it's not declared final here so that the slots can be reset and later
   * reused for other Chromosomes, thus saving some memory and the overhead
   * of constructing them from scratch.
   */
  private double m_fitnessValue;

  /**
   * The current number of Chromosomes represented by this counter.
   */
  private int m_count;

  /**
   * Resets the internal state of this SlotCounter instance so that it can
   * be used to count slots for a new Chromosome.
   *
   * @param a_initialFitness The fitness value of the Chromosome for which
   *                         this instance is acting as a counter.
   *
   * @author Neil Rotstan
   * @since 1.0
   */
  public void reset(double a_initialFitness) {
    m_fitnessValue = a_initialFitness;
    m_count = 1;
  }

  /**
   * Retrieves the fitness value of the chromosome for which this instance
   * is acting as a counter.
   *
   * @return The fitness value that was passed in at reset time.
   *
   * @author Neil Rotstan
   * @since 1.0
   */
  public double getFitnessValue() {
    return m_fitnessValue;
  }

  /**
   * Increments the value of this counter by the fitness value that was
   * passed in at reset time.
   *
   * @author Neil Rotstan
   * @since 1.0
   */
  public void increment() {
    m_count++;
  }

  /**
   * Retrieves the current value of this counter: ie, the number of slots
   * on the roulette wheel that are currently occupied by the Chromosome
   * associated with this SlotCounter instance.
   *
   * @return the current value of this counter.
   */
  public int getCounterValue() {
    return m_count;
  }

  /**
   * Scales this SlotCounter's fitness value by the given scaling factor.
   *
   * @param a_scalingFactor The factor by which the fitness value is to be
   *                        scaled.
   *
   * @author Neil Rotstan
   * @since 1.0
   */
  public void scaleFitnessValue(double a_scalingFactor) {
    m_fitnessValue /= a_scalingFactor;
  }
}