Genetic Algorithm

AIM:

To write a code to calculate the Global Maxima of a Stalagmite function using MATLAB

THEORY:

Genetic Algorithm is the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

There are six steps in a Genetic Algorithm

Initial population – The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.

Fitness function – The fitness function determines how fit an individual is. It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Selection – The idea of selection step is to select the fittest individuals and let them pass their genes to the next generation.

Crossover – Crossover is the most significant step in a genetic algorithm. For each air of parents to be mated, a crossover point is chosen at random from within the genes.

Mutation – In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Termination – The algorithm terminates if the population has converged. Then it is said that the genetic algorithm has provided a set of solutions to our problem.

Algorithm working sequence:

The algorithm begins by creating a random initial population.

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:

• Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
• Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
• Selects members, called parents, based on their expectation.
• Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passes to the next population.
• 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.
• Replaces the current population with the children to form the next generation.

The algorithm stops when one of the stopping criteria is met.

INPUT FUNCTION:

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

Where, `f_(1,x)=[sin⁡(5.1πx+0.5) ]^6 ; f_(2,y)=[sin⁡(5.1πy+0.5) ]^6 ; f_(1,x)=exp⁡[-(4 ln⁡(2) (x-0.0667)^2)/0.64] ; f_(2,y)=exp⁡[-(4 ln⁡(2) (x-0.0667)^2)/0.64]`

PROCEDURE:

FOR MAIN CODE

• Start programming in MATLAB with these three commands, as all the previous calculations are erased. “clear” this command clears all the data stored in the workspace previously. “close all” this command closes all the previous figures and plots. “clc” this command clears the command window.
• Now using the “linspace” command x and y variables are defined ranging from 0 to 0.6 in 150 elements.
• Now using the “meshgrid” command a 2 dimensional mesh plane is generated for the code to run properly.
• Now for evaluating the stalagmite function two “for” loops are used, the values for two input variables are given by the 2 dimensional mesh plane generated with the help of “meshgrid” command.

• Now starting with the first study that is ‘unbounded statistical behavior’. Here for defining the number of iterations a variable “num_cases” is used and is set to 50. For determining the time taken by then code to evaluate “tic” and “toc” command is used.
• The format of “ga” (genetic algorithm) used in this case is “ [inputs , fopt] = ga (fun , nvars) “. Here “inputs” represents the values of the parameters x and y for which the function has the least value (fopt), “fun” is the function to be optimized, here it is a Stalagmite function, “nvars” is the number of input variables, in this case its two, “input_value(1)” and “input_value(2)”.
• Now for plotting the graphs, “figure” command is used for a new figure window, “subplot” is used for dividing the window in parts, and here it divides the figure window in two parts. In the first half two graphs are plotted in a single graph using the “hold on” command, “surfc” command is used which plots a surface graph and the other graph is 3 dimensional line plot for this the command used is “plot3”. X and Y label is given along with the title. Now in the second half a 1D plot is generated of values stored in “fopt” using the “plot” command and then label the x-axis and y-axis.

• Now for staring with the second study ‘statistical behavior with upper and lower bound’. Here for defining the number of iterations a variable “num_cases” is used and is set to 50. For determining the time taken by then code to evaluate “tic” and “toc” command is used.
• The format of “ga” (genetic algorithm) used in this case is “ [inputs , fopt] = ga (fun,nvars,A,b,Aeq,beq,lb,ub) “. Here “inputs” represents the values of the parameters x and y for which the function has the least value (fopt), “fun” is the function to be optimized, here it is a Stalagmite function, “nvars” is the number of input variables, in this case its two, “input_value(1)” and “input_value(2)”, “A” is the linear inequality constraints : real matrix, if there are none, then [], “b” is the linear inequality constraints : real vector, if there are none, then [], “Aeq” is the linear inequality constraints : real matrix, if there are none, then [], “beq” is the linear inequality constraints : real vector, if there are none, then [], “lb” is the lower bounds, specified as a real vector or array, “ub” is the upper bounds, specified as a real vector ore array.
• Now for plotting the graphs, “figure” command is used for a new figure window, “subplot” is used for dividing the window in parts, and here it divides the figure window in two parts. In the first half two graphs are plotted in a single graph using the “hold on” command, “surfc” command is used which plots a surface graph and the other graph is 3 dimensional line plot for this the command used is “plot3”. X and Y label is given along with the title. Now in the second half a 1D plot is generated of values stored in “fopt” using the “plot” command and then label the x-axis and y-axis

• Now for staring with the second study ‘statistical behavior with increased population size’. Here for defining the number of iterations a variable “num_cases” is used and is set to 50. For determining the time taken by then code to evaluate “tic” and “toc” command is used.
• The format of “ga” (genetic algorithm) used in this case is “ [inputs,fopt]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options) “. Here inputs, fopt, fun, nvars, A, b, Aeq, beq, lb and ub are same as mentioned as above, “nonlcon” : nonlinear constraints, specified as afunction handle or function name, if there are none, then[], “IntCon” : integer variables, specified as a vector of positive integers, if there are none, then [], and “options” : optimization options, specified as the output of optimizations or a structure.
• Now for plotting the graphs, “figure” command is used for a new figure window, “subplot” is used for dividing the window in parts, and here it divides the figure window in two parts. In the first half two graphs are plotted in a single graph using the “hold on” command, “surfc” command is used which plots a surface graph and the other graph is 3 dimensional line plot for this the command used is “plot3”. X and Y label is given along with the title. Now in the second half a 1D plot is generated of values stored in “fopt” using the “plot” command and then label the x-axis and y-axis
• Now for printing the data on the command window “fprintf” command is used.

FOR FUNCTION CODE

• For the function code the function is created and its input vector is specified.
• Then all the four equations are written with the inputs from the meshgrid
• Now for maximizing the function a negative sign is used.

CODE:

FUNCTION CODE

function [f] = stalagmite(input_value)
f_1_x = (sin(5.1*pi*input_value(1)+0.5))^6;
f_1_y = (sin(5.1*pi*input_value(2)+0.5))^6;
f_2_x = exp(-(4*log(2)*((input_value(1)-0.0667)^2))/(0.64));
f_2_y = exp(-(4*log(2)*((input_value(2)-0.0667)^2))/(0.64));
 
f = -(f_1_x*f_1_y*f_2_x*f_2_y); % -ve sign for maximising the function
end

MAIN CODE

% genetic algorithm to calculate the global maxima of stalagmite function
 
clear ; close all ; clc
 
x = linspace(0,0.6,150);
y = linspace(0,0.6,150); 
num_cases=50;            % number of iterations
 
% creating a 2D mesh 
[xx, yy] = meshgrid(x,y);
 
% evaluating the stalagmite function
for i=1:length(xx)
    for j = 1:length(yy)
       input_value(1) = xx(i,j);
       input_value(2) = yy(i,j);
       f(i,j) = stalagmite(input_value); % function is called
    end
end
 
% Study 1 - unbounded statistical behavior
tic 
for i=1:num_cases
    [inputs1,fopt1(i)] = ga(@stalagmite,2);  % genetic algorithm is used, providing number of variables
    xopt(i) = inputs1(1);
    yopt(i) = inputs1(2);
end
study_time1=toc;
% plotting
figure(1)
subplot(2,1,1)
hold on 
surfc(xx,yy,-f)
xlabel('x-value')
ylabel('y-value')
zlabel('Function Value')
shading interp   % to remove the grid lines
plot3(xopt,yopt,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Statistical Behavior')
subplot(2,1,2)
plot(-fopt1)
xlabel('Iterations')
ylabel('Function Maximum')
 
% Study 2 - statistical behavior with upper and lower bound
tic;
for i = 1:num_cases
    [inputs2,fopt2(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs2(1);
    yopt(i)=inputs2(2);
end
study_time2=toc;
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x-label')
ylabel('y-value')
zlabel('Function Value')
shading interp
plot3(xopt,yopt,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behavior')
subplot(2,1,2)
plot(-fopt2)
xlabel('Iterations')
ylabel('Function Maximum')
 
% Study 3 - statistical behavior with increased GA population size
options = optimoptions('ga');
options = optimoptions(options,'populationsize',400);
tic
for i=1:num_cases
   [inputs3, fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
   xopt(i)=inputs3(1);
   yopt(i)=inputs3(2);
end
study_time3=toc;
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel('x-value')
ylabel('y-value')
zlabel('Function Value')
shading interp 
plot3(xopt,yopt,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behavior with Increased Population Size')
subplot(2,1,2)
plot(-fopt3)
xlabel('Iterations')
ylabel('Funtion Maximum')
 
Total_Time = study_time1+study_time2+study_time3;
 
fprintf ('Study 1 - Unbounded Statistical Behavior \n \n')
fprintf ('The time taken for the study 1 is : %f \n',study_time1)
fprintf ('The co-ordinates of x and y for the Global Maxima of the function are : %f,%f \n \n',inputs1(1),inputs1(2))
 
fprintf ('Study 2 - Bounded Statistical Behavior \n \n')
fprintf ('The time taken for the study 2 is : %f \n',study_time2)
fprintf ('The co-ordinates of x and y for the Global Maxima of the function are : %f,%f \n \n',inputs2(1),inputs2(2))
 
fprintf ('Study 3 - Bounded Statistical Behavior with Increased Population Size \n \n')
fprintf ('The time taken for the study 3 is : %f \n',study_time3)
fprintf ('The co-ordinates of x and y for the Global Maxima of the function are : %f,%f \n \n',inputs3(1),inputs3(2))
 
fprintf ('The total time taken to complete the study is : %f \n',Total_Time)

RESULTS:

FOR STUDY 1

FOR STUDY 2

FOR STUDY 3

COMMAND WINDOW

CONCLUSIONS:

We can see that after providing upper – lower bounds and options, it seems that value of co-ordinates x, y converges to only one value, the co-ordinates are x = 0.06683 and y = 0.06683. The graph shows that the Global Maxima is nearly 1 for the given stalagmite function.