This section describes the differences between genetic algorithms and traditional optimum search methods.

Search Space

A standard genetic algorithm deals with a set (a population) of possible solutions (individuals) of a problem.  Each individual is a point in the search space, so we can think of the genetic algorithm as a multi-point optimization technique for multi-dimensional spaces.  Usually, the size of the population is in the range from 20 to 200 or 300.  The majority of traditional optimization methods explores 1, 2, or 3 points in the search space on each iteration.

Traditional methods require a starting point to begin the optimization.  Often the quality of the final solution is very dependent upon the position of this starting point in the search space.  The choice of a starting point plays a significant role in finding a good solution to the problem with a large number of local optima.  Genetic algorithms, which offer many solutions and can search multiple points simultaneously, do not suffer as much from this drawback.

Mapping Variables

If a standard genetic algorithm is used to optimize a function of continuous variables, it does not work with the problem variables themselves.  Instead it uses "mapping" to code each continuous variable (a parameter of a problem called a chromosome) into an internal binary string of fixed length.  Such a mapping transforms the entire range of a continuous variable into a limited set of binary coded numbers.  The bigger the binary string, the larger the search space.  Obviously, to perform the mapping we need to set the minimum and maximum boundaries on the variable.

Consider a simple function of one variable: f(x)=x^2.  In order for the genetic algorithm to find a minimum value for the function, you need to limit the search space for x by some range.  For example, you could set an interval such as [-5,5] as the search range for the genetic algorithm.  Next, use an 8-bit binary string to code the values of the input variable from the range [-5,5].

The mapping scheme for two boundary values looks like the following:

In general, if we want to map a continuous variable X within the range [Xmin,Xmax] into a discreet variable Y with the integer range [Ymin,Ymax], we use the following formulas:

Forward transformation (X ⇒ Y):

     Y = Round(Ymin + (X-Xmin) * ((Ymax-Ymin)/(Xmax - Xmin)))    (1)

Backward transformation (X ⇐ Y):

     X = Xmin + (Y-Ymin) * (Xmax-Xmin)/(Ymax-Ymin)     (2)

In our case, the variable Y is an 8-bit binary variable.  Therefore, the whole continuous range [-5,5] of the input variable X is transformed into a finite set of 256 numbers of the internal (in the sense of genetic algorithm) variable Y.  Such discretization leads to two interesting conclusions.

1.   Each of the 256 values of Y represents all possible values (infinite number) of X with a small subrange.  The length of this subrange (called the discretization step) equals (Xmax-Xmin)/(Ymax-Ymin), so in our case the discretization step = 0.039215686...  In accordance with formula (1) the following table represents the correspondence between X and Y while performing the forward mapping:

This step significantly reduces the size of the search space of the input variable X, and allows the genetic algorithm to find an optimal bit combination within the internal variable Y to solve the problem.

2.  The genetic algorithm does not work with variable X but with the internal variable Y.  After the algorithm stops, the back transformation Y ⇒ X must be performed.  Using the formula for the back transformation, we can easily build the following table which maps the Y value to the corresponding X value:

The point X = 0 is exactly on the boundary between the two adjacent subranges with Y values of 127 and 128.  So the genetic algorithm will never obtain the exact answer X = 0.0000000 as the minimum solution while optimizing the parabola f(x) = x^2  when the symmetric range for X is [-5,5].  Instead, the genetic algorithm will get either 0.0196078 or -0.0196078, i.e., the half of the discretization step with either sign.

Nevertheless, it is easy to show that the exact solution X = 0.000000 still may be obtained using a non-symmetric range for X with the following values of Xnewmin and Xnewmax:

           Xnewmax=Xmax

           Xnewmin=Xmin+(Xmax-Xmin)/2^N,

or

           Xnewmax=Xmax-(Xmax-Xmin)/2^N

           Xnewmin=Xmin,

where N is the length of the bit string representing Y (N=8 in our case).

For example, using the range [-4.9609375, 5] will produce the exact minimum solution of X=0.