Optimisation of Stalagmite Function using Genetic Algorithm

Aim:

Optimization of stalagmite function to find its maxima by applying the Genetic Algorithm.

Genetic Algorithm:

The genetic algorithm is a method of solving optimization problems which could be constrained and unconstrained. This algorithm is based on natural selection i.e. the process that that drives the biological evolution. It solves practical problems as computational models of natural evolutionary systems.  The genetic algorithm selects individuals at random from the current population to be parents and use them to produce the children for the next generation, at each step.

This algorithm can be applied to solve a variety of optimization problems that are not well suited for standard optimization algorithms.

There are three main rules at each step to create the next generation from the current population:

1) Selection rule - selects the individuals called parents that contribute to the population of the next generation. On the basis of the scaled fitness values, called the expectation values, the parents are chosen from the next generation.
In case an individual is selected more than once as a parent then it contributes its genes to more than one child. The individuals with the best fitness values in the current generation that are guaranteed to survive in the next generation are called elites.

2) Crossover rule - combines two parents to form children for the next generation. The vector entries or genes are selected from a pair of individuals and are combined to form a child.

3) Mutation rule - applies random changes to individual parents to form children. By applying random changes to a single individual in the current generation, mutation children are created.

The genetic algorithm and classical algorithm differ from each other in the following ways:

Working of Genetic Algorithm:

• In the beginning, a random initial population is created.
• Then a sequence of new populations is created and at each step, the individuals in the current generation are used to create the next population.
• The algorithm stops when one of the stopping criteria is met.
  
  

Following steps are performed to create a new population:

1. For each member of the current population, a fitness value is computed, called the raw fitness scores.
2. These raw fitness scores are converted into a more usable range of values, called the expectation values.
3. On the basis of expectation values, members are selected, called parents.
4. Some individuals, having higher fitness are passed to the next population and are called elites.
5. Children are produced by parents either by crossover or by mutation.
6. The current population is replaced with the children to form the next generation.

Crossover – combining the vector of a pair of parents.

Mutation – making random changes to a single parent.

Conducted Studies:

There are a total of 3 studies conducted on the use of Genetic Algorithm for optimization of stalagmite function.

• First Study:

In this study, the Genetic Algorithm is applied with unbounded inputs and provides a large number of solutions with a higher range. This study takes least time to be conducted and does not provide very accurate results.

• Second Study:

In the study, the Genetic Algorithm is applied with upper and lower bounded inputs. This study takes longer time be conducted than the first study and also provides more accurate results. This study provides 4 to 5 solutions for optimization.

• Third Study:

In this study, the Genetic Algorithm is applied with upper and lower bounded inputs along with defined population size due which this study provides the most accurate solution for the optimization and thus, takes the longest time than the previous studies. Providing a higher population size yields more accurate result and as a result, takes more processing time.

Matlab ga Syntax:

x = ga(fun,nvars)

x = ga(fun,nvars, A,b)

x = ga(fun,nvars,A,b,Aeq,beq)

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

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)

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

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

x = ga(problem)

[x,fval] = ga(___)

[x,fval,exitflag,output] = ga(___)

[x,fval,exitflag,output,population,scores] = ga(___)

ga – the name of the function.

fun – the name of the function to be optimized.

nvars – number of design variables of the function (fun).

A – linear inequalities (A*x <= b).

b – the value of b used in linear equality.

Aeq – linear inequalities (Aeq*x = beq).

beq – the value of beq in linear inequality.

lb, up – lower and upper bounds on the design variables.

nonlcon – subjects the minimization to the constraints defined in nonclone.

options – minimizes with the default optimization parameters replaced by values in options.

problem – a predefined structure which can be directly fed to the ga function.

Stalagmite Function:

A stalagmite is a type of rock formation that rises from the floor of a cave due to accumulation of material deposited on the floor from ceiling drippings.

The stalagmite function contains a group of equations which when plotted in 3D resembles the shape of a stalagmite.

The mathematical function is as follows:

                                 `f(x,y) = f_(1,x) f_(2,x) f_(1,y) f_(2,y)`

where,                          `f_(1,x) = [sin(5.1pix + 0.5)]^6`

                                     `f_(1,y) = [sin(5.1piy + 0.5)]^6`

                        `f_(2,x) = exp[-4ln(2) frac{(x - 0.0667)^6}{0.64} ]`

                        `f_(2,x) = exp[-4ln(2) frac{(y - 0.0667)^6}{0.64} ]`

 This function needs to be modifies for maximization :

                                  `f(x,y) = f_(1,x) f_(2,x) f_(1,y) f_(2,y) * (-1)`

This is the modifies stalagmite function.

Program:

Function Program:

Here is the program of the stalagmite function, modified for calculation of minima.

The function is multiplied by (-1) for the calculation of minima.

%% Description
%
% This is a program for stalagmite function
%
%% Author
%
% Umang Tyagi
% Date of Creation - 06 August 2020
%
%% Program
function sol = stalagmite(input_vector)
x = input_vector(1);                              % seperating the values of inputs
y = input_vector(2);
                                                  % defining the four terms
f1x = (sin(((5.1 * pi).*x)+0.5)).^6;
f1y = (sin(((5.1 * pi)*y)+0.5)).^6;

f2x = exp((((x-0.0667)^2)*(-4*log(2)))/0.64);
f2y = exp((((y-0.0667)^2)*(-4*log(2)))/0.64);

sol = -f1x * f2x * f1y * f2y;                     % combibning all terms to get the final solution
% multiplying with -1 to get the maximum value of stalagmite function using Genetic Algorithm
                                                 
end

Main Program:

Here is the main program for optimization of stalagmite unction using Genetic Algorithm.

The algorithm of the program is as follows:

1. Specify the range of the function and convert it into a 2D array using ‘meshgrid’ function.
2. Set the number of iterations for ‘ga’ an store in a variable.
3. Call the ‘stalagmite’ function inside a nested ‘for’ loop for the predefined range of the function.
4. Plot the solution of stalagmite function in ‘figure (1)’
5. Start the timer for the first study and begin the iterations by calling the ‘ga’ functions inside a ‘for’ loop.
6. Store the solution and function’s value in separate arrays and stop the timer.
7. Plot the solution and function’s value array along with the stalagmite function solution, such that the plot inverted for better visualization and plot the function’s value array separately, completing the ‘figure (2)’.
8. Repeat the v, vi and vii steps for second and third study and plotting their outputs, obtaining ‘figure (3)’ and ‘figure (4)’.
9. Display the optimization solution in the command window along with the time taken for each study.

%% Description
%
% This is a program to maximize the Stalagmite function by using Genetic Algorithm and conducting its 3 studies.
%
%% Output
%
% Plot of Stalagmite function.
% Plot of all 3 studies.
% Maximized output of stalagmite function.
% Plot of maximum output vs no of iterations.
%% Author
%
% Umang Tyagi
% Date of creation - 06 August 2020
%
%% Program
clear all
close all
clc

%% 1) Defining Range
x = linspace(0,0.6,150);                        % range of x
y = linspace(0,0.6,150);                        % range of y

[xx yy] = meshgrid(x,y);                      % creating 2D array of range

iterations = 40;
%% 2) Solving Stalagmite Function
% nested loop is run for the entire range to input each range value one by one.

for i = 1:length(xx)
    for j= 1:length(yy)
        input_vector(1) = xx(i,j);                 % picking values from xx matrix
        input_vector(2) = yy(i,j);                 % picking values from yy matrix
        sol(i,j) = stalagmite(input_vector);       % calling the stalagmite function and proving inputs.
    end
end

%% 2.1) Plotting Stalagmite Function
figure(1)
surfc(xx, yy, -sol);                      % plotting the stalagmite functn using the surfc command
shading interp                            % removing the shadings from the plot
xlabel('xx'); ylabel('yy');
title('Stalagmite Function')
%% 3) First Study (Unbound Inputs)
%
% use the for loop to run the itaerations and call the ga function every time
%
tic;                                                % start the timer for first study
for i = 1:iterations;                               % start the loop
    [sol1 fval1(i)] = ga(@stalagmite, 2);           % calling ga function
                                                    % sol1 is the solution
                                                    % and fval1 is the function value
    sol_x1(i) = sol1(1);                               % storing the value of x seperately
    sol_y1(i) = sol1(2);                               % storing the value of y seperately
    clc                                             % clearing the command window after each iteration.
end
study1_time = toc;                                  % stopping the timer

%% 3.1) Plotting First Study
figure(2)
subplot(2,1,1);                                                  % creating first half of the figure

plot3(-sol_x1, -sol_y1, -fval1,'- .','markersize',10,'color','r')     % plotting the solution of first study
xlabel('x'); ylabel('y'); zlabel('function value');              % labelling the axes
title('Study 1');                                                % title of the plot
hold on                                                          % holding the next plots


surfc(-xx,-yy,-sol);                                                % plotting the stalagmite function
shading interp;                                                  % removing the shading from the plot
legend('Solutions')

subplot(2,1,2);                                                  % creating second half of the figure
plot(fval1,'-o');                                                % plotting the function values
title('Iterations vs Function Value');                           % title of the plot
xlabel('Iterations'); ylabel('Function Value');                  % labelling the axes
legend('function values')
hold off
%% 4) Second Study (Bounded Inputs)
%
% use the for loop to run the iterations and also provide the lower and upper bounds
%
tic;                                                                          
for i = 1:iterations                                                    % starting the timer
    [sol2 fval2(i)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[1;1]);       % calling the ga function
    sol_x2(i) = sol2(1);
    sol_y2(i) = sol2(2);                                                % storing x and y values seperately
    clc                                                                 % clearing command window on each iteration
end
study2_time = toc;                                                      % stooping the study timer

%% 4.1) Plotting Second Study
figure(3)
subplot(2,1,1);                                                         % generating the upper half of the figure

plot3(-sol_x2,-sol_y2,-fval2,'- .','markersize',10,'color','r');             % plotting the solution of the function
title('Study 2');                                                       % title of plot
xlabel('x'); ylabel('y'); zlabel('z');                                  % labelling the axes
hold on

surfc(-xx, -yy, -sol);                                                     % plotting the stalgmite function
shading interp;
legend('Solutions')                                                     % inseting the required legends

subplot(2,1,2);                                                         % generating the lower half of the plot
plot(fval2,'-o');                                                       % plotting the function values
xlabel('Iterations'); ylabel('Function Value');                         % labelling the axes
title('Iterations vs Function Values');                                 % title of the plot
legend('function values')                                               % inserting required legends
hold off
%% 5) Third Study (Bounded Inputs with Population Size')
tic;                                                                           % starting the study timer

options = optimoptions('ga');                                                  % initializing options
options = optimoptions('ga','PopulationSize',500);                             % proving options parameters using optimoptions function

% now ga will maximize the default optimization parameters replaced by values in options
for i = 1:iterations                                                            % starting the loop
    [sol3 fval3(i)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[1;1],[],options);    % solving the stalagmite function
    sol_x3(i) = sol3(1);                                                        % seperating x and y values
    sol_y3(i) = sol3(2); 
    clc                                                                         % clearing command window on each iteration
end
study3_time = toc;                                                              % stopping the timer

%% 5.1) Plotting the third Study
figure(4)
subplot(2,1,1);                                                        % generating the upper half of the plot

plot3(-sol_x3, -sol_y3, -fval3,'- .','markersize',15,'color','r');          % plotting the solution
xlabel('x'); ylabel('y'); zlabel('Function Value');                    % labelling the axes
title('Study 3');                                                      % title of the plot
hold on

surfc(-xx,-yy,-sol);                                                      % plotting th stalagmite function
shading interp;                         
legend('Solution')                                                     % inserting required legends

subplot(2,1,2);                                                        % generating lower half of the plot
plot(fval3,'-o');                                                      % plotting the function values
xlabel('Iterations'); ylabel('Function Value');                        % labelling the axes
title('Iterations vs Function Value');                                 % title of the plot
legend('function values')                                              % inserting legendd
hold off

%% Displaying Soluton Outputs
disp('------------------------------Maximized Stalagmite Function------------------------------')

disp('Solution Values :')                    % displaying value of solution obtained after third study 
disp(' ')
disp(sol_x3)                               % values of x (input_vector(1))
disp(' ')
disp(sol_y3)                               % values of y (input_vector(2))
disp('Function Values :') 
disp(' ')
disp(fval3)                                % displaying function values
disp(' ')
disp('------------------------------Time taken for each study------------------------------')
fprintf('nTime taken for first study = %f secondsnn',study1_time)     % displaying time taken for all three studies
fprintf('Time taken for second study = %f secondsnn',study2_time)
fprintf('Time taken for third study = %f secondsnn',study3_time)

Output:

Note* - All the plots are inverted for better visualization.

1. Here is the plot of the stalagmite function, plotted over the defined range:

2. Here is the plot of the solutions obtained from the first study:

The solutions obtained from the first study is not very accurate and highly unreliable as it can be seen from the plot below.

3. Here is the plot of the solutions of the second study:

The solutions obtained from the second are more accurate than those of the first study but are still unreliable because of more than one solution and each of different value.

4. Here is the plot of the solutions of the third study:

The solutions obtained from the third study are the most accurate, where the maxima can be easily seen from the plot below.

5. Here is the screen-shot of the command window, showing the optimization solutions and respective function values:

These values are obtained after the completion of the third study. Solution values are the values of the function for the respective inputs displayed below.

6. Lastly, here is another screen-shot of the command window, showing the taken in conducting all three studies respectively:

Conclusion:

1. All three optimization studies are conducted successfully and their outputs are plotted for visualization. The first study provided a large number of solutions which are unreliable whereas the second study provided four to five solutions which is more accurate than the first study but not completely reliable. The third study provides the most accurate results.

2. The time taken to conduct all three studies are also calculated. The first study took the least time around 2.9 seconds while the second study took around 3.4 seconds to complete. The third study took the longest time of around 18 seconds to complete and thus providing the most accurate solution to the optimization problem.

References:

1. https://www.mathworks.com/help/gads/some-genetic-algorithm-terminology.html

2. https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

3. https://en.wikipedia.org/wiki/Genetic_algorithm

4. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3