Week 4.1 - Genetic Algorithm
https://drive.google.com/file/d/1YxeTzV-NKTPc4YKm7zK5_wpFozmwYLXp/view?usp=sharing
GENETIC ALGORITHM
Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and
Natural Selection. It is frequently used to find optimal or near-optimal solutions to
difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve
optimization problems, in research, and in machine learning.
What are Genetic Algorithms?
Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAs) are search based
algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of
computation known as Evolutionary Computation.
GAs were developed by John Holland and his students and colleagues at the University of Michigan,
most notably David E. Goldberg and has since been tried on various optimization problems with a
high degree of success.
In GAs, we have a pool or a population of possible solutions to the given problem.
These solutions then undergo recombination and mutation (like in natural genetics),
producing new children, and the process is repeated over various generations.
Each individual (or candidate solution) is assigned a fitness value (based on its objective function value)
and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals.
This is in line with the Darwinian Theory of “Survival of the Fittest”.
In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.
Genetic Algorithms are sufficiently randomized in nature, but they perform much better than
random local search (in which we just try various random solutions, keeping track of the best so far),
as they exploit historical information as well.
Advantages of GAs
GAs have various advantages which have made them immensely popular. These include −
Does not require any derivative information (which may not be available for many real-world problems).
Is faster and more efficient as compared to the traditional methods.
Has very good parallel capabilities.
Optimizes both continuous and discrete functions and also multi-objective problems.
Provides a list of “good” solutions and not just a single solution.
Always gets an answer to the problem, which gets better over the time.
Useful when the search space is very large and there are a large number of parameters involved.
Limitations of GAs
Like any technique, GAs also suffer from a few limitations. These include −
GAs are not suited for all problems, especially problems which are simple and for which derivative information is available.
Fitness value is calculated repeatedly which might be computationally expensive for some problems.
Being stochastic, there are no guarantees on the optimality or the quality of the solution.
If not implemented properly, the GA may not converge to the optimal solution.
Syntax used for genetic algorithm in this program
1. x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function,
fun. nvars is the dimension (number of design variables) of fun.
2.x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables,
x, so that a solution is found in the range lb ≤ x ≤ ub.
(Set Aeq=[] and beq=[] if no linear equalities exist.)
3.x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters
replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.)
Create options using optimoptions.
stalagmite
why do we have use stalagmite?
it is just the real world reference we used in our program to make it more relatable and more understandable.
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. There are many other types of mineral formations
found in caves.
what is mathematical modelling
Mathematical modelling is the process of describing a real world problem in mathematical terms,
usually in the form of equations, and then using these equations both to help understand the original problem,
and also to discover new features about the problem.
Applications of mathematical modelling
epidemiology
biological transport
vehicular traffic
optimal strategies in business
economics
financial industry
engineering
software development
solution
formula to find the function
#find the global maxima of the function using genetic algorithm.
clear all
close all
clc
%defining the search space
x=linspace(0,0.6,150); %linspace used to get equal space between vectors
y=linspace(0,0.6,150);%linspace used to get equal space between vectors
num_cases=50;%no of times my genetic algorthim will run
%creating a 2D dimensional mesh
[xx, yy]=meshgrid(x,y);
%evaluating the stalagmite function
for i=1:length(xx) %used for loop
for j=1:length(yy)
input_vector(1)=xx(i,j);%defining input vector
input_vector(2)=yy(i,j);%defining input vector
f(i,j)=stalagmite(input_vector);%calling stalagmite function
end
end
surfc(xx,yy,f)%Contour plot under surface plot
xlabel('x axis')%for labelling the x axis
ylabel('y axis')%for labelling the y axis
shading interp %shading interp varies the color in each line segment and face by interpolating
%the colormap index or true color value across the line or face.
[input, fval]=ga(@stalagmite,2);%using genetic algorithm,it finds a local unconstrained minimum
x=linspace(0,0.6,150);%linspace used to get equal space between vectors
y=linspace(0,0.6,150);%linspace used to get equal space between vectors
num_cases=50;%no of times my genetic algorthim will run
%tic works with the toc function to measure elapsed time.
%The tic function records the current time and
%the toc function uses the recorded value to calculate the elapsed time.
tic %The tic function records the current time
%study 1 - statistical behaviour
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study_time=toc;%the toc function uses the recorded value to calculate the elapsed time.
figure(1)
subplot(2,1,1)%to plot the second graph in the existing graph
hold on%to add a second line plot without deleting the existing line plot.
surfc(x,y,f)%Contour plot under surface plot
shading interp%shading interp varies the color in each line segment and face by interpolating
%the colormap index or true color value across the line or face.
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')%to plot the graph between xopt,yopt and fopt.
title('unbounded inputs') %to give the title
subplot(2,1,2)%to plot the second graph in the existing graph
plot(fopt)%to plot the fopt
xlabel('iterations')%for labelling the x axis
ylabel('Function minimum')%for labelling the y axis
tic%The tic function records the current time
%study 2 =statistical behaviour -with upper bound and lower bound
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);%this syntax of genetic algorithm defines a set of lower and upper bounds on the design variables
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study_time=toc;%the toc function uses the recorded value to calculate the elapsed time.
figure(2)
subplot(2,1,1)%to plot the second graph in the existing graph
hold on%to add a second line plot without deleting the existing line plot.
surfc(x,y,f)%Contour plot under surface plot
shading interp%shading interp varies the color in each line segment and face by interpolating
%the colormap index or true color value across the line or face.
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')%to plot the graph between xopt,yopt and fopt.
title('bounded inputs')%to give the title
subplot(2,1,2)%to plot the second graph in the existing graph
plot(fopt)%to plot the fopt
xlabel('iterations')%for labelling the x axis
ylabel('Function minimum')%for labelling the y axis
%study 3 increasing ga iteration
options=optimoptions('ga');
options=optimoptions(options,'populationsize',170)%we have increased the size to 170 here
tic
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);%in this genetic algorithm ,it minimizes with the default optimization parameters
%replaced by values in options.
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study_time=toc;
figure(3)
subplot(2,1,1)%to plot the second graph in the existing graph
hold on%to add a second line plot without deleting the existing line plot.
surfc(x,y,f)%Contour plot under surface plot
shading interp%shading interp varies the color in each line segment and face by interpolating
%the colormap index or true color value across the line or face.
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')%to plot the graph between xopt,yopt and fopt.
title('bounded inputs')%to give the title
subplot(2,1,2)%to plot the second graph in the existing graph
plot(fopt)%to plot the fopt
xlabel('iterations')%for labelling the x axis
ylabel('Function minimum')%for labelling the y axis
#function
function f= stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);
f1=(sin(5.1*pi*x+0.5))^6;
f2=(sin(5.1*pi*y+0.5))^6;
term1=-4*log(2);
term2=(x-0.0667)^2;
term3=0.64;
term4=(y-0.0667)^2;
f3=exp(term1*(term2)/(term3));
f4=exp(term1*(term4)/(term3));
f=-(f1*f2*f3*f4);
end
the global maxima is the point on the highest peak.
conclusion
genetic algorithm is use for finding global minima so we add the -ve sign to make it global maxima.
to decrease the time for running the program we can reduce the limits and it will show more accurate results.
parse error
in my program ,it is caused by not using proper arithmatic according to matlab
i had used the dot before the log instead of dot i have to use multiplication (*).
sources
https://www.youtube.com/watch?v=df5EK1P6Ph0&list=PLKR57ZbLAFd7qx7Liej3UIZLuMGO07nj0&index=2
https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.htm#:~:text=Genetic%20Algorithm%20(GA)%20is%20a,take%20a%20lifetime%20to%20solve.
https://in.mathworks.com/help/
google images