Calculating the global maxima of a stalagmite function

Objective: To calculate the global maxima of a stalagmite function using a genetic algorithm and optimize the algorithm to obtain more accurate values.

What is the Genetic Algorithm (GA) and how does it work

A genetic algorithm is a technique to solve optimization problems using the concept of natural selection. It takes in a random sample having a known number of sample points as the input and modifies the sample population based on the following algorithm in order to obtain the desired output.

The algorithm is as follows:

1. A random sample having a known population is given as the input.

2. Each member of the population is given a particular score, also called the fitness score, by using a function known as the fitness function. In MATLAB, the genetic algorithm is developed to minimize this fitness function. This function handles the input arguments to the main GA function. The scores calculated from this fitness function are called the raw fitness scores.

3. These raw fitness scores are scaled to convert them into a more usable range of values. These values are now called expectation scores.

4. Parents are then selected based on these expectation scores.

5. Those parents whose fitness scores are low are chosen as the elite ones. These parents are then passed on to the next generation. This process is known as selection.

6. Children are produced from this elite population, based on certain changes made to the parents - either by crossover or mutation. In the process of crossover, two parents are simply combined to form the new children, while in the process of mutation, random changes are made to each parent to produce children.

7. This process is continued until certain criteria are fulfilled. These criteria can either be the number of generations, running after some time limits, fitness limits, etc, which is given by the user depending on the necessity.

Procedure

Step 1: Define the search space in order to find the maxima of the input stalagmite function, and create a 2D mesh in order to visualize the points more clearly.

Step 2: Define the stalagmite function given by the function stalagmite(), which takes in only one vector as the input and gives the output as a product of four functions defined mathematically within the stalagmite().

Step 3: A three-step approach is used to accurately determine the maxima of the function.

i) The first step involves finding the statistical behaviour of the stalagmite function using the genetic algorithm. This gives the output as a various number of sample points throughout the range of the input function, where a maximum is obtained.

ii) The second step involves constraining the upper and lower bounds of the function by modifying the genetic algorithm. This step would ensure that the minima lie within a much more smaller range of values, which can be observed from the figure.

iii) The third step involves increasing the input population given to the genetic algorithm so that the accuracy of the solver is improved and it produces an accurate value.

Syntax for GA

ga(@function_name, number_of_variables, inequality_1_parameter_1, inequality_1_parameter_2, inequality_2_parameter_1, inequality_2_parameter_2, lower_bound, upper_bound);

It is to be noted here that the above syntax is used to explain the case study represented in the below code, as the remaining parameters, such as parameters for non-linear inequalities and equalities, are not required in this problem.

In the current task, function_name is the name of the function, i.e., the stalagmite function, number_of_variables is the number of variables given as an input to the GA solver, and in this case, it is 2. Inequality_1_parameter_1 (A) and inequality_1_parameter_2 (b) are the two constant parameters that are used to solve the inequality:

`A*x <= b`

Inequality_2_parameter_1 (`A_eq`) and inequality_2_parameter_2 (b') are the two constant parameters that are used to solve the inequality:

`A_(eq)*x <= b'`

Lower_bound and upper_bound are the lower and upper bounds respectively of the data, which can be manipulated according to the requirements of the user.

Mistakes committed during programming and how to overcome them

1. The name of the user-defined function and the file name having the function is different. In such a case, the names should be similar so as to avoid confusion for the MATLAB solver.

2. The function optimoptions() not working. This could be caused because of the version of MATLAB being used. Instead of the above function, the function gaoptimset() must be used.

Conclusion

Thus, the stalagmite function has been used by the genetic algorithm to find the global maxima by a series of successive steps.

References

1. https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html

2. https://www.researchgate.net/post/How_can_you_find_the_max_function_with_Genetic_Algorithm

%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num = 50;

%Creating a 2D mesh
[xx yy] = meshgrid(x,y);
f = zeros(size(xx));

%Evaluating the 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 - Investigating the statistical behaviour of GA 
num = 50;
for i = 1:num
    [inputs, f_opt(i)] = ga(@stalagmite, 2);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end

%Plotting the stalagmite function
figure(1);
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')

%Plotting the optimum values of the unbounded function using GA
shading interp
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',5,'markerfacecolor','r');
title('Unbounded inputs');
subplot(2,1,2)
plot(f_opt)
xlabel('Iterations');
ylabel('Minima of the function');

%Study 2 - Setting upper and lower bounds for optimization, allowing to
%find the local maxima using GA
num = 50;
for i = 1:num
    [inputs, f_opt(i)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1]);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end

%Plotting the stalagmite function
figure(2);
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')

%Plotting the optimum values of the bounded function using GA
shading interp
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r');
title('Bounded inputs');
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations');
ylabel('Function local minima');

%Study 3 - Increasing the population size in order to find the global
%maxima and improve the optimization using GA
options = optimoptions(@ga,'PopulationSize',200);
for i = 1:num
    [inputs, f_opt(i)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1]);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end

%Plotting the stalagmite function
figure(3);
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x value')
ylabel('y value')

%Plotting the optimum values of the bounded function using GA and finding
%the global maxima of the stalagmite function along with the iteration

shading interp
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',5,'markerfacecolor','r');
title('Bounded inputs');
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations');
ylabel('Function global minima');

%stalagmite function code
function [ f ] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1_x = (sin(5.1*pi*x + 0.5))^6;
f1_y = (sin(5.1*pi*y + 0.5))^6;
f2_x = exp((-4)*log(2)*((x - 0.0667)^2)/0.64);
f2_y = exp((-4)*log(2)*((y - 0.0667)^2)/0.64);
f = -(f1_x*f1_y*f2_x*f2_y);
end