Genetic Algorithm
AIM - To study genetic algorithm and optimise stalagmite function by using it.
stalagmite function -
It is function of two variable which contains lot of local maxima solutions.and very difficult to evaluate for global maximum.mathematically represented as -
`f(x,y) = f1(x)f2(x)f1(y)f2(y)`
where;
`f1(x) = [sin(5.1*pi*x+0.5)]^6`;
f1(y) = `[sin(5.1*pi*y+0.5)]^6`;
`f2(x) = exp(-4*ln(2)*(x-0.0667)^2/0.64)`;
`f2(y) = exp(-4*ln(2)*(y-0.0667)^2/0.64)`;
plot of stalagmite function-
Genetic Algorithm -
It is evolutionary algorithm based of darwins theory of evolution which states that only fittest servives.It is approach to find function optimum value.In genetic algorithm fittest individuals are selected to produce offspring for next genaration.offspring are fitter than their parents and fitter offspring will produce more fit generations. this process goes on repeating until fittest individual is created. five phases of genetic algorithms are as follows-
1)Initial population
2)Fitness criteria
3)Selection
4)Crossover
5)Mutation
1)Initial population
first stage starts selecting initial set of individuals call as population.each individual have certain properties call as genes and set of properties is called as chromosome.
2)Fitness criteria
fitness criteria determines probablity of individual by giving fitness score on its solution.
3)Selection
In this generation pairs of fit individuals are selected to produce next generation.
4)Crossover
In this phase offspring are produced by mating fit individuals.random crossover point is selected for mating.
5)Mutation
Certain genes of individual are changed with low probablity to maintain diversity.
Syntax for inbuild ga function in matlab -
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
where,
x -optimum solution
fun -function to be optimised
nvars- number of variables
A,b- linear inequalities A*x ≤ b
Aeq,Beq - linear equalities Aeq*x = beq
lb,ub - it defines set of lower bounds and upper bounds,eg - 0<x<5 ;2<y<4 then lb -[0,2] and ub-[5,4]
nonlcon - it is used provide non linear inequaltity and equality contraint functions.
options -it is used to change default optimisation parameters ,options are provided using optimoptions.
[] -used to skip the particular input from above to genetic algorithm.
genetic algorithm is only used for minimisation purpose. to obtian maxima for function provide negative sign to function it will give is negative minima which is required maximum value.
MATLAB CODE -
We will study genetic algorithm by considering three cases
1)inputs are unbounded means they can take any random value.
2)bounded inputs means they can take value between certain region. all values beyon region are prohibited.
3)bounded inputs with increasing initial polpulation. by increasing initial population chances to reach global maxima increases but requires more solver time.
main code-
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)
%study 1 -statistical behaviour
for i=1:num_cases
[inputs,fopt(i)] =ga(@stalagmite,2);
xopt(i) =inputs(1);
yopt(i) =inputs(2);
end
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')
%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
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 the GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',250);
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
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 modified population size')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')
code for stalagmite function -
function[fall] =stalagmite(input_vector);
x = input_vector(1);
y = input_vector(2);
fx1 = [sin(5.1*pi.*x+0.5)].^6;
fy1 = [sin(5.1*pi.*y+0.5)].^6;
fx2 = exp(((-4)*log(2).*(x-0.0667).^2)/0.64);
fy2 = exp(((-4)*log(2).*(y-0.0667).^2)/0.64);
fall= -(fx1*fx2*fy1*fy2);
endcode for get _stalagmite-
function[g]=get_stalagmite(x,y)
clear all
close all
clc
%defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%creating 2D mesh
[xx yy] = meshgrid(x,y);
%evaluating 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
g=f;
endExplaination of code -
clear all ,close all and clc - to clear previous variables and clearing command window. then set of x and y variables is created using linspace command.
Genetic algorithm has to run for 50 times so num_cases is taken as 50.for loop is used to solve genetic algorithm for each case.
subplot divides figure in 2 by 1 array to show to output in one figure.
surfc to plot surface and grid is disabled using interp.title,xlabel,ylabel to provide title to plot and describe x axis,y axis quantities respectively.
For providing population size ,option variable is used by taking output of optimoptions.
Output of code -
case 1)unbounded input
it is seen that large number of local minimas are captured.
case 2) bounded inputs
it is showing that optimum solution lies between 0.7 to 1
case 3)bounded inputs with increased population
it is seen than solution converges to -1 which is global minima. in other words maximum value of stalagmite function. optimum valu of x is 0.0667 and y is 0.0667, and maximum value of function is 1.
references-
https://en.wikipedia.org/wiki/Genetic_algorithm
https://www.sciencedirect.com/topics/engineering/genetic-algorithm