Optimization of Stalagmite Function using Genetic Algorithm in MATLAB.

AIM:

To optimise the stalagmite function and find the global maxima of function using Genetic Algorithm in MATLAB.

OBJECTIVES:

1. Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
2. Expalin the concept of genetic algorithm.
3. Explain the syntax for ga in MATLAB.

THEORY:

Concept of Genetic Algorithm

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

We can apply the genetic algorithm to solve 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 differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.

How Genetic Algorithm works

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.
2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
   1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
   2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
   3. Selects members, called parents, based on their expectation.
   4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
   5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
   6. Replaces the current population with the children to form the next generation.
3. The algorithm stops when one of the stopping criteria is met

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

1. Selection rules select the individuals, called parents, that contribute to the population at the next generation. The selection function chooses parents for the next generation based on their scaled values from the fitness scaling function. The scaled fitness values are called the expectation values. An individual can be selected more than once as a parent, in which case it contributes its genes to more than one child.

2. Crossover rules combine two parents to form children for the next generation. The algorithm creates crossover children by combining pairs of parents in the current population. At each coordinate of the child vector, the default crossover function randomly selects an entry, or gene, at the same coordinate from one of the two parents and assigns it to the child. For problems with linear constraints, the default crossover function creates the child as a random weighted average of the parents.

3. Mutation rules apply random changes to individual parents to form children. The algorithm creates mutation children by randomly changing the genes of individual parents. By default, for unconstrained problems the algorithm adds a random vector from a Gaussian distribution to the parent. For bounded or linearly constrained problems, the child remains feasible.

Stopping Criteria for Genetic Algorithm

The genetic algorithm uses the following conditions to determine when to stop:

• Generations — The algorithm stops when the number of generations reaches the value of Generations.
• Time limit — The algorithm stops after running for an amount of time in seconds equal to Time limit.
• Fitness limit — The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to Fitness limit.
• Stall generations — The algorithm stops when the average relative change in the fitness function value over Stall generations is less than Function tolerance.
• Stall time limit — The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to Stall time limit.
• Stall test — The stall condition is either average change or geometric weighted. For geometric weighted, the weighting function is 1/2ⁿ, where n is the number of generations prior to the current. Both stall conditions apply to the relative change in the fitness function over Stall generations.
• Function tolerance — The algorithm runs until the average relative change in the fitness function value over Stall generations is less than Function tolerance.
• Constraint tolerance — The Constraint tolerance is not used as stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints. Also, max(sqrt(eps),ConstraintTolerance) determines feasibility with respect to linear constraints.

The algorithm stops as soon as any one of these conditions is met.

Significance of running multiple iterations and cases and results

As we have seen how the Genetic Algorithm works, the significance of running multiple iterations and cases and results is that we perform the algorithm multiple times and create a new solutions by computation. As the number of generations increases, the individuals in the population get closer together and approach the optimum solution. Over successive generations, the population "evolves" toward an optimal solution.

Solver 'ga’ is built-in function in MATLAB which finds minimum of function using genetic algorithm.

Syntax for ga

1. 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.
2. x = ga(fun,nvars,A,b) : Finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').
3. x = ga(fun,nvars,A,b,Aeq,beq) : Finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[ ] and b=[ ] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').
4. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) :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.)
5. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) : Subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
6. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) : Minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
7. x = ga(fun,nvars,A,b,[ ],[ ],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[ ],[ ],lb,ub,nonlcon,IntCon,options) : Requires that the variables listed in IntCon take integer values.
8. x = ga(problem) : Finds the minimum for problem, where problem is a structure.
9. [x,fval] = ga(___): For any previous input arguments, also returns fval, the value of the fitness function at x.
10. [x,fval,exitflag,output] = ga(___): Also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
11. [x,fval,exitflag,output,population,scores] = ga(___) : Also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

PROGRAM:

Programming language used is MATLAB.

This program is for stalagmite function , which performs as a fitness function in our main program.

% This the program for stalagmite function

function [f] = stalagmite_function(input_vector)
x = input_vector(1);        % 1st column of input vector has x values
y = input_vector(2);        % 2nd column of input vector has y values 
 
term1 = (sin((5.1*pi*x )+ 0.5))^6;
term2 = (sin((5.1*pi*y) + 0.5))^6;
term3 = exp(-4*log(2)*((x-0.0667)^2)/0.64);
term4 = exp(-4*log(2)*((y-0.0667)^2)/0.64); 
 
f = -(term1*term2*term3*term4);     % We use negative sing to get the opposite results (that is to get the maximum value instead of minimum) as the ga function finds the mininmum value

end

This program is the main program which optimizes the Stalagmite Function using Genetic Algorithm.

% This is a program to find the global maxima using Genetic Algorithm

clear all
close all
clc 
 
% Defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
n = 50;                     % no. of iterations 
 
[xx,yy] = meshgrid(x,y);        % Creating a 2D matrix of the search space for x and y values
 
%% Evaluating stalagmite function
for i = 1:length(xx)
    for j = 1:length(yy)         
        input_vector(1) = xx(i,j);                      % Taking x values in 1st column of input vector
        input_vector(2) = yy(i,j);                      % Taking y values in 2nd column of input vector
        f(i,j) = stalagmite_function(input_vector);     % Calculating the value of the stalagmite function at particular x and y coordinates
    end
end

% Plotting the stalagmite function
figure (1)
surf(xx,yy,-f)                  % Creating a 3D plot of the Stalagmite function
shading interp                  % Turning off the grid
xlabel ('x value')
ylabel ('y value')
title('Stalagmite Function')
colorbar

%% Case 1 - Statistical Behaviour (with Unbound conditions)

tic         % starting the time count

for k = 1:n     
    [inputs1 , fopt1(k)] = ga(@stalagmite_function, 2);     % Using "ga" to optimize the function for maximum value
    % fopt1 contains optimum value of the function at the particular inputs1 which has x and y coordinates for current iteration
    xopt1(k) = inputs1(1);
    yopt1(k) = inputs1(2);
end

time1 = toc             % Stopping time count and storing the time required for all the iterations in time1

% Plotting
figure(2)
subplot(2,1,1)
hold on
surf(xx,yy,-f)                  % Creating a 3D plot of the Stalagmite function
shading interp                  % Turning off the grid

% Plotting the optimum points produced by genetic algorithm performed on Stalagmite function
plot3(xopt1,yopt1,-fopt1,'marker','o','markerfacecolor','r')        
xlabel('X values')
ylabel('Y values')
title('Statistical Behaviour - with unbound conditions') 
 
% Plotting the optimum value produced with each iteration
subplot(2,1,2)
plot(-fopt1)
xlabel('Iterations')
ylabel('Optimum Value of the Function')
title('Statistical Behaviour - with unbound conditions') 
 

%% Case 2 - Statistical Behaviour - with upper and lower bound
tic             % Starting the time count
for k = 1:n     
    [inputs2 , fopt2(k)] = ga(@stalagmite_function, 2,[],[],[],[],[0;0],[1;1]);     % Using "ga" to optimize the function for maximum value
    % fopt1 contains optimum value of the function at the particular inputs1 which has x and y coordinates for current iteration
    xopt2(k) = inputs2(1);
    yopt2(k) = inputs2(2);
end

time2 = toc               % Stopping time count and storing the time required for all the iterations in time2

% Plotting
figure(3)
subplot(2,1,1)
hold on
surf(xx,yy,-f)                  % Creating a 3D plot of the Stalagmite function
shading interp                  % Turning off the grid
 
% Plotting the optimum points produced by genetic algorithm performed on Stalagmite function
plot3(xopt2,yopt2,-fopt2,'marker','o','markerfacecolor','r')
xlabel('x values')
ylabel('y values')
title('Statistical Behaviour - with upper and lower bound') 

% Plotting the optimum value produced with each iteration
subplot(2,1,2)
plot(-fopt2)
xlabel('Iterations')
ylabel('Optimum Value of the Function')
title('Statistical Behaviour - with upper and lower bound') 


%% Case 3 - Statistical Behaviour - with increasing GA iterations

options = optimoptions('ga');    % This line specifies that the opitions is to be given to ga function.        
options = optimoptions(options,'populationsize',300) ;      % This line specifies that the population size will be 300.

tic         % Starting the time count
for k = 1:n
    [inputs3 , fopt3(k)] = ga(@stalagmite_function, 2,[],[],[],[],[0;0],[1;1],[],[],options);
    % In above line we used "ga" to optimize the function for maximum value
    % fopt1 contains optimum value of the function at the particular inputs1 which has x and y coordinates for current iteration
    xopt3(k) = inputs3(1);
    yopt3(k) = inputs3(2);
end

time3 = toc          % Stopping time count and storing the time required for all the iterations in time3         

% Plotting
figure(4)
subplot(2,1,1)
hold on
surf(xx,yy,-f)                  % Creating a 3D plot of the Stalagmite function
shading interp                  % Turning off the grid

% Plotting the optimum points produced by genetic algorithm performed on Stalagmite function
plot3(xopt3,yopt3,-fopt3,'marker','o','markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Statistical Behaviour - with increased GA iterations') 
 
% Plotting the optimum value produced with each iteration
subplot(2,1,2)
plot(-fopt3)
xlabel('Iterations')
ylabel('Optimum Value of the Function')
title('Statistical Behaviour - with increased GA iterations')
%% Creating a table 

x_point = [xopt1(50);xopt2(50);xopt3(50)];
y_point = [yopt1(50);yopt2(50);yopt3(50)];
optimum_value = [-fopt1(50);-fopt2(50);-fopt3(50)];
time_taken = [time1;time2;time3];

names ={'Statistical Behaviour - with unbound conditions';'Statistical Behaviour - with upper and lower bound';'Statistical Behaviour - with increased GA iterations'};

tab = table(x_point,y_point,optimum_value,time_taken,'RowNames',names)

EXPLANATION OF THE PROGRAM:

1. In the first program we have created a stalagmite function. It takes input as row vector which has two columns and is called “input_vector”. The input vector has x values in first column and y values in the second column, which are extracted and stored in the variables x and y. The output of the function is calculated using these formulas:

2. Solving the Genetic algorithm for stalagmite function gives us minimum value of function. To find the maximum value of the function, we need to change the sign of function, so that it will give value for the reverse case of mimima, i.e. maxima.
3. Second program is our main program which calculates the function maximum using Genetic Algorithm.
4. We start with defining the search space for finding the values of x & y in the stalagmite function. The search space is chosen to be in between 0 to 0.6 with 150 intervals. For this purpose linspace() function is used.
5. As Genetic Algorithm can take no. of iterations each time we run the code giving different value each time. To save the time of calculations we have restricted our script to run for 50 iterations only. It doesn’t mean function will give maximum value in 50 iterations. We will consider whatever maximum value that came within those 50 iterations. We have restricted our area of search. This no of iterations is given by “n=50”.
6. As linspace create the series of numbers, x & y will be the column vector. As input to stalagmite function is row vector, we need to convert column vector to row vector. First step of this conversion is to create the meshgrid(x,y). Then we use for loops and calulate the value of the stalagmite function which is “f” at every particular value in the search space.
7. After calculating the function we start with finding the optimum function value which in our case is maximum value of the function. We take three cases.
8. In 1st case maximum value of function is found out with no restrictions, no bounds and no limits. Genetic algorithm is free to choose the population then reproduce & mutate. Then we plot graphs for case 1.In this we get results all over the place this was because we did not specify the upper and lower bounds.
9. In second case we restrict the ga with upper bound and lower bound. As we can see in the script of case 2 ,

[inputs2 , fopt2(k)] = ga(@stalagmite_function, 2,[],[],[],[],[0;0],[1;1])

Then we plot graphs for case 2.

10. In case 3 we increase GA iterations , and change the populationsize to 300. In this case syntax for ga is different than previous case. GA has to give this population size via an option. “optimoptions” facilitates this provision

options = optimoptions('ga');

This line specifies that the opitions is to be given to ga function.

options = optimoptions(options,'populationsize',300) ;

This line specifies that the population size will be 300.

As we can see the syntax of ga in the script of case 3 is ,

ga(@stalagmite_function, 2,[],[],[],[],[0;0],[1;1],[],[],options);

Then we plot graphs for case 3.

11. At the end we create a table which contains the x and y values at which we get maximum function value in each case and the time required for each case to get executed.

RESULTS:

1. This the graph of the stalagmite function.

2. This is the plot of Case 1 which has 2 graphs

2. 1. Plot of Stalagmite function and the value of function calculated by Genetic Algrithm at each particular iteration .

2. 2. Plot of optimum value of function vs iterations. It shows optimum value of function varies each time iteration runs. It also shows large variations in optimum value of function of each iterarion. The large variations are result of not providing any bound to the function.

3 . 3D plot for Stalagmite function and the value of function calculated by Genetic Algrithm at each particular iteration in Case 1. Red dots show the functions optimum value calculated .

4 . This is the plot of Case 2 which has 2 graphs

4. 1. Plot of Stalagmite function and the value of function calculated by Genetic Algrithm at each particular iteration .

4. 2. Plot of optimum value of function vs iterations. It shows optimum value of function varies very little each time iteration runs. It also shows small variations in optimum value of function of each iterarion. The small variations are result of providing bounds to the function.

5 . Case 2 3D plot for Stalagmite function and the value of function calculated by Genetic Algrithm at each particular iteration. Red dots show the functions optimum value calculated . We can see less no. of red dots this is because we provided bounds and ga operated within those bounds .

6. This is the plot of Case 3 which has 2 graphs.

6. 1. Plot of Stalagmite function and the value of function calculated by Genetic Algrithm at each particular iteration .

6. 2. Plot of optimum value of function vs iterations. It shows optimum value of function doesn’t vary a lot it isvery close to 1 for every iteration run. The reason for this is increasing the iterations in ga.

7. Case 2 3D plot for Stalagmite function and the value of function calculated by Genetic Algrithm at each particular iteration. We see only one red dot which is maximum value of the function which comes out to be 1.

8. Table created in the command window, it contains the x and y values at which we get maximum function value in each case and the time required for each case to get executed.

9. Validation using optimization toolbox.

CONCLUSION:

1. Genetic Algorithm was successfully performed on stalagmite function to calculate the global maxima using a MATLAB program. and the results were verified using optimization tool box in MATLAB.
2. Graphs for 3 studies and for F-maximum vs no. of iterations were plotted.
3. Understanding of genetic algorithm and optimization tool box in MATLAB was developed.

REFERENCE:

https://in.mathworks.com/discovery/genetic-algorithm.html?s_eid=PEP_12669

https://in.mathworks.com/help/gads/ga.html

https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f6243

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

https://in.mathworks.com/help/gads/examples/coding-and-minimizing-a-fitness-function-using-the-genetic-algorithm.html