KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgap > impl > BulkFitnessOffsetRemover


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 JavaDoc CVS_REVISION = "$Revision: 1.11 $";
227
228   /*
229    * Replace this member by the Configuration as soon as Configuration allows
230    * bulk fitness function and fitness function to be stored both in it.
231    */
232   private FitnessFunction m_ff;
233
234   /**@todo This constructor is planned but not possible yet,
235    * as the Configuration permits bulk fitness function and
236    * simple fitness function both existing in it at the same time.
237    */
238   /*
239     public BulkFitnessOffsetRemover(Configuration conf){
240    if(m_activeConfiguration)
241     }
242    */
243   /**
244    * <p>
245    * The last generations offset.
246    * This has to be stored because Chromosomes that were put into the new
247    * generation's candidate list already have the fitness value without offset
248    * from their previous evaluation.
249    * </p>
250    * <P>
251    * We try to avoid evaluations of the fitness function
252    * as it might be expensive, so we reuse fitness values.
253    * If a Chromosome already has a fitness value >0 this
254    * previousOffset is added to it's fitness to allow
255    * comparing this Chromosome's fitness with newly
256    * evaluated Chromosomes (which still have the offset from the evaluation).
257    * </p>
258    */
259   private double m_previousOffset;
260
261   public BulkFitnessOffsetRemover(final FitnessFunction a_ff) {
262     if (a_ff == null) {
263       throw new IllegalArgumentException JavaDoc("Fitness function must not be null!");
264     }
265     m_ff = a_ff;
266   }
267
268   /* (non-Javadoc)
269    * @see org.jgap.BulkFitnessFunction#evaluate(org.jgap.Chromosome[])
270    */
271   public void evaluate(final Population a_chromosomes) {
272     double offset = Double.MAX_VALUE;
273     double curFitness;
274     Iterator itChromosomes = a_chromosomes.iterator();
275     IChromosome chromosome;
276     while (itChromosomes.hasNext()) {
277       chromosome = (IChromosome) itChromosomes.next();
278       /*
279        * This is a workaround:
280        * We have to check, wethter a Chromosome has
281        * already been evaluated, because it may be too
282        * expensive to unconditionally evaluate each Chromosome.
283        * We use the "caching of fitness values" of the Chromosome.
284        * But in the current Configuration,
285        * there is no fittnessFunction: We have a bulk fitness function
286        * assigned.
287        * Look at the code of Chromosome.getFitnessValue():
288        * In that case, a negative value will be returned.
289        * If a redesign of that method is made, this has to be changed
290        * here too.. .
291        */
292       curFitness = chromosome.getFitnessValueDirectly();
293       if (curFitness < 0) {
294         // OK, get it from our fitness function.
295 curFitness = m_ff.getFitnessValue(chromosome);
296         // And store it to avoid evaluation of the same Chromosome again:
297 chromosome.setFitnessValue(curFitness);
298       }
299       else {
300         /*
301          * Those have fitness values already without offset
302          * of the previous evaluation.
303          * Reattach it to allow comparison.
304          * Else these Chromosomes would be the unfittest and
305          * additionally disallow cutting a huge offset from the others.
306          */
307         curFitness += m_previousOffset;
308         chromosome.setFitnessValue(curFitness);
309       }
310       // search for the offset that is to be cut:
311 offset = (offset < curFitness) ? offset : curFitness;
312     }
313     /*
314      * Now we have the classical evaluated Chromosomes
315      * and the minimum fitness.
316      * It would be easy to simply subtract that value from
317      * each Chromosomes fitness. But in that case the
318      * unfittest Chromosome would possible have no chance to survive.
319      * In a WeightedRouletteSelector it would not get
320      * a single slot to be selected as it's fitness value
321      * would be zero.
322      * So we have to leave at least a fitness value of 1.
323      * Ups, if forgot: Neil throws exceptions, whenever a
324      * fitness value is below 1 and also does not accept
325      * assignment of fitness values <1. Ok, so he ensures
326      * that every Chromosome may survive...
327      */
328     offset--;
329     m_previousOffset = offset;
330     // offset cannot be <0... thx to fitness value policy of jgap.
331 // finally remove the offset from every fitness value:
332 itChromosomes = a_chromosomes.iterator();
333     while (itChromosomes.hasNext()) {
334       chromosome = (IChromosome) itChromosomes.next();
335       chromosome.setFitnessValue(chromosome.getFitnessValue() - offset);
336     }
337   }
338
339   /**
340    * <p>
341    * Using this instance to remove the fitness offset in the
342    * populations brings the advantage of getting a selection
343    * more sensitive to the differences of fitness of the chromosomes.
344    * </p>
345    * <p>
346    * The disadvantage is, that the fitness values are modified.
347    * The modification is good for jgap's selection method but
348    * bad for the guys that want to see the success of your
349    * work, or need a proof that a GA improves over time:
350    * <br>
351    * The value of {@link org.jgap.Genotype#getFittestChromosome()}
352    * does not seem to increase over the generations. Most often
353    * it becomes worse. This is caused by the fact, that all
354    * Chromosomes are getting better over time
355    * (the fitness interval of all Chromosomes gets narrower) and
356    * the offset that may be cut becomes bigger.
357    * </p>
358    * <p>
359    * If you want to get an absolute value independant from the
360    * offset that is cut off from the chromosome's fitness value,
361    * this method has to be used.
362    * </p>
363    * <p>
364    * Stop reading here because a
365    * </p>
366    * <h4>Mathematical Proof</h4>
367    * <p>
368    * is following.
369    * How can it work to get the absolute value for all
370    * Chromosomes fitness values? Some Chromosomes may have lived
371    * for many generations and everytime their fitness was
372    * evaluated here, the old offset was added and a new one was
373    * calculated and subtracted from the fitness value.
374    * </p>
375    * <p>
376    * Each bulk fitness evaluation a Chromosome experiences,
377    * it's fitness value <i>F</i> get's an addition of the old offset
378    * <i>O<sub>(n-1)</sub></i>
379    * and a substraction by the new offset <i>O<sub>n</sub></i>.<br>
380    * <i><sub>n</sub></i> is the generation index.
381    *
382    * <pre>
383    * F<sub>1</sub> = F<sub>0</sub> + O<sub>0</sub> - O<sub>1</sub>
384    * F<sub>2</sub> = F<sub>1</sub> + O<sub>1</sub> - O<sub>2</sub>
385    * F<sub>3</sub> = F<sub>2</sub> + O<sub>2</sub> - O<sub>3</sub>
386    *
387    * =>
388    *
389    * 1) F<sub>n</sub> = <b>F<sub>(n-1)</sub></b>
390    * + O<sub>(n-1)</sub> - O<sub>n</sub>
391    *
392    * 2) <b>F<sub>(n-1)</sub></b> = F<sub>(n-2)</sub>
393    * + O<sub>(n-2)</sub> - O<sub>(n-1)</sub>
394    *
395    * 2 in 1)
396    * F<sub>n</sub> = (F<sub>(n-2)</sub> + O<sub>(n-2)</sub>
397    * - O<sub>(n-1)</sub>) + O<sub>(n-1)</sub> - O<sub>n</sub>
398    * F<sub>n</sub> = F<sub>(n-2)</sub> + O<sub>(n-2)</sub> - O<sub>n</sub>
399    *
400    * We made a step over 2 generations: With the current offset and the
401    * fitness & offset of the
402    * "preprevious" generation we can calculate the current fitness.
403    * We can assume that this generation stepping works for farer steps
404    * <sub>m</sub> (just continue step 2) until you have a generation step value
405    * high enough ;-))
406    *
407    * => F<sub>n</sub> = F<sub>(n-m)</sub> + O<sub>(n-m)</sub> - O<sub>n</sub>
408    *
409    * We want to get the original absolute value of fitness:
410    *
411    * 3) m := n
412    *
413    * => F<sub>n</sub> = F<sub>0</sub> + O<sub>0</sub> - O<sub>n</sub>
414    *
415    * solved to F<sub>0</sub> our original value:
416    *
417    * F<sub>0</sub> = F<sub>n</sub> + O<sub>n</sub> - O<sub>0</sub>
418    *
419    * And our initial offset {@link #m_previousOffset O<sub>0</sub>} is zero!
420    * </pre>
421    * </p>
422    * <p>
423    * This shows, that it is possible to compute the original fitness value of a
424    * Chromosome from it's current fitness value and the
425    * {@link #m_previousOffset previous offset}
426    * regardless of the amounts of generations between original evaluation and
427    * the current generation.
428    * </p>
429    * @param a_individuum any Chromosome that is normally being evaluated by
430    * this <tt>BulkFitnessFunction</tt>
431    * @return the original fitness value as returned by the registered
432    * {@link #m_ff fitnessFunction} instance.
433    */
434   public double getAbsoluteFitness(final IChromosome a_individuum) {
435     double fitness = a_individuum.getFitnessValue();
436     if (fitness < 0.0) {
437       // OK, get it from our fitness function.
438 fitness = m_ff.getFitnessValue(a_individuum);
439       // And store it to avoid evaluation of the same Chromosome again:
440 a_individuum.setFitnessValue(fitness);
441     }
442     else {
443       /*
444        * Those have fitness values already without offset
445        * of the previous evaluation.
446        * Reattach it to allow comparison.
447        * Else these Chromosomes would be the unfittest and
448        * additionally disallow cutting a huge offset from the others.
449        */
450       fitness += m_previousOffset;
451     }
452     return fitness;
453   }
454
455   /**
456    * @return deep clone of current instance
457    *
458    * @author Klaus Meffert
459    * @since 3.2
460    */
461   public Object JavaDoc clone() {
462     FitnessFunction ff = (FitnessFunction)m_ff.clone();
463     BulkFitnessOffsetRemover result = new BulkFitnessOffsetRemover(ff);
464     return result;
465   }
466 }
467
Popular Tags