Week 4.1 - Genetic Algorithm

AIM:

To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function and Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Introduction:

The idea behind GA´s is to extract optimization strategies nature uses successfully - known as Darwinian Evolution and transform them for application in mathematical optimization theory to find the global optimum in a defined phase space.

One could imagine a population of individual "explorers" sent into the optimization phase-space. Each explorer is defined by its genes, what means, its position inside the phase-space is coded in his genes. Every explorer has the duty to find a value of the quality of his position in the phase space. (Consider the phase-space being a number of variables in some technological process, the value of quality of any position in the phase space - in other words: any set of the variables - can be expressed by the yield of the desired chemical product.) Then the struggle of "life" begins. The three fundamental principles are

1. Selection
2. Mating/Crossover
3. Mutation

Only explorers (= genes) sitting on the best places will reproduce and create a new population. This is performed in the second step (Mating/Crossover). The "hope" behind this part of the algorithm is, that "good" sections of two parents will be recombined to yet better fitting children. In fact, many of the created children will not be successful (as in biological evolution), but a few children will indeed fulfill this hope. These "good" sections are named in some publications as building blocks

Algorithm

Initial Population

As described above, a gene is a string of bits. The initial population of genes (bitstrings) is usually created randomly. The length of the bitstring is depending on the problem to be solved (see section Applications).

Selection

Selection means to extract a subset of genes from an existing (in the first step, from the initial -) population, according to any definition of quality. In fact, every gene must have a meaning, so one can derive any kind of a quality measurement from it - a "value". Following this quality "value" (fitness), Selection can be performed e.g. by Selection proportional to fitness:

1. Consider the population being rated, that means: each gene has a related fitness. (How to obtain this fitness will be explained in the Application-section. ) The higher the value of the fitness, the better.

2. The mean-fitness of the population will be calculated.

3. Every individuum (=gene) will be copied as often to the new population, the better it fitness is, compared to the average fitness. E.g.: the average fitness is 5.76, the fitness of one individuum is 20.21. This individuum will be copied 3 times. All genes with a fitness at the average and below will be removed.

4. Following this steps, one can prove, that in many cases the new population will be a little smaller, than the old one. So the new population will be filled up with randomly chosen individua from the old population to the size of the old one.

Remember, that there are a lot of different implementations of these algorithms. For example the Selection module is not always creating constant population sizes. In some implementations the size of the population in dynamic. Furthermore, there exist a lot of other types of selection algorithms (the most important ones are: Proportional Fitness, Binary Tournament, Rank Based). I restrict myself to describe just the most common implementations in this short article. To get a deeper insight to this topic take a look to the Recommended Reading section.

Mating/Crossover

The next steps in creating a new population are the Mating and Crossover ,As described in the previous section there exist also a lot of different types of Mating/Crossover. One easy to understand type is the random mating with a defined probability and the b_nX crossover type. This type is described most often, as the parallel to the Crossing Over in genetics is evident:

1. P_M percent of the individua of the new population will be selected randomly and mated in pairs.

2. A crossover point will be chosen for each pair

3. The information after the crossover-point will be exchanged between the two individua of each pair.

In fact, more often a slightly different algorithm called b_uX is used. This crossover type usually offers higher performance in the search.

1. P_M percent of the individua of the new population will be selected randomly and mated in pairs.

2. With the probability P_C, two bits in the same position will be exchanged between the two individua. Thus not only one crossover point is chosen, but each bit has a certain probability to get exchanged with its counterpart in the other gene. (This is called the uniform operator)

Mutation

The last step is the Mutation, with the sense of adding some effect of exploration of the phase-space to the algorithm. The implementation of Mutation is - compared to the other modules - fairly trivial: Each bit in every gene has a defined Probability P to get inverted.

The effect of mutation is in some way a antagonist to selection:

Application(s) - Coding Problems

Three important applications will be mentioned here:

1. Parameter Estimation
2. Subset Selection
3. Sequencing

Though it is impossible to explain these three categories in detail, especially implementation of Subset Selection and Sequencing shows much more traps than the Parameter Estimation problem. For better understanding of this topic, I will describe the Parameter Estimation in more details. The other two points are well explained in Lucasius et.al.

Parameter Estimation

Consider a statistical model f(x₁, x₂, ... x_i) with parameters (a₁, a₂, ... a_j ) and the data set (y₁, y₂, ... y_k ). The task is to calculate the estimated parameters (a'₁, a'₂, ... a'_j ).

In many cases the calculation of the estimated parameters is possible with an mathematically derived formula (see Linear Regression). But in many interesting instances this is not possible. Furthermore, every time varying the model, a new derivation of the solution is necessary. Using GA´s can be a good solution in these (often rather complex) problems.

Programe

clear all

close all

clc

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

num_causes=50

f = get_stalagmaite

%study 1 statical behavior

for i=1:num_causes

[inputs,fopt(i)] = ga(@stalagmite,2);

xopt(i) = inputs(1);

yopt(i) = inputs(2);

end

figure(1)

subplot(2,1,1)

hold on

surfc(x,y,f)

shading interp

plot3(xopt,yopt,fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','auto')

title('unbounded inputs')

subplot(2,1,2)

plot(fopt)

xlable('iterations')

ylable('function maxima')

% study 2 - statistical behavior

for i = 1:num_causes

[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);

xopt(i) = inputs(i);

yopt(i) = inputs(i);

end

study2_time = toc

figure(2)

subplot(2,1,1)

hold on

surfc(x,y,f)

shading interp

plot 3 (xopt,yopt,fopt,'marker','0','markersize','5','markerface color','r')

title('bounded inputs')

subplot(2,1,2)

plot(fopt)

xlable('interations')

ylabel('function maxima')

%study 3 increasing GA interations

options = optimoptions('ga');

options = optimoptions(options,options,'populations size',170);

for i = 1:num_causes

[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);

xopt(i) = inputs(i);

yopt(i) = inputs(i);

end

study3_time = toc

figure(3)

subplot(2,1,1)

hold on

surfc(x,y,f)

shading interp

plot 3 (xopt,yopt,fopt,'marker','0','markersize','5','markerface color','r')

title('bounded inputs with population as 250')

subplot(2,1,2)

plot(fopt)

xlable('iterations')

ylabel('function maxima')