Week 4 - Genetic Algorithm
Aim :- To optimise the stalagmite function and find the global maxima of the function using MATLAB.
Plot graphs for all 3 studies and for F maximum vs no of iterations.
Genetic Algorithm
Terminology :- GAs are a subset of a much larger branch of computation known as Evolutionary Computation. 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”.
GA motivation
Genetic Algorithms have the ability to deliver a “good-enough” solution “fast-enough”. This makes genetic algorithms attractive for use in solving optimization problems.
Flow of the ga can be expalined by the flow chart given below:-
Basic Terminology
1) Population :- It is a subset of all the possible (encoded) solutions to the given problem. The population for a GA is analogous to the population for human beings except that instead of human beings, we have Candidate Solutions representing human beings.
2) Chromosomes :- A chromosome is one such solution to the given problem.
3) Genes :- A gene is one element position of a chromosome.
4) Allele :- It is the value a gene takes for a particular chromosome.
5) Genotype :- Genotype is the population in the computation space. In the computation space, the solutions are represented in a way which can be easily understood and manipulated using a computing system.
6) Phenotype :- Phenotype is the population in the actual real world solution space in which solutions are represented in a way they are represented in real world situations.
7) Decoding and Encoding :- Decoding is a process of transforming a solution from the genotype to the phenotype space, while encoding is a process of transforming from the phenotype to genotype space. Decoding should be fast as it is carried out repeatedly in a GA during the fitness value calculation.
8) Fitness Function :- A fitness function simply defined is a function which takes the solution as input and produces the suitability of the solution as the output. In some cases, the fitness function and the objective function may be the same, while in others it might be different based on the problem.
9) Genetic operators :- These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc.
Termination Condition
The termination condition of a Genetic Algorithm is important in determining when a GA run will end. It has been observed that initially, the GA progresses very fast with better solutions coming in every few iterations, but this tends to saturate in the later stages where the improvements are very small. We usually want a termination condition such that our solution is close to the optimal, at the end of the run.
Usually, we keep one of the following termination conditions −
- When there has been no improvement in the population for X iterations.
- When we reach an absolute number of generations.
- When the objective function value has reached a certain pre-defined value.
Syntax for ga in MATLAB.
x = ga(fun,nvars,A,b)x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').
x = ga(fun,nvars,A,b,Aeq,beq)x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)
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.)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)IntCon take integer values.
x = ga(problem)problem, a structure described in problem.
[, for any previous input arguments, also returns x,fval] = ga(___)fval, the value of the fitness function at x.
[ also returns x,fval,exitflag,output] = ga(___)exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
[ also returns a matrix x,fval,exitflag,output,population,scores] = ga(___)population, whose rows are the final population, and a vector scores, the scores of the final population.
FUNCTION CODE FOR STALAGMITE 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 ;
t=((x-0.0667)^2/0.64)
t1=((y-0.0667)^2/0.64)
f3 = exp(-4*log(2)*t);
f4 = exp(-4*log(2)*t1);
f= -(f1.*f2.*f3.*f4)
end
MAIN CODE TO OPTIMISE THE STALAGMITE FUNCTION AND FIND GLOBAL MAXIMA
clear all
close all
clc
%Defining search space for ga
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iteration = 50;
%creating a 2d array and generating the mesh for it
[xx,yy] = meshgrid(x,y);
% evaluating the stlagmite 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 1
tic
for i= 1:iteration;
[inputs1, fval1(i)] = ga(@stalagmite,2)
xopt1(i)= inputs1(1);
yopt1(i)= inputs1(2);
end
study1_time = toc
figure(1)
subplot(2,1,1)
hold on
f1 = -f
surfc(xx,yy,f1)
shading interp
title ('unbounded trial');
xlabel('X-values')
ylabel('Y-values')
fval11 = -fval1
plot3(xopt1,yopt1,fval11,'marker','o','markersize',5,'markerfacecolor','r');
subplot(2,1,2);
plot(fval1)
xlabel('Iterations')
ylabel('Function Maximum')
%Study 2
tic
for i= 1:iteration
[inputs2, fval2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt2(i)= inputs2(1);
yopt2(i)= inputs2(2);
end
study2_time = toc;
figure(2)
subplot(2,1,1)
hold on
f2=-f
surfc(xx,yy,f2)
shading interp
title ('bounded trial');
xlabel('X-values')
ylabel('Y-values')
fval22=-fval2;
plot3(xopt2,yopt2,fval22,'marker','o','markersize',5,'markerfacecolor','k');
subplot(2,1,2);
plot(fval2)
xlabel('Iterations')
ylabel('Function Maximum')
%study 3
tic
options = optimoptions('ga'); %optimising the ga
options = optimoptions(options,'PopulationSize',200); %then calling it it here
for i= 1:iteration
[inputs3, fval3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);% putting the boundary conditions
xopt3(i)= inputs3(1);
yopt3(i)= inputs3(2);
end
study3_time = toc;
figure(3)
subplot(2,1,1)
hold on
f3 = -f
surfc(xx,yy,f3)
shading interp
title ('bounded trial Constrained population');
xlabel('X-values')
ylabel('Y-values')
fval33 = -fval3
plot3(xopt3,yopt3,fval33,'marker','o','markersize',5,'markerfacecolor','c');
subplot(2,1,2);
plot(fval3)
xlabel('Iterations')
ylabel('Function Maximum')
Max_value = fval3
fprintf ('\n Study 1 :- unbounded statiscal behavior')
fprintf ('\n The time taken for study 1 is : %f',study1_time)
fprintf ('\n The co ordinate of x and y for global maxima of the function is:%f%f',inputs1(1),inputs1(2))
fprintf ('\n The gobal maxima of the function is :%f',-(stalagmite(inputs1)))
fprintf ('\n Study 2 :- Bounded statiscal behavior')
fprintf ('\n The time taken for study 2 is : %f',study2_time)
fprintf ('\n The co ordinate of x and y for global maxima of the function is:%f%f',inputs2(1),inputs2(2))
fprintf ('\n The gobal maxima of the function is :%f',-(stalagmite(inputs2)))
fprintf ('\n Study 3 :- Bounded statiscal behavior with population control')
fprintf ('\n The time taken for study 3 is : %f',study3_time)
fprintf ('\n The co ordinate of x and y for global maxima of the function is:%f%f',inputs3(1),inputs3(2))
fprintf ('\n The gobal maxima of the function is :%f',-(stalagmite(inputs3)))
NOTE :- GA always uses random sampling and gives us the minima of the function so to get the maxima from the program we use the rule `f max = - f min`
PLOTS
1) Unbounded Statistical Behavior
2) Bounded Statistical Behavior
3) Bounded Statistical Analaysis with specified Constraints and population size
OUTPUT WINDOW
Study 1 :- unbounded statiscal behavior
The time taken for study 1 is : 109.230463
The co ordinate of x and y for global maxima of the function is:-0.135472-0.148805
t =
0.0639
t1 =
0.0726
f =
-0.4928
The gobal maxima of the function is :0.492763
Study 2 :- Bounded statiscal behavior
The time taken for study 2 is : 75.088955
The co ordinate of x and y for global maxima of the function is:0.0668350.066836
t =
2.8439e-08
t1 =
2.8732e-08
f =
-1.0000
The gobal maxima of the function is :1.000000
Study 3 :- Bounded statiscal behavior with population control
The time taken for study 3 is : 281.228103
The co ordinate of x and y for global maxima of the function is:0.0668320.066831
t =
2.7385e-08
t1 =
2.6964e-08
f =
-1.0000
The gobal maxima of the function is :1.000000>> I ran the code multiple times and all of the time the Function Value was 1 which is the global maxima.