Finding the Global Maxima of Stalagmite function form Genetic Algorithm method

Genetic Algorithm

Objective - Finding the Global maxima for Stalagmite function in MATLAB using optimization method.

What is Genetic Algorithm?

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research and in machine learning.

In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo crossover and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.

In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.

Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well.

Syntax for GA -

In MATLAB the function is denoted by \'ga\'. Here it always tries to minimize the given fitness function i.e. try to minimize the error as low as possible.

The syntax for ga is as below :-

[inputs, fval] = ga(@fitnessfunction,nVars,A,b,Aeq,Beq,lb,ub,nonlcon,Intcon,options);

where,

input - returns the input value

fval - returns the value of fitness function

@fitnessfunction - function that needs to be minimized

nVars - no. of variables associated with that function

A & b - linear inequality constraints of type A*x<=b

Aeq & Beq - linear equality constraints of type A*x ==b

lb & ub - it is the search space where the ga try to get optimized results

nolcon - sets non-linear constraints

Intcon - sets integer constraints

options - used when we need to change the default ga functioning, to get the dersired optimized results.

% Program of Genetic algorithm 

clear all
close all
clc

% inputs
x = linspace(0,0.6,150); % boundary condition along the x axis
y = linspace(0,0.6,150); % boundary condition along the y axis
num_cases = 50;          % no of iteration that needs to run to get the optimum output

% creating 2d mesh
[xx , yy] = meshgrid(x, y); % creates the meshgrid of input values x & y

% evaluating the stalagmite function
for i = 1:length(xx)        % i = to consider the the length xx from 1 t0 the last value
    for j = 1:length(yy)    % j = to consider the the length yy from 1 t0 the last value
        input_vector(1) = xx(i,j); % assigning the value of xx(i,j) to input_vector(1)
        input_vector(2) = yy(i,j); % assigning the value of yy(i,j) to input_vector(2)
        f(i,j) = stalagmite(input_vector); % function of stalagmite is executed here
    end
end

% To find Stastical Behaviour for different conditions

% A)Stastical Behaviour, plotting unbound conditions

numcases = 50;
tic                       % starting time for the program
for i =1:numcases         % no of iterations from 1 to 50
    [inputs,fopt(i)] = ga(@stalagmite,2); % ga function which calculate the stalagmite function having two variables 
                                            x & y  without any boundary conditions.
    xopt(i) = inputs(1);  % input(1) is stored in xopt(i)
    yopt(i) = inputs(2);  % input(2) is stored in yopt(i)
end
study_time1 = toc         % ending time for the program

figure(1)                 % shows the output in figure 1
subplot(2,1,1)            % subplot divides the figure to 2 by 1 grid, and created plot no 1, 
                           here will be plot for unbounded condition
hold on                   % will help to display the other plot
surfc(xx,yy,f)            % creates the surface of the plot in 3D with meshes in them
shading interp            % created the plot in smooth curvature without meshes in them
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
                          % shows the output in a red marker .i.e. optmised point 
title(\'Unbounded Inputs\') % title of the plot that is obtained
subplot(2,1,2)            % subplot divides the figure to 2 by 1 grid, and created plot no 2, 
                           here will be plot for unbounded condition
plot(fopt)                % gives the plot of foutput 
xlabel(\'no of iterations\')% label alon x-axis
ylabel(\'f minimum\')       % label alon x-axis

% B)Stastical Behaviour, plotting bound conditions(upper & lower bounds)

num_cases = 50;
tic
for i = 1:num_cases        % starting time for the program
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
                           % ga function which calculate the stalagmite function having two variables 
                           x & y  with lb and ub boundary conditions.
    xopt(i) = inputs(1);   % input(1) is stored in xopt(i)
    yopt(i) = inputs(2);   % input(2) is stored in yopt(i)
end
study_time2 = toc          % ending time for the program

figure(2)                  % shows the output in figure 2
subplot(2,1,1)             % subplot divides the figure to 2 by 1 grid, and created plot no 1, 
                           here will be plot for bounded condition
hold on                    % will help to display the other plot
surfc(xx,yy,f)             % creates the surface of the plot in 3D with meshes in them
shading interp             % created the plot in smooth curvature without meshes in them
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
                           % shows the output in a red marker .i.e. optmised point 
title(\'Bounded Inputs\')    % title of the plot that is obtained
subplot(2,1,2)             % subplot divides the figure to 2 by 1 grid, and created plot no 2, 
                           here will be plot for bounded condition
plot(fopt)                 % gives the plot of foutput
xlabel(\'no of iterations\') % label alon x-axis
ylabel(\'f minimum\')        % label alon y-axis

% study 3 increasing the ga iterations by oincreasing population size
options = optimoptions(\'ga\');      
options = optimoptions(options,\'populationsize\',170); % we are exclusively increasing 
                                                        the population size here

tic
for i = 1:num_cases       % starting time for the program
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
                          % ga function which calculate the stalagmite function having two variables 
                           x & y bounded condition with population size.
    xopt(i) = inputs(1);  % input(1) is stored in xopt(i)
    yopt(i) = inputs(2);  % input(2) is stored in yopt(i)
end
study_time3 = toc         % ending time for the program

figure(3)                 % shows the output in figure 3
subplot(2,1,1)            % subplot divides the figure to 2 by 1 grid, and created plot no 1, 
                           here will be plot for options - increasing population size
hold on
surfc(xx,yy,f)            % creates the surface of the plot in 3D with meshes in them
shading interp            % created the plot in smooth curvature without meshes in them
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
                          % shows the output in a red marker .i.e. optmised point
title(\'bounded inputs with modified populatiom size\')
subplot(2,1,2)            % subplot divides the figure to 2 by 1 grid, and created plot 
                      no 2, here will be plot for bounded condition with population size
plot(fopt)                 % gives the plot of foutput
xlabel(\'no of iterations\') % label alon x-axis
ylabel(\'f minimum\')        % label alon y-axis

% Function for the stalagmite function defifition
function [f] = stalagmite(input_vector)

x = input_vector(1); % input_vector value is assigned to x
y = input_vector(2); % input_vector value is assigned to y

% formauls to calculate
f1x = (sin(5.1*pi*x + 0.5))^6;
f2x = exp(-4*log(2)*(x - 0.0667)^2/0.64);
f1y = (sin(5.1*pi*y + 0.5))^6;
f2y = exp(-4*log(2)*(y - 0.0667)^2/0.64);

f = -(f1x*f2x*f1y*f2y);
end

Figure 1 -

From the above figure 1 there a so many f minimum values which is not a optimized solution.

Time taken to solve the function is 2.69 secs.

Figure 2 -

From the above figure 2 we can see that are of f minimum has reduced compared to figure 1. The range is varying from(-0.4 to -1). Time taken to solve the function is 4.34 secs.

Figure 3 -

From the above figure 3 we can see that the range is between (-0.85 to -1) so the optimized value range are better than that of figure 2 and figure 3. Time taken to solve the function is 18.69 secs.

To find the Global Maxima there are two possibilities they are that

1. B)Stastical Behaviour, plotting bound conditions(upper & lower bounds) the boundary conditions are to be changed to get the optimized value & to get global maxima.

2.C)Bounded inputs with modified populatiom size ,the population size is increased to get the global maxima.

Here i have used the second option(population size increase) and the optimum value is 1 as per below image.

The change in the below program part to obtain Gllobal Maxima

% study 3 increasing the ga iterations by increasing population size
options = optimoptions(\'ga\');  
options = optimoptions(options,\'populationsize\',300); % we are exclusively increasing 
                                                        the population size here

tic
for i = 1:num_cases       % starting time for the program
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
                          % ga function which calculate the stalagmite function having two variables 
                           x & y bounded condition with population size.
    xopt(i) = inputs(1);  % input(1) is stored in xopt(i)
    yopt(i) = inputs(2);  % input(2) is stored in yopt(i)
end
study_time3 = toc         % ending time for the program

figure(3)                 % shows the output in figure 3
subplot(2,1,1)            % subplot divides the figure to 2 by 1 grid, and created plot no 1, 
                           here will be plot for options - increasing population size
hold on
surfc(xx,yy,-f)            % creates the surface of the plot in 3D with meshes in them
shading interp            % created the plot in smooth curvature without meshes in them
plot3(xopt,yopt,-fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
                          % shows the output in a red marker .i.e. optmised point
title(\'bounded inputs with modified populatiom size\')
subplot(2,1,2)            % subplot divides the figure to 2 by 1 grid, and created plot no 2, 
                           here will be plot for bounded condition with population size
plot(fopt)                 % gives the plot of foutput
xlabel(\'no of iterations\') % label alon x-axis
ylabel(\'f minimum\')        % label alon y-axis

The global maxima is at point x=0.06683, y = 0.06684, z=1.