org.jgap.impl

Class BulkFitnessOffsetRemover

java.lang.Object

org.jgap.BulkFitnessFunction

org.jgap.impl.BulkFitnessOffsetRemover

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, ICloneable

public class BulkFitnessOffsetRemover
extends BulkFitnessFunction

Takes away the fitness offset of the population to evolve. The fitness function values of the population of IChromosome instances will start from a minimum of 1 afterwards.

The removal of an offset in the fitness values of a population strengthens the "survival of the fittest" effect of a selector that performs selection upon fitness values. A high offset in the fitness values of a population lowers the relative difference between the fitness values of the Chromosomes in a population.

Example of applicability

You are optimizing a black box with n parameters that are mapped to IChromosome instances each having n Gene instances.
You want to minimize the answer time of the black box and provide a FitnessFunction.evaluate(org.jgap.IChromosome) that takes the genes out of the chromosome, put's it's Gene.getAllele() values to the parameters and measures the answer time of the black box (by invoking it's service to optimize).
The longer the time takes, the worse it's fitness is, so you have to invert the measured times to fitness values:

 
 class BlackBoxOptimizer extends org.jgap.FitnessFunction{
   private BlackBox bbox;
   //Additional code: constructors
   ...
   public double evaluate(org.jgap.IChromosome chromosome){
     double fitness = 0;
     // get the Gene[] & put the parameters into the box.
     ...
     
     long duration = System.currentTimeMillis();
 
 // You certainly will use an advanced StopWatch...
     this.bbox.service();
 // The black boxes service to optimize.
     duration = System.currentTimeMillis()-duration;
     // transform the time into fitness value:
     fitness = double.MAX_VALUE - (double)duration;
     return fitness;
   }
 }
 
 

We might get the following results (each row stands for a Chromosome, the table is a population):

duration	fitness	piece of fitness cake
2000	9218868437227403311	33.333333333333336949106088992532 %
3000	9218868437227402311	33.333333333333333333333333333333 %
4000	9218868437227401311	33.333333333333329717560577674135 %

If any NaturalSelector performs selection based upon the fitness values, it will have to put those values in relation to each other. As a fact, the probability to select the Chromosome that contained the black box parameters that caused an answer time of 4000 ms is "equal" to the probability to select the Chromosome that caused a black box answer time to be 2000 ms!

Of course one could work around that problem by replacing the Integer.MAX_VALUE transformation by a fixed maximum value the black box would need for the service. But what, if you have no guaranteed maximum answer time for the service of the black box ? Even if you have got one, it will be chosen sufficently high above the average answer time thus letting your fitness function return values with a high offset in the fitness.

This is, what happens, if you use this instance for fitness evaluation:

duration	fitness	piece of fitness cake
2000	2001	66.63 %
3000	1001	33.33 %
4000	1	0.03 %

Example of usage

This example shows how to use this instance for cutting fitness offsets. It is the same example as used above.

 
 class BlackBoxOptimizer extends org.jgap.FitnessFunction{
   // Additional code: constructors
   ...
   public double evaluate(org.jgap.IChromosome chromosome){
     .... // As shown above.
   }

   public void startOptimization(org.jgap.Configuration gaConf)
       throws InvalidConfigurationException{
     
     // The given Configuration may be preconfigured with
     // NaturalSelector & GeneticOperator instances,.
     // But should not contain a FitnessFunction or BulkFitnessFunction!
 
     gaConf.setBulkFitnessFunction(new BulkFitnessOffsetRemover(this));
     // Why does it work? We implement FitnessFunction!
     // Still to do here:
     // - Create a sample chromosome according to your blackbox & set it to
      //   the configuration.
     // - Create a random inital Genotype.
     // - loop over a desired amount of generations invoking
      //   aGenotype.evolve()..
   }
 }
 
 

Since:

2.2

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
BulkFitnessOffsetRemover(FitnessFunction a_ff)

Method Summary

Modifier and Type	Method and Description
java.lang.Object	clone() Override in your implementation if necessary.
void	evaluate(Population a_chromosomes) Calculates and sets the fitness values on each of the given Chromosomes via their setFitnessValue() method.
double	getAbsoluteFitness(IChromosome a_individuum) 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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BulkFitnessOffsetRemover

public BulkFitnessOffsetRemover(FitnessFunction a_ff)

Method Detail

evaluate

public void evaluate(Population a_chromosomes)

Description copied from class: BulkFitnessFunction

Calculates and sets the fitness values on each of the given Chromosomes via their setFitnessValue() method.

Specified by:

evaluate in class BulkFitnessFunction

Parameters:

a_chromosomes - list of Chromosomes for which the fitness values must be computed and set

getAbsoluteFitness

public double getAbsoluteFitness(IChromosome a_individuum)

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.

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:
The value of 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.

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.

Stop reading here because a

Mathematical Proof

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.

Each bulk fitness evaluation a Chromosome experiences, it's fitness value F get's an addition of the old offset O_(n-1) and a substraction by the new offset O_n.
_n is the generation index.

 F1 = F0 + O0 - O1
 F2 = F1 + O1 - O2
 F3 = F2 + O2 - O3

 =>

 1) Fn = F(n-1)
 + O(n-1) - On

 2) F(n-1) = F(n-2)
 + O(n-2) - O(n-1)

 2 in 1)
    Fn = (F(n-2) + O(n-2)
 - O(n-1)) + O(n-1) - On
    Fn = F(n-2) + O(n-2) - On

 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
 m (just continue step 2) until you have a generation step value
 high enough ;-))

 => Fn = F(n-m) + O(n-m) - On

 We want to get the original absolute value of fitness:

 3) m := n

 => Fn = F0 + O0 - On

 solved to F0 our original value:

 F0 = Fn + On - O0

 And our initial offset O0 is zero!
 

This shows, that it is possible to compute the original fitness value of a Chromosome from it's current fitness value and the previous offset regardless of the amounts of generations between original evaluation and the current generation.

Parameters:

a_individuum - any Chromosome that is normally being evaluated by this BulkFitnessFunction

Returns:

the original fitness value as returned by the registered fitnessFunction instance.

clone

public java.lang.Object clone()

Description copied from class: BulkFitnessFunction

Override in your implementation if necessary.

Specified by:

clone in interface ICloneable

Overrides:

clone in class BulkFitnessFunction

Returns:

deep clone of current instance

Since:

3.2