bulkfitnessoffsetremover.java

jGAp 遗传算法 提不错的一款软件 最新的更新

   * as the Configuration permits bulk fitness function and
   * simple fitness function both existing in it at the same time.
   */
  /*
    public BulkFitnessOffsetRemover(Configuration conf){
   if(m_activeConfiguration)
    }
   */
  /**
   * <p>
   * The last generations offset.
   * This has to be stored because Chromosomes that were put into the new
   * generation's candidate list already have the fitness value without offset
   * from their previous evaluation.
   * </p>
   * <P>
   * We try to avoid evaluations of the fitness function
   * as it might be expensive, so we reuse fitness values.
   * If a Chromosome already has a fitness value >0 this
   * previousOffset is added to it's fitness to allow
   * comparing this Chromosome's fitness with newly
   * evaluated Chromosomes (which still have the offset from the evaluation).
   * </p>
   */
  private double m_previousOffset;

  public BulkFitnessOffsetRemover(final FitnessFunction a_ff) {
    if (a_ff == null) {
      throw new IllegalArgumentException("Fitness function must not be null!");
    }
    m_ff = a_ff;
  }

  /* (non-Javadoc)
   * @see org.jgap.BulkFitnessFunction#evaluate(org.jgap.Chromosome[])
   */
  public void evaluate(final Population a_chromosomes) {
    double offset = Double.MAX_VALUE;
    double curFitness;
    Iterator itChromosomes = a_chromosomes.iterator();
    IChromosome chromosome;
    while (itChromosomes.hasNext()) {
      chromosome = (IChromosome) itChromosomes.next();
      /*
       * This is a workaround:
       * We have to check, wethter a Chromosome has
       * already been evaluated, because it may be too
       * expensive to unconditionally evaluate each Chromosome.
       * We use the "caching of fitness values" of the Chromosome.
       * But in the current Configuration,
       * there is no fittnessFunction: We have a bulk fitness function
       * assigned.
       * Look at the code of Chromosome.getFitnessValue():
       * In that case, a negative value will be returned.
       * If a redesign of that method is made, this has to be changed
       * here too.. .
       */
      curFitness = chromosome.getFitnessValueDirectly();
      if (curFitness < 0) {
        // OK, get it from our fitness function.
        curFitness = m_ff.getFitnessValue(chromosome);
        // And store it to avoid evaluation of the same Chromosome again:
        chromosome.setFitnessValue(curFitness);
      }
      else {
        /*
         * Those have fitness values already without offset
         * of the previous evaluation.
         * Reattach it to allow comparison.
         * Else these Chromosomes would be the unfittest and
         * additionally disallow cutting a huge offset from the others.
         */
        curFitness += m_previousOffset;
        chromosome.setFitnessValue(curFitness);
      }
      // search for the offset that is to be cut:
      offset = (offset < curFitness) ? offset : curFitness;
    }
    /*
     * Now we have the classical evaluated Chromosomes
     * and the minimum fitness.
     * It would be easy to simply subtract that value from
     * each Chromosomes fitness. But in that case the
     * unfittest Chromosome would possible have no chance to survive.
     * In a WeightedRouletteSelector it would not get
     * a single slot to be selected as it's fitness value
     * would be zero.
     * So we have to leave at least a fitness value of 1.
     * Ups, if forgot: Neil throws exceptions, whenever a
     * fitness value is below 1 and also does not accept
     * assignment of fitness values <1. Ok, so he ensures
     * that every Chromosome may survive...
     */
    offset--;
    m_previousOffset = offset;
    // offset cannot be <0... thx to fitness value policy of jgap.
    // finally remove the offset from every fitness value:
    itChromosomes = a_chromosomes.iterator();
    while (itChromosomes.hasNext()) {
      chromosome = (IChromosome) itChromosomes.next();
      chromosome.setFitnessValue(chromosome.getFitnessValue() - offset);
    }
  }

  /**
   * <p>
   * Using this instance to remove the fitness offset in the
   * populations brings the advantage of getting a selection
   * more sensitive to the differences of fitness of the chromosomes.
   * </p>
   * <p>
   * The disadvantage is, that the fitness values are modified.
   * The modification is good for jgap's selection method but
   * bad for the guys that want to see the success of your
   * work, or need a proof that a GA improves over time:
   * <br>
   * The value of {@link org.jgap.Genotype#getFittestChromosome()}
   * does not seem to increase over the generations. Most often
   * it becomes worse. This is caused by the fact, that all
   * Chromosomes are getting better over time
   * (the fitness interval of all Chromosomes gets narrower) and
   * the offset that may be cut becomes bigger.
   * </p>
   * <p>
   * If you want to get an absolute value independant from the
   * offset that is cut off from the chromosome's fitness value,
   * this method has to be used.
   * </p>
   * <p>
   * Stop reading here because a
   * </p>
   * <h4>Mathematical Proof</h4>
   * <p>
   * is following.
   * How can it work to get the absolute value for all
   * Chromosomes fitness values? Some Chromosomes may have lived
   * for many generations and everytime their fitness was
   * evaluated here, the old offset was added and a new one was
   * calculated and subtracted from the fitness value.
   * </p>
   * <p>
   * Each bulk fitness evaluation a Chromosome experiences,
   * it's fitness value <i>F</i> get's an addition of the old offset
   * <i>O<sub>(n-1)</sub></i>
   * and a substraction by the new offset <i>O<sub>n</sub></i>.<br>
   * <i><sub>n</sub></i> is the generation index.
   *
   * <pre>
   * F<sub>1</sub> = F<sub>0</sub> + O<sub>0</sub> - O<sub>1</sub>
   * F<sub>2</sub> = F<sub>1</sub> + O<sub>1</sub> - O<sub>2</sub>
   * F<sub>3</sub> = F<sub>2</sub> + O<sub>2</sub> - O<sub>3</sub>
   *
   * =>
   *
   * 1) F<sub>n</sub> = <b>F<sub>(n-1)</sub></b>
   * + O<sub>(n-1)</sub> - O<sub>n</sub>
   *
   * 2) <b>F<sub>(n-1)</sub></b> = F<sub>(n-2)</sub>
   * + O<sub>(n-2)</sub> - O<sub>(n-1)</sub>
   *
   * 2 in 1)
   *    F<sub>n</sub> = (F<sub>(n-2)</sub> + O<sub>(n-2)</sub>
   * - O<sub>(n-1)</sub>) + O<sub>(n-1)</sub> - O<sub>n</sub>
   *    F<sub>n</sub> = F<sub>(n-2)</sub> + O<sub>(n-2)</sub> - O<sub>n</sub>
   *
   * We made a step over 2 generations: With the current offset and the
   * fitness & offset of the
   * "preprevious" generation we can calculate the current fitness.
   * We can assume that this generation stepping works for farer steps
   * <sub>m</sub> (just continue step 2) until you have a generation step value
   * high enough ;-))
   *
   * => F<sub>n</sub> = F<sub>(n-m)</sub> + O<sub>(n-m)</sub> - O<sub>n</sub>
   *
   * We want to get the original absolute value of fitness:
   *
   * 3) m := n
   *
   * => F<sub>n</sub> = F<sub>0</sub> + O<sub>0</sub> - O<sub>n</sub>
   *
   * solved to F<sub>0</sub> our original value:
   *
   * F<sub>0</sub> = F<sub>n</sub> + O<sub>n</sub> - O<sub>0</sub>
   *
   * And our initial offset {@link #m_previousOffset O<sub>0</sub>} is zero!
   * </pre>
   * </p>
   * <p>
   * This shows, that it is possible to compute the original fitness value of a
   * Chromosome from it's current fitness value and the
   * {@link #m_previousOffset previous offset}
   * regardless of the amounts of generations between original evaluation and
   * the current generation.
   * </p>
   * @param a_individuum any Chromosome that is normally being evaluated by
   * this <tt>BulkFitnessFunction</tt>
   * @return the original fitness value as returned by the registered
   * {@link #m_ff fitnessFunction} instance.
   */
  public double getAbsoluteFitness(final IChromosome a_individuum) {
    double fitness = a_individuum.getFitnessValue();
    if (fitness < 0.0) {
      // OK, get it from our fitness function.
      fitness = m_ff.getFitnessValue(a_individuum);
      // And store it to avoid evaluation of the same Chromosome again:
      a_individuum.setFitnessValue(fitness);
    }
    else {
      /*
       * Those have fitness values already without offset
       * of the previous evaluation.
       * Reattach it to allow comparison.
       * Else these Chromosomes would be the unfittest and
       * additionally disallow cutting a huge offset from the others.
       */
      fitness += m_previousOffset;
    }
    return fitness;
  }

  /**
   * @return deep clone of current instance
   *
   * @author Klaus Meffert
   * @since 3.2
   */
  public Object clone() {
    FitnessFunction ff = (FitnessFunction)m_ff.clone();
    BulkFitnessOffsetRemover result = new BulkFitnessOffsetRemover(ff);
    return result;
  }
}