Week 4.1 - Genetic Algorithm
Aim: - TO study about genetic algorithm and to calculate the global maxima of stalagmite function using genetic algorithm in MATLAB.
Objective: -
- To study about genetic algorithm and stalagmite function.
- To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
- to plot the graphs based on the studies done for genetic algorithm.
THEORY:
Concept of Genetic Algorithm -
The genetic algorithm works on the process of natural selection where the fitting individual are selected for reproduction in order to produce offspring of the next generation. it is the method of solving both constrained and unconstrained optimization problems that is based on natural selection. the algorithm beings by creating a random initial population of individual selections and it keeps on modifying this population repeatedly crating a sequence of new population. the algorithm uses the individuals in the current generation to create the new population. the genetic algorithm selects individuals at random from the current population to be present and uses them to produce the children for the next generation. over successive generation, the population evolves toward an optimal solution.
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:
- selection rules select the individuals’ called parents, that contribute to the population at the next generation.
- crossover rules combine two parents to from children for the next generation.
- mutation rules apply random changes to individual parents to from children.
The basic steps in creating a genetic algorithm are as follows,
- The algorithm creates a random initial population at beginning.
- Then to create a new population, the algorithm scores each member of the current population by computing its fitness value and converts them into a more usable range to values.
- then based on three new values the algorithm selects members, called as parents.
- Then algorithm produce a child from the parents. children are produced either by making random changes to a single parent which is mutation or by combining the vector entries of pair of parents which is crossover.
- in this way the algorithm replaces the current population with the children to from the next generation.
- The algorithm stops when it reaches any one of the specified factors such as time limit, fitness limit, generations, function tolerance, constraint tolerance, etc.
The flowchart for genetic algorithm is given below,
What is stalagmite function?
stalagmite function is a mathematical model which helps to generate local minima and maxima. it is a three-dimensional function and way the function is designed is that it has a lot of local maxima or minima and one global maxima or minima. the name stalagmite is actually a types of rock formation that arises from the floor of a curve due to the accumulation of material deposited on the accumulation of material deposited on the floor from ceiling drippings.
The stalagmite function is given as,
Syntax for defining 'ga'(Genetic Algorithm) in MATLAB -
The 'ga' syntax in MATLAB is used to find the maximum function using genetic algorithm. there are several ways to define the 'ga' function depending on the problem being solving, the syntax used for this study is shown below.
- x = ga(fun,nvars)
where,
x = optimal solution/variables;
fun = objective function;
nvars = numbers of variables;
sometime '[x,fval]' is used instead of 'x' where 'fval' gives objective function value at the solution
- x = ga (fun, nvars, A,B,Aeq,Beq,lb,ub)
where,
A, B = linear inequality constraints
Aeq, Beq = linear equality constraints
if there are no linear equalities and inequalities, then A,B,Aeq,Beq are set to '[]'.
- x = ga (fun, nvars, A,B,Aeq,Beq,lb,ub,nonlcon,intCon,options)
where,
nonlcon = Nonlinear constraints
intCon = integer values
options = optimization options
if there are no nonlinear constraints and integer values, the nonlcon and intCon are set to '[]'.
MATLAB Program:
first in order to define stalagmite function, we need to write a different script defining the stalagmite function.
%Define Stalagmite Function
function[f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
t1 = (sin((5.1*pi*x) +0.5)) ^6;
t2 = (sin((5.1*pi*y) +0.5)) ^6;
t3 = exp (-4*log (2) *((x-0.0667) ^2)/0.64);
t4 = exp (-4*log (2) *((y-0.0667) ^2)/0.64);
f = -(t1*t2*t3*t4);
end
The negative sing in the function will invert the stalagmite plot which will eventually give the function maxima.
now we can proceed for coding the genetic. algorithm for this stalagmite function.
clear all
close all
clc
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
n = 50;
%creating a 2Dimensional mesh
[xx yy] = meshgrid(x,y);
%Evaluating the stalagmite 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
%Study 1: Statistical Behaviour
tic
for i = 1: n
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study1_time=toc
figure (1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('X-axis')
ylabel('Y-axis')
title('Statistical Behaviour With Unbound Inputs')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('No. of iteration')
ylabel('Function maximum')
%study2: Statistical behaviour with upper and lower bounds
tic
for i = 1: n
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
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
xlabel('X-axis')
ylabel('Y-axis')
title('Statistical Behaviour With Upper and lower bounds')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('No. of iteration')
ylabel('Function maximum')
%study3: Statistical Behaviour with increasing iterations of GA
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',300);
tic
for i = 1: n
[inputs, fopt(i)] =ga (@stalagmite,2, [], [], [], [], [0;0], [1;1], [], [], options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time=toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('X-axis')
ylabel('Y-axis')
title('Statistical Behaviour With increasing iterations')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('No. of iteration')
ylabel('Function maximum')
Here in this code,
- the code starts with clear all, close all, clc, where,
- 'clear all' command is used to clear the data stored in the workspace.
- 'close all' command is used to clear all plot and figures.
- 'clc' command is used to clear the command window.
- Then the 'x' array and 'y' array is defined using 'linspace' command to create values at 150 equal intervals.
- A 2D mesh of x and y array is created by using 'meshgrid' command and the number of iterations or cases that the code should perform is defined. this is given by n = 50.
- To evaluated the stalagmite function, 'for' loop is used where 'i' is initialized and for every value of 'i' another 'for' loop is used to initialize 'j'.
- The input vector values of 'xx' and 'yy' are defined and the stalagmite function for their input vector is defined. This will from a basic stalagmite function and we can plot it separately if needed.
- after preparing the inputs needed for the function, next step is to obtain the results for 3 cases of the genetic algorithm. in first case or study, the maximum value of function is found out with no restrictions, no bounds and limits.
- This is done using 'for' loop where we use 'ga' syntax to give values for inputs and optimum max value. the stalagmite function is called in 'ga' syntax and number of variables 'nvars' are 2.
- to know the time that is taken to solve the loop for 50 iterations, 'tic' and 'toc' commands is used before and after the loop respectively.
- Then the function create in the loop is plotted by using 'surfc' command for 'xx and yy and function output. to negate the gridelines on the surface and obtain a smooth and clean plot, 'shading interp' command is used. the ‘subplot (2,1,1)' is used to plot multiple plot on same figure which also divides figure in grid of 2x1 and axes to be placed at 1.
- The 'plot3' command plots hte 3D points at 'xopt, yopt and optimum value of function ' with 'o' shaped and res colour. the labels and title are then provided. now in the same figure, the values of optimum function 'fopt' are plotted for 50 iterations.
- The results of the above case will be different for each time we run the program. To get same value each time, we need to restrict the program within specific bounds namely upper bound and lower bound. hte procedure for coding and plotting this procedure is same as study 1. The only difference is in the 'ga' syntax. this tome the algorithm is provided lower limits and upper limits as [0;0] and [1;1] respectively.
- After plotting the results for study 2 or the bounded case, it is observed that the results are not same even time the program terminates. A solution to this problem is to increase the number of cases or iterations.
- So for study 3, the number of iterations is increased to 300. so for this study, the syntax, "options = optimoptions ('Solver Name’, ‘Name’, ‘Value')" is used which returns with named parameter 'populations' with the altered values '300'.
- The syntax for 'ga' contains 'option' term and the rest of the code is same as for study 1 and 2.
Results:
study 1 - statistical Behaviour.
in above plot, it can be observed how the random sampling of the genetic algorithm generates a new optimum value for the function every time the code is run. although this falls in line with the definition of genetic algorithm. large number of red dots shows values of co-ordinates of x, y varies each time iteration runs.
study 2 - statistical Behaviour with upper and lower bounds.
The above result shows the convergence of x and y values. the number of red dots is less compared to previous plot. This is the result of providing upper and lower bounds to the function.
study 3 - Statistical Behaviours with increasing iterations of GA.
in this study, the number of iterations in increased to 300 to converge and find the global maxima of the function. Here we can see that there is only one red dot on the stalagmite function and that is the required global maxima point.
on rotating the plot, we can clearly see the stalagmite function along with the global maxima value as x = 0.06683 and y = 0.06683.
Also, the graph of 'Function maximum vs no. of iterations' results that the value of optimum function 'fopt' is approximately equal to 1.
Workspace Values -
Errors:
No major error was faced while coding.
References: