Week 4 - Genetic Algorithm

Aim: Write a code in matlab to optimise stalagmite function and to find the Global Maximum of the function.

Optimization: Optimization is a process of finding the optimised solution to a problem .Its ia an iterative process which analyses the possible solutions for the best solution. It includes maximizing criteria like peoductivity,efficiency,strength,reliability while minimizing factors like cost,lead time etc. It is a tiring process to perform the iterations manually. So to make it easier we can use Optimization algorithm. Genetic Algorithm is one of the optimization alorithm.

Genetic Algorithm: Genetic Algorithm is based on evolution theory proposed by Charles Darwin. It is a natural selection process Genetic algorithm always returns the minimum values. we can use Genetic Algorithm for problems where there is a clear way to evaluate fitness. If your search space is not well constrained or your evaluation process is computationally expensive, discontinuous objective function, nondifferentiable, stochastic, or highly nonlinear. Genetic Algorithms may not find solutions in a sane amount of time. GAs rely on biologically inspired processes crossover, mutation and, selection.

Process followed by Genetic Algorithm:

Genetic Alogorithm starts with population initialization, the sample data in the population undergoes three steps

1.Selection: In selection process fittest individuals i.e the parents are selected from the sample data. The more fitter individulas in the population produce fitter offsprings over a time.

2.Crossover: crossover is used to combine the genetic information of two parents to generate new offspring. for example Set of genes from parent A is combined with set of genes with parent B. A better offsprings with both the parents qualities are produced.

3.Mutation: mutation is used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. If mutation is not performed it results in convergence and local minima. It is analogous to biological mutation. Mutation alters one or more gene values in a chromosome from its initial state.

STALAGMITE Function: Stalagmite and stalactite are mathematical functions that resembles Stalagmite and Stalactite structures in nature. Stalagmite is formed on the cave floor and Stalactite is formed from the roof of the cave. These formations are formed due to redeposition of minerals from water droplets which evaporates leaving behind minerals. When stalactite and stalagmite meet it is called Stalagnates.

Syntax for GA:

X = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.

X = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, 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,[],[],lb,ub,nonlcon,Intcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

Main Function:

 close all
 clear all
 clc
 % defining the search space
 x = linspace(0,0.6,150);
 y = linspace(0,0.6,150);
 % to create 2d mesh
  [xx yy] = meshgrid(x,y);
%  % assigning valus to inputs
  for i = 1:length(xx)% takes values until length of xx
      for j = 1:length(yy)% takes values until length of xx
          inputs(1) = xx(i,j);
          inputs(2) = yy(i,j);
          f(i,j) = stalagmite(inputs);
      end
  end
 num_case = 50; % creating a variable and assigning the number to which iterations performed

 tic % Starts the timer
 % Studt case-1
 for z = 1:num_case% takes values until length of num_cases
         [inputs,fopt(z)]  = ga(@stalagmite,2);% solve stalagmite function using GA and assigning to variables
         xopt(z) = inputs(1);
         yopt(z) = inputs(2);
 end
 Time_study1 = toc % Gives time taken to perform the case

 figure(1)
 subplot(2,1,1) % creates sub-plot in the figure 
 hold on
 surfc(xx,yy,-f) % Creates a surface
 shading interp % varies the color in each line segment and face by interpolating the colormap index or true color value across the line or face.
 plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')% plot3 command used to plot in 3 axis
 % marker is used to create a visible points on the plot
 title('unbounded inputs') 
 xlabel('x-axis')
 ylabel('y-axis')
 zlabel('z-axis')
 subplot(2,1,2)
 plot(-fopt)
 xlabel('iterations')
 ylabel('Function maximum')

% Study Case-2 Defining upper and lower bounds
tic
 for z = 1:num_case
         [inputs,fopt(z)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
         %defines a set of lower and upper bounds on the design variables
         xopt(z) = inputs(1);
         yopt(z) = inputs(2);
 end
 Time_study2 = toc

 figure(2)
 subplot(2,1,1)
 hold on
 surfc(xx,yy,-f)
 shading interp
 plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','b')
 title('Bounded inputs')
 xlabel('x-axis')
 ylabel('y-axis')
 zlabel('z-axis')
 subplot(2,1,2)
 plot(-fopt)
 xlabel('iterations')
 ylabel('Function maximum')
 clc
 % Study Case-3 Increasing iterations
 options = optimoptions('ga');% returns a set of default options for the SolverName solver.
 options = optimoptions(options,'PopulationSize',270);%Defining population size
 
 tic
 for z = 1:num_case
         [inputs,fopt(z)]  = ga(@stalagmite, 2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
         % takes the values of options and solves ga in required population
         xopt(z) = inputs(1);
         yopt(z) = inputs(2);
 end
 Time_study3 = toc;

 figure(3)
 subplot(2,1,1)
 hold on
 surfc(xx,yy,-f)
 shading interp
 plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
 title('Increased population')
 xlabel('x-axis')
 ylabel('y-axis')
 zlabel('z-axis')
 subplot(2,1,2)
 plot(-fopt)
 xlabel('iterations')
 ylabel('Function maximum')
 % The Global Maximum at the position
 display(inputs,'Global maximum')

Sub Function (Stalagmite function):

function [f]=stalagmite(inputs)
x = inputs(1);
y = inputs(2);

f1x=(sin((5.1*pi*x)+0.5))^6;
f1y=(sin((5.1*pi*y)+0.5))^6;
f2x=exp(-4*log(2)*(((x-0.0667)^2)/0.64));
f2y=exp(-4*log(2)*(((y-0.0667)^2)/0.64));

f=-(f1x*f1y*f2x*f2y);
end

Code Explaination:

1. Defining the search space for the GA to be performed. Using the mesh caommand to create 2d matrix.Writing stalagmite function which will be called in the main function.
2. Negative sign is used in the stalagmite function to get the global maximum as GA always returns global minima.
3. Assigning the values to inputs using for loop and to be used in the stalagmite function .
4. Getting values of stalagmite to the variable f.
5. Applying Genetic algorithm on stalagmite function.
6. Assigning the Genetic algoritm values to inputs, and then assigning to xopt,yopt ,foptusing for loop.
7. Three studies are made to get the optimised results.in the first study bounds are not defined. In the second study boundaries are defined. In the third study population size is defined.
8. Used tic and toc commands to know the time taken for each case.
9. creating surface using surf command among xx,yy,f ,using plot3 command to plot xopt,yopy,fopt. Plot fopt to show the optimized point.

Plots for case-1 [unbounded inputs]:

Plots for case-2 [Bounded inputs]:

Plots for case-3 [Icreasing population]:

Result shown in command window:

Stopping criteria:

1. The iterations stops when the iteration limit is reached.

2. When it is known that there wont be any change in the result for the iteration .

3. When the population limit is reached.

Results:

The Genetic Algorithm is performed on stalagmite function for optimization and to get global maxima.

And Required graphs are plotted.

References:

https://www.researchgate.net/post/How_to_write_genetic_algorithms_codes_in_Matlab

https://skill-lync.com/knowledgebase/genetic-algorithm-explained

https://in.mathworks.com/discovery/genetic-algorithm.html?s_tid=srchtitle