bulkfitnessoffsetremover.java

用java语言写的遗传算法库

  /*
   * This constructor is planned but not possible yet,
   * 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 by a {@link org.jgap.ReproductionOperator} 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 previousOffset;

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

  /* (non-Javadoc)
   * @see org.jgap.BulkFitnessFunction#evaluate(org.jgap.Chromosome[])
   */
  public void evaluate(Population a_chromosomes) {
    double offset = Double.MAX_VALUE;
    double curFitness;
    Iterator itChromosomes = a_chromosomes.iterator();
    Chromosome a_Chromosome;
    while (itChromosomes.hasNext()) {
      a_Chromosome = (Chromosome) 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 = a_Chromosome.getFitnessValue();
      if (curFitness < 0) {
        // OK, get it from our fitness function.
        curFitness = ff.getFitnessValue(a_Chromosome);
        // And store it to avoid evaluation of the same Chromosome again:
        a_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 += previousOffset;
        a_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--;
    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()) {
      a_Chromosome = (Chromosome) itChromosomes.next();
      a_Chromosome.setFitnessValue(a_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</i></sub>. <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 #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 #previousOffset previous offset}
   * regardless of the amounts of generations between original evaluation and
   * the current generation.
   * </p>
   * @param individuum Any Chromosome that is normally being evaluated by this <tt>BulkFitnessFunction</tt>.
   * @return The original fitness value as returned by the registered {@link #ff fitnessFunction} instance.
   */
  public double getAbsoluteFitness(Chromosome individuum) {
    double fitness = individuum.getFitnessValue();
    if (fitness < 0.0) {
      // OK, get it from our fitness function.
      fitness = ff.getFitnessValue(individuum);
      // And store it to avoid evaluation of the same Chromosome again:
      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 += previousOffset;
    }
    return fitness;
  }
}