close all
clear all
clc
%% PART 1: INPUTS:
x = linspace(0,0.6,150); % X input row vector.
y = linspace(0,0.6,150); % Y input row vector.
num_spaces = 50; % No. of Iterations of Genetic Algorithm undergoes.
% creating 2D arrays.
[xx, yy] = meshgrid(x,y);
for i = 1:length(x)
for j = 1:length(y)
input_vector(1) = xx(i,j); % First input to stalagmite function.
input_vector(2) = yy(i,j); % Second input to stalagmite function.
f(i,j) = stalagmite(input_vector); % Value of stalagmite function.
end
end
%% PART 2: 1st Study: Statistical Behaviour (Unbounded Inputs):
tic
for i = 1:num_spaces
[results,fopt(i)] = ga(@stalagmite,2);
xopt(i) = results(1);
yopt(i) = results(2);
end
time1 = toc
%Plotting the function surface and maximum function values.
figure(1)
subplot(2,1,1)
surfc(x,y,-f) % Stalagmite Function Surface.
shading interp
hold on
%PLotting the Maximum function values:
% a) 3D plot of xopt, yopt and fopt.
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','b')
title('Genetic Algorithm function with Unbounded Inputs')
subplot(2,1,2)
% b) Ploting Max. function value for each Iteration.
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
%% PART 3: 2nd Study: Statistical Behaviour with Bounded Inputs (Lower and Upper Bound):
tic
for i = 1:num_spaces
[results, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(i) = results(1);
yopt(i) = results(2);
end
time2 = toc
%PLotting the Maximum function values:
figure(2)
subplot(2,1,1)
surf(x,y,-f) % Stalagmite Function Surface.
shading interp
hold on
%PLotting the Maximum function values:
% a) 3D plot of xopt, yopt and fopt.
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','b')
title('Genetic Algorithm function with Bounded Inputs')
subplot(2,1,2)
% b) Ploting Max. function value for each Iteration.
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
%% PART 3: 3rd Study: Statistical Behaviour with Increased Initial Population:
tic
options = optimoptions('ga');
options = optimoptions(options,'populationsize',250);
for i = 1:num_spaces
[results, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt(i) = results(1);
yopt(i) = results(2);
end
time3 = toc
figure(3)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
%PLotting the Maximum function values:
% a) 3D plot of xopt, yopt and fopt.
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','b')
title('Genetic Algorithm function with New Population Size')
subplot(2,1,2)
% b) Ploting Max. function value for each Iteration.
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
Optimization: -
Optimization is a process of advancing to a better, more efficient, and more beneficial state. Mathematically, optimization is a process of calculating the maximum or the minimum value of a given function for a given domain of the input variables.
The process involves some inputs and some outputs, and through optimization, values of those inputs are found out for which the outputs are maximum or minimum.
These to the input variables is termed as ‘searchspace’. In this searchspace a certain set of input is present for which the function will be optimum.
The optimization method is different for different types of functions. If a function is continuous and differentiable for the given input range, then optimization is done by calculating the derivative of the function and equating it to zero to find out the value of the independent variable at which function will have an optimum value.
But if the function is not continuous and differentiable then to find the function optimum value can be found out by the Genetic Algorithm (GA) method.
Stalagmite Function: -
‘Stalagmite’ is a structure found in caves that forms due to deposition of the sediments and other matter dissolved in the water which keeps on dropping at the same location for a very long period of time.
Stalagmite function is a mathematical reconstruction of that structure.
Genetic Algorithm (GA) Method: -
It is a technique based on the principle of evolution by natural selection given by Darwin. GA is a subset of a branch known as Evolutionary Computation. It is developed by scientists of the University of Michigan.
The process followed in GA involves 5 steps performed repeatedly to reach the optimum value.
1. Initial Population.
2. Fitness Function.
3. Selection.
4. Crossover.
5. Mutation.
Initial Population: this is a set of selected possible solutions for the function. Each of these solutions is characterized by some parameters called, Genes. In GA, the genes for an individual are represented using a string of binary values. These Genes are joined together and this gives a Chromosome or Solution.
Fitness Function: this is also known as the Evaluation function which calculates the degree of closeness of the given solution to the optimum solution. A fitness score is awarded to each of the chromosomes (solution) corresponding to their closeness to the optimum solution.
Selection: here, the fittest solution is selected which will be eligible to pass into the next generation. The highest fitness score solutions have the most chances.
Crossover: This is the most important step of GA. in this step, each pair of parents selected will be mated and Offspring is created by exchanging the genes of parents among themselves. the crossover point is the point where the process is done.
Mutation: it is a process of altering the chromosome structure of some of the offspring. this is done by flipping some of the bits in the string. This is done to maintain a certain level of diversity within the population and to prevent premature convergence. Convergence can be defined as the termination of the GA due to the fact that the new generation population is not different from the previous one.
These steps are followed repeatedly till there is a new generation of solutions that is better than the previous one.
The code is divided into 4 parts:
Part 1: inputs:
Line 7 and 8, stores the value of x and y is which are the input row vectors for generating the initial population Genetic Algorithm function.
Line 9, ‘num_spaces’ is the variable which will store the number of iterations of the genetic algorithm will execute.
Line 12, ‘meshgrid’ will convert the row vectors ‘x’ and ‘y’ into the [xx] and [yy] matrices.
Line 13 for loop is initiated from i = 1 to i=length(x) i.e. 1-150.
line 14, Another for loop with counter ‘j’ is initiated for the same span (1-150).
Line 15-16, ‘input_vector’ is a row vector with 2 elements in it. The value for this variable is decided with the help both the loop counters (i,j). these counters will draw the respective elements from [xx] and [yy] as values 1st and 2nd elements of ‘input_vector’.
Line 17, calls the stalagmite function, this function takes ‘input_vector’ as an input and the output returned is stored in variable named ‘f’.
The code for the stalagmite function is mentioned below:
function F = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x + 0.5)).^6;
f2 = (sin(5.1*pi*y + 0.5)).^6;
f3 = exp((-4*log(2)*((x - 0.0667).^2))/0.64);
f4 = exp((-4*log(2)*((y - 0.0667).^2))/0.64);
F = -(f1*f2*f3*f4);
end
Line 1, the function name is defined (stalagmite), the output of the function is (F) and the inputs for the function is defined. Input for this function is the row vector ‘input_vector’.
Line 2, ‘x’ takes value from 1st column of the input_vector.
Line 3, ‘y’ takes value from 2nd column of the input_vector.
Line 5-9, f1, f2, f3, f4 all are the individual functions which help in calculating the stalagmite function (F) value in line 11.
The negative sign is provided because as a default setting the genetic algorithm function always calculates the minimum value for any function. So in order to find the maximum value of the function it is necessary to multiply it with negative sign.
For different values of i and j stalagmite function will be executed and its value which will be stored in variable ‘f’.
after execution of these two for loops the initial population for the genetic algorithm function is created.
Part 2: 1st study: Statistical Behaviour (Unbound Inputs):
Line 24, ‘tic-toc’ function is initiated by giving ‘tic’ command. This will record the time for which the study is underway.
And stop when the counterpart ‘toc’ command is provided.
Line 26, for loop is initiated, which will run from i = 1to 50 (No. of Iterations of the Genetic Algorithm function).
fopt(i) is the optimum value of the stalagmite function calculated for each iteration.
Results is the row vector storing the value of x and y coordinates (xopt, yopt) for each fopt(i) value.
Line 30, loop will end when all the iterations for the genetic algorithm are executed successfully.
Line 32, time1 is the variable which will store the time taken by the genetic algorithm function.
Line 33, will open a figure window.
Line 34, subplot command will divide the figure window into two parts so that two different plots can be plotted in a same figure window.
Line 35, the ‘surfc’ command generates the surface of the function by taking in [xx], [yy] and the ‘f’ as inputs.
The ‘shading interp’ command will supress the grid lines covering the surface generated. And gives the surface a shading effect which looks more smoother and easily understood.
Line 37, hold on command will superimpose two or more plots created.
Line 38, ‘plot3’ command will plot the ‘xopt’, ‘yopt’ and the ‘fopt’values for all the 50 iterations of genetic algorithm function, ‘marker, command will help in visualising these plotted points more efficiently.
Line 39, separately plots the maximum function value (fopt) w.r.t. the iterations as the other axis.
This study gives figure 1 as one output. From the plot on the the top is is seen that the function value is out of the desired range of [xx] and [yy], which lies from [0,0] to [0.6,0.6]. this is due to the fact that ‘GA’ function is randomly picking the inputs. The ‘GA’ does not know to find the maximum within a specific range of the inputs.
The bottom plot shows the function maximum value with iterations as x-axis for the plot.
Problems acknowledged from the above study are:
The maximum value is changing between 0 and 1 for different iterations, which is quite large.
The ‘GA’ function is going out of bound of the input variables.
The time elapsed in this study is ‘time1’ = 5.6908 sec.
To rectify these problems 2nd study was performed.
Before going for the 2nd study it is necessary to look into the different syntax of the genetic algorithm function.
1. x = ga(FITNESSFUN, NVARS), with this syntax the ga function will find out the local unconstrained minima (x) for the function ‘fun’. Where ‘NVARS’ is the number of the variables in the function FITNESSFUN.
2. x = ga(FITNESSFUN, NVARS, A, b), calculates the local minima (x) for the function FITNESSFUN. In addition the function is subjected to a linear inequality, A*x <= b.
2 .x = ga(FITNESSFUN, NVARS, A, b, Aeq, Beq), this will also calculate local minima for function ‘FITNESSFUN’ equal to (x). subject to two linear inequalities. A*x <= beq, and Aeq*x = beq. If there are no inequalities then [] are placed in their respective positions.
4. x = ga(FITNESSFUN, NVARS, A, b, Aeq, Beq, lb, ub), gives boundary to the design variable (x), so that solution is calculated within the given range only. If ‘x’ is unbounded for one extremity then the respective value for ‘ub’ or ‘lb’ is set to (Inf) or (-Inf) respectively.
5. x = ga(FITNESSFUN, NVARS, A, b, Aeq, Beq, lb, ub, NONLCON) this subjects the function to another constraint mentioned by NONLCON. NONLCON takes x as input variable and returns the outputs C and Ceq. The set which represents the non-linear inequalities and equalities respectively. Such that
C(x) <= 0 and Ceq(x) = 0.
6. x = ga(FITNESSFUN, NVARS, A, b, Aeq, Beq, lb, ub, NONLCON, options) will minimize the default optimization parameters replaced by the values in ‘options’. ‘Options’ is created using ‘OPTIOPTIONS’ function.
7. x = ga(FITNESSFUN, NVARS, A, b, Aeq, Beq, lb, ub, NONLCON, INTCON) the ‘intcon’ requires the variables listed in ‘intcon’ to take integer values only.
8. x = ga(FITNESSFUN, NVARS, A, b, Aeq, Beq, lb, ub, NONLCON, INTCON, options) it will minimize with integer constraints and default optimization parameters replaced by the values in the ‘options’.
Similar to the loop that was created in previous study from line 26-30, another one is created in the second study also in line 56-60. However in this one the syntax for the ‘ga’ function is changed such that the input variables are bounded within [0,0.6] for both the variables and the ‘ga’ function in this study cannot go beyond the prescribed bounds.
This solves the 2nd problem encountered.
Line 24, starts recording the time consumed by this ‘ga’ function execution by giving the ‘tic’ command.
And this command stops at line 62 with 'time2' as the consumed time.
Results from this study obtained can be seen in figure 2. In this figure, it is clear that now the ‘ga function do not go beyond the given boundary limits set for the input variables.
Secondly, the variation of the maximum function value is also within the values 0.85-1, except for the iteration number 45. Also, the maximum of the function now is found at 4 different peaks. This is still not the ideal outcome, so to rectify this another study is done. In this study the initial population size is increased for better continuity as well as accuracy of the ‘ga’ function.
The time elapsed in this study is ‘time2’ = 8.3489 sec, which is slightly more than ‘time1’.
Part 4: behaviour with increased population size:
In this study, the syntax for the ‘ga’ function is changed such that the optimization parameters are different in this case. The parameter changed in here is the size of the initial population. The size for previous 2 studies was set to default value of 50 i.e. 50 set of values of the input variables. But in this case the population size is increased to 250. So for this study there will be 250 sets of values for the input variables.
This change is done by changing the ‘ga’ syntax and adding another term ‘options’ within the brackets in the last as described above.
‘Options’ is created using MATLAB inbuilt function OPTIOPTIONS.
Line 89, ‘optioptions’ function is called and variable ‘options’ is the output of this function, which takes in the ‘ga’ function as input. This line will add ‘options’ as another input for the ‘ga’ function.
Line 90, the new value of the population size is given. Now when the ‘ga’ function is executed the population size will be 250 for each variable.
Line 87, again the 'tic' command is activated to record the time consumed in this study and this command stops once the outputs of the 'ga' functions are obtaied for all iterations.
Line93-97, the for loop is created for the study and will run and execute the changed ‘ga’ function which will give maximum value for the stalagmite function as ‘fopt’. The x and y coordinates of these values as ‘xopt’ and ‘yopt’.
Line 99, the 'toc' command will save the time consumed by the 3rd study.
Line 100, a new figure window is opened, named figure 3.
Line 101, subplot will divide the current figure window into 2 sections.
The 1st section is used for plotting the stalagmite function surface in line 102 and the maximum function value (fopt) both superimposed as explained below.
Line 103, the shading interp command will provide the surface with a better shaded look.
Line 104, hold on command will keep the previous plots from been overwritten.
Line 109, plots command plots the 'xopt', 'yopt' and 'fopt' on a 3D plot to see the maximum function value for the stalagmite function (fopt) obtained from the 'ga' function in the 3rd study.
Line 110, subplot(2,1,2) is the second section which contains the plot of the maximum function value (fopt) against the corresponding Iterations in line 111.
Line 104-106 provides the xlabel, ylabel and title for the plot.
The result from this study is the figure 3.
The top plot shows the stalagmite function for the given input variables domain. The blue dots shows the values obtained from the 'ga' function for every iteration.
It this there is only one bot dot on the highest peak of the function which is the global maxima of the function for the given input domain.
The plot in below shows the variation of the maximum function value for all the iterations and it is seen that its value varies within the range of [0.9999985, 0.999975] . This is acceptable result.
The time consumed for this study is 23.2849 sec, which is almost 4 times that of the 1st study.
But the result from 3rd are much more accurate and acceptable.