Week 4 - Genetic Algorithm
A Genetic Algorithm is a method of solving both Constrained and Unconstrained optimization problems based on natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.
Syntax of GA is given as:
x = ga(fun,nvars)x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
x = ga(fun,nvars,A,b)x to fun, subject to the linear inequalties A*x ≤ b. ga eveluates the matrix product A*x as if x is transposed (A*x').
x = ga(fun,nvars,A,b,Aeq,beq)x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)IntCon take integer values.
NOTE: When there are integer constraints, ga does not accept linear or nonlinear equality constraints, only inequality constraints.
x = ga(problem)problem, where problem is a structure.
[, for any previous input arguments, also returns x,fval] = ga(___)fval, the value of the fitness function at x.
[ also returns x,fval,exitflag,output] = ga(___)exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
[ also returns a matrix x,fval,exitflag,output,population,scores] = ga(___)population, whose rows are the final population, and a vector scores, the scores of the final population.
By this Optimisation model we'll find out how to minimise/maximize a particular Function which depends on multiple Input parameteres and the objective here is to determine the Global Maxima without having any prior knowledge of this field.
Initial CODE before Optimising the Stalagmite function.
clear all
close all
clc
%find the maxima of the input using Genetic Algorithm
%input data
x= linspace(0,0.6,250);
y= linspace(0,0.6,250);
%creating a 2D array
[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
figure(1)
surfc(xx,yy,F)
xlabel('x value')
ylabel('y value')
shading interp
[input,fval] = ga(@stalagmite,2)
Stalagmite function
function [F] = stalagmite(input_vector);
x= input_vector(1)
y= input_vector(2)
f1x = [sin(5.1*pi*x+0.5)]^6;
f1y = [sin(5.1*pi*y+0.5)]^6;
f2x = exp((-4)*log(2)*(((x-0.0667)^2)/(0.64)));
f2y = exp((-4)*log(2)*(((y-0.0667)^2)/(0.64)));
F = (f1x*f1y*f2x*f2y)
endResult
The above program will give the global minimum as Genetic Algorith always returns the minimum value of the function.
Here we also noticed that every time we run the code it gives random values for an output, so For Global Optimisation of a function following 3 studies are taken into consideration by which we will see how it will return the same maxium value with consistently of the function using 'ga' :
Study 1). Statisitical behaviour
Study 2). Statisitical behaviour with upper and lowe bounds
Study 3). Increasing the ga iterations
Code for the 3 studies:
clear all
close all
clc
%find the maxima of the input using Genetic Algorithm
%input data
x= linspace(0,0.6,150);
y= linspace(0,0.6,150);
%creating a 2D array
[xx,yy] = meshgrid(x,y);
num_cases = 100
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 - Statisitical Behaviour
tic
for i = 1:num_cases
[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
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(Fopt)
xlabel('iterations')
ylabel('function maximum')
%Study2 - Statistical behaviour with upper and lower bounds
tic
for i = 1:num_cases
[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
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(Fopt)
xlabel('iterations')
ylabel('function maximum')
%Study3 - Increasing the 'ga' iterations
tic
options = optimoptions('ga');
options = optimoptions (options,'populationsize',750);
for i = 1:num_cases
[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
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(Fopt)
xlabel('iterations')
ylabel('function maximum')
Stalagmite Function Code
function [F] = stalagmite(input_vector);
x= input_vector(1)
y= input_vector(2)
f1x = [sin(5.1*pi*x+0.5)]^6;
f1y = [sin(5.1*pi*y+0.5)]^6;
f2x = exp((-4)*log(2)*(((x-0.0667)^2)/(0.64)));
f2y = exp((-4)*log(2)*(((y-0.0667)^2)/(0.64)));
F = -(f1x*f1y*f2x*f2y)
endHere we have used the -ve(minus) sign in the equation. The reason being, 'GA' normally returns only the minimum value of the function but in this challenge we needed to find the Global Maxima of the function. so the -ve sign will give us the opposite of the minimum value i.e the Maxima.
Rresults
Study1:
Here we can see that the Stalagmite function is being plotted. we have plotted the maximum values of the function which 'ga' is trying to predict and we can see that it is spread all over the place.This happens because 'ga' works on random sampling. Each and every time we run the code we will get different results
Study2:
here the plot looks a lot cleaner and the fuction predicts the maximum value is between the four mountain peaks as shown in the plot.
we can see the maximum value exits between -1 and -0.85, which is much more narrow range.
Study 3:
from the plot we can see the max values are not changing considerably. from the bottom image we can also see the the maximum value is always around -0.99999985 and have changed only after sixth decimal point, so the results we are consistent enough..
from this we can say that the more iterations we have it will converge into maximum value (in this case) irrespective of how many times we run the ga.
Here we can also see it took considerably longer for Study 3 to finish as it has more number of iterations with increase in population as well.
Explanation
I. Initial Code before Optimisation
- First Command Window and Workspace are being cleared and closed.
- Search space is defined using linspace command taking 250 values between 0 and 0.6
- using the 1 dimensional arrays we have created a 2D array using meshgrid command
- Now with the help of for loop, we have created arrays called input_vector(1) and input_vector(2) for each value of x and y of the 2D array.
- Now we have used a function called stalagmite, it takes in the input_vector and calculates F.
- Now we use surfc plot the visualise the function.
- after that we have used shading interp function to remove the grid lines from the plot, so basically it performs shading in the plot and we get a smoother looking plot.
- finally we have performed 'ga'. 'ga' is an inbuilt function and for 'ga' we are passing in two inputs, mentioning the function we need to minimise, as 'ga' always minimises the function
- for ga we are passing into two inputs 1) function handle (here stalagmite), 2) no. of variables in the function
- this will evaluate the optimum value of our Inputs. at these values of Inputs function will have the minimum value of zero.
- Stalagmite function: the stalagmite function code is written based upon the equation given for F, where in input vectors are defined and equations are formulated accordingly.
II. Optimisation Studies.
Study 1: Statistical Behaviour
- first and foremost the command window was cleared and closed.
- the input arrays are defined and with those 1D arrays a 2D array is created using meshgrid command.
- here we would assign 100 cases, so our genetic algorithm will run for 100 times.
- followed by generation of Stalagmite function and it is passed through the genetic algorithm in the main code.
- Here in study 1 we call the 'ga' and we passed the no. of variables as inputs and the x values and y values are stored as well as the optimum value that is predicted by the function.
- after this we have opened a new figure window and a subplot is created.
- It is done to have multiple plots inside the same figure window.
- a surface plot is created first for the stalagmite function.
- plot3 command is used to plot x,y and optimum value of function which is predicted by the 'ga' over the 100 studies
- Now the second subplot is created and here we direactly plot the optimum value that the function is predicting as the function of the iteration (here the number of cases i.e. 100)
- we use the tic-toc command to measure the time taken to complete the study.
Study 2: Statistical Behaviour with lower and upper bounds
- first thing we do here is we set up the bounds fro the variables
- in the previous study result we saw the values are going below 0 and and above 0.6, so here we defined the boundaries as we want the values between 0 and 1.
- the function defintion changes a bit as defined the lower and upper bounds [inputs, Fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]). this means the solution of the funtion will be found in this range of lower and upper bounds.
- the same steps are taken to run 'ga' as in study 1 and registering the time it took to complete the study.
- after this we have opened a new figure window and a subplot is created.
- It is done to have multiple plots inside the same figure window.
- a surface plot is created first for the stalagmite function.
- plot3 command is used to plot x,y and optimum value of function which is predicted by the 'ga' over the 100 studies
- Now the second subplot is created and here we direactly plot the optimum value that the function is predicting as the function of the iteration (here the number of cases i.e. 100)
Study 3: increasing the number of Interations keeping the lower and upper bounds.
- here in addition to the bounds we have also changed the initial population size
- we have increased the population size to 750 using options command.
- to further optimise the function we have to modify the 'ga' syntax [inputs, Fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
- the solution gets minimised with the default optimization parameters replaced by values in options.
- Optimoptions is used to create options
- again the same steps are taken to run 'ga' as in study 1 and registering the time it took to complete the study
- after this we have opened a new figure window and a subplot is created.
- It is done to have multiple plots inside the same figure window.
- a surface plot is created first for the stalagmite function.
- plot3 command is used to plot x,y and optimum value of function which is predicted by the 'ga' over the 100 studies
- Now the second subplot is created and here we direactly plot the optimum value that the function is predicting as the function of the iteration (here the number of cases i.e. 100)
Stalagmite function
the stalagmite function is created from the equations and formulaes provided and later called upon in the main code.
we have used -ve sign here as ga always returns the minima of the function but here we needed the maxima. so the -ve sign will return the opposite of minima i.e maxima of the function.
Erros and Rectification
1.)
this error came because there is space after optimoptions in line 73. this was rectified by removing that space.
2.)
this error came because the GLOBAL OPTIMIZATION TOOLBOX wasn't installed in the system. After installing it when i ran the code it ran perfectly.
References
https://in.mathworks.com/discovery/genetic-algorithm.html
https://in.mathworks.com/help/gads/ga.html#d120e39200
https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html