To write a program to find the global maxima of a Stalagmite function using Genetic Algorithm and to explain the concept of Genetic Algorithm.
AIM of the Project:
To write a program to find the global maxima of a Stalagmite function using Genetic Algorithm and to
explain the concept of Genetic Algorithm.
1. GENETIC ALGORITHM:
Genetic Algorithm is a search based optimization technique to find the optimum or near optimum
solutions to difficult problems.
The aim of optimization is to find better solutions.
Basic Terminology:
1. Population: Subset of all the possible solutions.
2. Chromosome: One of the candidate solutions.
3. Gene: One element or property of a Chromosome.
4. Allele: Value of the gene for a particular Chromosome.
Population can be represented in two types:
a. Phenptype: Population in the computation space.
b. Genotype: Population in the real world.
Fitness Function:
It is the function that takes a candidate solution and analyzises it for its output.
Genetic Operators:
These are used to alter the composition of candidate solutions to get better solutions.
1. Selection:
Used to select good candidates. As per GA documentation in MATLAB, initial population is randomly
selected using a random number generator.
2. Crossover: Combines two good candidates to form better solutions.
Two candidates are chosen randomly.
A point is chosen randomly between the elements of the Chromosome, and then Crossover is
done.
* Not all candidate solutions from the Initial Population are chosen.
* Randomly chosen with a Crossover probability, Pc.
* N*Pc are selected for Crossover
* Remaining are not selected.
Types of Crossover methods:
a. One-Point Crossover
b. Multi-Point Crossover
c. Uniform Crossover
d. Davis Order Crossover
3. Mutation:
It is used to alter the properties of a Chromosome. The probablity for the selection of the
candidates must be low.
Mutation is very important for the convergence of GA.
Types of Mutation methods:
a. Bit Flip Mutation
b. Swap Mutation
c. Inversion Mutation
Basic Structure of Genetic Algorithm:
1. Start with the Initial Population.
2. Select parent candidate solutions for mating.
3. Crossover, Mutation are applied to generate new candidate solutions.
4. Fitness of the new candidate solutions is determined.
5. Better candidate solutions replace the existing solutions.
6. The process repeats till the optimum solution is found.
2. CODE FOR THE PROJECT:
%Maximization of a Stalagmite Function using Genetic Algorithm.
clear all
close all
clc
x = linspace(0,1,150);
y = linspace(0,1,150);
n_cases = 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
%Case 1: Study the statistical behaviour of Genetic Algorithm
tic
for k = 1:n_cases
[Inputs, Fopt(k)] = ga(@stalagmite,2);
xopt(k) = Inputs(1);
yopt(k) = Inputs(2);
end
Fopt = -Fopt;
f = -f;
Time_Study1 = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,Fopt,'color','b','marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt,'color','b','linewidth',1)
xlabel('Iterations');
ylabel('Function Maximum');
%Case2: Study the Statistical behaviour of Genetic Algorithm with Upper and
%Lower Bounds
tic
for k = 1:n_cases
[Inputs2, Fopt2(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt2(k) = Inputs2(1);
yopt2(k) = Inputs2(2);
end
Fopt2 = -Fopt2;
Time_Study2 = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt2,yopt2,Fopt2,'color','b','marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt2,'color','b','linewidth',1)
xlabel('Iterations');
ylabel('Function Maximum');
%Case3: Study the statistical behaviour of GA by increasing the number of
% iterations.
options = optimoptions('ga');
options = optimoptions(options, 'PopulationSize',200);
tic
for k = 1:n_cases
[Inputs3, Fopt3(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt3(k) = Inputs3(1);
yopt3(k) = Inputs3(2);
end
Fopt3 = -Fopt3;
Time_Study3 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt3,yopt3,Fopt3,'color','b','marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt3,'color','b','linewidth',1)
xlabel('Iterations');
ylabel('Function Maximum');
rng('default');Explanation of the Code:
clear all
To clear all the variables from the workspace.
close all
To close all the outputs that are opened.
clc
To clear the command window.
x = linspace(0,1,150);
To store 150 values of 'x' from 0 to 1.
y = linspace(0,1,150);
To store 150 values of 'y' from 0 to 1.
n_cases = 50;
To assign value of 50 to a variable 'n_cases', representing the number of cases.
[xx,yy] = meshgrid(x,y);
To create a 2D array using the arrays 'x' and 'y' using 'meshgrid' function.
for i = 1:length(xx)
Starting for loop from 1 to the length of array 'xx' using the variable 'i'.
for j = 1:length(yy)
Starting one more nested for loop from 1 to the length of array 'yy' using the variable 'j'.
input(1) = xx(i,j);
Storing the value of 'xx' as per the sequence of iteration of the for loops, in the first column of array
'input'.
input(2) = yy(i,j);
Storing the value of 'xx' as per the sequence of iteration of the for loops, in the second column of array
'input'.
f(i,j) = stalagmite(input);
Calling the function 'stalagmite' that contains the code for evaluating the value of the function as per
the provided inputs as the argument to the function.
The array 'input' contains the values of 'x' and 'y' and is passed as an argument to the function.
end
End of nested for loop
end
End of for loop
%Case 1: Study the statistical behaviour of Genetic Algorithm
tic
for k = 1:n_cases
Starting for loop from 1 to the length of 'n_cases' using the variable 'k'.
[Inputs, Fopt(k)] = ga(@stalagmite,2);
Calling the 'ga' solver by passing the function handle of the stalagmite function with two number of
variables.
'Inputs' is the array to store the optimum values if the variables of the stalagmite function as selected
by GA.
'Fopt' is the array to store the optimum values of the stalagmite function for all the values of 'x' and
'y'.
'Inputs' and 'Fopt' are the outputs of the GA.
xopt(k) = Inputs(1);
Storing the optimum value of the variable 'x' selected by GA in the array 'xopt' for every iteration of
the for loop.
yopt(k) = Inputs(2);
Storing the optimum value of the variable 'y' selected by GA in the array 'yopt' for every iteration of
the for loop.
end
End of for loop
Fopt = -Fopt;
Converting the values of the stalagmite function stored in the array 'Fopt' to their negative values,
since we have a maximization problem.
The minimum value of '-f(x)' is the maximum value of 'f(x)'.
f = -f;
Converting all the values of the stalagmite function calculated as per the unbounded inputs.
Time_Study1 = toc
Storing the time taken by MATLAB to run the first iteration of GA in the variable 'Time_Study1'.
figure(1)
Using the figure command to generate the first figure.
subplot(2,1,1)
Using the subplot command to divide the first figure into a 2x1 grid and indicating the position of the
first subplot in the figure.
hold on
Using hold on command to generate all the plots.
surfc(x,y,f)
Using surfc command to create a surface plot of the values of the stalagmite function stored in the
array 'f', for all the unblunded values of the variables 'x' and 'y'.
shading interp
Using the shading interp command to generate a smooth surface plot without grids.
plot3(xopt,yopt,Fopt,'color','b','marker','o','markersize',5,'markerfacecolor','r');
Using the plot3 command to create a 3D plot of the optimum valus of the stalagmite function for all
all the optimum values of the variables 'x' and 'y' selected by the Genetic Algorithm.
title('Unbounded Inputs');
Giving the title as 'Unbounded Inputs'.
subplot(2,1,2)
Using the subplot command to divide the first figure into a 2x1 grid and indicating the position of the
second subplot in the figure.
plot(Fopt,'color','b','linewidth',1)
Creating the plot of the values of the 'Fopt' for all the values of the variables 'x' and 'y'.
xlabel('Iterations');
Giving xlabel as 'Iterations'.
ylabel('Function Maximum');
Giving ylabel as 'Function Maximum'.
%Case2: Study the Statistical behaviour of Genetic Algorithm with Upper and Lower Bounds
tic
for k = 1:n_cases
Starting for loop from 1 to the length of 'n_cases' using the variable 'k'.
[Inputs2, Fopt2(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
Calling the 'ga' solver by passing the function handle of the stalagmite function with two number of
variables, and providing the upper and lower bounds for the values of 'x' and 'y'.
'Inputs2' is the array to store the optimum values if the variables of the stalagmite function as selected
by GA.
'Fopt2' is the array to store the optimum values of the stalagmite function for all the values of 'x'
and 'y'.
'Inputs2' and 'Fopt2' are the outputs of the GA.
xopt2(k) = Inputs2(1);
Storing the optimum value of the variable 'x' selected by GA in the array 'xopt2' for every iteration of
the for loop.
yopt2(k) = Inputs2(2);
Storing the optimum value of the variable 'y' selected by GA in the array 'yopt2' for every iteration of
the for loop.
end
End of for loop
Fopt2 = -Fopt2;
Converting the values of the stalagmite function stored in the array 'Fopt2' to their negative values,
since we have a maximization problem.
The minimum value of '-f(x)' is the maximum value of 'f(x)'.
Time_Study2 = toc
Storing the time taken by MATLAB to run the second iteration of GA in the variable 'Time_Study2'.
figure(2)
Using the figure command to generate the second figure.
subplot(2,1,1)
Using the subplot command to divide the first figure into a 2x1 grid and indicating the position of the
first subplot in the figure.
hold on
Using hold on command to generate all the plots.
surfc(x,y,f)
Using surfc command to create a surface plot of the values of the stalagmite function stored in the
array 'f', for all the unblunded values of the variables 'x' and 'y'.
shading interp
Using the shading interp command to generate a smooth surface plot without grids.
plot3(xopt2,yopt2,Fopt2,'color','b','marker','o','markersize',5,'markerfacecolor','r');
Using the plot3 command to create a 3D plot of the optimum valus of the stalagmite function for all
the optimum values of the variables 'xopt2' and 'yopt2' selected by the Genetic Algorithm.
title('Unbounded Inputs');
Giving the title as 'Unbounded Inputs'.
subplot(2,1,2)
Using the subplot command to divide the first figure into a 2x1 grid and indicating the position of the
second subplot in the figure.
plot(Fopt2,'color','b','linewidth',1)
Creating the plot of the values of the 'Fopt2' for all the values of the variables 'xopt2' and 'yopt2'.
xlabel('Iterations');
Giving xlabel as 'Iterations'.
ylabel('Function Maximum');
Giving ylabel as 'Function Maximum'.
%Case3: Study the statistical behaviour of GA by increasing the number of% iterations.
options = optimoptions('ga');
Using the optimoptions function to return default options to the 'ga' solver.
options = optimoptions(options, 'PopulationSize',200);
Providing the default options of the 'ga' solver with named parameter 'Population Size' with a value of
200.
tic
for k = 1:n_cases
Starting for loop from 1 to the length of 'n_cases' using the variable 'k'.
[Inputs3, Fopt3(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
Calling the 'ga' solver by passing the function handle of the stalagmite function with two number of
variables, and providing the upper and lower bounds for the values of 'x' and 'y', along with the default
options for the population size.
'Inputs3' is the array to store the optimum values if the variables of the stalagmite function as selected
by GA. 'Fopt3' is the array to store the optimum values of the stalagmite function for all the values of
'x' and 'y'.
'Inputs3' and 'Fopt3' are the outputs of the GA.
xopt3(k) = Inputs3(1);
Storing the optimum value of the variable 'x' selected by GA in the array 'xopt3' for every iteration of
the for loop.
yopt3(k) = Inputs3(2);
Storing the optimum value of the variable 'y' selected by GA in the array 'yopt3' for every iteration of
the for loop.
end
End of for loop
Fopt3 = -Fopt3;
Converting the values of the stalagmite function stored in the array 'Fopt3' to their negative values,
since we have a maximization problem. The minimum value of '-f(x)' is the maximum value of 'f(x)'.
Time_Study3 = toc
Storing the time taken by MATLAB to run the second iteration of GA in the variable 'Time_Study3'.
figure(3)
Using the figure command to generate the third figure.
subplot(2,1,1)
Using the subplot command to divide the first figure into a 2x1 grid and indicating the position of the
first subplot in the figure.
hold on
Using hold on command to generate all the plots.
surfc(x,y,f)
Using surfc command to create a surface plot of the values of the stalagmite function stored in the
array 'f', for all the unblunded values of the variables 'x' and 'y'.
shading interp
Using the shading interp command to generate a smooth surface plot without grids.
plot3(xopt3,yopt3,Fopt3,'color','b','marker','o','markersize',5,'markerfacecolor','r');
Using the plot3 command to create a 3D plot of the optimum valus of the stalagmite function for all
the optimum values of the variables 'xopt3' and 'yopt3' selected by the Genetic Algorithm.
title('Unbounded Inputs');
Giving the title as 'Unbounded Inputs'.
subplot(2,1,2)
Using the subplot command to divide the first figure into a 2x1 grid and indicating the position of the
second subplot in the figure.
plot(Fopt3,'color','b','linewidth',1)
Creating the plot of the values of the 'Fopt2' for all the values of the variables 'xopt2' and 'yopt2'.
xlabel('Iterations');
Giving xlabel as 'Iterations'.
ylabel('Function Maximum');
Giving ylabel as 'Function Maximum'.
rng('default');
Using the 'rng' function to set the random number generator to its default state, to have reproducibility
of the random numbers generated in the first run of GA.
Without reproducibility, GA produces different results on each run.
Code for the Stalagmite Function:
The Stalagmite function is given by the following equation:
%Stalagmite Function for GA
function sol = stalagmite(input)
x = input(1);
y = input(2);
fxone = (sin(((5.1*pi).*x)+0.5)).^6;
fxtwo = exp((((x-0.0667).^2).*(-4*log(2)))./0.64);
fyone = (sin(((5.1*pi).*y)+0.5)).^6;
fytwo = exp((((y-0.0667).^2).*(-4*log(2)))./0.64);
sol = -((fxone)*(fxtwo)*(fyone)*(fytwo));
endExplanation of the Code:
%Stalagmite Function for GA
function sol = stalagmite(input)
Creating a function 'stalagmite' by passing the 'input' array as the argument for the variables 'x' and
'y'. The output of the function is stored in the variable 'sol'.
x = input(1);
Storing the value of the first column of the 'input' array in the variable 'x'.
y = input(2);
Storing the value of the second column of the 'input' array in the variable 'y'.
fxone = (sin(((5.1*pi).*x)+0.5)).^6;
fxtwo = exp((((x-0.0667).^2).*(-4*log(2)))./0.64);
fyone = (sin(((5.1*pi).*y)+0.5)).^6;
fytwo = exp((((y-0.0667).^2).*(-4*log(2)))./0.64);
Code for the stalagmite function.
sol = -((fxone)*(fxtwo)*(fyone)*(fytwo));
Calculating the value of the stalagmite function and storing the variable 'sol'.
end
End of the function
Results of the three Studies:
Study 1:
Study 2:
Study 3:
Syntax of GA in MATLAB:
The syntax of GA in MATLAB is as follows:
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)
Let us take the example of the following function to understand the syntac of GA:
" f(x) = 100*((x1)^2 - (x2)^2) + (1 - x(1)^2)^2 ".
The function is subjected to the following constraints:
1. Linear Constraints:
x(1) + x(2) > = 1.
x(2) - x(1) = 5.
2. Non-linear Constraints:
x(1)*x(2) + x(1) - x(2) + 1.5 <= 0.
10 - x(1)*x(2) <= 0.
3. Bounds:
0 <= x(1) <= 1.
0 <= x(2) <= 2.
'x' is the variable to store the output of the Genetic Algorithm.
'fun' is the function handle to call the function.
'A' and 'b' are used to represent the linear inequalities of the the function, if any. Otherwise, they are
set as empty, '[]'.
As per the above constraints:
A = [1 1];
b =1;
'Aeq' and 'beq' are used to represent the equality constraints.
As per the above constraints:
Aeq = [-1 1];
beq = 5;
'lb' and 'ub' are used to specify the upper and the lower bounds of the variables of the function.
As per the above values:
lb = [0,0];
ub = [1,1];
'nonlcon' is a function that is specified using a function handle. A separate function code must be
written as per the constraints of the function.
This function gives two arrays 'c' and 'Ceq' as its outputs.
'c' stores the values of the equality constraints.
'Ceq' stores the values of the inequality constraints.
'IntCon' is used to specify the Integer Constraint, such that the value of the function is an integer.
'options' is used to provide the values of the default parameters using named parameters, if it is
required to replace the default parameters. This is done by using the function 'optimoptions'.