Week 4 - Genetic Algorithm
AIM - To study about Genetic Algorithm and to calculate Global Maxima of Stalagmite function using GA in Matlab.
OBJECTIVE -
- To Study About Genetic Algorithm and Stalagmite Function.
- To Write Code in Matlab to Optimise the Stalagmite Function and Find the Global Maxima of the fFnction.
- To Plot Graphs for all 3 related studies.
THEORY-
A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.
We can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.
The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.
| Classical Algorithm | Genetic Algorithm |
|---|---|
| Generates a single point at each iteration. The sequence of points approaches an optimal solution. | Generates a population of points at each iteration. The best point in the population approaches an optimal solution. |
| Selects the next point in the sequence by a deterministic computation. | Selects the next population by computation which uses random number generators. |
FLOW CHART OF GENETIC ALGORITHM
MEANING OF STALAGMITE -
A stalagmite 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 .
STALAGMITE FUNCTION-
Stalagmite function is a mathematical model which helps to generate local Maxima and Minima.
CODE FOR STALAGMITE FUNCTION-
%Stalagmite Function Code
function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x+0.5))^6;
f2 = exp(-4*log(2)*((x-0.0667)^2)/0.64);
f3 = (sin(5.1*pi*y+0.5))^6;
f4 = exp(-4*log(2)*((y-0.0667)^2)/0.64);
f = -(f1*f2*f3*f4);
endSYNTAX FOR GENETIC ALGORITHM (GA)-
Syntax
Description
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
ABBREVIATION-
- fun - Objective Function
- nvars - No. Of Variables
- A,b - Linear Inequality Constraints ;
A*x≤b - Aeq , beq - Linear Equality constraints ;
Aeq*x=beq - lb , ub, - Lower Bound , Upper Bound
- nonlcon - Non linear Constraints
- options - Optimization option.
MATLAB CODE FOR STALAGMITE FUNCTION-
clear all
close all
clc
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%Creating a 2d mesh
[xx yy] = meshgrid(x,y);
tic
%Evaluate the stalagmite 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);
end
end
study_time = toc
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')
title('Stalagmite function')
shading interp
[inputs , fval] = ga(@stalagmite,2)
CODE FOR DIFFERENT STUDIES-
%Optimization Of Stalagmite Function Using GA
clear all
close all
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50
f = get_stalagmite(x,y);
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')
tic %The tic function records the current time.
%Study 2 - Statistical Behaviour - With upper and lower bounds
for i = 1:num_cases
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study2_time = toc %The toc function uses the recorded value to calculate the elapsed time
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')
%Study 3 - Increasing GA Iterations
options = optimoptions ('ga')
options = optimoptions (options,'PopulationSize',150);
tic
for i = 1:num_cases
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],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,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs With Increased Population')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')
RESULTS-
1.Stalagmite Function
2.STUDY 1- Statistical Behavior With Unbound Inputs
In above plot it can be observed that how the random sampling of genetic algorithm generates a new optimum value for the function every time the code is run.
3.STUDY 2-Statistical Behaviour With Upper And Lower Bounds
Above plots show convergence of x and y values.The above value is with upper and lower bounds.
4.STUDY 3-Statistical Behaviour With Inceasing Iteration Of GA
Number of iteration is increased to 150.