Week 5 - Genetic Algorithm
AIM:
To Optimise the stalagmite function and find the Global Maxima using this function in Matlab.
OBJECTIVE:
To learn and understand the concept of Genetic algorithm and how we can optimize the stalagmite function in order to get the value for Global Maxima.
GENETIC ALGORITHM:
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals randomly from the current population to be parents and uses them to produce children for the next generation. over successive generations, the population evolves toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly non-linear. The genetic algorithm can address issues of mixed-integer programming, where some components are restricted to be integer-valued.
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 of the next generation.
Crossover rules: combine two parents to form children for the next generation.
Mutation rules: apply random changes to individual parents to form the children.
Genetic algorithms are primarily used in optimization problems of various kinds, but they are frequently used in other application areas as well.
The areas in which Genetic algorithms are frequently used are listed below:
Optimization:
Genetic algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints.
Economics:
GAs are used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.
Neutral Networks:
GAs are used to train neural networks, particularly recurrent neural networks.
Image processing:
GAs are used for various digital image processing(DIP) tasks as well as dense pixel matching.
The above are some of the areas where the genetic algorithm is extensively used for optimization.
FITNESS FUNCTION:
The fitness function takes the solution as input and produces the suitability of the solution as the output. This evaluates how close the solution is to the optimal solution of the desired problem.
The syntax for GA in Matlab:
x=ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,Intcon,options)
This syntax is explained as follows:
'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 function, if the linear inequalities do not exist, they can be set as empty[].
Aeq and Beq - are used to represent the equality constraints. similarly, if the linear equalities do not exist, they can be set as empty[].
'lb' and 'ub' - are used to specify the upper and the lower bounds of the variables of the function.
'nonlcon' - represents the non-linear constraints.
Intcon - represents the integer constraint, such that the value of the function is an integer.
'options' - used to provide the value of the default parameters used named parameters if it is required to replace the default parameters. This is done by using the 'optimoptions'
what is Stalagmite?
- A Stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. Most stalagmites have rounded or flattened tips.
- Calcium carbonate deposition as a stalagmite occurs when the solution carries the calcium-laden leachate solution to the ground under the concrete structure. Carbon dioxide is absorbed into the alkaline leachate solution, which facilitates the chemical reactions to deposit calcium carbonate as a stalagmite.
The following function will look like this feature hence it is called the Stalagmite function.
The following is the given stalagmite function for which we need to find the global maxima.
- The above equations are used in the stalagmite function to plot the graph in the main functions.
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;
t1 = ((x - 0.0667).^2)/(0.64);
f2_x = exp(-4.*log(2)*t1)
t2 = ((y - 0.0667).^2)/(0.64);
f2_y = exp(-4.*log(2)*t2)
f = -(f1_x.*f2_x.*f1_y.*f2_y);
end
- While using the function at the end as we are using the -ve sign so that the plot will be reversed as we have to find the maxima of the given function using ga.
- MAIN BODY
- Firstly, creating the mesh from the two vectors which will be acting as a search space to find the maxima of the function.
- Creating the mesh of these two vectors using the ‘mesh’ command and defining the no. of iterations as num_cases to iterate the values of the optimum values of the function.\
- Now calculating the values of fitness function at each point of the mesh grid formed.
- Now creating its surface through ‘surfc’ command which will also provide the contour of the generated surface.
- While using surfc applying the -ve sign to the function will generate the surface upside down which will be quite good to get the maxima of the function, as it will provide positive value for the maxima using the -ve sign.
- STATISTICAL STUDY WITHOUT BOUNDATION
- In this evaluating the optimum value of fitness function at each iteration and calculating it using the above-mentioned syntax in the intro part (which gives the inputs ie. Values of x and y at which the stalagmite function is minimum)
- Then plotting it into the surf command and also providing the optimum values of the function that how it is varying.
- Also using the tic and tok command to evaluate the time used for optimizing the function.
%% STATISTICAL BEHAVIOUR (UNBOUNDED)
tic %calculating the study time through tic and toc command
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2); %calculating the optimized value of the function
xopt(i)=inputs(1); %at each iteration
yopt(i)=inputs(2);
end
study1_time=toc %displaying the time taken to evaluate
% PLOTING THE GRAPH
figure(1)
subplot(2,1,1)
surfc(X,Y,-f);
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
- From the figure, as shown above, it is clear that the results are not that much accurate and give a lot of variation in optimizing the function.
2. STATISTICAL STUDY WITH BOUNDATION
- The difference over here is in providing the upper and the lower limit in the ga so that the search space is reduced with the upper and lower boundary
- And then plotting it as similar to the above study.
%% STATISTICAL BEHAVIOUR (BOUNDED)
tic %calculating the study time through tic and toc command
for j=1:num_cases
[inputs,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]); %calculating the optimized value of the function
xopt(j)=inputs(1); %at each iteration with boundation
yopt(j)=inputs(2);
end
study2_time=toc
%PLOTTING
figure(2)
subplot(2,1,1)
hold on
surfc(X,Y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
RESULTS
- It is clearly seen from the above that after providing the boundary limits the variation in the optimum value of the function has reduced.
3. STATISTICAL STUDY WITH AN INCREASE IN SIZE OF POPULATION
- In this study using the ‘optimoptions’ command to increase the size of population.
- The benefit of that will be it will be working on the large set of numbers and which will be led to increase
- the possibilities of finding the better fitness of the function.
- The drawback is that the time for evaluation will increase.
options=optimoptions('ga','populationsize',300) %increaing the size of population by using optimoptions function
tic
for k=1:num_cases
[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
end
study3_time=toc
%PLOTTING
figure(3)
subplot(2,1,1)
hold on
surfc(X,Y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')RESULTS
RESULTS
- It is clearly seen in the above case that the value of the variation range has changed to a large extent.
NOW THE WHOLE PROGRAM AT ONCE:
clear all
close all
clc
%% PROVIDING THE SEARCH SPACE FOR THE FUNCTION
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[x,y] = meshgrid(x,y);
num_cases = 50; %Number of iterations for which the function will evaluate the fitness
%% CREATING THE SURFACE PLOT OF THE STALAGMITE FUNCTION
for i = 1:length(x)
for j = 1:length(y)
input_vector(1) = x(i,j);
input_vector(2) = y(i,j);
f(i,j) = stalagmite(input_vector); %values of function in given search space
end
end
surf(x,y,-f); %generating the surface
shading interp %To remove the lines produced by the mesh grid
%% STATISTICAL BEHAVIOUR (UNBOUNDED)
tic %calculating the study time through tic and toc command
for i = 1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2); %calculating the optimized value of the function
xopt(i)=inputs(1); %at each iteration for x
yopt(i)=inputs(2); %at each iteration for y
end
study1_time=toc %displaying the time taken to evaluate
% PLOTING THE GRAPH
figure(1)
subplot(2,1,1)
surfc(x,y,-f);
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x- axis');
ylabel('y- axis');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
%% STATISTICAL BEHAVIOUR (BOUNDED)
tic %calculating the study time through tic and toc command
for j=1:num_cases
[inputs,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]); %calculating the optimized value of the function
xopt(j)=inputs(1); %at each iteration with boundation
yopt(j)=inputs(2);
end
study2_time=toc
%PLOTTING
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
%% MODIFYING THE NUMBER OF POPULATION
options= optimoptions('ga','populationsize',300) %increaing the sixe of population by using optimoptions function
tic
for k=1:num_cases
[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
end
study3_time=toc
%PLOTTING
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
- No Errors were thrown in the command window
WORKSPACE VALUES
OUTPUT:
CONCLUSION:
ga is useful for optimizing the function but still the result are not accurate as the maximum value for the function lies at -1.
to overcome that using the given program shown below
clear
close all
clc
%% creating the mesh
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
%% for plotting the surface of stalagmite
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
%% evalutaing the function
options=optimoptions('ga','PlotFcn',@gaplotbestf,'populationsize',200);
[x,fval]=ga(@get_stalagmite,2,[],[],[],[],[0;0],[1;1],[],options)
xopt=x(1);
yopt=x(2);
figure(1)
surf(xx,yy,-f);
shading interp
hold on
plot3(xopt,yopt,-fval,'ro','markersize',5,'markerfacecolor','r')
The above program will display the best value in the graph.
another way to find the best value is shown below.
- NOTE:gaplotbestf, which plots the best and mean score of the population at every generation. Also setting gaplotstopping, which plots the percentage of stopping criteria satisfied.
clear
close all
clc
%% creating the mesh
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
%% for plotting the surface of stalagmite
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
surfc(xx,yy,-f)
shading interp
%% evalutaing the function
options=optimoptions('ga','PlotFcn',{@gaplotbestf,@gaplotstopping},'populationsize',170);
[x,fval]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],options)
xopt=x(1);
yopt=x(2);
figure(1)
hold on
plot3(xopt,yopt,-fval,'ro','markersize',5,'markerfacecolor','r')OUTPUT
Thus, it can be much more visualized that how the fitness is been calculated and best result is displayed even with the decrease in the size of population.
References:
https://mech.iitm.ac.in/nspch52.pdf
https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm