Week 4.1 - Genetic Algorithm

AIM: To write a code in MATLAB and to optimise the stalagmite function to find the global maxima of the function.

OBJECTIVE:
Expalin the concept of genetic algorithm in your own words and also explain the syntax for ga.
Plot graphs for all 3 studies and for F maximum vs no. of iterations.

SOLUTION:

Genetic Algorithm :
Genetic Algorithm (GA) is a branch of field of study called evolutionary comutation. It is based on evolution theory by Darwin. GA is used to optimize a given function to find its maximum or minimum value. The Genetic Algorithm works on the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. It is a method for solving both constrained and unconstrained optimization problems that is based on naturalselection. The algorithm begins by creating a random initial population of individual selections and it keeps on modifying this population. Thealgorithm uses the individuals in the current generation to create the next population. 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.

The basic components of a GA are
1. Fitness function : It is the function that GA is trying to optimize.
2. A population of chromosome : It is the numerical values that represent all the solutions to the
function. The selection operator chooses some of the chromosomes (with replacement) for
reproduction based on probability distribution. fitter the chromosome more likely it is to be selected.
3. Cross over : This operator swaps in random a subsequence of two of the chosen chromosomes to
create two offspring. Usually each chromosome is converted into binary code and then cross over is
done from one parent chromosome into another.
4. Mutation : Mutation operator randomly flips individual bits in the new chromosomes.

FLOWCHART OF GENETIC ALGORITHM:

STALAGMITE FUNCTION:

• Stalagmite function is a mathematical model which helps to generate local minima and maxima.
• It is a three dimensional function and the way the function is designed is that it has a lot of local maxima or minima and one global maxima or minima.
• The name stalagmite is actually a type of rock formation that arises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings.

The stalagmite function equations is given as follows:

SYNTAX FOR DEFINING GENETIC ALGORITM:

• x = ga(fun,nvars)
  where,
  x = optimal solution/variables;
  fun = Objective function;
  nvars = Number of variables;
  Sometimes ‘[x,fval]’ is used instead of ‘x’ where ‘fval’ gives objective function value at the solution
• x = ga(fun,nvars,A,B,Aeq,Beq,lb,ub)
  where,
  A, B = Linear inequality constraints
  Aeq, Beq = Linear equality constraints
  If there are no linear equalities and inequalities, then A, B, Aeq, Beq are set to ‘[ ]’
• x = ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,IntCon,options)
  where,
  nonlcon = Nonlinear constraints
  IntCon = Integer Values
  options = Optimization options
  If there are no nonlinear constraints and integer values, the nonlcon and IntCon are set to ‘[ ]’

MATLAB CODE:

close all
clear all
clc
%defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%creating a 2-d array
[xx yy] = meshgrid(x,y);
num_cases = 50;
%evaluating 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) = stalagmite(input_vector);
end
end
surfc(xx,yy,-F)
shading interp
xlabel('x value')
ylabel('y value')
title('Stalagmite Function')
%study 1
tic
for i = 1:num_cases
[inputs,Fopt(i)] = ga(@stalagmite,2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_1 = toc
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('Unbounded Inputs')
subplot(2,1,2)
plot(-Fopt)
xlabel('iterations')
ylabel('function maximum')
%study 2
tic
for i = 1:num_cases
[inputs,Fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0:0],[1:1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_2 = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-F)
shading interp
plot3(xopt,yopt,-Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Optimal solution')
subplot(2,1,2)
plot(-Fopt)
xlabel('iterations')
ylabel('function maximum')
%study 3
options = optimoptions(@ga)
options = optimoptions(options,'populationsize',400);
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
study_3 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-F)
shading interp
plot3(xopt,yopt,-Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-Fopt)
xlabel('iterations')
ylabel('function maximum')
Global_Maxima = -Fopt

In order to define stalagmite function, we need to write a different script defining the stalagmite function:

function [F] = stalagmite(input_vector)
a = input_vector(1);
b = input_vector(2);
f1 = (sin((5.1*pi*a)+0.5))^6;
f2 = (sin((5.1*pi*b)+0.5))^6;
f3 = exp((-4*log(2)*((a-0.0667)^2))/(0.64));
f4 = exp((-4*log(2)*((b-0.0667)^2))/(0.64));
F = -(f1*f2*f3*f4);
end

1. The the ‘x’ array and ‘y’ array is defined using ‘linspace’ command to create values at 150 equal intervals.

2. A 2D mesh of x and y array is created by using ‘meshgrid’ command and the number of iterations or cases that the code should perform is
defined. This is given by n = 50.

3. To evaluate the stalagmite function, ‘for’ loop is used where ‘i’ is initialized, for every value of ‘i’ another ‘for’ loop is used to initialize ‘j’.

4. The input vector values of ‘xx’ and ‘yy’ are defined and the stalagmite function for these input vector is defined. This will form a basic
stalagmite function and we can plot it separately if needed.

5. After preparing the inputs needed for the function, next step is to obtain the results for 3 cases of the genetic algorithm. In first case or study,
the maximum value of function is found out with no restrictions, no bounds and no limits.

6. This is done using ‘for’ loop where we use ‘ga’ syntax to give values for inputs and optimum max value. The stalagmite function is called in ‘ga’
syntax and number of variables ‘nvars’ are 2.

7. To know the time that is taken to solve the loop for 50 iterations, ‘tic’ and ‘toc’ command is used before and after the loop respectively.

8. Then the function created in the loop is plotted by using ‘surfc’ command for ‘xx, yy and function output’. To neglect the gridlines on the
surface and obtain a smooth and clean plot, ‘shading interp’ command is used. The ‘subplot(2,1,1)’ is used to plot multiple plots on same figure
which also divides figure in grid of 2x1 and axes to be placed at 1.

9. The ‘plot3’ command plots the 3D points at ‘xopt, yopt and optimum value of function’ with ‘o’ shaped and red colour. The labels and title are
then provided. Now in the same figure, the values of optimum function ‘fopt’ are plotted for 50 iterations.

10. The results of the above case will be different for each time we run the program. To get same value each time, we need to restrict the
program within specific bounds namely upper bound and lower bound. The procedure for coding and plottind this procedure is same as Study

11. The only difference is in the ‘ga’ syntax. This time the algorithm is provided lower limits and upper limits as [0;0] and [1;1] respectively.

12. After plotting the results for Study 2 or the bounded case, it is observed that the results are not same every time the program terminates. A
solution to this problem is to increase the number of cases or iterations.

13. So for Study 3, the number of iterations are increased to 300. So for this study, the syntax,
“optionsoptimoptions(‘SolverName’,’Name’,‘Value’)” is used which returns with named parameter ‘Populations’ with the altered values ‘300’.

14. The syntax for ‘ga’ contains ‘option’ term and the rest of the code is same as for Study 1 and 2.

RESULTS:

STUDY 1- STATISTICAL BEHAVIOUR

• Study1 = 2.1731
• In above plot, it can be observed how the random sampling of the genetic algorithm generates a new optimum value for the function every
  time the code is run. Although this falls in line with the definition of Genetic Algorithm. Large number of red dots shows values of coordinates of x, y varies each time iteration runs.

STUDY 2 - STATISTICAL BEHAVIOUR WITH UPPER AND LOWER BOUNDS:

• Study2 = 4.5296
• The above results show the convergence of x and y values. The number of red dots are less compared to previous plot. This is the result of
  providing upper and lower bounds to the function.

STUDY 3 - STATISTICAL BEHAVIOUR WITH INCREASING ITERATIONS OF GA

• Study3 = 15.5372
  
• In this above study, the number of iterations is increased to 300 to converge and find the global maxima of the function. Here we can see that there is only one red dot on the stalagmite function and that is the required global maxima point.
• On rotating the plot, we can clearly see the stalagmite function along with the global maxima value as x = 0.066834 and y = 0.0668346

From the graph of ‘Function maximum vs No. of Iterations’ results, the value of optimum function ‘fopt’ is approximately equal to 1.

CONCLUSION :
Optimised stagalmite function and global maxima of function is found successfully by using
MATLAB.