Week 4.1 - Genetic Algorithm

Aim: To optimize the stalagmite function and find the global maxima of the function.

Theory:

A genetic algorithm is a search experiential that is stimulated by Charles Darwin’s theory of natural evolution. This algorithm reproduces the process of natural selection where the appropriate individuals are selected for reproduction in order to produce offspring of the next generation.

 The genetic algorithm is a technique for solving both constrained and unconstrained optimization problem that are based on natural selection, the process that drives biological evolution. The genetic algorithm constantly modifies the population size of individuals solutions.

Phases in genetic algorithm:-

1. Initialization of population: The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on no of iteration performed.
2. Fitness Function: It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with the fitness value of each member generated , these fitness values are used for the reproduction of the children.
3. Selection: The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more.

• Inspiration for this is from the survival of the fittest
• It should be a balance between exploration and exploitation of search space.
• GA tries to move the genotype to higher fitness in the search space.
• Too strong fitness selection bias can lead to sub-optimal solution.
• Too little fitness bias selection results in unfocused search.

4. Reproduction : Generation of offspring happen in 2 ways:

• Crossover
• Mutation

 

1. Crossover: Crossover is the most significant stage in the genetic algorithm . During crossover, a random point is selected while mating a pair of parents to generates offspring.

 

There are three type of crossover

• Single point crossover: A point on both parent chromosomes is picked randomly and designated a ‘crossover point’.
• Two-point crossover : Two crossover points are picked randomly from the parent chromosomes.
• Uniform crossover: In a uniform crossover, typically each bit is chosen from either parent with equal probability. The new offspring are added to the population.

1. Mutation : In a few new offspring formed , some of their genes can be subjected to a mutation with a low random probability. This indicates that some of the bit in the bit chromosomes can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

Syntax for GA:

[x,fval,exitflag,output,population,scores]=ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,intcon,options)

x= optimum solution

exitflag = reason ga stopped

output = information about optimization process

population = final population

scores = final scores

f = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,intcon,options)

fun = fitness function

nvars = number of variables

A,b = linear inequality constraints

Aeq,beq = linear equality constraints

lb = lower bound(limit)

ub = upper bound(limit)

nonlcon : use for nonlinear constraints

intCon = to get solution in integer.

Options = to get population size minimize with non-default options.

Body of the content

Fitness Function:

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

`f_(1,x)= [sin(5.1pix+0.5)]^6`                  `f_(1,y) =[sin(5.1piy+0.5)]^6`

 `f_(2,x) = exp[-4ln(2)((x-0.0667)^2)/0.64]`

`f_(2,y) = exp[-4ln(2)((y-0.0667)^2)/0.64]`

The above equation are used in the stalagmite function to plot the graph in the main function.

 #Functon program

% creating function to get called in main program
function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);

% witting the formula

f1_x = (sin(5.1*pi*x + 0.5)).^6;
f1_y = (sin(5.1*pi*y + 0.5)).^6;

t1 = ((x-0.0667).^2)/(0.64);
f2_x = exp(-4.*log(2)*t1);

t2 = ((y-0.0667).^2)/(0.64);
f2_y = exp(-4.*log(2)*t2);
f = -(f1_x.*f2_x.*f1_y.*f2_y);
end

• While using the function at the end as we are using the -ve sign so that the plot will be reversed as we have to find the maxima of the given function using ‘ga’.

Main Body:

• Firstly creating the mesh from the two vectors which will be acting as a search space to find the maxima of the function.
• Creating the mesh of these two vectors using the ‘mesh’ command and defining the no. of iteration as num_cases to iterate the values of the optimum values of the function.
• Now calculating the values of the fitness function at each point of the mesh grid formed .
• Now creating its surface through ‘surfc’ command which will also provide the contour of the generated sign.

 #Main Program

clear all
close all
clc
% providing the search space for the function
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[X Y] = meshgrid(x,y); % creating the metrix of 150x150 from x,y value
num_cases = 50; % number of iteration at which function will evaluate the fitness

% Creating the surface plot of the stalagmite function
for i = 1:length(X)
for j = 1:length(Y)
input_vector(1) = X(i,j);
input_vector(2) = Y(i,j);
f(i,j) = stalagmite(input_vector); % values of function in given search space
end
end

surfc(X,Y,-f); % generating the surface
shading interp % to remove the line produced by the mesh grid

#Results

1. Statistical study without boundation

• In this evaluating the optimum value of fitness function at each iteration and calculating its using the above mentioned syntax in the intro part (which gives the inputs i.e. values of x and y at which the stalagmite function is minimum ).
• The plotting it into the ‘surfc’ command and also providing the optimum value of the function that how it is varying.
• Also using the tic and toc command to evaluate the time used for optimizing the function.

#Program

% Statistical behaviour (Unbound)
tic           % calculating the study time through tic and toc command
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2);    % calculating the optimized value of the function
    xopt(i) = inputs(1);                         % at each iteration
    yopt(i) = inputs(2);
end
study_time1 =toc;    % displaying the time taken to evaluate
%ploting the graph
figure(1)
subplot(2,1,1)
surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function min value');

#Results

• From the figure as shown above it is clear that results are not that much accurate and giving a lot of vaiation in optimizing the function.

2. Statistical study with boundation

• The difference over here is in providing the upper and the lower limit in the ‘ga’ so that the search space is reduced with the upper and lower boundary.
• And then plotting it as similar to the above study.

#Program

% Statistical behaviour (bound)
tic           % calculating the study time through tic and toc command
for j = 1:num_cases
    [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);    % calculating the optimized value of the function
    xopt(j) = inputs(1);                         % at each iteration with boundation
    yopt(j) = inputs(2);
end
study_time2 =toc;    % displaying the time taken to evaluate
%ploting the graph
figure(2)
subplot(2,1,1)
surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function min value');

#Results

• It is clearly seen from the above that after providing the boundary limit the variation in the optimum value of the function has increased.

3. Statistical study with increase in population size

• In this study using the ‘optimoption’ command to increase the size of population.
• The benefits of that will be working in the large set of numbers and which will be led to increase the possibilities of finding the better fitness of the function.
• The drawback is that the time for evaluation will increase .

#Program

%Statistical study with increase in size of population
options = optimoptions('ga','populationsize',300);   % incrasing the size of population by using 
                                                    %optimoptions function
tic           % calculating the study time through tic and toc command
for k = 1:num_cases
    [inputs,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);    % calculating the optimized value of the function
    xopt(k) = inputs(1);                         % at each iteration with boundation
    yopt(k) = inputs(2);
end
study_time3 =toc;    % displaying the time taken to evaluate
%ploting the graph
figure(3)
subplot(2,1,1)
surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function min value');

#Results

• It is clearly seen in the above case that the value of the variation range has changed to a large extent.

Whole program:

clear all
close all
clc
% providing the search space for the function
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[X, Y] = meshgrid(x,y);   % creating the metrix of 150x150 from x,y value
num_cases = 50;   % number of iteration at which function will evaluate the fitness

% Creating the surface plot of the stalagmite function
for i = 1:length(X)
    for j = 1:length(Y)
        input_vector(1) = X(i,j);
        input_vector(2) = Y(i,j);
        f(i,j) = stalagmite(input_vector);  % values of function in given search space
    end
end

surfc(X,Y,-f);   % generating the surface
shading interp    % to remove the line produced by the mesh grid

% Statistical behaviour (Unbound)
tic           % calculating the study time through tic and toc command
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2);    % calculating the optimized value of the function
    xopt(i) = inputs(1);                         % at each iteration
    yopt(i) = inputs(2);
end
study_time1 =toc;    % displaying the time taken to evaluate
%ploting the graph
figure(1)
subplot(2,1,1)
surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function min value');
      
% Statistical behaviour (bound)
tic           % calculating the study time through tic and toc command
for j = 1:num_cases
    [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);    % calculating the optimized value of the function
    xopt(j) = inputs(1);                         % at each iteration with boundation
    yopt(j) = inputs(2);
end
study_time2 =toc;    % displaying the time taken to evaluate
%ploting the graph
figure(2)
subplot(2,1,1)
surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function min value');

%Statistical study with increase in size of population
options = optimoptions('ga','populationsize',300);   % incrasing the size of population by using 
                                                    %optimoptions function
tic           % calculating the study time through tic and toc command
for k = 1:num_cases
    [inputs,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);    % calculating the optimized value of the function
    xopt(k) = inputs(1);                         % at each iteration with boundation
    yopt(k) = inputs(2);
end
study_time3 =toc;    % displaying the time taken to evaluate
%ploting the graph
figure(3)
subplot(2,1,1)
surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function min value');

Output:

Unbounded

Bounded

 

 Population size

Conclusion:

‘ga’ is useful for optimizing the function but still the results are not accurate as the maximum value for the function lies at -1.

To overcome that using the given programme shown below

 #program

clear all
close all
clc
% providing the search space for the function
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[xx, yy] = meshgrid(x,y);   % creating the metrix of 150x150 from x,y value
%num_cases = 50;   % number of iteration at which function will evaluate the fitness

% Creating the surface plot of the 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(input_vector);  % values of function in given search space
    end
end

%evaluating the function
options = optimoptions('ga','PlotFcn',@gaplotbestf,'populationSize',200);
[x,fval]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],options)
xopt=x(1);
yopt = x(2);

figure(1)

surf(xx,yy,-f);
shading interp
hold on
plot3(xopt,yopt,-fval,'ro','MarkerSize',5,'MarkerFaceColor','r');

Results

The  above program will display the best value in the graph.

Another way to find the best value is shown below

• Note: ‘gaplotbestf’ which plots the best and mean score of the population at every generation. Also setting ‘gaplotstopping’ which plot the percentage of stopping criteria satisfied.
• It can be much more visualized that how the fitness is been calculated and best results is being displaced even with the decrease in size population.