Optimising Stalagmite Function using Generative Algorithm in MATLAB
Genetic Algorithm:
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:
- Selection rules select the individuals, called parents, that contribute to the population at the next generation.
- Crossover rules combine two parents to form children for the next generation.
- Mutation rules apply random changes to individual parents to form children.
The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways:
Classical Algorithm:
Generates a single point at each iteration. The sequence of points approaches an optimal solution. Selects the next point in the sequence by a deterministic computation.
Genetic Algorithm:
Generates a population of points at each iteration. The best point in the population approaches an optimal solution. Selects the next population by computation which uses random number generators.
Syntax for ga:
x = ga(fun,nvars)
finds a local unconstrained minimum, x, to the objective function fun, nvars is the dimension (number of design variables) of fun.
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
finds a local constrained minimum, x, to the objective function fun, nvars is the dimension (number of design variables) of fun. It defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
requires that the variables listed in IntCon take integer values. (Set A=[] and b=[] if no linear inequalities exist)
For example,
ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)
where fun = function
nvars = No. of design variables e.g. 2
A = [];b = []; % Since no linear inequalities exist
Aeq = [];beq = []; % Since no linear equalities exist
lb = []; % lower bound e.g. [0;0]
ub = []; % upper bound e.g. [0.6;0.6]
nonlcon = [];
IntCon = []; % If any variable is listed in it than it takes integer value otherwise it is null.
optionsoptions = optimoptions('ga','Param1', value1, 'Param2', value2, ...);
With optimoptions we can add more options to ga like 'populationsize' i.e. 'Param1' and it's value i.e. 'value1'.
Stalagmite Function:
A stalagmite is an upward-growing mound of mineral deposits onto the floor of a cave.
Here the function is termed as stalagmite because on plotting the function, the graph looks like stalagmite mineral deposit.
Finding Optimum Maximum value using GA:
Ga by default finds the minima but here maxima needs to be searched. Therefore, it can be done by adding a minus sign inside the function in front of the final output statement. This may give a flipped graph. So, in order to have a correct plot 'fopt' should be replaced by '-fopt' and 'f' should be replaced by '-f'.
--------------------------------------------------------------------------------------------------------
Explanation of the Code:
clear all, close all and clc are the commands given to clean the command window and close all the previous opened figures.
% Defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
'x and y' are row matrix containing 150 values each from 0 to 0.6 .
% Creating a 2D mesh
[xx yy] = meshgrid(x, y);
'xx and yy' are the square matrix of order 150 each generated by meshgrid function using x and y row matrix.
% 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
A nested for loop have been used to evaluate the stalagmite function. Stalagmite function recieves input_vector and input_vector contains the elements of xx & yy. The output have been stored in a square matrix 'f' of order 150. For each iteration, stalagmite recieves two elements, it is evaluated and gives a single value to be stored in 'f' .
Stalagmite Function contains the formulas which needs to be evaluated. The formulas are mentioned below:
`f_(1x) = (sin((5.1 *pi*x) +0.5))^6`
`f_(1y) = (sin((5.1 *pi*y) +0.5))^6`
`f_(2x) = exp((-4*log(2)*(x-0.0667)^2)/0.64)`
`f_(2y) = exp((-4*log(2)*(y-0.0667)^2)/0.64)`
`f = -(f_(1x) * f_(2x) * f_(1y) * f_(2y))`
Study 1 - Statistical Behaviour
rng('default')
Rng('default') function resets the set of random values so that the code may give the same output on each and every execution.
tic
for i = 1: num_cases
[inputs, fopt(i)] = ga(@stalagmite, 2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study1_time = toc
The tic and toc command have been used to study and store the code execution time. A for loop have been used to evaluate the genetic algorithm.
[inputs, fopt(i)] = ga(@stalagmite, 2)
The above statement performs the generative algorithm. It returns the possition of optimum which is stored in inputs and the optimum value which is stored in fopt.
figure(1) : For a new figure window.
subplot(2, 1, 1) : For adjusting 2 plots in a single figure window.
hold on : Fix the curve on the figure window as it is.
surfc(xx, yy, -f) : Used to generate surface from the search space and stalagmite function output.
shading interp : Used to remove the grid from the surface and shade the surface.
plot3(xopt, yopt, -fopt, 'marker','o','markersize',5, 'markerfacecolor','r') : Plots coordinates in 3-D space where xopt, yopt and fopt contains the optimum point and value generated by genetic algorithm.
title('Unbounded Inputs') : Title of the figure window.
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
subplot(2, 1, 2) : For ploting second graph in the same figure window.
plot(-fopt) : Plots optimum values versus iteraions.
xlabel('Iterations') : x-axis name
ylabel('Function Maximum') : y-axis name
Study 2 - Statistical Behaviour with upper and lower bounds
tic
for i=1: num_cases
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study2_time = toc
The tic and toc command have been used to study and store the code execution time. A for loop have been used to evaluate the genetic algorithm.
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1])
The above statement performs the generative algorithm. It returns the possition of optimum which is stored in inputs and the optimum value which is stored in fopt. In input ga recieves the stalagmite function, no. of design variables, 4 null values, upper bound and lower bound. Rest code is same for study 2.
Study 3 - Increasing GA Iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',500);
In the above code , using options, the population size has been increased by 500.
options = optimoptions(SolverName,Name,Value) returns options with the named parameters altered with the specified values.
Population size is an additional option available under ga. Population size (PopulationSize) specifies how many individuals there are in each generation. With a large population size, the genetic algorithm searches the solution space more thoroughly, thereby reducing the chance that the algorithm returns a local minimum that is not a global minimum. However, a large population size also causes the algorithm to run more slowly.
tic
for i = 1:num_cases
[inputs, fopt(1)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1],[],[],options);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study3_time = toc
The tic and toc command have been used to study and store the code execution time. A for loop have been used to evaluate the genetic algorithm.
[inputs, fopt(1)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1],[],[],options);
The above statement performs the generative algorithm. It returns the possition of optimum which is stored in inputs and the optimum value which is stored in fopt. In input ga recieves the stalagmite function, no. of design variables, 4 null values, upper bound, lower bound, 2 null values and options. Rest code is same for study 3.
--------------------------------------------------------------------------------------------------------
MATLAB Code:
The following MATLAB code optimises the stalagmimte function using GA.
% Optimising Stalagmite Function using GA
clear all
close all
clc
% Defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
% Creating a 2D mesh
[xx yy] = meshgrid(x, y);
% 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
% Study1 - Statistical Behaviour
% rng('default') function resets the set of random values so that the code may give the same output on each and every execution.
rng('default')
% tic toc command studies the execution time
% for loop to evaluate stalagmite function.
tic
for i = 1: num_cases
[inputs, fopt(i)] = ga(@stalagmite, 2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study1_time = toc
figure(1)
subplot(2, 1, 1)
hold on
% To generate a surface
surfc(xx, yy, -f)
% To convert the surface into smooth shaded surface
shading interp
% To plot in 3 dimensions or 3D Plot.
plot3(xopt, yopt, -fopt, 'marker','o','markersize',5, 'markerfacecolor','r')
title('Unbounded Inputs')
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
subplot(2, 1, 2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
% To know all the optimum values at optimum points.
fprintf('The local maximum value of the function is %f at x = %f and y = %f\n',fopt, xopt, yopt)
% Study2 - Statistical Behaviour with upper and lower bounds
rng('default')
tic
for i=1: num_cases
% Here the upper and lower limits are also given to ga.
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study2_time = toc
figure(2)
subplot(2, 1, 1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(xopt, yopt, -fopt, 'marker','o','markersize',5, 'markerfacecolor','r')
title('Bounded Inputs')
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
subplot(2, 1, 2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
% To know all the optimum values at optimum points.
fprintf('The local maximum value of the function is %f at x = %f and y = %f\n',fopt, xopt, yopt)
% Study3 increasing GA Iterations
% Using options, the population size has been increased by 400
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',400);
rng('default')
tic
for i = 1: num_cases
[inputs, fopt(i)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1],[],[],options);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study3_time = toc
figure(3)
subplot(2, 1, 1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(xopt, yopt, -fopt, 'marker','o','markersize',5, 'markerfacecolor','r')
title('Increased Population Size')
xlabel('x-axis')
ylabel('y-axis')
zlabel('z-axis')
subplot(2, 1, 2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
% for loop to store the unique the optimum points.
a = -max(fopt);
for i = 1: length(fopt)
if(a == -fopt(i))
pos1 = xopt(i);
pos2 = yopt(i);
end
end
% To know all the optimum values at optimum points.
fprintf('The local maximum value of the function is %f at x = %f and y = %f\n', -fopt, xopt, yopt)
% To print the optimum value at optimum points.
fprintf('\n\nThe global maximum value of the function is %f at x = %f and y = %f\n', a, pos1, pos2)
--------------------------------------------------------------------------------------------------------
Output:
Case 1 : Unbounded Inputs
Case 2 : Bounded Inputs
Case 3 : Increased Population Size
Global Maximum Value Output :
The program was executed 5 times and each time the same output was observed.
------------------------------------------------------------------------------------------------------------
Errors:
Error 1 : Use of rng() function inside the loop
Solution: The rng() function was repositioned before the loop.
-----------------------------------------------------------------------------
Error 2 : Typo Error
Solution: 1 was replaced by i
------------------------------------------------------------------------------------------------------------
References:
https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
https://in.mathworks.com/help/gads/ga.html?s_tid=doc_ta#mw_a9a9e523-4242-481e-b6b9-acbe194a2432