Clover coverage report - JGAP 3.1
Coverage timestamp: Mo Dez 11 2006 21:16:18 CET
file stats: LOC: 455   Methods: 3
NCLOC: 52   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
BulkFitnessOffsetRemover.java 91,7% 100% 100% 97,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.util.*;
 13    import org.jgap.*;
 14   
 15    /**
 16    * <p>
 17    * Takes away the fitness offset of the population to evolve.
 18    * The fitness function values of the population of {@link org.jgap.IChromosome}
 19    * instances will start from a minimum of 1 afterwards.
 20    * </p>
 21    * <p>
 22    * The removal of an offset in the fitness values of a population strengthens
 23    * the "survival of the fittest" effect of a selector that performs selection
 24    * upon fitness values. A high offset in the fitness values of a population
 25    * lowers the relative difference between the fitness values of the Chromosomes
 26    * in a population.
 27    * </p>
 28    * <h3>Example of applicability</h3>
 29    * <p>
 30    * You are optimizing a black box with <i>n</i> parameters that are mapped
 31    * to {@link org.jgap.IChromosome} instances each having <i>n</i>
 32    * {@link org.jgap.Gene} instances.<br>
 33    * You want to minimize the answer time of the black box and provide
 34    * a {@link org.jgap.FitnessFunction#evaluate(org.jgap.IChromosome)}
 35    * that takes the genes out of the chromosome, put's it's
 36    * {@link org.jgap.Gene#getAllele()}
 37    * values to the parameters and measures the answer time of the black box
 38    * (by invoking it's service to optimize). <br>
 39    * The longer the time takes, the worse it's fitness is, so you have to
 40    * invert the measured times to fitness values:
 41    * <a name="bboptimizer"/>
 42    * <pre>
 43    * <font color="#0011EE">
 44    * class BlackBoxOptimizer extends org.jgap.FitnessFunction{
 45    * private BlackBox bbox;
 46    * <font color="#999999">//Additional code: constructors</font>
 47    * <font color="#999999">...</font>
 48    * public double evaluate(org.jgap.IChromosome chromosome){
 49    * double fitness = 0;
 50    * <font color="#999999">// get the Gene[] & put the parameters into the box.
 51    * ...
 52    * </font>
 53    * long duration = System.currentTimeMillis();
 54    * <font color="#999999">
 55    * // You certainly will use an advanced StopWatch...</font>
 56    * this.bbox.service();
 57    * <font color="#999999">// The black boxes service to optimize.</font>
 58    * duration = System.currentTimeMillis()-duration;
 59    * <font color="#999999">// transform the time into fitness value:</font>
 60    * fitness = double.MAX_VALUE - (double)duration;
 61    * return fitness;
 62    * }
 63    * }
 64    * </font>
 65    * </pre>
 66    * </p>
 67    * <p>
 68    * <h4>We might get the following results (each row stands for a Chromosome,
 69    * the table is a population):</h4>
 70    * <table border="1">
 71    * <tr align="left" valign="top">
 72    * <th>
 73    * duration
 74    * </th>
 75    * <th>
 76    * fitness
 77    * </th>
 78    * <th>
 79    * piece of fitness cake
 80    * </th>
 81    * </tr>
 82    * <tr align="left" valign="top">
 83    * <td>
 84    * 2000
 85    * </td>
 86    * <td>
 87    * 9218868437227403311
 88    * </td>
 89    * <td>
 90    * 33.333333333333336949106088992532 %
 91    * </td>
 92    * </tr>
 93    * <tr align="left" valign="top">
 94    * <td>
 95    * 3000
 96    * </td>
 97    * <td>
 98    * 9218868437227402311
 99    * </td>
 100    * <td>
 101    * 33.333333333333333333333333333333 %
 102    * </td>
 103    * </tr>
 104    * <tr align="left" valign="top">
 105    * <td>
 106    * 4000
 107    * </td>
 108    * <td>
 109    * 9218868437227401311
 110    * </td>
 111    * <td>
 112    * 33.333333333333329717560577674135 %
 113    * </td>
 114    * </tr>
 115    * </table>
 116    * </p>
 117    * <p>
 118    * If any {@link org.jgap.NaturalSelector} performs selection based upon the
 119    * fitness values, it will have to put those values in relation to each other.
 120    * As a fact, the probability to select the Chromosome that contained the black
 121    * box parameters that caused an answer time of 4000 ms is "equal" to the
 122    * probability to select the Chromosome that caused a black box answer time to
 123    * be 2000 ms!
 124    * </p>
 125    * <p>
 126    * Of course one could work around that problem by replacing the
 127    * <tt>Integer.MAX_VALUE</tt> transformation by a fixed maximum value the black
 128    * box would need for the service.
 129    * But what, if you have no guaranteed maximum answer time for the service of
 130    * the black box ?
 131    * Even if you have got one, it will be chosen sufficently high above the
 132    * average answer time thus letting your fitness function return values with a
 133    * high offset in the fitness.
 134    * </p>
 135    * <p>
 136    * <h4>This is, what happens, if you use this instance for fitness
 137    * evaluation:</h4>
 138    * <table border="1">
 139    * <tr align="left" valign="top">
 140    * <th>
 141    * duration
 142    * </th>
 143    * <th>
 144    * fitness
 145    * </th>
 146    * <th>
 147    * piece of fitness cake
 148    * </th>
 149    * </tr>
 150    * <tr align="left" valign="top">
 151    * <td>
 152    * 2000
 153    * </td>
 154    * <td>
 155    * 2001
 156    * </td>
 157    * <td>
 158    * 66.63 %
 159    * </td>
 160    * </tr>
 161    * <tr align="left" valign="top">
 162    * <td>
 163    * 3000
 164    * </td>
 165    * <td>
 166    * 1001
 167    * </td>
 168    * <td>
 169    * 33.33 %
 170    * </td>
 171    * </tr>
 172    * <tr align="left" valign="top">
 173    * <td>
 174    * 4000
 175    * </td>
 176    * <td>
 177    * 1
 178    * </td>
 179    * <td>
 180    * 0.03 %
 181    * </td>
 182    * </tr>
 183    * </table>
 184    * </p>
 185    * <h3>Example of usage</h3>
 186    *
 187    * <p>
 188    * This example shows how to use this instance for cutting fitness offsets.
 189    * It is the same example as used <a href="#bboptimizer">above</a>.
 190    * <pre>
 191    * <font color="#0011EE">
 192    * class BlackBoxOptimizer extends org.jgap.FitnessFunction{
 193    * <font color="#999999">// Additional code: constructors
 194    * ...</font>
 195    * public double evaluate(org.jgap.IChromosome chromosome){
 196    * <font color="#999999">.... // As shown above.</font>
 197    * }
 198    *
 199    * public void startOptimization(org.jgap.Configuration gaConf)
 200    * throws InvalidConfigurationException{
 201    * <font color="#999999">
 202    * // The given Configuration may be preconfigured with
 203    * // NaturalSelector & GeneticOperator instances,.
 204    * // But should not contain a FitnessFunction or BulkFitnessFunction!
 205    * </font>
 206    * <b>gaConf.setBulkFitnessFunction(new BulkFitnessOffsetRemover(this));</b>
 207    * <font color="#999999">// Why does it work? We implement FitnessFunction!
 208    * // Still to do here:
 209    * // - Create a sample chromosome according to your blackbox & set it to
 210    * // the configuration.
 211    * // - Create a random inital Genotype.
 212    * // - loop over a desired amount of generations invoking
 213    * // aGenotype.evolve()..</font>
 214    * }
 215    * }
 216    * </font>
 217    * </pre>
 218    * </p>
 219    * @author Achim Westermann
 220    * @since 2.2
 221    *
 222    */
 223    public class BulkFitnessOffsetRemover
 224    extends BulkFitnessFunction {
 225    /** String containing the CVS revision. Read out via reflection!*/
 226    private final static String CVS_REVISION = "$Revision: 1.10 $";
 227   
 228    /*
 229    * Replace this member by the Configuration as
 230    * soon as Configuration allows bulk fitness function and
 231    * fitness function to be stored both in it.
 232    */
 233    private FitnessFunction m_ff;
 234   
 235    /**@todo This constructor is planned but not possible yet,
 236    * as the Configuration permits bulk fitness function and
 237    * simple fitness function both existing in it at the same time.
 238    */
 239    /*
 240    public BulkFitnessOffsetRemover(Configuration conf){
 241    if(m_activeConfiguration)
 242    }
 243    */
 244    /**
 245    * <p>
 246    * The last generations offset.
 247    * This has to be stored because Chromosomes that were put into the new
 248    * generation's candidate list already have the fitness value without offset
 249    * from their previous evaluation.
 250    * </p>
 251    * <P>
 252    * We try to avoid evaluations of the fitness function
 253    * as it might be expensive, so we reuse fitness values.
 254    * If a Chromosome already has a fitness value >0 this
 255    * previousOffset is added to it's fitness to allow
 256    * comparing this Chromosome's fitness with newly
 257    * evaluated Chromosomes (which still have the offset from the evaluation).
 258    * </p>
 259    */
 260    private double m_previousOffset;
 261   
 262  13 public BulkFitnessOffsetRemover(final FitnessFunction a_ff) {
 263  13 if (a_ff == null) {
 264  1 throw new IllegalArgumentException("Fitness function must not be null!");
 265    }
 266  12 m_ff = a_ff;
 267    }
 268   
 269    /* (non-Javadoc)
 270    * @see org.jgap.BulkFitnessFunction#evaluate(org.jgap.Chromosome[])
 271    */
 272  5 public void evaluate(final Population a_chromosomes) {
 273  5 double offset = Double.MAX_VALUE;
 274  5 double curFitness;
 275  5 Iterator itChromosomes = a_chromosomes.iterator();
 276  5 IChromosome chromosome;
 277  5 while (itChromosomes.hasNext()) {
 278  16 chromosome = (IChromosome) itChromosomes.next();
 279    /*
 280    * This is a workaround:
 281    * We have to check, wethter a Chromosome has
 282    * already been evaluated, because it may be too
 283    * expensive to unconditionally evaluate each Chromosome.
 284    * We use the "caching of fitness values" of the Chromosome.
 285    * But in the current Configuration,
 286    * there is no fittnessFunction: We have a bulk fitness function
 287    * assigned.
 288    * Look at the code of Chromosome.getFitnessValue():
 289    * In that case, a negative value will be returned.
 290    * If a redesign of that method is made, this has to be changed
 291    * here too.. .
 292    */
 293  16 curFitness = chromosome.getFitnessValueDirectly();
 294  16 if (curFitness < 0) {
 295    // OK, get it from our fitness function.
 296  15 curFitness = m_ff.getFitnessValue(chromosome);
 297    // And store it to avoid evaluation of the same Chromosome again:
 298  15 chromosome.setFitnessValue(curFitness);
 299    }
 300    else {
 301    /*
 302    * Those have fitness values already without offset
 303    * of the previous evaluation.
 304    * Reattach it to allow comparison.
 305    * Else these Chromosomes would be the unfittest and
 306    * additionally disallow cutting a huge offset from the others.
 307    */
 308  1 curFitness += m_previousOffset;
 309  1 chromosome.setFitnessValue(curFitness);
 310    }
 311    // search for the offset that is to be cut:
 312  16 offset = (offset < curFitness) ? offset : curFitness;
 313    }
 314    /*
 315    * Now we have the classical evaluated Chromosomes
 316    * and the minimum fitness.
 317    * It would be easy to simply subtract that value from
 318    * each Chromosomes fitness. But in that case the
 319    * unfittest Chromosome would possible have no chance to survive.
 320    * In a WeightedRouletteSelector it would not get
 321    * a single slot to be selected as it's fitness value
 322    * would be zero.
 323    * So we have to leave at least a fitness value of 1.
 324    * Ups, if forgot: Neil throws exceptions, whenever a
 325    * fitness value is below 1 and also does not accept
 326    * assignment of fitness values <1. Ok, so he ensures
 327    * that every Chromosome may survive...
 328    */
 329  5 offset--;
 330  5 m_previousOffset = offset;
 331    // offset cannot be <0... thx to fitness value policy of jgap.
 332    // finally remove the offset from every fitness value:
 333  5 itChromosomes = a_chromosomes.iterator();
 334  5 while (itChromosomes.hasNext()) {
 335  16 chromosome = (IChromosome) itChromosomes.next();
 336  16 chromosome.setFitnessValue(chromosome.getFitnessValue() - offset);
 337    }
 338    }
 339   
 340    /**
 341    * <p>
 342    * Using this instance to remove the fitness offset in the
 343    * populations brings the advantage of getting a selection
 344    * more sensitive to the differences of fitness of the chromosomes.
 345    * </p>
 346    * <p>
 347    * The disadvantage is, that the fitness values are modified.
 348    * The modification is good for jgap's selection method but
 349    * bad for the guys that want to see the success of your
 350    * work, or need a proof that a GA improves over time:
 351    * <br>
 352    * The value of {@link org.jgap.Genotype#getFittestChromosome()}
 353    * does not seem to increase over the generations. Most often
 354    * it becomes worse. This is caused by the fact, that all
 355    * Chromosomes are getting better over time
 356    * (the fitness interval of all Chromosomes gets narrower) and
 357    * the offset that may be cut becomes bigger.
 358    * </p>
 359    * <p>
 360    * If you want to get an absolute value independant from the
 361    * offset that is cut off from the chromosome's fitness value,
 362    * this method has to be used.
 363    * </p>
 364    * <p>
 365    * Stop reading here because a
 366    * </p>
 367    * <h4>Mathematical Proof</h4>
 368    * <p>
 369    * is following.
 370    * How can it work to get the absolute value for all
 371    * Chromosomes fitness values? Some Chromosomes may have lived
 372    * for many generations and everytime their fitness was
 373    * evaluated here, the old offset was added and a new one was
 374    * calculated and subtracted from the fitness value.
 375    * </p>
 376    * <p>
 377    * Each bulk fitness evaluation a Chromosome experiences,
 378    * it's fitness value <i>F</i> get's an addition of the old offset
 379    * <i>O<sub>(n-1)</sub></i>
 380    * and a substraction by the new offset <i>O<sub>n</sub></i>.<br>
 381    * <i><sub>n</sub></i> is the generation index.
 382    *
 383    * <pre>
 384    * F<sub>1</sub> = F<sub>0</sub> + O<sub>0</sub> - O<sub>1</sub>
 385    * F<sub>2</sub> = F<sub>1</sub> + O<sub>1</sub> - O<sub>2</sub>
 386    * F<sub>3</sub> = F<sub>2</sub> + O<sub>2</sub> - O<sub>3</sub>
 387    *
 388    * =>
 389    *
 390    * 1) F<sub>n</sub> = <b>F<sub>(n-1)</sub></b>
 391    * + O<sub>(n-1)</sub> - O<sub>n</sub>
 392    *
 393    * 2) <b>F<sub>(n-1)</sub></b> = F<sub>(n-2)</sub>
 394    * + O<sub>(n-2)</sub> - O<sub>(n-1)</sub>
 395    *
 396    * 2 in 1)
 397    * F<sub>n</sub> = (F<sub>(n-2)</sub> + O<sub>(n-2)</sub>
 398    * - O<sub>(n-1)</sub>) + O<sub>(n-1)</sub> - O<sub>n</sub>
 399    * F<sub>n</sub> = F<sub>(n-2)</sub> + O<sub>(n-2)</sub> - O<sub>n</sub>
 400    *
 401    * We made a step over 2 generations: With the current offset and the
 402    * fitness & offset of the
 403    * "preprevious" generation we can calculate the current fitness.
 404    * We can assume that this generation stepping works for farer steps
 405    * <sub>m</sub> (just continue step 2) until you have a generation step value
 406    * high enough ;-))
 407    *
 408    * => F<sub>n</sub> = F<sub>(n-m)</sub> + O<sub>(n-m)</sub> - O<sub>n</sub>
 409    *
 410    * We want to get the original absolute value of fitness:
 411    *
 412    * 3) m := n
 413    *
 414    * => F<sub>n</sub> = F<sub>0</sub> + O<sub>0</sub> - O<sub>n</sub>
 415    *
 416    * solved to F<sub>0</sub> our original value:
 417    *
 418    * F<sub>0</sub> = F<sub>n</sub> + O<sub>n</sub> - O<sub>0</sub>
 419    *
 420    * And our initial offset {@link #m_previousOffset O<sub>0</sub>} is zero!
 421    * </pre>
 422    * </p>
 423    * <p>
 424    * This shows, that it is possible to compute the original fitness value of a
 425    * Chromosome from it's current fitness value and the
 426    * {@link #m_previousOffset previous offset}
 427    * regardless of the amounts of generations between original evaluation and
 428    * the current generation.
 429    * </p>
 430    * @param a_individuum any Chromosome that is normally being evaluated by
 431    * this <tt>BulkFitnessFunction</tt>
 432    * @return the original fitness value as returned by the registered
 433    * {@link #m_ff fitnessFunction} instance.
 434    */
 435  2 public double getAbsoluteFitness(final IChromosome a_individuum) {
 436  2 double fitness = a_individuum.getFitnessValue();
 437  2 if (fitness < 0.0) {
 438    // OK, get it from our fitness function.
 439  1 fitness = m_ff.getFitnessValue(a_individuum);
 440    // And store it to avoid evaluation of the same Chromosome again:
 441  1 a_individuum.setFitnessValue(fitness);
 442    }
 443    else {
 444    /*
 445    * Those have fitness values already without offset
 446    * of the previous evaluation.
 447    * Reattach it to allow comparison.
 448    * Else these Chromosomes would be the unfittest and
 449    * additionally disallow cutting a huge offset from the others.
 450    */
 451  1 fitness += m_previousOffset;
 452    }
 453  2 return fitness;
 454    }
 455    }