AIM:-
Write a code in MATLAB to optimise the stalagmite function & find the global maxima
THEORY :-
Genetic Algorithm is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms.
A genetic algorithm is a heuristic search method used in artificial intelligence and computing. It is used for finding optimized solutions to search problems based on the theory of natural selection and evolutionary biology. Genetic algorithms are excellent for searching through large and complex data sets. They are considered capable of finding reasonable solutions to complex issues as they are highly capable of solving unconstrained and constrained optimization issues.
A genetic algorithm makes uses of techniques inspired from evolutionary biology such as selection, mutation, inheritance, and recombination to solve a problem. The most employed method in genetic algorithms is to create a group of individuals randomly from a given population. The individuals thus formed are evaluated with the help of the evaluation function provided by the programmer. Individuals are then provided with a score which indirectly highlights the fitness to the given situation. The best two individuals are then used to create one or more offspring, after which random mutations are done on the offspring. Depending on the needs of the application, the procedure continues until an acceptable solution is derived or until a certain number of generations have passed.
A genetic algorithm differs from a classical, derivative-based, optimization algorithm in two ways:
• A genetic algorithm generates a population of points in each iteration, whereas a classical algorithm generates a single point at each iteration.
• A genetic algorithm selects the next population by computation using random number generators, whereas a classical algorithm selects the next point by deterministic computation.
Compared to traditional artificial intelligence, a genetic algorithm provides many advantages. It is more robust and is susceptible to breakdowns due to slight changes in inputs or due to the presence of noise. With respect to other optimization methods like praxis, linear programming, heuristic, first or breadth-first, a genetic algorithm can provide better and more significant results while searching large multi-modal state spaces, large state spaces or n-dimensional surfaces.
GA function in MATLAB
GA function in MATLAB is used to find the minimum of function using genetic algorithm
X=ga(problem)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values. [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
where fun =objective function (in our case stalagmite)
nvars -number of variables (in our case 2)
A= Linear inequality constraints
b=Linear inequality constraints
Aeq=Linear equality constraints
beq= Linear equality constraints
lb =lower bounds
ub= upper bounds
nonlcon= nonlinear constraints
options = optimization options
Stalagmite Function
MATLAB CODE FOR STALAGMITE FUNCTION
The following code will create a function named “stalagmite” that accepts inputs as “input_vector” and returns output “S”.
function S = 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;
f3=exp((-4*log(2))*(x-0.0667)^2/0.64);
f4=exp((-4*log(2))*(y-0.0667)^2/0.64);
S=-(f1*f2*f3*f4);
end
Stalagmite function explanation
1. The function code is created with name “stalagmite” that accepts inputs as “input _vector” and returns output “S”.
2. Different parts of the functions are created in the code.
3. Then the output S is obtained by combining different parts of the code.
4. The function is provided with “-ve sign” to calculate maxima when calling the function in the GA main code as GA function always provide global minima to a function but we require global maxima.
MATLAB CODE FOR UNBOUNDED GA FUNCTION
Clear all
Close
Clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
[xx,yy]=meshgrid(x,y);
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)= stalagmite(input);
end
end
tic
% study 1- Statistical behaviour
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(x,y,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 Minimum')
Explanation of code for Unbounded GA function
1. In the first step, we define the variable x & y with linspace commands to create an array of 150 values from 0 to 0.6.
2. Then [X,Y] = meshgrid(x,y) transforms the domain specified by vectors x and y into arrays X and Y , which can be used to evaluate functions of two variables and three-dimensional mesh/surface plots. The rows of the output array X are copies of the vector x ; columns of the output array Y are copies of the vector y .
3. Now we will use a for loop to calculate stalagmite function at different values of inputs.
4. Then we will evaluate the stalagmite function using genetic algorithm function at each iteration using for loop.
5. Now the time of 50 iterations is calculated for all 50 iterations.
6. Now the values of all iterations are plotted after different processes have been carried out in ga function like selection, crossover, mutation.
7. The plot contains 2 subplots, one showing the different values of x,y & optimum function points calculated in different iterations & second sub plot showing no. of iterations Vs the range in which the optimum points lie.
8. The plot shows unbounded inputs between the iterations & minimum function.
MATLAB CODE FOR BOUNDED GA FUNCTION
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
[xx,yy]=meshgrid(x,y);
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)= stalagmite(input);
end
end
tic
% study2- statistical behaviour- with upper & lower bounds
for i=1:num_cases
[inputs,fopt2(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study2_time=toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(fopt2)
xlabel('Iterations')
ylabel('Function Minimum')
xopt
yopt
fopt
Explanation of code for Bounded GA function
1. In this study, we plot the values of ga function which shows bounded inputs between 0 & 0.6 The subplot shows more converging range with more optimum points lying in the shorter range.
MATLAB CODE FOR BOUNDED & INCREASED POULATION GA FUNCTION
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
[xx,yy]=meshgrid(x,y);
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)= stalagmite(input);
end
end
% study3- increasing GA iterations
tic
options=optimoptions('ga');
options=optimoptions(options,'populationSize',170);
for i=1:num_cases
[inputs,fopt3(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time=toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(fopt3)
xlabel('Iterations')
ylabel('Function Minimum')
xopt
yopt
fopt
Explanation of code for Bounded & Higher population GA function
1. In this study, we plot the values of ga function which shows bounded inputs between 0 & 0.6 along with initial population size of 170 points. The subplot shows more converging range with more optimum points lying in the shorter range.
Conclusion:-
In study 1,with unbounded inputs,we get the global maxima with a wider range values
In study 2 ,with bounded inputs,we get more converging global maxima with more shorter range
In study 3,with bounded inputs & more population size,we get almost a converged range with function value being the maximum & constant.
Complex Terms Explanation: -
1. Heuristic – it is a technique designed for solving a problem more quickly when classic methods are too slow or for finding an approximate solution more quickly when classic methods fail to find an exact solution.
A heuristic function, also simply called a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution.
2. Metaheuristic – high level procedure
3. Stalagmite - stalagmias, "dropping, trickling") is a type of rock formation that rises from the floor of a cave due to the accumulation of 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).
4. Stalagmite function - A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function.
References:-
What is a Genetic Algorithm? - Definition from Techopedia
Stalagmite - Wikipedia
Find minimum of function using genetic algorithm - MATLAB ga - MathWorks India
