Problem Solving Using GA - 2

Still Confused? Let us see another example. Maybe this will be a bit easier to understand.

In this Example, all significant steps of the genetic algorithm will be explained using a simple example of finding a maximum of the function (sin2(x)-0.5*x)2 with the range of x from 0 to 1.6. Note, that in this range the function has global maximum at x=1.309, and local maximum at x=0.262 as seen in the fig below:
The plot was obtained using MATLAB

Coding and initialization

At first, the variable x has to be represented as a string of symbols. With longer strings process converges usually faster, so less symbols for one string field are used it is the better. While this string may be the sequence of any symbols, the binary symbols "0" and "1" are usually used. In our example, let us use for coding six bit binary numbers having a decimal value of 40x.

Process starts with a random generation of the initial population given in Table 1



Selection and reproduction

Selection of the best members of the population is an important step in the genetic algorithm. Many different approaches can be used to rank individuals. In our example the ranking function is given. Highest rank has member number 6 and lowest rank has member number 3. Members with higher rank should have higher chances to reproduce.The probability of reproduction for each member can be obtained as fraction of the sum of all objective function values. This fraction is shown in the last column of the Table.

Using a random reproduction process the following population arranged in pairs could be generated:
101101 -> 45 110001 -> 49 100101 -> 37 110001 -> 49
100111 -> 39 101101 -> 45 110001 -> 49 101000 -> 40



Reproduction

101101 -> 45 110001 -> 49 100101 -> 37 110001 -> 49
100111 -> 39 101101 -> 45 110001 -> 49 101000 -> 40

If size of the population from one generation to another is the same,therefore two parents should generate two children. By combining two strings two another strings should be generated. The simplest way to do it is to split in half each of the parent string and exchange
substrings between parents. For example from parent strings 010100 and 100111 the following child strings will be generated 010111 and 100100. This process is known as the crossover and
resultant children are shown below
101111 -> 47 110101 -> 53 100001 -> 33 110000 -> 48
100101 -> 37 101001 -> 41 110101 -> 53 101001 -> 41

Mutation

On the top of properties inherited from parents they are acquiring some new random properties. This process is known as mutation. In most cases mutation generates low
ranked children, which are eliminated in reproduction process.

Sometimes however, the mutation may introduce a better individual with a new property into. This prevents process of reproduction from degeneration. In genetic algorithms mutation plays usually secondary role. Mutation rate is usually assumed on the level much below 1%. In our
example mutation is equivalent to the random bit change of a given pattern.

In this simple example with short strings and small population with a typical mutation rate of 0.1%, our patterns remain practically unchanged by the mutation process. The second generation for our example is shown in Table 2

Note, that two identical highest ranking members of the second generation are very close to the solution x=1.309. The randomly chosen parents for third generation are

010111 -> 47 110101 -> 53 110000 -> 48 101001 -> 41
110101 -> 53 110000 -> 48 101001 -> 41 110101 -> 53

which produces following children:

010101 -> 21 110000 -> 48 110001 -> 49 101101 -> 45
110111 -> 55 110101 -> 53 101000 -> 40 110001 -> 49

The best result in the third population is the same as in the second one. By careful inspection of all strings from second or third generation one may conclude that using crossover, where strings are always split into half, the best solution 110100 -> 52 will never be reached no matter how many generations are created.

The genetic algorithm is very rapid and it leads to a good solution within a few generations. This solution is usually close to global maximum, but may not the best.