Week 5 - Genetic Algorithm
AIM :
- Concept of genetic algorithm.
- Information regarding stalagmite function and ways to optimise it.
- Finding the global maxima of the function.
- Plot graphs for all 3 studies and for F maximum vs no. of iterations.
OBJECTIVES :
The objective of this report is to optimize the Stalagmite function by coding the program with help of Genetic algorithm in MATLAB and explain the concept of Genetic algorithm and also explain the syntax of “ga” in MATLAB .
STALAGMITE :
A Stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of the material deposited on the floor from ceiling drippings. Stalagmites are typically composed of calcium carbonate, but may consist of lava, mud, peat, pitch, sand, sinter and amberat (crystallized urine of pack rats.)
Since our function gives a shape of stalagmite it is named as stalagmite function . Stalagmite function is the mathematical model that helps us to generate minimas and maximas. It is 3-Dimensional function and is designate to generate local maximas.
THEORY OF GENETIC ALGIORITHM:
A Genetic Algorithm is a search heuristic that is inspired by Charles Darwin’s Theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individual is selected for reproduction in order to produce offspring of the next generation.
In computer science, operations research , a genetic algorithm are commonly used to generate high-quality solutions to optimation and search problems by relying on biologically inspired operators such as mutations, crossover and selection. John Holland introduced genetic algorithm in 1960 based on the concept of Darwin’s theory Od evolution, and his student David E.Goldberg further extended GA in 1989.
Notion of Natural selection
The process of natural selection starts with the selection of fittest individual from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation .If parents have better fitness ,their offspring’s will be better than parents and have better chance of survival. This process keeps on iterating until it generates the fittest individual.
This notion can be applied for search problem .We considers set of solution for a problem and select the set of best one out of them.
Five set are consider in a Genetic Algorithm.
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
- Initial Population : The process begins with the set of individual which is called as population. Each individual is solution to the problem you want to solve.
An individual is characterized by a set of parameters (variables) known as Genes .Genes are joined into strings to form a Chromosome (solution).
In genetic algorithm, the set of genes of individual is represented using string, in term of an alphabet; usually binary values are used (strings of 1s and 0s). We say that we encode the genes in chromosome.
- FITNESS FUNCTION :
The fitness function determines how fit an individual is (the ability of an individual to compete with individuals). It gives the fitness score to each individual .The probability that an individual will be selected for reproduction is based on it fitness score.
- SELECTION :
The idea of selection phase is to select the fittest individuals and let them pass on their genes to next generation.
Two pairs of individuals (parents) are selected based on fitness scores. Individual with high fitness have more chance to be selected for reproduction.
- CROSSOVER :
Crossover is the most significant phase in a genetic algorithm .For each pair of parents to be mated a crossover point is chosen at random from within the genes.
For example, consider the crossover points to be 3 as shown below.
Offspring’s are created by exchanging the genes of parents among themselves until the crossover point is reached.
The new offspring are added to the population
- MUTATION :
In certain new offspring formed, some off their genes are subjected to a mutation with a low random probability. This implies that some of the bots in the bit string can be flipped.
Mutation occurs to maintain diversity within the population and prevent premature convergence.
- TERMINATION :
The algorithm terminates if the population has converged. Then it is said that the genetic algorithm has provided the set of solution to our problem.
Using this approach of Genetic Algorithm we are going to optimize the stalagmite function and find the optimized value of stalagmite function.
GOVERNING EQUATION:
To generate the stalagmite function following function is used.
PROGRAM:
CODE FOR FINDING GLOBAL MAXIMA :-
clear all
close all
clc
[% Defining our Search Space]
x = linspace(0,0.6,150); [ for x]
y = linspace(0,0.6,150); [for y]
[% Creating 2-d Array]
[xx,yy] = meshgrid(x,y)
[% Calculating Fitting Function]
for i = 1:length(xx); [length of i]
for j = 1:length(yy); [length of j]
input(1) = xx(i,j); [inputs]
input(2) = yy(i,j); [inputs]
f(i,j) = stalagmite_func(input);
end
end
[% Converting Fitting Function to change the graph upwards]
F = -f;
[% Plotting Stalagmite Function]
surface(xx,yy,F);
[% shading interp;]
hold on;
[% Performing the Genetic Algorithm]
[output , fval] = ga(@stalagmite_func,2,[],[],[],[],[0,0],[0.6,0.6])
[% Plotting Global Maxima]
x_max = output(:,1);
y_max = output(:,2);
f_max = -fval;
plot3(x_max,y_max,f_max,'marker','o','markersize',5,'markerfacecolor','r');
xlabel ('X-value');
ylabel ('y-value');
title('GLOBAL MAXIMA');
legend('STALAGMITE','GLOBAL MAXIMA')
Study 1 : STATISTICAL BEHAVIOUR
CODE :
clear all
close all
clc
[% Defining our Search Space]
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_case = 50;
[% Creating 2-d Array]
[xx,yy] = meshgrid(x,y)
[% Calculating Fitting Function]
for i = 1:length(xx);
for j = 1:length(yy);
input(1) = xx(i,j);
input(2) = yy(i,j);
f(i,j) = stalagmite_func(input);
end
end
[% Converting Fitting Function to change the graph upwards]
F = -f;
[% Performing the Genetic Algorithm]
tic
for k =1:num_case
[inputs , fopt(k)] = ga(@stalagmite_func,2);
xopt(k) = inputs(1);
yopt(k) = inputs(2);
end
study_time = toc
[% Plotting Global Maxima And Function Values]
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,F)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel ('X-value');
ylabel ('y-value');
title('Unbounded Inputs');
legend('STALAGMITE','GLOBAL MAXIMA')
subplot(2,1,2)
hold on
plot(fopt)
xlabel ('Iterations');
ylabel ('Function Maxima');
title('Variation in F');
legend('Change in F value')
Study 2 : STATISTICAL BEHAVIOUR WITH UNBOUNDED INPUTS AND INCREASED POPULATION.
CODE:
clear all
close all
clc
[% Defining our Search Space 1-D Array]
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_case = 50;
% Creating 2-d Array
[xx,yy] = meshgrid(x,y)
% Calculating Fitting Function
for i = 1:length(xx);
for j = 1:length(yy);
input(1) = xx(i,j);
input(2) = yy(i,j);
f(i,j) = stalagmite_func(input);
end
end
% Converting Fitting Function to change the graph upwards
F = -f;
% Performing the Genetic Algorithm
tic
for m =1:num_case
[inputs , fopt(m)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(m) = inputs(1);
yopt(m) = inputs(2);
end
Fopt = - fopt;
study2_time = toc
% Plotting Global Maxima And Function Values
figure(1)
subplot(2,1,1)
hold on
surface(x,y,F)
shading interp
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel ('X-value');
ylabel ('y-value');
title('Unbounded Inputs');
legend('STALAGMITE','GLOBAL MAXIMA')
subplot(2,1,2)
hold on
plot(Fopt)
xlabel ('Iterations');
ylabel ('Function Maxima');
title('Variation in F');
legend('Change in F value')
Study 3 : STATITICAL BEHAVIOUR WITH BOUNDED INPUTS AND INCREASED POPULATION
CODE :-
clear all
close all
clc
[% Defining our Search Space 1-D Array]
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_case = 50;
[% Creating 2-d Array]
[xx,yy] = meshgrid(x,y)
[% Calculating Fitting Function]
for i = 1:length(xx);
for j = 1:length(yy);
input(1) = xx(i,j);
input(2) = yy(i,j);
f(i,j) = stalagmite_func(input);
end
end
[% Converting Fitting Function to change the graph upwards]
F = -f;
[% Performing the Genetic Algorithm]
tic
for m =1:num_case
[inputs , fopt(m)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(m) = inputs(1);
yopt(m) = inputs(2);
end
Fopt = - fopt;
study2_time = toc
[% Plotting Global Maxima And Function Values]
figure(1)
subplot(2,1,1)
hold on
surface(x,y,F)
shading interp
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel ('X-value');
ylabel ('y-value');
title('Unbounded Inputs');
legend('STALAGMITE','GLOBAL MAXIMA')
subplot(2,1,2)
hold on
plot(Fopt)
xlabel ('Iterations');
ylabel ('Function Maxima');
title('Variation in F');
legend('Change in F value')
References :
- https://www.youtube.com/watch?v=8DZH20i52jw&t=2258s
- https://www.youtube.com/watch?v=8DZH20i52jw&list=TLPQMTgwMTIwMjE80zYapPSC5g&index=1
- https://www.youtube.com/watch?v=nas28_u-dJw&list=PLYwpaL_SFmcDHUTN26NXKfjg6wFJKDO9R&index=2
- https://www.youtube.com/watch?v=skqn8nAwt5w
- https://www.youtube.com/watch?v=HM6RhxWcXnY&t=57s
- https://www.youtube.com/watch?v=LREPlWJmvAY