Week 4.1 - Genetic Algorithm
Aim
- To optimise the stalagmite function and find the global maxima of the function.
- To understand the concept of Genetic algorithem.
Objectives
- Explain the concepts of genetic algorithem and also explain the syntax for ga in matlab.
- Plot graphs for all 3 studies and for F maximum vs no. of iterations.
Theory
Introduction
A genetic algorithm is a experimental search method used in artificial intelligence and computing. This algorithm reproduces the process of natural selection where the appropriate individuals are selected for reproduction in order to produce offspring of the next generation.
The genetic algorithem is a technique for solving optimization problems that are based on natural selection, the process that drives the biological evolution.
Phases in genetic algorithem
- Initialization of population
The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on no. of iterations performed
2. Fitness Function
It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with the fitness value of each member generated, these fitness values are used for the reproduction of the children.
3.Selection
The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more.
Inspiration for this is from the survival of the fittest.
It should be a balance between exploration and exploitation of search space.
GA tries to move the genotype to higher fitness in the search space.
Too strong fitness selection bias can lead to sub-optimal solutions.
Too little fitness bias selection results in unfocused search.
- Reproduction
Generation of offspring happen in 2 ways:
Crossover
Mutation
- a) Crossover
Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.
There are 3 major types of crossover.
Single Point Crossover: A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’.
Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes.
Uniform Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability. The new offspring are added to the population.
- Mutation
In a few new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.
Syntax for GA:
[x,fval ,exitflag ,output ,population ,scores]= ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,Intcon,options)
x = optimum solution
exitflag = reason ga stopped
output= information about optimization process
population=final population
scores= final scores
f=ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
fun - fitness function.
nvars- number of variables,
A,b= Linear inequality constraints
Aeq,beq=Linear equality constraints
lb- Lower bound(limit),
ub- Upper bound(limit),
nonlcon : Use for nonlinear constraints
IntCon : to get solution in integer.
options- To set population size minimize with non-default options
BODY OF THE CONTENT:
- FITNESS FUNCTION
`f(x,y) = f_(1,x)f_(2,x)f_(1,y)f_(2,y)`
`f_(1,x) = [sin(5.1pix+0.5)]^6` `f_(1,y) = [sin(5.1piy+0.5)]^6`
`f_(2,x) = exp[-4ln(2)(x-0.0667)^2/0.64]`
`f_(2,y) = exp[-4ln(2)(y-0.0667)^2/0.64]`
These equations are used in stalagmite function to plot the graph in main function.
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
At the end of the function we are using a negative sign so that the plot will be reversed since we have to find the maxima of the given function using ga.
clear all
close all
clc
% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases=50; %Number of iteration for which the function will evaluate the fitness
% Creating a 2Dimensional mesh
[xx,yy] = meshgrid(x,y);
% Evaluating the stalagmaite 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); %values of function in given search space
end
end
surfc(xx,yy,-f) %generating the surface
shading interp %To remove the lines produced by the mesh grid
[inputs,fval] = ga(@stalagmite,2)
- Two vectors x,y are defined. Creating a mesh from the given 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.
Result
- 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')Result
- From the above graph it is clear that the results are not that mcuh accurate
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')Result
- After providing the lower and upper limits the variation in the optimum value of the function has reduced.
STATISTICAL STUDY WITH 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')
- It is clearly seen in the above case that the value of the variation range has changed to a large extent.
The whole programme is written at once,
clear all
close all
clc
% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50; %Number of iteration for which the function will evaluate the fitness
% Creating a 2Dimensional mesh
[xx,yy] = meshgrid(x,y);
% Evaluating the stalagmaite 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); %values of function in given search space
end
end
surfc(xx,yy,-f) %generating the surface
shading interp %To remove the lines produced by the mesh grid
[inputs,fval] = ga(@stalagmite,2)
% 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')
% 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')
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')
Output
ga is useful for optimizing the function but still the result are not accurate. The maximum value of the function lies at -1.
to overcome this we use following progamme.
clear
close all
clc
% creating a 2D 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')This programme will display the best value in the graph.
Result
