Evaluating the Global Maxima of a Stalagmite function using Genetic Algorithm.

Concept of Genetic Algorithm:-

Genetic Algorithm starts from a population of possible solutions (called individuals) and move towards the optimal one by applying the principle of Darwinian evolution theory i.e., survival of the fittest. Objects forming possible solution sets to the original problem is called phenotype and the encoding (representation) of the individuals in the GA is called genotype.An individual consists a genotype and a fitness function. Fitness represents the quality of the solution (normally called fitness function). It forms the basis for selecting the individuals and thereby facilitates improvements.

Stalagmite function:-

`f_(1x) = [sin(5.1pix+0.5)]^6`

`f_(1y) = [sin(5.1piy+0.5)]^6`

`f_(2x) = exp[-4ln2(x-0.0667)^2/0.64]`

`f_(2y) = exp[-4ln2(y-0.0667)^2/0.64]`

Procedure/Explaination of the code:-

1) Code to optimise the stalagmite function and to find the global maxima of the function.

In this step, 1-D array is created using linspace command and using these values, a 2D array is created using built in meshgrid command. Then, each value of the 2D vector 'xx' and 'yy' is stored in the variable 'input_vector' which is a row vector containing two columns. The values stored in the variable 'input_vector' are then passed to the stalagmite function which is used to evaluate the stalagmite function.

clear all
close all
clc

%Defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Creating a 2D mesh
[xx yy] = meshgrid(x,y);

%Evaluating the function
for  i = 1:length(xx)
       for j = 1:length(yy)
    
        input_vector(1) = xx(i,j);
        input_vector(2) = yy(i,j);
        f(i,j) = stalagmite(input_vector);
        
    end
end

After the stalagmite function is evaluated, the result is then plotted using 'surfc' command since stalagmite function is a 3D function. The inbuilt 'ga' command is then used which optimises the stalagmite function and finds the optimum value and the location at which it occurs.

'x = ga(fun,nvars)' finds a local unconstrained minimum,x, to the objective function, nvars is the number of design variables of function.

%Plotting
surfc(xx,yy,f);
xlabel('x axis')
ylabel('y axis')
shading interp
[inputs, fval] = ga(@stalagmite, 2)

2) Code to evaluate the stalagmite function(Function definition):-

In this step, the values obtained from the previous step are passed as an input to the stalagmite function which evaluates the values of `f1_x , f1_y , f2_x , f2_y`. Finally, the function is inverted using minus sign which is done deliberately since genetic algorithm always finds the minimum value.

function f = stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);
f1_x = (sin(5.1*pi*x+0.5))^6;
f1_y = (sin(5.1*pi*y+0.5))^6;
    
f2_x = exp((-4*log(2)*(x-0.0667)^2/0.64));
f2_y = exp((-4*log(2)*(y-0.0667)^2/0.64));

g= f1_x*f1_y*f2_x*f2_y;
f = -g;
end

Now, whenever the program is made to run, it gives different results everytime and therefore different studies are carried out so that the program gives the same result everytime the program is executed.

In the subsequent studies, the genetic algorithm is made to run 100 times and f = get_stalagmite(x,y) is used to evaluate the stalagmite function.

3-(i) Study-1:- Statistical behaviour

The function value and its location (x and y co-ordinates) are obtained using the inbuilt ga function. The results are then plotted in the same figure window using the 'subplot' command in which the 1st graph is plotted aganist function value and x,y co-ordinates , whereas the 2nd graph shows the minimum value of function against the number of iterations.

clear all
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 100;
f = get_stalagmite(x,y)

%STUDY - 1 -STATISTICAL BEHAVIOUR

for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
    
end

[xx yy] = meshgrid(x,y);

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs');
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

3-(ii) Study-2:- Setting upper and lower bounds(Restricting the searchspace.)

In Study 2, the search space of the genetic algorithm is restricted i.e the search space is limited between (0,0) and (0.6,0.6) , therefore the genetic algorithm which uses random sampling method cannot go below (0,0) and beyond (0.6,0.6). The tic and toc commands are used to register the time taken by the algorithm to evaluate the results.

'x = ga(func,nvars,A,B,Aeq,Beq,lb,ub)' defines a set of lower and upper bounds on the design variables,x, so that a solution is found in the range lb ≤ x ≤ ub. since there are no linear equalities, Aeq and Beq is set as [].

%STUDY - 2 -STATISTICAL BEHAVIOUR
tic
num_cases = 100;
[xx yy] = meshgrid(x,y);
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

3-(iii)Study-3:- Increasing Initial population size.

In the 3rd study, the population size is increased to 170 since genetic algorithm takes initial population as 50. If the initial population is too small, GA finds the local minima and not the global minima which was happening in study 2. This study takes more time as compared to study 1 and study 2 which is the major drawback.

'x = ga(func,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)' minimizes with the default optimization parameters replaced by values in options. Since nonlinear constraints do not exist, A,b,Aeq,beq,nonlcon are set as [].

%Study -3 Increasing GA Iterations

options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',170)
num_cases = 100;
tic
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_3 = toc
figure(3)
subplot(2,1,1)
hold on
surf(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

   

• Output:-

1) The below figure shows the stalagmite function.

2)This figure shows the plot obtained in study 1. From the figure, it is clear that the function value oscillates between -1 and 0. As the number of iterations increases, the function value obtained is different which is obviously not desirable.

3)This plot obtained through study 2 gives quite good results as compared to study 1 since we have restricted the workspace of genetic algorithm.

4)This plot obtained through study 3 gives the accurate result and a single value is obtained on every iteration except for one iteration. The function value obtained is -1. This study takes comparatively more time which is the main drawback.

The value of (x,y) coordinates are (0.0668,0.0668)

X-co-ordinate:-

Y-co-ordinate:-

Below figure shows the time taken by study 2 and study 3.

The function value obtained is -1.

Function Value:-

Errors faced/Screenshot:-

Steps taken to overcome the error:-

The error was rectified by defining only one input to the function definition and then storing one value of input vector in 'x' variable and other value in 'y' variable.

References:-

https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

http://www.cs.cmu.edu/~02317/slides/lec_8.pdf

https://www.youtube.com/watch?v=Z_8MpZeMdD4