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.

 
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

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.