Global Maxima of Stalagmite Function using Genetic Algorithm

DETERMINE THE GLOBAL MAXIMA OF STALAGMITE FUNCTION USING GENETIC ALGORITHM

AIM :-

To create a program to optimize the stalagmite function and obtain the global maxima value using genetic algorithm.

PLATFORM USED :-

1. Software – MATLAB R2019a
2. Programming Language – C/C++

SYSTEM SPECIFICATIONS :-

1. Manufacturer - DELL
2. Model – Vostro 3478
3. Operating System - Windows 10
4. Processor - Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz 1.80GHz
5. RAM – 8 GB

DESCRIPTION :-

OPTIMIZATION :-

Optimization is a process which is used to find the best solution out of all possible solutions available. A one such process is the Genetic Algorithm (GA) which is built on the basis of theory of evolution by Natural Selection proposed by Charles Robert Darwin in 1859.

GENETIC ALGORITHM :-

Genetic Algorithm (GA) is a search-based optimization technique which is used to find optimal or near-optimal solutions to the difficult problems that consumes more time for solving. The various phases that GA undergoes during solving a problem are,

1. Initial Population
2. Fitness Function
3. Selection
4. Crossover
5. Mutation
6. Converge

INITIAL POPULATION :-

The process begins with the set of individuals which is called population. Each individual is a solution to the problem that has to be solved.

FITNESS FUNCTION :-

Fitness function determines how fit an individual is by providing a fitness score to the individual. Based on the fitness score the individuals will be selected for crossover.

SELECTION :-

In selection process two individuals (parents) will be selected for reproduction based on the fitness score which is higher.

CROSSOVER :-

Crossover is the process where the selected fit individuals chose an point to exchange their genes in order to produce offspring.

MUTATION :-

In the offspring, the permanent alteration in the DNA sequence that makes up a gene in order to maintain diversity with the population and premature convergence.

CONVERGE :-

Convergence is that the state at which the algorithm comes to an end i.e., when there is no improvement in the solution quantity or an acceptable solution is obtained.

STALAGMITE :-

A stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings. Stalagmites are typically composed of calcium carbonate, but may consist of lava, mud, peat, pitch, sand, sinter and amberat.

STALAGMITE FUNCTION :-

The function that is used to obtain the 3D model of stalagmite model is,

`f(x,y) = (f1_x*f2_x*f1_y*f2_y)`

Where,

`f1_x` = `[sin((5.1*π*x)+0.5)]^6`

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

`f1_y` = `[sin((5.1*π*y)+0.5)]^6`

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

GENETIC ALGORITHM SYNTAX :-

To find the minimum value the syntax used in MatLab is ‘ga’.

SYNTAX:-

1. x = ga(fun,nvars)
2. x = ga(fun,nvars,A,b)
3. x = ga(fun,nvars,A,b,Aeq,beq)
4. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
5. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
6. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
7. [x,fval] = ga(___)
8. options = optimoptions(SolverName)
9. options = optimoptions(SolverName,Name,Value)

Where,

GENETIC ALGORITHM IN MATLAB :-

In MATLAB, Genetic Algorithm (GA) is used to obtain global minima for high non-linear problems. The syntax used in this program are,

SYNTAX 1 : [x,fval] = ga(fun,nvars)

SYNTAX PROCEDURE :-

1. The compiler takes random samples (search space).
2. Then the best fit value (x) is obtained for cross-over process.
3. Then the best fits are being evaluated in the function (fun).
4. The variables in the function to be evaluated being specified (nvars).
5. After many number of iterations it converges to a value.
6. Then the global minimum value is obtained.

SYNTAX 2 : x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

1. The compiler takes the values defined between boundary condition from function (search space).
2. Then the best fit value (x) is obtained for cross-over process.
3. Then the best fits are being evaluated in the function (fun).
4. The variables in the function to be evaluated being specified (nvars).
5. Also, it checks for linear equalities and inequalities.
6. After many number of iterations it converges to a value.
7. Then the global minimum value is obtained.

SYNTAX 3 : options = optimoptions(SolverName)

SYNTAX 4 : options = optimoptions(SolverName,Name,Value)

SYNTAX 5 : x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

1. The value in the specified ‘Name’ in the solver changes.
2. The compiler takes the values defined between boundary condition from function (search space).
3. Then the best fit value (x) is obtained for cross-over process.
4. Then the best fits are being evaluated in the function (fun).
5. The variables in the function to be evaluated being specified (nvars).
6. Also, it checks for linear equalities and inequalities.
7. After many number of iterations it converges to a value.
8. Then the global minimum value is obtained.

GLOBAL MAXIMA AND GLOBAL MINIMA :-

GLOBAL MAXIMA :-

It is the largest overall value of a set, function, etc., over its range. It’s also known as absolute maximum.

IN CODE :-

To find the global maxima while using Genetic Algorithm we need to include negative (‘-ve’) sign while evaluating the function, plotting the 3D model using the function values and also in optimum value while plotting in ‘plot3’ command.

f(x,y) = - (f1x*f2x*f1y*f2y)

surf(xg,yg,-f)

plot3(x_opt,y_opt,-opt_value,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')

GLOBAL MINIMA :-

It is the smallest overall value of a set, function, etc., over its range. It’s also known as absolute minimum.

IN CODE :-

The nature of Genetic Algorithm is to predict the GLOBAL MINIMA value, so no changes in the code.

INPUT AND OUTPUT PARAMETERS :-

INPUT PARAMETERS :-

1. Population generation using linspace and meshgrid (x & y).
2. Determining the iterations for Genetic Algorithm to run (run_time).
3. Stalagmite function input (f_input(1) and f_input(2)).

OUTPUT PARAMETERS :-

1. xg and yg using meshgrid for population size.
2. i and j (x&y) values for evaluating the function.
3. b_fit is the best fit value found by Genetic Algorithm.
4. Opt_value is the global minima found by Genetic Algorithm.
5. k is the used to store all the values of opt_value and b_fit during the iteration.

CODING :-

CODE FOR GENERATING STALAGMITE 3D MODEL :-

MAIN CODE :-

% Initializing the run time for Genetic Algorihtm Loop
run_time = 50;

% Generating 2D array
[xg,yg] = meshgrid(x,y);

% Loop statement (FOR LOOP)
% Inputting x & y values from 2D array to solve the function
for i = 1:length(xg)
    for j = 1:length(yg)
        f_input(1) = xg(i,j);
        f_input(2) = yg(i,j);
        f(i,j) = stalagmite_function(f_input);
        
    end
end

% Plotting 3D model of Stalagmite Function
surfc(xg,yg,-f)

% X,Y & Z Labels
xlabel('X - Values')
ylabel('Y - Values')
zlabel('Function Values')

% Enabling Title
title('Stalagmite 3D Model')

% Varying the colour in each line segment and face
shading interp

% Enabling Colorbar for plot
colorbar

FUNCTION CODE :-

% Solving stalagmite function to generate 3D Model
% Inputting the x & y values as 'f-input' array
function f = stalagmite_function(f_input)

% Assigning the x & y values
x = f_input(1);
y = f_input(2);

% Solving the equations
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));

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

NOTE :-

The function code used above is common for all the three studies performed to obtain the GLOBAL MAXIMA.

PROGRAM PROCESS :-

MAIN CODE :-

1. The compiler starts the program.
2. The compiler checks for the input values x, y and run_time.
3. Using ‘meshgrid’ command 2D array is generated.
4. The looping statement starts.
5. The length of ‘xg’ and ‘yg’ are calculated then stored in ‘i and ‘j’ variables.
6. The compiler checks for ‘stalagmite_function’ to verify.
7. Then each value of x and y from 2D array is being passed to the function through ‘f_input’ array.
8. In the function the x and y variables are initialized followed by calculation of the function.
9. The looping statement ends.
10. Then using ‘surfc’ command 3D model of stalagmite function is plotted.
11. The labels for x,y and z axes are enabled.
12. Title for the plot is enabled.
13. The ‘shading interp’ command is used to remove the grid lines on the 3D plot.
14. Colorbar for the plot is turned ON.
15. The compiler terminates the program.

FUNCTION CODE :-

1. The compiler starts the program.
2. Using function code the values for x & y are imported from the main code whenever it’s called by ‘f_input’ array.
3. Then the variables for x & y are assigned respectively.
4. Next all the four terms in the function are being solved.
5. Finally all the four values are multiplied for obtaining the stalagmite data points.
6. The function ends.
7. The compiler terminates the program.

OUTPUT :-

The 3D model of stalagmite is obtained.

GENERATING GLOBAL MAXIMA BY OPTIMIZING THE FUNCTION

STUDY 1 – WITHOUT BOUNDARY CONDITIONS

MAIN CODE :-

% Clearing all previous memory in Workspace
clear all
% Terminating all the previous plots
close all
% Clearing all the values in Command Window
clc
 
% x & y values for generating 2D array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
% Initializing the run time for Genetic Algorihtm Loop
run_time = 50;
 
% Generating 2D array
[xg,yg] = meshgrid(x,y);
 
% Loop statement (FOR LOOP)
% Inputting x & y values from 2D array to solve the function
for i = 1:length(xg)
    for j = 1:length(yg)
        f_input(1) = xg(i,j);
        f_input(2) = yg(i,j);
        f(i,j) = stalagmite_function(f_input);

            end
end

% Using Genetic Algorithm to predict global maximum
% No Boundary Conditions
for k = 1: run_time
% Genetic Algorithm Code
% Storing all the optimum values during iteration
[b_fit,opt_value(k)] = ga(@stalagmite_function,2);
% Storing all thr best fit(individuals) during iteration
x_opt(k) = b_fit(1);
y_opt(k) = b_fit(2);
end
 
% Plotting
% Creating subplot - First Subplot
subplot(2,1,1)

% Retaining the plot
hold on

% Plotting the 3D Stalagmite Model
surfc(xg,yg,-f)

% Varying the colour in each line segment and face
shading interp

% Plotting the x,y&z coordinates in 3D space
plot3(x_opt,y_opt,-opt_value,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')

% Assigning Title
title('Stalagmite 3D Model - No Boundary Conditions')

% Enabling labels for axes
xlabel('X-values')
ylabel('Y-values')
zlabel('Function Value')
% Turning on grid
grid on

% Second Subplot
subplot(2,1,2)

% Plotting the optimum values during iteration
plot(opt_value)

% Enabling labels for axes
xlabel('No of Iterations')
ylabel('Minimum Value - GA Predicts')

PROGRAM PROCESS :-

1. The compiler starts the program.
2. Using function code the values for x & y are imported from the main code whenever it’s called by ‘f_input’ array.
3. Then the variables for x & y are assigned respectively.
4. Next all the four terms in the function are being solved.
5. Finally all the four values are multiplied for obtaining the stalagmite data points.
6. The function ends.
7. The looping statement starts for genetic algorithm.
8. Length of loop time is calculated.
9. Genetic Algorithm syntax finds the optimum value and the values generated during iterations in ‘opt_value’ and ‘b_fit’ are stored.
10. Looping Statement ends.
11. Subplot is created of two rows and one column.
12. Now the 3D model of stalagmite is plotted in first space.
13. Within the same subplot the 3D graph is plotted.
14. The title and labels are provided.
15. In the second space of subplot the graph is plotted between iterations and generated maximum values during iterations from function.
16. The labels are provided foe the axes.
17. The compiler terminates the program.

OUTPUT :-

The output obtained in this code is that to verify the search space for obtaining the global maxima.

STUDY 2 – WITH BOUNDARY CONDITIONS

In the above code the search space exceeded the function area, in order to avoid this situation we are defining the boundaries for Genetic Algorithm to search within the function area.

MAIN CODE :-

% Clearing all previous memory in Workspace
clear all
% Terminating all the previous plots
close all
% Clearing all the values in Command Window
clc
 
% x & y values for generating 2D array(0.0668,0.0668) 
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
% Initializing the run time for Genetic Algorihtm Loop
run_time = 50;
 
% Generating 2D array
[xg,yg] = meshgrid(x,y);
 
% Loop statement (FOR LOOP)
% Inputting x & y values from 2D array to solve the function
for i = 1:length(xg)
    for j = 1:length(yg)
        f_input(1) = xg(i,j);
        f_input(2) = yg(i,j);
        f(i,j) = stalagmite_function(f_input);

            end
end

% With Boundary Conditions
for k = 1: run_time
[b_fit,opt_value(k)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[0.5;0.5]);
x_opt(k) = b_fit(1);
y_opt(k) = b_fit(2);
end

% Plotting
% Creating subplot - First Subplot
subplot(2,1,1)

% Retaining the plot
hold on

% Plotting the 3D Stalagmite Model
surfc(xg,yg,-f)

% Varying the colour in each line segment and face
shading interp

% Plotting the x,y&z coordinates in 3D space
plot3(x_opt,y_opt,-opt_value,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')

% Assigning Title
title('Stalagmite 3D Model - No Boundary Conditions')

% Enabling labels for axes
xlabel('X-values')
ylabel('Y-values')
zlabel('Function Value')
% Turning on grid
grid on

% Second Subplot
subplot(2,1,2)

% Plotting the optimum values during iteration
plot(opt_value)

% Enabling labels for axes
xlabel('No of Iterations')
ylabel('Minimum Value - GA Predicts')

PROGRAM PROCESS :-

1. The compiler starts the program.
2. Using function code the values for x & y are imported from the main code whenever it’s called by ‘f_input’ array.
3. Then the variables for x & y are assigned respectively.
4. Next all the four terms in the function are being solved.
5. Finally all the four values are multiplied for obtaining the stalagmite data points.
6. The function ends.
7. The looping statement starts for genetic algorithm.
8. Length of loop time is calculated.
9. Genetic Algorithm syntax finds the optimum value within the given boundary conditions.
10. The values generated during iterations in ‘opt_value’ and ‘b_fit’ are stored.
11. Looping Statement ends.
12. Subplot is created of two rows and one column.
13. Now the 3D model of stalagmite is plotted in first space.
14. Within the same subplot the 3D graph is plotted.
15. The title and labels are provided.
16. In the second space of subplot the graph is plotted between iterations and generated maximum values during iterations from function.
17. The labels are provided foe the axes.
18. The compiler terminates the program.

OUTPUT :-

The output obtained in this code is to verify whether the compiler uses ‘ga’ syntax to search the global maxima within the function.

STUDY 3 – WITH BOUNDARY CONDITIONS AND INCREASE IN POPULATION

In the above code the search space is defined within the boundary conditions of function but we are not able to obtain the global maxima. To obtain the global maxima the population size is being increased so that the perfect fit will be selected to evaluate the function.

MAIN CODE :-

% Clearing all previous memory in Workspace
clear all
% Terminating all the previous plots
close all
% Clearing all the values in Command Window
clc
 
% x & y values for generating 2D array
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
% Initializing the run time for Genetic Algorihtm Loop
run_time = 50;
 
% Generating 2D array
[xg,yg] = meshgrid(x,y);
 
% Loop statement (FOR LOOP)
% Inputting x & y values from 2D array to solve the function
for i = 1:length(xg)
    for j = 1:length(yg)
        f_input(1) = xg(i,j);
        f_input(2) = yg(i,j);
        f(i,j) = stalagmite_function(f_input);

            end
end

% Modifying the Population Size with Boundary Conditions

options = optimoptions('ga','PopulationSize',300);
for k = 1: run_time
[b_fit,opt_value(k)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[0.5;0.5],[],[],options);
x_opt(k) = b_fit(1);
y_opt(k) = b_fit(2);
end

% Plotting
% Creating subplot - First Subplot
subplot(2,1,1)

% Retaining the plot
hold on

% Plotting the 3D Stalagmite Model
surfc(xg,yg,-f)

% Varying the colour in each line segment and face
shading interp

% Plotting the x,y&z coordinates in 3D space
plot3(x_opt,y_opt,-opt_value,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')

% Assigning Title
title('Stalagmite 3D Model - No Boundary Conditions')

% Enabling labels for axes
xlabel('X-values')
ylabel('Y-values')
zlabel('Function Value')
% Turning on grid
grid on

% Second Subplot
subplot(2,1,2)

% Plotting the optimum values during iteration
plot(opt_value)

% Enabling labels for axes
xlabel('No of Iterations')
ylabel('Minimum Value - GA Predicts')

PROGRAM PROCESS :-

1. The compiler starts the program.
2. Using function code the values for x & y are imported from the main code whenever it’s called by ‘f_input’ array.
3. Then the variables for x & y are assigned respectively.
4. Next all the four terms in the function are being solved.
5. Finally all the four values are multiplied for obtaining the stalagmite data points.
6. The function ends.
7. The looping statement starts for genetic algorithm.
8. Length of loop time is calculated.
9. The population size is modified using ‘optimoptions’ command.
10. Genetic Algorithm syntax finds the optimum value within the given boundary conditions.
11. The values generated during iterations in ‘opt_value’ and ‘b_fit’ are stored.
12. Looping Statement ends.
13. Subplot is created of two rows and one column.
14. Now the 3D model of stalagmite is plotted in first space.
15. Within the same subplot the 3D graph is plotted.
16. The title and labels are provided.
17. In the second space of subplot the graph is plotted between iterations and generated maximum values during iterations from function.
18. The labels are provided foe the axes.
19. The compiler terminates the program.

OUTPUT :-

In this code we obtained the GLOBAL MAXIMA value from the function and it’s achieved by increasing the population size.

BEST FIT = [0.66382,0.66382] (x & y values)

GLOBAL MAXIMA = 1

GRAPH OBSERVATION :-

To check the values obtained in all the three studies the codes of three codes are executed three times continuosly. In optimum value random values from the array are considered fore evaluation purpose (because it’s an array containing the values for all 50 iterations).

CONCLUSION :-

In comparision of all three studies the third one is best for obatainig the global maxima because of inclusion of search space (boundary) and increase in population.

REFERENCES :-

1. https://medium.com/the-z/a-gentle-introduction-to-genetic-algorithm-30695a6084c2
2. https://in.mathworks.com/help/gads/ga.html#bs08mt7-1_sep_buxdit7-fval
3. https://in.mathworks.com/help/optim/ug/optim.problemdef.optimizationproblem.optimoptions.html#namevaluepairarguments
4. https://www.educba.com/what-is-genetic-algorithm/
5. https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm