Week 4 - Genetic Algorithm
To study about Genetic Algorithm and to calculate the ecumenical maxima of stalagmite function utilizing the Genetic Algorithm in MATLAB.
- Write code in MATLAB to optimize the stalagmite function and find the global
maxima of the function. - Clearly explain the concept of genetic algorithm in your own words and also explain the
syntax for ga in MATLAB. - Make sure that code gives the same output, even if it is made to run several times.
Plot graphs for all 3 studies and for F maximum vs no. of iterations. Title and axes labels are a must, legends could be shown if necessary.
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 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. We 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-predicated, optimization algorithm in two main ways, as summarized in the following table.
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.
Stalagmite Function:
- It is a mathematical model that helps to generate local minima and maxima.
- It is a three-dimensional function and the way the function is designed is that it has a lot of local maxima or minima and one global maxima or minima.
- The name stalagmite is actually a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings.
Syntax for GA:
The ‘ga’ syntax in Matlab is used to find the minimum of a function using a genetic algorithm.
There are several ways to define the ‘ga’ function depending on the problem being solved. The syntax used for this study is shown below.
MATLAB Program:
Stalagmite Function:
function [f] = stalagmite_func(input_vector)
x = input_vector(1);
y = input_vector(2);
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);
endGenetic Algorithm for Stalagmite function:
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);
% Evaluating 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_func(input_vector);
end
end
tic
% Case 1 - Statistical Behaviour
for k = 1:n
[inputs1 , fopt1(k)] = ga(@stalagmite_func, 2);
xopt1(k) = inputs1(1);
yopt1(k) = inputs1(2);
end
study1_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt1,yopt1,-fopt1,'marker','o','markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Statistical Behaviour')
figure(2)
plot(-fopt1)
xlabel('Iterations')
ylabel('fopt')
title('Statistical Behaviour')
% Case 2 - Statistical Behaviour - with upper and lower bound
for k = 1:n
[inputs2 , fopt2(k)] = ga(@stalagmite_func, 2,[],[],[],[],[0;0],[1;1]);
xopt2(k) = inputs2(1);
yopt2(k) = inputs2(2);
end
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Statistical Behaviour - with upper and lower bound')
figure(4)
plot(-fopt2)
xlabel('Iterations')
ylabel('fopt')
title('Statistical Behaviour - with upper and lower bound')
% Case 3 - Statistical Behaviour - with increasing GA iterations
options = optimoptions('ga')
options = optimoptions(options,'populationsize',300)
for k = 1:n
[inputs3 , fopt3(k)] = ga(@stalagmite_func, 2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt3(k) = inputs3(1);
yopt3(k) = inputs3(2);
end
figure(5)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
title('Statistical Behaviour - with increasing GA iterations')
figure(6)
plot(-fopt3)
xlabel('Iterations')
ylabel('fopt')
title('Statistical Behaviour - with increasing GA iterations')Steps:
1) Start the program with clear all , close all and clc commands
2) First, we have to write a program for the Stalagmite function. Solving the Genetic algorithm for stalagmite function gives us a minimum value of the 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 minima, i.e. maxima.
3)Now we require to define the search space for finding the values of x & y in the stalagmite function. The search space is opted to be between 0 to 0.6 with 150 intervals. For this we have utilized \'linspace()\'. Genetic Algorithm can take no. of iterations each time we run the code giving different values each time. To preserve 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. These no of iterations is given by \'n=50\'.
4) As \'linspace()\' engenders the series of nos, x & y will be the column vector. As input to the stalagmite function, we require to convert the column vector to a row vector. The first step of this conversion is to engender the \'meshgrid(x,y)\'. Next, we utilize \'for\' loop for conversion.
5) The next step is to obtain the results for 3 cases of the genetic algorithm in Matlab. In the first case, maximum value of the function is found out with no restrictions, no bounds, and no limits.Genetic algorithm is free to choose the population then reproduce and mutate.
6) To get the same value each time we run the program, we need to restrict the program within specific bounds namely upper bound and lower bound. The whole procedure for programming this case the same as that of the previous one, exception being for GA.
7) Even the results from the bounded cases are not the same every time the program terminates.Hence we now need to increase GA iterations. We can raise it to any value, we have chosen it as 300. In this case, syntax for GA is different than the previous case. GA has to give this population size via an option.
8) Results for this case will be just one value of function which does not deviate with no of
iterations.
Results:
Study 1: Statistical Behaviour
- In the above result, the red dot shows no. of points or coordinates of x,y under
consideration for each iteration. Large no. of red dots shows values of coordinates of
x,y varies each time iteration runs. - Above plot of fopt vs iterations shows optimum value of function, fopt varies each time iteration runs. It also shows large variations in fopt values of each iteration.
The large variations are result of not providing any bound to the function
Study 2: Statistical Behaviour with upper and lower bound
- The above result shows coordinates of x,y are converging that of the previous case. No.
of red dots are less showing values of x & y are not varying much as in the previous
case. This is the result of providing upper and lower bounds to the function. - As bounds are provided, the value of function varies only in between prescribed limit i.e, 0 to 1. This reduces variation in function value with each iteration.
Study 3: Statistical Behaviour with increasing GA iterations
- After providing upper-lower bounds and options, it seems that value of co-ordinates x,y
coverges to only one value for each iteration. Values of x = 0.0668 & y = 0.0668. - The Above graph shows that variations in values of a function are very low than that of
other cases. The value of fopt comes out to be nearly 1.
Validation: - Results obtained using the Optimization tool in Matlab. We have validated the results for 3rd case only.
Errors:
No complicated errors occurred while running the MATLAB program.
Referance: