Week 4.1 - Genetic Algorithm

Aim:

To study about Genetic Algorithm and to calculate the global maxima of Stalagmite function using Genetic Algorithm in MATLAB.

Objective:

• To study about Genetic Algorithm and Stalgamite function.
• To write a code in Matlab to optimise the stalagmite function and find the global maxima of the function.
• To plot the graphs based on the studies done for Genetic Algorithm.

What is Stalagmite function?

Stalagmite function is a mathematical model which helps to generates local maxima & minima. It is a 3D 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 ceilling drippings.

The Stalagmite function is as follows:

Genetic Algorithm:

The Genetic Algorithm repeatedly modifies a population of individual solutions. At each steps, 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. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

This flow chart outlines the main algorithmic steps:

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 combinetwo parents to form children for the next generation.
3. Mutation rules apply random changes to individual parents to form children.

Syntax of GA:

The 'GA' syntax in matlab is used to the find the minimum of function using genetic algorithm. There are several ways to define the 'ga' function depending on the problem being solved. The syntax used for this study is shown below:

• x = ga(fun,nvars)

where,

x = optimal solution/ variables

fun = Objective function

nvars = No. 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 equalties and inequalties, then A,B,Aeq,Beq, are set to'[]'.

• x = ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,IntCon,options)

where,

nonlcon = Non linear constraints

IntCon = Integer values

options = Optimization options

If there are no nonlinear constraints & integer value, the nonlcon & IntCon are set to '[]'.

Main Program:

% Writing a program for optimizing the stalagmite function using Genetic
% algorithm

clear all
close all
clc

% Define search space
x = linspace(0,0.6,150);  % X array
y = linspace(0,0.6,150);  % Y array
n = 50;  % no.of cases

% Creating a 2D meshing
[xx , yy] = meshgrid(x , y);

% Evaluating a 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

% Study 1: Statistical behaviour

tic  % Start stopwatch timer
for i = 1:n
    [inputs,fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study1_time = toc;   % Read elapsed time from stopwatch

figure(1)
subplot(2,1,1)
hold on 
surface(xx,yy,-f)  % Primitive surface plot
shading interp   % Setting shading color option as Interpolated
xlabel('X axis')
ylabel('Y axis')
title('Statistical behaviour with Unbound inputs')
plot3(xopt,yopt,-fopt,'marker','o','MarkerFaceColor','r','MarkerSize',5)
subplot(2,1,2)
plot(-fopt)
xlabel('No. of Iterations')
ylabel('Function Maximum')

% Study 2: Statistical behaviour with upper and lower bounds

tic  % Start stopwatch timer
for i = 1:n 
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);

end
study2_time = toc;   % Read elapsed time from stopwatch

figure(2)
subplot(2,1,1)
hold on
surface(xx,yy,-f)  % Primitive surface plot
shading interp    % Setting shading color option as Interpolated
xlabel('X axis')
ylabel('Y axis')
title('Statistical behaviour with upper and lower bounds')
plot3(xopt,yopt,-fopt,'Marker','o','Color','r','MarkerSize',5)
subplot(2,1,2)
plot(-fopt)
xlabel('No.of Iterations')
ylabel('Function maximum')


% Study 3: Statistical behaviour with increasing iterations

options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',300);

tic
for i = 1:n
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc;  % Read elapsed time from stopwatch

figure(3)
subplot(2,1,1)
hold on
surface(xx,yy,-f)  % Primitive surface plot
shading interp   % Setting shading color option as Interpolated
xlabel('X axis')
ylabel('Y axis')
title('Statistical behaviour with Increasing Iterations')
plot3(xopt,yopt,-fopt,'Marker','o','Color','r','MarkerSize',5)
subplot(2,1,2)
plot(-fopt)
xlabel('No.of Iterations')
ylabel('Function maximum')

Stalagmite Function:

% The function is for Stalagmite Optimzation

function[f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
t1 = (sin(5.1*pi * x+0.5)).^6;
t2 = (sin(5.1*pi * y+0.5)).^6;
t3 = exp(-4*0.6931.*(x-0.0667)^2/(0.64));
t4 = exp(-4*0.6931.*(y-0.0667)^2/(0.64));
f = -(t1*t2*t3*t4);
end

The negative sign in the function will invert the stalagmite plot which will eventually give the function maxima.

Steps Taken:

1. The code starts with clear all, close all and clc where, 'clear all' command is used to clear the data stored in the workspace. 'Close all' command is used to close the plots & figures, and 'clc' command is used clear the command window.
2. Then the 'x' array and 'y' array is defined using 'linspace' command to create values at 150 equal iterations.
3. A 2D mesh of x and y array is created by using 'meshgrid' command and the no. of iterations or cases that the code should perform is defined. This is give by n = 50.
4. To evaluate the stalagmite function, 'for loop' is used where 'i' is initialized and for every value of 'i' another 'for loop' is used to initialize 'j'.
5. The input vector values of 'xx' & 'yy' are defined and the stalagmite function for these input vector is defined. This will form a basic function and we can plot is separately if needed.
6. After preparing the inputs needed for the function, next step is to obtain the results for 3 cases of the genetic algorithm. In first study, the maximum valur of function is found out within no restrictions, no bounds & no limits.
7. 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 no. of variables 'nvars' are 2.
8. 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.
9. Then the function created in the loop is plotted by using 'surface' command 'xx,yy and f'. To a neglect gridlines on the surface & to obtain a smooth & 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 & axes to be placed at 1.
10. The 'plot3' command plots the 3D points at 'xopt, yopt, and fopt', with 'o' shaped and red color. The labels and titles are then provided.
11. 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 specfic bounds namely upper bounds and lower bounds. The procedure for coding and plotting this procedure is same as Study 1. The only difference is in the 'ga' syntax, this time it is provided with upper and lower limits as [0;0],[1;1] respectively.
12. After plotting the results for Study 2, or it is observed that the results are not same every time the program terminates. A solution to this is to increase the no. of cases or iterations.
13. So for Study 3, the no. of iterations are increased to 300. So for this study, the syntax, "options = optimoptions('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:

• Statistical Behaviour-

In the above plot, it can be observed how the random sampling of the genetic algorithm generates to new optimum value for the function every time the code is run. Although this falls in line with the definition of Genetic Algorithm. Large no. of red dots shows values of co-ordinates of x,y values each time iterations runs.

• Statistical behaviour with upper and lower limits-

The above results shows the convergence of x and y values. The no. of red dots are less compared to previous plot. This is the result of providing upper and lower bounds to the functions.

• Statistical behaviour with increasing iterations-

In this study, the no. 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. We can clearly see that the stalagmite function along with the global maxima value as x=0.06683 and y=0.06683.

References:

• https://in.mathworks.com/help/gads/ga.html