Genetic Algorithm using MATLAB

AIM :

To create a code in MATLAB to optimise the stalagmite function and find the Global maxima of the function.

THEORY :

• Genetic algorithms are a type of gradient free optimization algorithm. These algorithms are based on the ideas of biology and evolution.
• This algorithm is a random-based classical evolutionary algorithm. By random here we mean that in order to find a solution using the GA, random changes applied to the current solutions to generate new ones.
• Genetic Algorithms (GA) are a computerized search-based optimization algorithms based on the mechanics of Natural Genetics and Natural Selection.
• GA is based on Darwin’s theory of evolution. It is a slow gradual process that works by making changes to the making slight and slow changes. Also, GA makes slight changes to its solutions slowly until getting the best solution.
• They are commonly used to generate high-quality solutions to  optimization and search problems by relying on biologically inspired operators such as Mutation, Crossover and Selection.

Concept & working of Genetic Algorithm(GA) :

• 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. 
• Instead of proposing just a single solution to an optimization problem, a genetic algorithm generates many possible solutions that form a “population”.
• For example, if we were trying to optimize x and y, a population would be formed from various combinations of values of x and y. The solutions are scored using a fitness function, or objective function to decide which solutions are better than others.
• These candidate solutions are then recombined so that the best solutions “reproduce” to form a new generation of solutions with the best traits of the previous solutions. This continues until improvement stops or the maximum number of generations is reached.

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

• Reproduction or Selection rules to 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.

Syntax of Ga used in MATLAB

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

• Here, the ga is used to find minimum of function using genetic algorithm which is inbuilt by global optimization toolbox.
• fun represents an objective function, specified as a function handle or function name. We write the objective function to accept a row vector of length nvars and return a scalar value.
• 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 ≤
• A represents the linear inequality constraints, specified as a real matrix.
• B represents the linear inequality constraints, specified as a real vector.
• Aeq and beq represents linear equality constraints, specified as a real matrix and real vector. 
• nonlcon represents the Nonlinear constraints, specified as a function handle or function name. nonlcon is a function that accepts a vector or array x and returns two arrays, c(x) and ceq(x).
• The syntax minimizes with the default optimization parameters replaced by values in   
• To create options using optimoptions, the term options is used in syntax.

GOVERNING EQUATIONS :

Equations used in stalagmite function are as follows -

OBJECTIVES OF THE PROJECT:

• To write a code in MATLAB to optimise the stalagmite function.
• To Find the Global maximaof the function.
• Understand & explain the Concept of Ga.

FUNCTION CODE :

function [f] = stalagmite_Func(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*f2_x*f1_y*f2_y);
end

MAIN CODE :

%% PROGRAM FOR STALAGMITE MATHEMATICAL MODEL USING GA
clear all
close all 
clc

% Preparing or Defining the Search space 
x = linspace(0,0.6,150) ;                         % Assigning the range for x co-ordinates
y = linspace(0,0.6,150) ;                         % Assigning the range for y co-ordinates

% Creating a Array or 2D MESH for search space
[X , Y] = meshgrid(x,y) ;                         % Giving inputs x and y to form 2D Mesh

% No. of Iterations 
num_case = 100;

% Evaluating the Stalagmite function
for i = 1:length(X)
    for j = 1:length(Y)
        Input_vector(1) = X(i,j);                   % Input vector for x
        Input_vector(2) = Y(i,j);                   % Input vector for y
        f(i,j) = stalagmite_Func(Input_vector);     % Calling the stalagmite Function
    end
end

surfc(X,Y,f)
xlabel('x values')
ylabel('y values')

shading interp                                      % Using shading command to removing the grid lines

[inputs , fval] = ga(@stalagmite_Func , 2) 

      
% STUDY 1 Statistical Behaviour

tic                                                     % Using tic to start stopwatch timer

for i = 1 : num_case
    [inputs, f_opt(i)] = ga(@stalagmite_Func,2);        % Using ga for stalagmite function 
    x_opt(i) = inputs(1);                               % Storing the x values
    y_opt(i) = inputs(2);                               % Storing the y values
end

study1_time = toc

figure(1)
subplot(2,1,1)                                          % To plot multiple plots using subplot
hold on
surfc(x,y,-f)                                           % Plotting surface for x vs y with function
shading interp
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('UNBOUNDED INPUT')

subplot(2,1,2)
plot(-f_opt)
xlabel('No.of Iterations')
ylabel('Maximum Function Value')


% STUDY 2 Statistical Behaviour with Upper and Lower Bounds

tic

for i = 1 : num_case
    [inputs, f_opt(i)] = ga(@stalagmite_Func,2,[],[],[],[],[0;0],[1;1]);  % Using ga commmand & giving lower and upper bounds
    x_opt(i) = inputs(1);                                                 % Storing the x values
    y_opt(i) = inputs(2);                                                 % Storing the y values
end

study2_time = toc                                                         % Using toc to read the elapsed time from timer

figure(2)
subplot(2,1,1)                                                            % To plot multiple plots using subplot
hold on
surfc(x,y,-f)                                                             % Plotting surface for x vs y with function
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('No.of Iterations')
ylabel('Maximum Function Value')

% STUDY 3 Statistical Behaviour by Increasing GA Iterations

options = optimoptions('ga')
options = optimoptions(options,'PopulationSize',350)                        % Giving the population size to 350 for ga

tic                                                                         % Using tic to start stopwatch timer

for i = 1 : num_case
    [inputs, f_opt(i)] = ga(@stalagmite_Func,2,[],[],[],[],[0;0],[1;1],[],[],options);  % Using ga commmand & giving lower and upper bounds
    x_opt(i) = inputs(1);                                                               % Storing the x values
    y_opt(i) = inputs(2);                                                               % Storing the y values
end

study3_time = toc                                                           % Using toc to read the elapsed time from timer

figure(3)
subplot(2,1,1)                                                                  % To plot multiple plots using subplot
hold on
surfc(x,y,-f)                                                                   % Plotting surface for x vs y with function
shading interp
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('BOUNDED INPUTS with Modified Population Size ')

subplot(2,1,2)                                                                  % To plot multiple plots using subplot
plot(-f_opt)                                                                    % Plot for the optimum function
xlabel('No.of Iterations')
ylabel('Maximum Function Value')

OUTPUTS :

• Results for Study 1 -

The above output plot gives the results for unbounded input in which we get the x_optimum vs y_optimum over optimum function over the surface showing randomly populated results without the restrictions which is not appropriate. The sub plot output shows the no of iterations on x axis vs the maximum value for the function on y axis in which iterations starts from 1 to 100 and function value starts from 0.6-0.7 respectively.

• Results for Study 2 -

The above output plot gives the results for Bounded input in which we get the x_optimum vs y_optimum over optimum function over the surface showing results with the restrictions that is the upper and the lower bounds which is more accurate & better than the study 1 output to reach global maxima.The sub plot output shows the no of iterations on x axis vs the maximum value for the function on y axis in which iterations starts from 1 to 100 and function value starts in between 0.5-0.6 respectively.

• Results for Study 3 -

The above output plot gives the results for Bounded input with the modified population for ga in which we get the x_optimum vs y_optimum over optimum function over the surface showing results with the limitations that is the upper and the lower bounds which is more accurate & best than the study 2 output for global maxima.The sub plot output shows the no of iterations on x axis vs the maximum value for the function on y axis in which iterations starts from 1 to 100. Here, we get the exact global maxima on the peak after using the population size as 350 respectively.

•  Output for time taken for each case study after recording the processing time by using tic toc command -

STEPWISE EXPLANATION OF THE CODE :

• We start the program by clearing the window and previous plots by using basic commands clear all ; close all ; clc .
• Initially, we define the space or a range for the x and y co-ordinate using linspace command starting from 0 up to 0.6.
• Then, we create an array or a 2 Dimensional mesh for the search space using command meshgrid for x and y and storing it in variables X & Y.
• Here, syntax meshgrid(x,y) means to returns 2-D grid coordinates based on the coordinates contained in vectors x and 
• Next, we give the No of iterations to be followed by genetic algorithm(ga) as 100 by using variable num_case.
• Also, in another new script we are creating a function named stalagmite_Func for Input_vector in which giving the function equations and using it as stalagmite function in ga program.
• Then we are evaluating the stalagmite function using 2 for loops 1 for x and another for y and saving it as 2 Input_vectors and then calling the function stalagmite_Func and ending the loop.
• Next, we are coding for the 3 Case Studies to solve Ga problem.
• In study 1 statistical behaviour is for unbounded input where we use for loop in which we use ga inbuilt command and address the stalagmite function with 2 variables for x & y and keeping it for the optimum function. That is the syntax for it is [inputs, f_opt(i)] = ga(@stalagmite_Func,2).
• Plot using subplot for plotting multiple plots in 1. First we create the surface plot for x and y with the function (f) by using surfc command and then we main plot for x_optimum, y_optimum and optimum function(f_opt) on the surface created and next we create a 2^nd  subplot to plot the optimum function only for the no. of iterations as x & Maximum Function value as y accordingly.
• Study 2 is the statistical behaviour by giving the bounded inputs with the upper and lower bound. Almost the program for study 2 is similar to that of study 1 except the syntax is slightly changed for command ga. Thus, the syntax is

                   [inputs, f_opt(i)] = ga(@stalagmite_Func,2,[],[],[],[],[0;0],[1;1])

• Here, the above syntax defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤x ≤
• Study 3 is the bounded inputs with increasing the ga iteration thus by increasing the population. The program for study 3 is almost same as Study 2 except in ga syntax by adding the options which we had defined for the ga before as for optimumoptions with population size as 350 to get best results.
• We had also use the tic and toc command tic before for loop and toc after for loop and stored the time study 1 by toc in variable study1_time. Similarly, used tic and toc command and calculated the time for study 12 and study 3.Here, tic works with the toc function to measure elapsed time. The tic function records the current time, and the toc function uses the recorded value to calculate the elapsed time respectively.

• Errors faced while programming :

• Error faced in function code for stalagmite_Func in which in defining the f2_x equation we used * operator for exponent.

        i.e. for exp*(-4*log()… ) which is wrong.

• Steps taken to overcome the Errors Faced –

• To avoid the syntax error eliminate the multiplication operator * after exp.
• That is correct syntax is  f2_x = exp(-4*log(2)*((x-0.0667)^2)/0.64);

• Screenshots showing errors -

CONCLUSION :

Optimization is best suited to find the extreme stage either to maximize or minimize function of any real world case. Here, after performing 3 case study we finally get the global maxima in study 3 after iterating the population size respectively. Also, we had briefly undertsood the stalagmite function to optimize and the concept of GA easily by using MATLAB.

REFERENCES -

• https://en.wikipedia.org/wiki/Genetic_algorithm
• sciencedirect.com/topics/medicine-and-dentistry/genetic-algorithms