BlogFor BusinessTalk to a counsellor
CoursesIIT ProgramsPlacementsLog in
BlogFor Business
Talk to a counsellor
Challenge

Week 4.1 - Genetic Algorithm

SSumeet Joshi19 May 2022
MATLAB

Aim:

To optimise the stalagamite function and find the global maxima of the function.

Objective of the project:

Explaining the concept of genetic algorithm and also explain the syntax for ga in matlab.

plot graphs for all 3 studies and for F maximu vs no. of iterations.

INTRODUCTION:

A Genetic algorithm is a search experiential that is similuted by the charles darwin's theory of natural evolution.This algorithm reproduce the process of natural selection where the appropriate individual are selected for reproduction in order to produce offspring of the next generation.

The gentic algorithm is a technique for solving both constrained and unconstrained optimisation problems that are based on the natural selection, the process that drives biological selection.The genetic algorithm constantly modifies the population size of the individual solution.

Phases in the genetic Algorithm:

initialization of the population(coding)

The code generates the random population of the defined size and from that population the codes evaluates the fitness of the member of the population according to which its formed new population based on no. of iteration performed.

1)fitness function

It is that function which we have to optimised and its optimisation is done with the help of the number of generation which have been formed by the code accordance with the fitness value of each member generated,these fitness value are used for the reproduction of the children.

2)Selection:

The idea of the selection phase is to select the fittest individuals and let themm pass their genes to the next generation. The main goal of this phase to find the region where the chances of getting the best solution are more.

inspiration for this is from the survial of the fittest.

It should be a balance between the exploration and exploitation of the search space.

GA tries to move the genotype to higher fitness in the search space.

Too strong fitness selection bias can led to sub optimal solution.

too little fitness selection bias can led to unfocused search.

3)Reproduction:

Generation of offspring happens in 2 ways

crossover

Mutation

a) crossover is the most significient stage in the genetic algorithm. during crossover, a random point is selected while mating a pair of parents to generate the offspring

There are three major tyoes if crossover

a.1)single point crossover : a point on both parents 'chromosomes is picked randomly ' and designated a 'crossover point'.

a.2)Two point crossover : Two crossover point are picked randomly from the parents chromosomes

a.3)uniform crossover : in a uniform crossover, each bit is chosen from either parents with equal probability the new offspring are added to the mutation.

2)Mutation:

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

FOW CHART:

SYNTAX FOR GA:

[xfval,exitflag,output,population,scores]=ga(func,nvars,A,b,aeq,beq,ib,ub,noncon,lntcon,option)

x = optimum solution

exitflag = reason ga stopped

output = information about the optimisation process

population = final population

scores = final scores

f = ga(fun,nvars,A,b,[],ib,ub,noncon,lntcon,options)

fun = fitness function

nvars = no. of variables

A,B = linear inequality constraints

aeq,beq = liner equality constraints

lb = lower bound(limits)

ub = upper bound(limits)

nonlcon = use of non linear constraints

intCon = to get solution in integer

options = to set population size minimize with the non default options

Body of the content:

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

function [f] = stalagmite(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;

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 we are creating the mesh from the two vectors which will be acting as a search space to find the maxima of the given function.
  • creating the mesh of these two vector using the mesh command and defining the number of iterations 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 the mesh grid formed.
  • now creating its surface through surf command which will also provide the counter of the generated surface.
  • while using the surf and applying the negative sign to the function will generate the surface upside down which will be quite good to get the maxima of the function, as it will provie the positive value for the maxima using the negative sign.
clear all
close all 
clc

%providing the space search for the function 

x = linspace(0, 0.6, 150);
y = linspace(0, 0.6, 150);
[X,Y] = meshgrid(x,y);

%number of iteration for which the function will evaluate the fitness 
num_cases = 50;

%creating the surface plot of stalagmite function 

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

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

The plot generated is shown below:

statistical study without boundation:

In this evaluating the optimum value of fitness function at each iteration and calculating it using the above mentioned syntax in the intro part (which gives the value of inputs of x and y at which the stalagmite function is minimum

Then plotting it into the surf command and also providing the optimum values of the function that how it is varying.

And also using the tic and toc command to evaluate the time used for optimising the function.

%statistical behaviour (unbounded)
%calculating the study time through tic and toc command
tic 
for i = num_cases
    [inputs,fopt(i)]= ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);

end
study1_time = toc


%plotting the graph 
figure(2)

subplot(2,1,1)

surfc(x,y,-f);
hold on 
shading interp
plot3(xopt,yopt,-fopt,'o','markersize',5,'markerfacecolor','r')
xlabel('x')

ylabel('y')
grid on 
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum value')

Results:-

from the figure as shown above it is clear that the results are not that much accurate and giving a lot of variation in optimising the function.

STATISTICAL STUDY WITH BOUNDATION

The difference over here is in providing the upper and lower limit in the GA so that the search space is reduced with the lower and upper boundry and plotting it as similar to the above study. 

%statistical behaviour bounded 
%calculating the study time through tic and toc command 
tic
for j = num_cases
    %calculating the optimised value of the function at each iteration with
    %boundation
    [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(j) = inputs(1);
    yopt(j) = inputs(2);

end

study2_time = toc

%plotting
figure(3)

subplot(2,1,1)
hold on 
surfc(X,Y,-f)
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('iteration')
ylabel('function maximum value')

Results:-

It is clearly seen from the above that providing the boundary limits the variation in the optimum value of the function has reduced/

statistical study with increase in size of population:-

  • In this study using the 'optimoptions' command to increase the size of popultion.
  • The benifit of that will be it will be working on 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.
%modifying the number of population 
options= optimoptions('ga','PopulationSize',500)

tic
for k = 1:num_cases

    [inputs,fopt(k)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
    xopt(k)= inputs(1);
    yopt(k)= inputs(2);

end
study3_time = toc

%plotting
figure(4)

subplot(2,1,1)
hold on 
surfc(X,Y,-f)
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('iteration')
ylabel('function maximum value')

Results

It is clearly seen in the above case thst the value of the variation rabge has changed to a large extent.

NOW THE WHOLE PROGRAMMA AT ONCE:

clear all
close all 
clc

%providing the space search for the function 

x = linspace(0, 0.6, 150);
y = linspace(0, 0.6, 150);
[X,Y] = meshgrid(x,y);

%number of iteration for which the function will evaluate the fitness 
num_cases = 50;

%creating the surface plot of stalagmite function 

for i = 1:length(X)
    for j = 1:length(Y)
        input_vector(1) = X(i,j);
        input_vector(2) = Y(i,j);
        %values of function in given search space 
        f(i,j) = stalagmite(input_vector);
    end 
end 
figure(1)
%generating the surface 
surfc(X,Y,-f);
%to remove the lines created by the mesh grid
shading interp
xlabel('x value')
ylabel('y value')
title('stalagmite_function')

%statistical behaviour (unbounded)
%calculating the study time through tic and toc command
tic 
for i = num_cases
    [inputs,fopt(i)]= ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);

end
study1_time = toc


%plotting the graph 
figure(2)

subplot(2,1,1)

surfc(x,y,-f);
hold on 
shading interp
plot3(xopt,yopt,-fopt,'o','markersize',5,'markerfacecolor','r')
xlabel('x')
ylabel('y')
grid on 
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function min value')

%statistical behaviour bounded 
%calculating the study time through tic and toc command 
tic
for j = num_cases
    %calculating the optimised value of the function at each iteration with
    %boundation
    [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(j) = inputs(1);
    yopt(j) = inputs(2);

end

study2_time = toc

%plotting
figure(3)

subplot(2,1,1)
hold on 
surfc(X,Y,-f)
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('iteration')
ylabel('function maximum value')

%modifying the number of population 
options= optimoptions('ga','PopulationSize',500)

tic
for k = 1:num_cases

    [inputs,fopt(k)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
    xopt(k)= inputs(1);
    yopt(k)= inputs(2);

end
study3_time = toc

%plotting
figure(4)

subplot(2,1,1)
hold on 
surfc(X,Y,-f)
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('iteration')
ylabel('function maximum value')

OUTPUTS:-

CONCLUSION:-

ga is useful for optimising the function but still resukts are not accurate as the maximum value for the function lies at -1

to overcome that using the given programme shown below 

clear all
close all 
clc

%providing the space search for the function 

x = linspace(0, 0.6, 150);
y = linspace(0, 0.6, 150);
[X,Y] = meshgrid(x,y);

%number of iteration for which the function will evaluate the fitness 
num_cases = 50;

%creating the surface plot of stalagmite function 

for i = 1:length(X)
    for j = 1:length(Y)
        input_vector(1) = X(i,j);
        input_vector(2) = Y(i,j);
        %values of function in given search space 
        f(i,j) = stalagmite(input_vector);
    end 
end 
%evaluating the function
options= optimoptions('ga','PopulationSize',200)

tic
for k = 1:num_cases

    [inputs,fopt(k)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
    xopt(k)= inputs(1);
    yopt(k)= inputs(2);

end
study3_time = toc

%plotting
figure(5)

subplot(2,1,1)
hold on 
surfc(X,Y,-f)
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('iteration')
ylabel('function maximum value')

output:-

The above programm will display the best value in the graph

Your portfolio, next

Ship work like this
in your own course.

Talk to a career counsellor

Free 20-minute call. We'll map the right course to where you want to work.

By submitting you agree to our Terms and Privacy Policy.

Talk to a career counsellor

Free 20-minute call. We'll map the right course to where you want to work.

By submitting you agree to our Terms and Privacy Policy.