Optimisation of Stalagmite Function using Genetic Algorithm in MATLAB
A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.
The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.
This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.
Five phases are considered in a genetic algorithm.
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
GA in MatLab: In MatLab, the function for a genetic algorithm is \'ga\'. It always tries to minimise the given fitness function. So, GA can be used when a certain function needs to be minimised. For example, minimising some error.
The syntax for the \'ga\' is as: [input, fval]= ga (fitnessfcn, nvars, A, b, Aeq, beq, LB, UB, nonlcon, IntCon, options).
Where: \'input\' returns the input values,
\'fval\' returns the value of the fitness function.
\'fitnessfcn\' is the function which we desire to minimise.
\'nvars\' are the number of variables associated with the function.
\'A\' and \'b\' is the linear inequality constraint of the type A*x ≤ b, if any. (In MatLab, it\'s always \'Ax is less than b\' form).
\'Aeq\' and \'beq\' is the equality constraint of the type A*x = b, if any.
LB and UB set the lower and upper bound for the GA. These provide the GA the search-space. Otherwise, the GA will try to look at points beyond the function\'s domain.
\'nonlcon\' sets the non-linear constraint, if any.
\'IntCon\' sets the integer constraint, if any.
\'options\' are used whenever we need to change the way of the Matlab\'s default GA functioning. to the desired optimisation requirements. For example, MaxGenerations is used to change the default no. of generations that the GA uses before stopping the search. (generally 100*number of variables). Similarly, the \'populationSize\' is used when we need to change the size of the population to be considered (default size = 50 for 5 or less no of input variables).
Note: When there are no constraints and say we need to change the upper and lower bounds, we need to provide [] for each entry that comes before the UB and LB in the syntax of GA function. For example in the given problem, we need to change the upper and lower bounds only. The syntax becomes:
[inputs, Fopt(i)] = ga (@stagfun, 2, [], [], [], [], [0;0], [0.6;0.6])
and not [inputs, Fopt(i)] = ga (@stagfun, 2, [0;0], [0.6;0.6]) XX
Problem Statement:
To find the maximum value of Stalagmite function within the given workspace co-ordinates.
For this problem we are considering workspace co-ordinates to be
x= 0 to 0.6 and y= 0 to 0.6 having values 150 values each.
Following is the code to define the Stalagmite function.
1. Function is created by combining the 4 components involving trigonometric and exponential expression as function of x and y.
2. Stalagmite is function of two variables x and y and thus output objective function is developed.
3. Also as we are using GA to solve for the maximum value of objective function, but GA only solves for the minimum value from the population in MATLAB we have to modify the objective function.
4. This can be done by taking the negative form of Stalagmite function and the GA solution will give give the negative form of Maximum value of objective function at some coordinates.
5. Thus we have objective function as \' -1*ST \'.
%Forming the Stalagmite function
%Stating the Function
function [S]=stalagmite(input)
%Stating the inputs
k=input(1);
l=input(2);
%Forming the equations
aa=(sin((k.*(5.1*pi))+0.5));
a=(aa).^6;
bb=((((k-0.0667).^2).*(-4*log(2)))./0.64);
b=exp(bb);
cc=(sin((l.*(5.1*pi))+0.5));
c=(cc).^6;
dd=((((l-0.0667).^2).*(-4*log(2)))./0.64);
d=exp(dd);
%Combining the equations
ST=(a.*b.*c.*d);
%GA solves for the minimum value of Function
%In order to find the maximum value we will consider the negative form of function
S=(-ST);
endFollowing is the Code for solving the Stalagmite Function using GA.
Steps:
1.Defing the Workspace and inputs
2.Also we define the no. of itterations to be done in order to get the optimium value.
2.Calling the Stalagmite function and passing the grid of co-ordinates we form the Stalagmite function over the work space.
clear all
close all
clc
%Defing the workspace in which Stalagmite function is spread
x=linspace(0,0.6,150);
y=linspace(0,1,150);
%Forming the grid of Co-ordinates
[xx yy]=meshgrid(x,y);
%Defining the no. of itterations to find the optimum value
n=50;
%Calling the stalagmite function and using the co-ordinates as inputs
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)= stalagmite(input);
end
end
4. Now we have the workspace co-ordinates and the different values of objective function thus by using the GA solver we will determine the minimum value of objective function.
5. This can be done in 3 different cases
First Case: Using GA solver directly without specifing the boundary of workspace.
1.In this case we are solving GA by directly passing the input values into objective function and running the GA.
2.As GA works on random selection it will return unique value each time GA is run, thus we will run the GA for certain itterations here 50 times so that a spreaded set of minimum values of objective values is calculated.
3.Also we provide timer to calculate the time elapsed in finding the minimum values 50 times
4.The optimisation solver used is GA solver. MATLAB has built in function for GA, the syntax used is [input,fopt(q)]= ga(@stalagmite,2);
5. In this case directly Stalagmite function and 2 no. of variables are fed into the GA solver.
6.We store the minimum value of function in \'fopt\'\'and X, Y coordinate in \'\'input 1\'and 2\'\' at which minimum value is returned.
7.Two figures are created and figure 1 is used as two subplots.
8.Figure 1 has 2 subplots: Subplot 1 represents the 3D view of inverted Stalagmite function and the various minimum values returned by GA are ploted with red marker.
9.Subplot2 graph represents the various minimum values returned with the No. of itterations
10.As GA gives the minimum value and our objective is to determine the Maximum value of Stalagmite finction, this can be achieved by determining the minimum of the different values returned by GA and taking the negative form of it. thus Maximum = -1*(min(fopt))
11.This value obtained is represented in 3D view of original positive form of stalagmite function by a marker of red.
% First Case Unbounded Workspace
%As GA works on random selection thus each time we run the solver we will get a unique
%optimum value each time. Thus we will run the solver for a no. of itteration and we
%will have no. of optimum values.
tic % Starting timer
%Running the GA solver for No. of itteration and storing the minimum value as fopt
for q=1:n
[input,fopt(q)]= ga(@stalagmite,2);
xopt(q)=input(1);
yopt(q)=input(2);
end
Time_taken = toc % ending the Timer
%Creating the figure 1 and subplot 1
figure(1)
subplot(2,1,1)
hold on
%Creating a 3D view of inverted Stalagmite
surfc(xx,yy,f)
shading interp
%Ploting the Fopt value for each itteration and highlighting it with marker.
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',6,\'markerfacecolor\',\'red\');
title(\'Unbounded Inputs\');
xlabel(\'X AXIS\');
ylabel(\'Y AXIS\');
zlabel(\'Z AXIS\');
grid on
%Creating Subplot 2
%ploting the fopt value with the itteration
subplot(2,1,2)
plot(fopt,\'color\',\'green\',\'linewidth\',1)
title(\'Variation in Fopt with Itterations\');
xlabel(\'NO. of Itterations\');
ylabel(\'Function Minimum\');
grid on
%As GA returns the minimum value of objective function
%To find the Maximum value of stalagmite we will take the negative of Fopt
Maximum =-1*(min(fopt));
%Display of Maximum vaue of Stalagmite function
M = [\'Global Maxima of Given Stalagmite function is: z = \',num2str(Maximum),\'at (x,y) = \',num2str(input)];
disp(M)
%Creating figure 2 to represent the maximum value of stalagmite
figure(2)
surf(x,y,-f)
shading interp
hold on;
plot3(input(1),input(2),1,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'red\')
Second Case: Using GA solver by specifing the boundary of workspace.
1. In this case all the steps to determine the Maximum value remains same only some modification are done in GA solver.
2. In this case as we are restricting the search space of variables we are specifing the upper and lower limits of vaiables passed.
3. This is done by syntax:[input,fopt(q)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]); where first objective function is passed then 2 No. of variables.
4.The 4 \'[]\' empty brackets are used for linear equality and non-equality constraints, while \'[0;0]\' and \'[0.6;0.6]\' are used to declare the lower and upper boundaries of variables.
5.All the other steps remains the same as First Case
clear all
close all
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=50;
[xx yy]=meshgrid(x,y);
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)= stalagmite(input);
end
end
%Starting the timer
tic
%GA solver used by specifing the uppper and lower limits of variables
for q=1:n
[input,fopt(q)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(q)=input(1);
yopt(q)=input(2);
end
%End of timer
Time_taken = toc
%creating the figure 1
figure(1)
%creating the subplot 1 for 3D of inverted Stalagmite function
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
%representing the minimum value on 3D view of function
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',6,\'markerfacecolor\',\'red\');
title(\'Unbounded Inputs\');
xlabel(\'X AXIS\');
ylabel(\'Y AXIS\');
zlabel(\'Z AXIS\');
grid on
%creating subplot2 representing the variations of minimumvalues with itterations
subplot(2,1,2)
plot(fopt,\'color\',\'green\',\'linewidth\',1)
title(\'Variation in Fopt with Itterations\');
xlabel(\'NO. of Itterations\');
ylabel(\'Function Minimum\');
grid on
% determining the maximum value of stalagmite function
Maximum =-1*(min(fopt));
M = [\'Global Maxima of Given Stalagmite function is: z = \', num2str(Maximum),\'at (x,y) = \',num2str(input)];
disp(M)
figure(2)
surf(x,y,-f)
shading interp
hold on;
plot3(input(1),input(2),1,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'red\')
Third Case: Using larger population size to arrive at better solution over bounded workspace
1.In this case we are aiming to determine the most suitable Maximum value of Stalagmite function as in case 2 also there are various optimum values returned by GA.
2.In order to have better optimum value which converges to a single value we vary the population size of variables in GA.
3.More the population size more number of data points will be checked against the GA and more converged solution will be found.
4.Thi is achieved by using the \'optimoptions\' function handle to return the default options to GA solver. Providing the default options of the GA solver with named parameter Population size of 200.
5. Along with it GA solver iscalled and additional two values are passed into solver, two empty brackets \'[]\' and \'option\'is passed.
6.All the other steps to represent the maximum value of stalagmite function remains same as First Case.
clear all
close all
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=50;
[xx yy]=meshgrid(x,y);
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)= stalagmite(input);
end
end
%calling the option handle and providing GA into it
options = optimoptions(\'ga\');
%providing the population size
options = optimoptions(options,\'PopulationSize\',170);
tic
%upper and lower bounds for search space
for q=1:n
[input,fopt(q)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt(q)=input(1);
yopt(q)=input(2);
end
Time_taken = toc
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',6,\'markerfacecolor\',\'red\');
title(\'Unbounded Inputs\');
xlabel(\'X AXIS\');
ylabel(\'Y AXIS\');
zlabel(\'Z AXIS\');
grid on
subplot(2,1,2)
plot(fopt,\'color\',\'green\',\'linewidth\',1)
title(\'Variation in Fopt with Itterations\');
xlabel(\'NO. of Itterations\');
ylabel(\'Function Minimum\');
grid on
Maximum =-1*(min(fopt));
M = [\'Global Maxima of Given Stalagmite function is: z = \', num2str(Maximum),\'at (x,y) = \',num2str(input)];
disp(M)
figure(2)
surf(x,y,-f)
shading interp
hold on;
plot3(input(1),input(2),1,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'red\')
Following are the outputs of Case 1 and Case 2, representing the various different minimum values of inverted stalagmite function.
It can be observed that in Case 1 figure the minimum values go beyound the workspace and in Case 2 figure they are within the boundaries.
Also in Case 2 the variations in minimum values with no. of itterations is slightky low and better than Case 1.
Following figures illustartes 3D view of desired positive form of Stalagmite function and the required Maximum value at the highest peak.
The Maximum Value is 1 for the Case 3 which occurs for No. of itterations.
Case 2 Stalagmite Max value Case 3 Stalagmite Max Value
Following are some errors occured during Coding the Challenge.
1.Following error occured while developing the Stalagmite function where the equations were not written using proper multplication operators. This error was rectified by writing the equations using element wise operator \'.\' befor multiplication operator.
2. The following error occured when the no. of itterations occured only one time instead of 50 times as specified. This error was rectified using the for loop properly eg; for q=1:n
3.This error occured when positive 3D form of Stalagmite function was represented and optimimum value was still neagative. This was solved by considering the Negative form of optimmum value obtained from GA.
Following are the study resources used for this Challenge:
1.For GA Study :GA - https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3?gi=70b9c6dde88e
2. For GA used in MATLAB: \\Documents\\MATLAB\\Challenges\\GA\\Genetic Algorithm_ Finding The Global Maxima of The Stalagmite Function in MatLab - Projects - Skill-Lync.mht
GA - https://in.mathworks.com/help/gads/examples/genetic-algorithm-options.html