Week 4 - Genetic Algorithm

STUDY ON OPTIMIZATION OF STALAGMITE FUNCTION
USING GENETIC ALGORITHM

AIM:
To study the optimization of Stalagmite Mathematical Model using Genetic Algorithm in the Matlab software.

OBJECTIVES:
⦁ To optimize the stalagmite function and find the global maxima of the function using genetic algorithm.
⦁ To plot the Function maxima vs Number of iterations of the stalagmite function using Matlab software.

THEORY:
Genetic Algorithm or GA is an optimization technique to find out the optimized or nearly optimized values of a constrained or unconstrained function problem based on natural selection process, proposed by Charles Darwin's theory of Evolution. GA generally determines the local and global minima, since it is basically a minimization technique. But in our case, we intend to find the global maxima. This can be achieved by simply changing the sign of the resulting function values. So, if GA tries to find the Minimum values, the -ve sign with highest magnitude is the least value which is the global maximum value that we desire.

GA in matlab is an in-built tool that can be used for optimizing problems even which are dealt with highly non-linear or discontinuous functions. It works by ramdomly or natural selection of individuals from a set population of values which are then taken as parents and made to reproduce to produce offspring by using cross-over or mutation technique. This is based on the hope that the offsprings would have evolved characteristics with superior fit for survival and can be used for reproducing next set of individuals and so on until we get the desired minimum value, and after which even for several successive reproductions, the character set doesn't change, i.e., the minimum value reaches the global limit.

Matlab takes a healthier size of population and generates modified population of the same size from which the fittest parents are taken for the next iteration. Also the population selection is completely random based on random number generator computational technique.

Stalagmites are tapered columns rising from the follr of a cave which are nothing but mineral deposits formed by dripping of water over a very long period of time. Stalagmite mathematical function is similar to the shape of stalagmite formed by a set of equations. In this study, we generate a stalagmite function, whcih can be optimized using Genetic Algorithm, Neural networking, Fuzzy logics, ANFIS,etc. But in this study, we use Genetic Algorithm in Matlab to find out the global maxima.

FORMULAE USED:

Stalagmite mathematical function formula:

where, x and y are the input variables to the function.

PROCEDURE:
⦁ This study program is completely coded using Matlab software which has an in-built GA tool.

% Program for understanding of working of GA in optimization using
% Stalagmite Mathematical Model
clear all;
close all;
clc;

% Inputs
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iter = 50;% represents the no. of iterations
[xx, yy] = meshgrid(x,y);% Simple command for representing x and y values in
                         % a grid pattern. So, basically all x-values will
                         % have non changing column values and vice versa.
for k = 1:length(xx)
    for l = 1:length(yy)
        input_var(1) = xx(k,l);
        input_var(2) = yy(k,l);
        f(k,l) = stalagmite(input_var);% Stalagmite function needs to capture
                                       % all the possible combinations of x
                                       % and y for GA input.
    end
end

% Studu-case1: Optimization with un-bounded function variable
tic
for i=1:iter
    % In this syntax for GA, we give the function (in our case annonymous
    % function) as the first input argument and the number of 
    % inputs in the function(that is 2) as the 2nd input argument.
 
    [inputs1, f1opt(i)] = ga(@stalagmite, 2);
    x1opt(i) = inputs1(1);%Storing inputs in varaibles x1opt,y1opt 
    y1opt(i) = inputs1(2);%for plotting
end
case1_time = toc;%tic/toc cmd is used to get the time taken for execution.

figure(1);
subplot(2,1,1);% Subplot command is used to split the plot into two or more 
               % plots in the same figure window. 
hold on;
surfc(x,y,f);% plotting the surface of all values of x,y and function values
shading interp;% removes the default generated grid lines.
% To plot points in 3D space, we use 'plot3' command;
plot3(x1opt,y1opt,f1opt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x-values');
ylabel('y-values');
zlabel('Minimization values');% Here the negative minimum gives the maximum
                              % of the Stalagmite function.
title('Unbounded optimization');
subplot(2,1,2);
plot(f1opt);% plotting optimized f-values with respect to iterations.
xlabel('Iteration');
ylabel('Function optimization');
hold off;

% Study-case2: Optimization with bounded function variable
tic
for i=1:iter
    % In this syntax for GA, we give the function (in our case annonymous
    % function) as the first input argument, the number of 
    % inputs in the function(that is 2) as the 2nd input argument, value of
    % 'A' matrix if function has linear inequaltities with respect to 'b'
    % which does not exist in our case so we use null[]. The last two input
    % arguments are the 'lower bounds' and 'upper bounds' of the function.

    [inputs2, f2opt(i)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[1;1]);
    x2opt(i) = inputs2(1);%Storing inputs in varaibles xopt2,yopt2 
    y2opt(i) = inputs2(2);%for plotting
end
case2_time = toc;

figure(2);
subplot(2,1,1);
hold on;
surfc(x,y,f);
shading interp;
plot3(x2opt,y2opt,f2opt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x-values');
ylabel('y-values');
zlabel('Minimization values');
title('Bounded optimization');
subplot(2,1,2);
plot(f2opt);
xlabel('Iteration');
ylabel('Function optimization');
hold off;

% Study-case3: Optimization with bounded function variable and increases
% sampling size of population with increased iterations.
options = optimoptions('ga');%here, we set optimazition options to ga solver
options = optimoptions(options,'PopulationSize',250);%here we increase 
                                                     %population size of ga
iter = 300;
tic
for i=1:iter
    % In this syntax for GA, we give the function (in our case annonymous
    % function) as the first input argument, the number of 
    % inputs in the function(that is 2) as the 2nd input argument, value of
    % 'A' matrix if function has linear inequaltities with respect to 'b'
    % which does not exist in our case so we use null[]. The last two input
    % arguments are the 'lower bounds' and 'upper bounds' of the function.
    % In this case, we need to enter options as an input, fot that, ga in
    % matlab takes non-linear constraints and integer constraints before
    % taking 'options'. In our case, both constrains are an empty array [].

    [inputs3,f3opt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    x3opt(i) = inputs3(1);%Storing inputs in varaibles xopt3,yopt3 
    y3opt(i) = inputs3(2);%for plotting
end
case3_time = toc;

figure(3);
subplot(2,1,1);
hold on;
surfc(x,y,f);
shading interp;
plot3(x3opt,y3opt,f3opt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x-values');
ylabel('y-values');
zlabel('Minimization values');
title('Bounded and accurately converged optimization');
subplot(2,1,2);
plot(f3opt);
xlabel('Iteration');
ylabel('Function optimization');
axis([0 300 -1.5 -0.5]);% axis is set to indicate the global maximum as it
                        % reaches a straight line.    
hold off;

⦁ In the above program, the x and y values for the stalagmite function are first defined and are given as inputs to the function program. To create a surface plot and to determine x and y values at each and every point of the function, 'meshgrid' command is used which creates 150x150 matrix for both x and y values for which function is solved.
⦁ The GA function is called inside a 'for' loop so that the number of iterations required for the function optimization can be done. Basically, in this study, I used three study cases for determining the global maxima of the stalagmite function. The stalagmite function is defined in a separate function program which us the function formulae to determine the function values.

% Stalagmite function definition program
% "GA in general can ony determine the minimization optimization, i.e, the
% local  and global minima. But in our case, we intend to find the global
% maximum. This can be achieved by simply changing the sign of the
% resulting function values. So, if GA tries to find the Minimum values,
% the -ve sign with highest magnitude is the least value which is the
% global maximum value."
function f = stalagmite(inputs)
            % Function inputs:
            x = inputs(1);
            y = inputs(2);
            % Function formulae:
            f1x = (sin((5.1*pi*x)+0.5))^6;
            f1y = (sin((5.1*pi*y)+0.5))^6;
            X = -4*log(2)*(((x-0.0667)^2)/0.64);
            Y = -4*log(2)*(((y-0.0667)^2)/0.64);
            f2x = exp(X);
            f2y = exp(Y);
            % Calculation of Function values
            f = -(f1x*f2x*f1y*f2y);
end
        

⦁ In study case1, the syntax used for GA definition in matlab is [inputs, function_values] = ga(@stalagmite, 2). In this, the optimized function values with the corresponding input values are obtained as outputs. 'ga' is an inbuilt function-call for Genetic Algorithm in which an anonymous function called 'stalagmite' is used along with dimension or number of design varaibles (in our case 2 [x&y]) are given as inputs. We must keep in mind that, we did not define the bound for which the function is to be solved. So, GA randomly sets values which can be even irrelevant to the input values. This study case1 is mainly done to understand the importance of bounded conditions for the function to stick within a set of input values only.
⦁ In study case2, the syntax used for GA definition in matlab is [inputs, function_values] = ga(@stalagmite, 2, A, b, Aeq, beq, lb, ub). In this, A, b are provided only when the function is having some linear inequalities (in our case, A=[] and b=[] empty matrices since we don't consider any inequality), also Aeq, beq are provided only when the function is having some linear equality (in our case, Aeq=[] and beq=[] since we don't have any linear equalities). The 'lb and 'ub' are the values for lower bounds and upper bounds of the function variables respectively. The 'tic/toc' command is used to get the time taken to perform a set of operations. The 'subplot' command is used to create various plots in a single figure window. The 'plot3' command is used to create a 3-D plot. While providing bounding conditions, we are able to determine some of the local maxima but we are not sure at which point, i.e., (x,y) values, lies the global maximum of the function.
⦁ Finally, in study case3, the syntax used for GA definition in matlab is [inputs, function_values] = ga(@stalagmite, 2, A, b, Aeq, beq, lb, ub, nonlcon, Intcon, options), where 'nonlcon' and 'Intcon' are Nonlinear constraints and Integer constraints respectively (in our case, both are empty[] matrices). The major advantage of GA in Matlab is we can actually modify the options of GA and optimize it for our convenience. In this case, we modify the 'populationsize' of natural selection process to be higher than 50 since the default values of 'populationsize' in matlab is set to 50. Here we take 'populationsize' as 250 and increase the number of iterations to 300 to get a more precise optimization value.

RESULTS:
Thus, the study on optimization of Stalagmite Mathematical Model using Genetic Algorithm on Matlab software was successfully performed and the Global Maximum of the function was determined.

According to the above Study cases1, 2 and 3, we can observe that with respect to increase in the amount of information given to GA tool, we can optimize and get more accurate solutions based on the amount of understanding we have on that function. So, the results of any problem, in general, is based on the understanding that we have on that problem.

So, the maximum or global maximum of aproximately 1 on the input values x = 0.0668 and y = 0.0668 were obtained as the optimization solution for the Stalagmite function using GA in matlab.

REFERENCES:

1. Genetic Algorithm - MATLAB & Simulink - MathWorks (www.mathworks.com › discovery › genetic-algorithm).

2. Find minimum of function using genetic algorithm - MATLAB ga (in.mathworks.com › ... › Choose a Solver).

3. Genetic Algorithm - an overview | ScienceDirect Topics (www.sciencedirect.com).

4. When we use Genetic Algorithm , how we know the solution has reached the global minima? (www.researchgate.net).

5. Introduction to Genetic Algorithms — Including Example Code | by Vijini Mallawaarachchi | Towards Data Science (www.towardsdatascience.com).