Evaluation of the function's global maxima using Genetic Algorithm

1. Aim: To get the global maxima of the stalagmite function using genetic algorithm.

2. Objectives:

• To write the stalagmite function.
• To understand the working and terms of the genetic algorithm.
• To use the inbuit ga solver.

3. Theory:

1. Genetic Algorithm (GA): It is an algorithm for solving both constrained and unconstrained optimization problems. This algorithm is influenced by a natural selection process that is similar to biological evolution. It repeatedly modifies a population of individual solutions. At every step, it randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. After iterations (generation), the population results toward an optimal solution.
2. Working of the Genetic Algorithm: For creating the new population, the algorithm performs the following steps:

   1. It calculates every member of the current population by computing its fitness value. These values are known as the raw fitness scores.

   2. It scales the raw fitness scores to convert them to a more usable range of values. These scaled values are known as expectation values.

   3. It selects members which are called parents based on their expectation values.

   4. Some of the lower-fitness individuals in the current population are chosen as elite.
      These elite individuals are handed over to the next population.

   5. It produces children from the parents. This process is carried out either by making random changes to a single parent (mutation) or by combining the vector entries of a pair of parents (crossover).

   6. Then it replaces the current population with the children to form the next generation.

   7. The algorithm stops when the optimal solution is reached or until the value of the generations.

3. GA solver: It finds the minimum of the function using the genetic algorithm and attempts to solve problems of the following forms:
   min fun(X) subject to: A*X <= B (linear inequality constraints), Aeq*X = Beq (linear equality constraints) where A and B are the matrices
   C(X) <= 0 (nonlinear inequality constraints), Ceq(X) = 0 (nonlinear equality constraints) where C is the matrix
   LB (lower bounds) <= X <= UB (upper bounds)
   X(i) integer, where i is in the index and vector INTCON (integer constraints)
   
   
4. Syntax of the ga solver is given by: X = ga(fun,nvars,A,B,Aeq,Beq,LB,UB,NONLCON,INTCON, options) where fun is the function, nvars are the number of variables, function NONLCON accepts X and returns vectors C and Ceq.
5. Global and local maxima or minima: A maximum or minimum is said to be local if it is the largest or smallest value of the function respectively within a set range. While, a maximum or minimum is said to be global if it is the largest or smallest value of the function respectively on the entire domain of a function.

4. MATLAB program: The following the MATLAB program along with the comments to find the global maxima of the stalagmite function using the genetic algorithm.

Mathematically the stalagmite function used to find the global maxima is:

`f(x,y) = f1,x * f2,x * f1,y * f2,y`

where `f1,x = [sin(5.1πx + 0.5)]^6`

`f1,y = [sin(5.1πy + 0.5)]^6`

`f2,x = exp[-4ln(2) ((x - 0.0667)^2)/0.64]`

`f2,y = exp[-4ln(2) ((y - 0.0667)^2)/0.64]`

The stalagmite function is defined in which the body of the function is coded as given below:

function y1 = stalagmite(input_vector)

% input_vector is an array which stores the x values and y values
x = input_vector(1);
y = input_vector(2);
first_term_x = (sin(((5.1*pi)*x) + 0.5))^6;
expo_term_x = ((-4*log(2)*((x-0.0667)^2)/0.64));
second_term_x = exp(expo_term_x);
first_term_y = sin(((5.1*pi*y) + 0.5))^6;
expo_term_y = ((-4*log(2)*((y-0.0667)^2)/0.64));
second_term_y = exp(expo_term_y);

% to find the maximum value of the function, -ve sign is given to the
% function
y1 = -((first_term_x)*(second_term_x)*(first_term_y)*(second_term_y));
end

The main program in which the stalagmite function is called is as follows:

% A program on genetic algorithm finding the global maxima of the function 

% clearing the workspace
clear all

% closing the plots
close all

% clearing the command window
clc

% defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% As genetic algorithm doesn't know the search space so setting the number
% of iterations
num_cases = 50;

% creating a 2-dimensional mesh
[xx,yy] = meshgrid(x,y);

% evalauting the stalagmite function
for i = 1:length(xx)
    for j = 1:length(yy)
        % assinging the first data (xx) of an array
        input(1) = xx(i,j);
        % assigning the second data (yy) of an array
        input(2) = yy(i,j);
        f(i,j) = stalagmite(input);
    end
end

% surface plot
surfc(x,y,-f)

% labelling the X-axis
xlabel('X - axis');

% labelling the Y - axis
ylabel('Y - axis');
 
% shading the plot 
shading interp

% to calculate the study time using tic and toc commands
tic

% Study 1 - Statistical behaviour 
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study1_time = toc

% opening a new figure window
figure(1)

% sub plotting the graphs by the two rows and a single column in a single
% figure
subplot(2,1,1)

%holding the plot
hold on

% surface plot to maximize the function so f = -f and also ftop = - ftop
surfc(x,y,-f)

% shading the plot
shading interp

% 3D plot using marker 'o' with markersize as 5 and markerfacecolor as red
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

% setting the title of the plot as unbounded imputs
title('Unbounded inputs')

% to plot the optimum maximum value of the function
subplot(2,1,2)
plot(-fopt)

% labelling the X - axis
xlabel('Iterations')

% labelling the Y - axis
ylabel('Function maximum')

% to calculate the study time using tic and toc commands
tic

% Study 2 - Statistical behaviour using upper and lower bounds
% lower and upper bounds are set on the basis of the search space
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc

% opening a new figure window
figure(2)

% sub plotting the graphs by the two rows and a single column in a single
% figure
subplot(2,1,1)

%holding the plot
hold on

% surface plot to maximize the function so f = -f and also ftop = - ftop
surfc(x,y,-f)

% shading the plot
shading interp

% 3D plot using marker 'o' with markersize as 5 and markerfacecolor as red
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

% setting the title as bounded inputs
title('Bounded inputs')

% plotting the optimum maximum value of the function
subplot(2,1,2)
plot(-fopt)

% labelling the X - axis
xlabel('Iterations')

% labelling the Y - axis
ylabel('Function maximum')

% Study 3 - Increasing GA iterations using the optimoptions function
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',170);

%to calculate the study time using tic and toc commands
tic
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc

% opening a new figure window
figure(3)

% sub plotting the graphs by the two rows and a single column
subplot(2,1,1)

%holding the plot
hold on

% surface plot to maximize the function so f = -f and also ftop = - ftop
surfc(x,y,-f)

% shading the plot
shading interp

% 3D plot using marker 'o' with markersize as 5 and markerfacecolor as red
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

% setting the title as bounded inputs with modified population size
title('Bounded inputs with modified population size')

% plotting the optimum maximum value of the function
subplot(2,1,2)
plot(-fopt)

% labelling the X - axis
xlabel('Iterations')

% labelling the Y - axis
ylabel('Function maximum')

5. Explanation of the MATLAB program:

1. First, the search space is defined using the linspace function and storing the linspace values in the array having xx and yy. Then, the stalgamite function is called and the function values are stored in the variable f. The surface plot is plotted using the surfc function. f is passed as -f in the surfc function to get the maximum value.
2. Statistical behaviour of the genetic algorithm with unbounded inputs: Stalagmite function is again called with the help of ga solver. Initially, the number of iterations is 50. Then, the 3D plot is plotted with the unbounded inputs and also the -fopt (optimum maximum value) is plotted. These two plots are plotted using the subplot commands in the figure 1. tic and toc commands are used to study the time elapsed in the execution of the ga solver.
3. Statistical behaviour of the genetic algorithm with bounded inputs: Here, the same process is carried out as done but inputs are bounded from [0;0] to [0.6;0.6]. So, that the optimum value of the function is found within the bounds given. The 3D plot with the bounded inputs and the -fopt (optimum maximum value) are plotted. These two plots are plotted using the subplot commands in the figure 2. Again, time elapsed is calculated using tic and toc commands.
4. Statistical behaviour of the genetic algorithm with bounded inputs and increased generations: Here, the same process is carried out by increasing the number of iterations. This is done with the help of optimoptions function by defining the population size as 170. The 3D plot and the fopt plot is given in the figure 3.

6. Results:

The plot using the surfc plot is given by:

The above plot shows the 9 peaks which gives the global and local maxima function values as the objective function is to be maximize.

The following image is the 3D plot showing the statistical behaviour with the unbounded inputs and also the optimum value variation with respect to the iterations as figure 1:

The above plot shows the red markers as the function values outside the search space as the upper and lower bounds are not defined. The maximum function values varies from 0 to 1 with the iterations.

The following image shows the time elapsed for the statistical behaviour with the unbounded inputs:

The following image is the 3D plot showing the statistical behaviour with the bounded inputs and also the optimum value variation with respect to the iterations as figure 2:

The above plot shows the red markers as the function values inside the search space as the upper and lower bounds are defined.

The following image shows the time elapsed for the statistical behaviour with the bounded inputs:

The following image is the 3D plot showing the statistical behaviour with the bounded inputs and increased generations and also the optimum value variation with respect to the iterations as figure 3:

The following image shows the time elapsed for the statistical behaviour with the bounded inputs and increased generations:

7. Conclusion:

• The statistical behaviours of the genetic algorithm with unbounded inputs, bounded inputs and bounded inputs with increased generations are studied. The optimum maximum value of the function from figure 3 (a single red marker) can be concluded as 0.9999.
• The time elasped for the optimization is 14.9495 seconds which is stored in the variable study3_time.

8. References:

1. Genetic Algorithm- https://in.mathworks.com/discovery/genetic-algorithm.html
2. How the Genetic Algorithm Works - https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f6243
3. ga - https://in.mathworks.com/help/gads/ga.html#d120e40486
4. Genetic Algorithm Options - https://in.mathworks.com/help/gads/genetic-algorithm-options.html
5. MATLAB Answers - https://in.mathworks.com/matlabcentral/answers/430760-find-the-maximum-value-of-a-function