Week 4 - Genetic Algorithm

PROJECT NAME - GENETIC ALGORITHM

In this project we will solve global optimization problem. We have used MATLAB to write specified programs and in this process we have learned how to use for loops, if conditions and also functions. So, what is optimization?

When it comes to our engineering function it can be something like internal combustion engines or aircraft mechanism there are certain things to do very well for e.g. an airfoil needs to provide proper lift at different angle of attack and also minimize drag. That means for flight condition drag value should be minimum. When we say that the drag value should be minimum how do we modify designs to get there? Well, you can modify all the design parameters and can see which design parameter gives you lowest drag coefficient.but this process is quite exhausting it will take a lot of time to use optimization is basically the area of study that deals with how to minimize or maximize the particular function which depends on multiple different parameters. There are several ways to go about optimization.

Stalagmite function is a mathematical model that helps us to generate local minimas & maximas & this actually looks like 3 Dimensional function. So the stalagmite function is mathematical model that actually helps us to generate local minimas and maximas. This is actually a 3 Dimensional function.so, the way the function defined is it has a lot of local maximas & it refers to the tiny peaks for e.g. if you are at the top of the local mountain then there will be at local maxima & the point of the highest peak of the mountain will be of global maxima and now to know the position of the optimum point we will be going to write a genetic algorithm. And the genetic algorithm is based upon the evolution theory stated by Charles Darwin & MATLAB actually provides inbuilt function that actually gives us Genetic Algorithm. also we will code the stalagmite function based upon the below-

function code -

function [f]= stalagmitenew(input_vector)
x = input_vector(1);
y = input_vector(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

Now, I will use surface plot command so that I can visualize the function that I have used –

surfc(xx,yy,f)

& now we will use the command called shading interp –

If you use it as % Shading interp you will see a graph having lot of meshings in it. (grid lines)

That’s why you will use shading interp to perform the program which will give us smooth shading plot.

And now at the end you will perfrom GA (Genetic Algorithm) which is an inbuilt function and as a part of function we are passing two inputs 1^st you will call it as a function handle and here I am trying to say name of the function i am trying to minimize. Genetic Algorithm which is incorporated in MATLAB this routine only minimizes the function. Now in our case we are interested to find peak not the minimum value that is another thing you need to investigate & in other script you have already typed a stalagmite function & at second place we will show how many variables are required to perform the function. from the equation 1 we can see we need two variables I pass as an input for the stalagmite function right here & hence this value is 2 and we will evaluate optimum value formally input so I other words we will call that output place as input…

Main code -

clear all
 close all
   clc
   % Input variables
   x = linspace(0, 0.6, 150);
   y = linspace(0, 0.6, 150);
   num_case = 250; 
   % creating an arraay
   [xx, yy] = meshgrid(x,y);
   % loop for passing 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) = stalagmitenew(input_vector);
       end
   end
      surfc(x , y , -f) 
      colorbar
      xlabel('x values')
      ylabel('y values')
      zlabel('function values')
      title('stalagmite function')
      shading interp
      [x_output , fval] = ga(@stalagmitenew , 2);
      
      
       % case study 1
      tic
      for i = 1 : num_case
          [inputs , f_optima(i)] = ga(@stalagmitenew , 2)
          x_optima(i) = inputs(1);
          y_optima(i) = inputs(2);
          
      end
      case1 = toc;
      figure(2)
      subplot(2,1,1)
      surfc(x , y, -f)
      shading interp
      xlabel('x values')
      ylabel('y values')
      zlabel('function values')
      hold on
      
      plot3(x_optima, y_optima, -f_optima, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'g')
      
      title('unbounded input')
      subplot(2, 1, 2)
      plot(-f_optima);
      xlabel('number of iterations')
      ylabel('max. value of the function')
      
      % case study 2
      tic
      for i = 1 : num_case
         [inputs , f_optima(i)] = ga(@stalagmitenew , 2, [], [], [], [], [0;0], [0.5;0.5]); 
          x_optima(i) = inputs(1);
          y_optima(i) = inputs(2);
          
      end
      case2 = toc;
      figure(3)
      subplot(2,1,1)
      surfc(x , y, -f)
     shading interp
      xlabel('x values')
      ylabel('y values')
      zlabel('function values')
      hold on
       
      plot3(x_optima, y_optima, -f_optima, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'g')
      title('unbounded input')
      subplot(2, 1, 2)
      plot(-f_optima);
      xlabel('number of iterations')
      ylabel('max. value of the function')
      
      
     % case study 3
     options = optimoptions('ga');
     options = optimoptions(options,  'populationsize',  250);
      tic
      for i = 1 : num_case
          [inputs , f_optima(i)] = ga(@stalagmitenew , 2, [ ], [ ], [ ], [ ], [0;0], [0.5 ; 0.5], [ ], [ ], options);
          x_optima(i) = inputs(1);
          y_optima(i) = inputs(2);
          
      end
      case3 = toc;
      figure(4)
      subplot(2,1,1)
      surfc(x , y, -f)
      shading interp
      xlabel('x values')
      ylabel('y values')
      zlabel('function values')
      hold on
      
      plot3(x_optima, y_optima, -f_optima, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'g')
      title('unbounded input')
      subplot(2, 1, 2)
      plot(-f_optima);
      xlabel('number of iterations')
      ylabel('max. value of the function')
      

STEPWISE EXPLANATION OF THE CODE -

Step 1 – To define x & y co-ordinates with 150 elements between 0 to 0.6 including the bounds kinspace command will be used.

Step 2 – Then, num_cases will be set as 250 which will be used as a counter for iterations.

Step 3 – Meshgrid command is used to create the 2D surface from co-ordinates x & y and given variable name (output) as xx & yy.

Step 4 – Every element of 2D mesh of Genetic Algorithm in the mesh grid is solved and iterated using the loop command.

Step 5 – the length of rows and columns which have an equal length used as counters.

Step 6 – the input vector is declared as GA requiring input vector which has each value of the mesh grid.

Step 7 – The output has stalagmite function is stored in matrix.

Step 8 – To start timer tic command is used

Step 9 – for loop bounded by number of iterations is formed.

Step 10 – Then GA code will be entered for unbounded statistical study.

Step 11 – The smallest & minimum value and its x & y co – ordinates stored in a separate variables & function is iterated for its each value.

Step 12 – toc command is used to stop the timer & output is stored in case 1.

Step 13 – figure(2), figure(3), figure(4) is plotted -

1. in order to create partition so that more than one plot can be drawn in the same window hence, two rwos and one column can be specified and each plot’s position can be selected.
2. In order to prevents overwriting of the plot hold on command is used.
3. To plot contour with xx & yy values from the mesh grid as input surfc command is used. also, in order to maximize function negative optimum value is used.
4. Then, x, y, z axis is labelled.
5. To remove the grid lines and to smoothen the surface of the plot shading interp function is used.
6. plot3 command is used to plot to a point in 3 dimensions & -fplot is used because to maximize value of the function.
7. Graph title is selected.
8. –fplot value of the function is plotted on the second plot in the second row.
9. Then x & y axis are labelled.
10. To increase the accuracy optimoptions command used to increase the population size.

Hence, in this way we can optimize the Genetic Algorithm through case 1, case 2, case 3.

Fig. - Genetic Algorithm

CASE STUDY 1-

In case study 1 we can see randomness of plots of Genetic Algorithm by using the Stalagmite function.

CASE STUDY 2-

By using upper and lower bounds we plotted all the x, y ,f values plotted by the function. Plot shows the range and the coverage of global maxima and its peaks which is the region covered by the function and its values.

CASE STUDY 3-

Aim of the third case study and its plot is to show the coverage and the range of the data to one final value can be seen from the graph that has covered after the varying populationsize and piloted to the value of 1 (0.99999).

What is Genetic Algorithm?

Genetic Algorithm is unique technique which is used in evolutionary computer research. In traditional GA we represent fixed length bit string & position of the string is used as representation of particular feature of an individual & in that particular position value stored shows how the feature is expressed in the solution. String is defined as ‘evaluation of a collection of structural features of a solution that has little or no interactions.’

Bit string crossover is the most used operator (two strings used as parents and a new individual is formed by swapping a sub-sequence between the two strings). Bit flipping mutation is another popular operator in which a single bit in string flipped to form new offspring string.

Genetic Algorithm generates population of points at each iteration. The optimal solution approached by the best point in the population & by using random number generators & with the help of computation GA selects the next population.

In 1960 evolutionary computing was introduced by I. Rechenberg in his work of ‘Evolutionary strategies’. Then by other researchers and scientists this idea was developed further & then John Holland introduced the idea of ‘Genetic Algorithm’ in 1975. He stated that ‘it is the heuristic method uses the principle of survival of the fittest’. Later then, It is most used tool for search and optimization problem.

Some of the most important features of GA is that it is the stochastic algorithm; the most essential role is played by GA is randomness. Second most important point is GA always takes in point of solution randomness. It keeps more than one solution in its memory at every iteration. By combining different solutions, we get better one. GA is a population based algorithm so it’s very feasible for parallelization. Robustness of GA is very essential for algorithm’s success. Robustness has ability perform with perseverance with broad range of problmes. GA is used where we have wide range of problem area and it is difficult to solve by traditional algorithms. GA is a quite powerful algorithm this gives them something exciting and enjoyable algorithm.

Genetic Algorithm is a method by which we can solve both constrained and unconstrained optimization (constrained optimization is a process of optimizing an objective function with respect to some variables in the presence of constraints on those variables while unconstrained optimization based on natural selection that drives biological evolution.) GA randomly and repeatedly modifies population of individual solutions. From the current fitting solution GA selects individuals at random at each step and uses them for production of next for next generation. Population evolves toward an optimal solution & towards the fittest solution which can lie in current era.

The genetic algorithm uses three main types at each step to create next generation from the current population –

1. Selection rules – used for selecting individuals, called parents, that contribute to the population at the next generation.
2. Crossover rules – combine two parents to form children for next generation.
3. Mutation rules – Apply random changes to individual’s parents to form children.

Syntax for GA –

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(___)

FOR COMPLETE AND DETAILED EXPLANATION - Minimum function using Genetic Algorithm

In our problem the syntax used for GA is as above

CASE STUDY 1-

1. The syntax used in our initial study is [x_output , fval] = ga(@stalagmitenew , 2) = which is ga(@fun,nvars) which finds local constrained minimum x, to the objective function fun. nvars is a number of design variables(dimension) of fun.
2. As in first study there is a high variation.

CASE STUDY 2 –

1. Similar approach as first case study is made and the syntax for GA is further modified and upper and lower bounds are assigned from 0 to 1 for both co-ordinates x & y.
2. [inputs , f_optima(i)] = ga(@stalagmitenew , 2, [ ], [ ], [ ], [ ], [0;0], [0.5;0.5]) is same as x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) where A, b, aeq, bwq, are blanks. ib, ub represents lower and upper bounds.
3. It defines a set oflower and upper bounds on the design variables x, so that the solution is found in the range ib ≤ x ≤ ub (by setting aeq = [ ] and beq = [ ].
4. The rest procedure is same as case study 1.

CASE STUDY 3 –

1. After successful optimization of the function for study 2, further optimization is possible where we can do further study in which we can increase the population size by modifying the syntax of GA.
2. options = optimoptions(options, 'populationsize', 250)
3. [inputs , f_optima(i)] = ga(@stalagmitenew , 2, [ ], [ ], [ ], [ ], [0;0], [0.5 ; 0.5], [ ], [ ],options) is similar to the x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes the default optimization parameters replaced by values in options. Create options using optimoptions. Where values are not placed are simply replaced by blank brackets. Again similar approach as study 1 is followed.

ERROR FACED - No major errors faced as such.