Clone wiki

GAF / How to Encode Parameters

How to Encode Parameters

Most GAs are designed to optimise a set of parameters, for example, if the GA was being used to try and create a new rear wing for a Formula 1 Grand Prix car, the parameters might include length leading edge radius, angle of incidence etc. Typically these parameters are of differing units of measure (degrees, millimeters etc.) in addition the range of values for each parameter will be different also.

The simplest way to deal with the differences mentioned above is to normalise the parameters.

Lets say we have three variables, x, y and z, with the following ranges;

x: -2.5 + 9.5 (range is 12 with an offset of -2.5)
y: 0 to 1000 (range is 1000 with an offset of 0)
x:-50 to 0 (range is 50 with an offset of -50)

Assuming that we are not working with integers we need to determine the resolution i.e. how many values we need between the range. For example, if we are happy with say a million values between the upper and lower values in the ranges, 20 bits per variable will suffice (2^20 = 1048576). Based on this we can determine how many bits each variable will use.

Each variable can have any appropriate number of bits, however, let's say we use the same bit length of 20 bits for x, y and z. This gives us three values in our chromosome each with a bit length of 20, therefore, we will need a chromosome that is 60 bits long.

The GA will continually generate solutions (chromosomes) 60 bits long. In order to retrieve the real domain values from our chromosome, we use a range constant.

This is calculated as follows;

rangeConstant = range /(System.Math.Pow(2, numberOfBits) - 1);

To simplify things, the GAF has a helper method called GAF.Math.GetRangeConstant(), for example with a range for the value of 200 and a parameter bit length of 20, the following code could be used:

rangeConstant = GAF.Math.GetRangeConstant (200, 20);

Here is an example of the range constant approach for x, y and z.

// range constant for x
var rcx = GAF.Math.GetRangeConstant(12, 20);

// range constant for y
var rcy = GAF.Math.GetRangeConstant(1000, 20);

// range constant for z
var rcz = GAF.Math.GetRangeConstant(50, 20);

// when evaluating the fitness simply retrieve the 20 bit values as integers 
// from the chromosome e.g.
var x1 =Convert.ToInt32(chromosome.ToBinaryString(0, 20), 2);
var y1 =Convert.ToInt32(chromosome.ToBinaryString(20, 20), 2);
var z1 =Convert.ToInt32(chromosome.ToBinaryString(40, 20), 2);

// multiply by the appropriate range constant and adjust for any offset 
// in the range to get the real values
double x = (x1 * rcx) - 2.5;
double y = (y1 * rcy);
double y = (y1 * rcz) - 50;

This simple approach ensures that any given binary string will always decode to valid, within range, values for each of our variables. Once we have the real values, we can test for fitness and the GA will do the rest.