Global optimization using Genetic Algorithm

Genetic Algorithm :

• A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.
• Genetic Algorithm in matlab :-
• The genetic algorithm is a method for solving both constrained (constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables) and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions at random. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population evolves toward an optimal solution , a fitter solution which can dwell in the current era . 
• The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

1. Selection rules select the individuals, called parents, that contribute to the population at the next generation.
2. Crossover rules combine two parents to form children for the next generation.
3. Mutation rules apply random changes to individual parents to form children.

• General Syntax For Genetic Algorithm : -  (for fully detailed syntax click here )

• Syntax
  x = ga(fun,nvars)
  x = ga(fun,nvars,A,b)
  x = ga(fun,nvars,A,b,Aeq,beq)
  x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
  x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
  x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
  x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)
  x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
  x = ga(problem)
  [x,fval] = ga(___)
  [x,fval,exitflag,output] = ga(___)
  [x,fval,exitflag,output,population,scores] = ga(___)

• The syntax used in this code is explained in the Explanation area .

Stalagmite Function :

• A Stalagmite function which is represented by these formulas & equations is used to obtain a stalagmite structure : 
• 
• This is then ran through the genetic algorithm command in matlab to optimize the solution and find more fit value through random selection .

• The initial code for generating stalagmite function through GA is :- 

• clear all
  close all
  clc
  
  x = linspace(0,0.6,250);
  y = linspace(0,0.6,250);
  [xx, yy] = meshgrid(x,y);
  
  % Evaluating the stalagmite function
  for i = 1:length(xx)
      for j = 1:length(yy)
          input_vec(1) = xx(i,j);
          input_vec(2) = yy(i,j);
         f(i,j) = stalagmite(input_vec);
      end
  end
  
  
  surfc(x,y,f)
  xlabel('x-axis')
  ylabel('Y-axis')
  
  shading interp
  [input , fval] = ga(@stalagmite , 2)

• It gives the output as :- 
• 
• 

• The code runs the stalagmite function through the GA and produces results for minimum value , for global maxima we need the global optimization tool box by matlab . but a simple trick is to put minus sign before the equation output value which gives the negative value, which is actually opposite of minimum and i.e the global maxima of the stalagmite function as shown above. 
• But the genetic algorithm in this case produces random out every time its made to run . hence to optimize it further , several studies are done further to get a more fit value. 

Studies for optimization of stalagmite function to find Global Maxima :- 

• The code is :

• clear all
  close all
  clc
  x = linspace(0,0.6,250);
  y = linspace(0,0.6,250);
  [X,Y] = meshgrid(x,y);
  
  % assigning 200 cases
  num_cases = 200;
  f = get_stalagmite;  % calling the stalagmite function
  
  % study 1_ statistical behavior
  tic
  for i = 1:num_cases
      [inputs , fopt(i)] = ga(@stalagmite, 2);
      xopt(i) = inputs(1);
      yopt(i) = inputs(2);  
  end
  study1_time = toc
  
  % figure one from study one 
  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('Study 1 : Unbounded inputs')
  subplot(2,1,2)
  plot(fopt)
  xlabel('Iterations')
  ylabel('Function maximum')
  
  tic
  %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
  
  % figure from study two
  figure(2)
  subplot(2,1,1)
  hold on
  surf(X,Y,f)
  shading interp
  plot3(xopt ,yopt ,fopt, 'marker' , 'o', 'markersize',5,'markerfacecolor' ,'r')
  title('Study 2 : Bounded inputs')
  subplot(2,1,2)
  plot(fopt)
  xlabel('Iterations')
  ylabel('Function maximum')
  
  % study 3  and also increasing ga iteratins 
  options = optimoptions('ga');
  options = optimoptions(options,'populationsize',500);
  
  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 = toc
  
  % figure from study 3
  figure(3)
  subplot(2,1,1)
  hold on
  surf(X,Y,f)
  shading interp
  plot3(xopt ,yopt ,fopt, 'marker' , 'o', 'markersize',5,'markerfacecolor' ,'r')
  title('Study 3 : Bounded inputs')
  subplot(2,1,2)
  plot(fopt)
  xlabel('Iterations')
  ylabel('Function maximum')

• Explanation : 

1. 200 cases are assigned to run through the stalagmite function & genetic algorithm .
2. Stalagmite function is called then from the code shown later which produces the stalagmite and is passed to the genetic algorithm in the main command shown above . 
3. Study 1 : 
4. Is done for 200 iterations as mentioned and further genetic algorithm is used for the stalagmite function comprising of the equations shown above in the picture with its 2 variables . 
5. the syntax used in this one is :  [inputs , fopt(i)] = ga(@stalagmite, 2);
6. which is : 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
7. the study is timed using tic toc commands. 
8. The study 1 is done for statistical behaviour of the stalagmite function and its values are random and changes and not much optimized .
9. markers are plotted using plot3 command over the fitness values obtained in the first study and also a 2d graph is shown for a more understanding to its global maxima. 
10. for first study there is a high variation. 
11. Study 2 : 
12. This study is done for further optimization of the stalagmite function . 
13. Similar approach as first study is made and the syntax for GA is further modified and upper and lower bounds are assigned from 0-1 for both x and y. 
14. [inputs , fopt(i)] = ga(@stalagmite, 2, [],[] ,[],[],[0;0],[1;1]);
15. syntax - x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)  , where A ,B and Aeq and beq are blanks . lb and ub represents lower and upper bounds respectively. 
16.  It 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.)
17. The rest approach is same as study 1 .
18. Study 3 :
19. Study 2 sucessfully optimized the function but it can still be further optimized, hence we do further one more study where we increase the ga populationsize by modifying the syntax for GA and set it to 500 from default 50. 
20. [inputs , fopt(i)] = ga(@stalagmite, 2, [], [] ,[],[],[0;0],[1;1],[],[],options); 
21. Syntax - x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
22. where values not placed are simply replaced with blank brackets .
23. Again similar approach as study 1 is followed.

• Calling stalagmite funtion :

• function f = get_stalagmite
  
  x = linspace(0,0.6,250);
  y = linspace(0,0.6,250);
  [X,Y] = meshgrid(x,y);
  
  % Evaluating the stalagmite function
  for i = 1:length(X)
      for j = 1:length(Y)
          input_vec(1) = X(i,j);
          input_vec(2) = Y(i,j);
          f(i,j) = stalagmite(input_vec);
         
      end
  end
  
  end 

• This is used to call the stalagmite algorithm funtion in the main function which runs through all the studies and uses the another stalagmite equation function to produce result through studies conducted .

• Stalagmite Function : 

• function  input = stalagmite(vec)
  
  x =  vec(1);
  y =  vec(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.0067)^2)/0.64);
  fy2 = exp((-4)*log(2)*((y - 0.0067)^2)/0.64);
        
  input = -(fx1 * fx2 * fy1 * fy2);
  end
  

• This is stalagmite function developed from the formulas and equations above to produce stalagmite and its used in the GA and it also follows from the get_stalagmite funtion and then passed through studies conducted . 

 Output : 

• For study 1 below it is seen the value varies alot in negative direction . (global maxima)

• Time for study 1: 

• For study 2 the value is optimized and the global maxima is bounded between 0-1 and it still needs more optimization and shows the global maxima value ranges between -1 and -0.9 majorly

• Time for study 2 : 

• In study 3 the genetic algorithm has highly optimized the value for 200 iterations and 500 population size .  Our global maxima range lies between - 0.96932615 to -0.96932614 even though it still shows slight variation as can be seen in the 2d graph . but the stalagmite algorithm is considerably optimized. 

• Time for study 3 :

• References : 

1. https://in.mathworks.com/help/gads/ga.html?s_tid=srchtitle
2. https://in.mathworks.com/help/gads/options-in-genetic-algorithm.html
3. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
4. https://www.youtube.com/watch?v=Z_8MpZeMdD4
5. https://in.mathworks.com/help/gads/examples.html?s_cid=doc_ftr
6. https://in.mathworks.com/help/gads/genetic-algorithm.html