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

Week 4.1 - Genetic Algorithm

AAnkit .26 Jul 2022
MATLAB

Aim - Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Theory -

Genetic Algorithm -

The genetic algorithm is a method for solving both constrained and unconstrained optimization problem that are based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the currant 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. You can apply the genetic algorithm to solve a variety of optimization problems, that are not well suited for standard optimization algorithm, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly non-linear. The genetic algorithm can address problem 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 currant population -

  • Selection rules - Select the individuals, called parents that contribute the population at the next generation.

  • Crossover rules - Combine two parents to from children for the next generation.

  • Mutation rules - Apply random changes to individual parents to from the children.

Genetic Algorithms are primarily used in optimization problems of various kinds, but they are frequently used in other application areas as well.

The areas in which Genetic Algorithm are frequently used are listed below.

  • Optimization – Genetic algorithm are most commonly used in optimization problem wherein we have to maximize or minimize a given objective function values under given set of constraints.

  • Economics – GAs are used to characterize various economic model like the cobweb model, game theory equilibrium resolution, asset pricing, etc.

  • Neutral Network – GAs are used to train neutral network, particularly recurrent neural networks.

  • Image Processing – GAs are used for various digital image processing(DIP) takes as well as dense pixel matching.

The above are same of the areas where the genetic algorithm is extensively used for optimization.

  • Fitness Function – The fitness function takes the solution as input and produces the suitability of the solution as the output. The evaluates how close the solution is to the optimal solution of the desired problem.

    The Syntax for GA in Matlab -

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

    The Syntax is explained as follows -

  • ‘x’ is the variable to store the output of the genetic algorithm.

  • ‘fun’ is the function handle to call the function.

  • ‘A’ and ‘b’ are used to represent the linear inequalities of the function, if the linear inequalities do not exist, they can be set as empty [].

  • ‘Aeq’ and ‘beq’ are used to represent the equality constraints. Similarly, if the linear equalities do not exits, they can be set as empty [].

  • ‘lb’ and ‘ub’ are used to simplify the upper and the lower bounds of the variables of the function.

  • ‘nonlcon’ represents the non-linear constraints.

  • ‘intcon’ represent the integer constraint, such that the value of the function is an integer.

  • ‘options’ used to provide the value of the default parameters used named parameters, if it is required to replace the default parameters. This is done by using the ‘optimoptions’.

  • Stalagmite Function – A stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. Most stalagmite have rounded or flattened tips.

The following function will took like this feature hance it is called the stalagmite function.

The following is the given stalagmite function for which we need to find the global maxima.

Procedure -

  • First we create function program for the equation -
function [f] = stalagmite(input_vector)

a = input_vector(1);
b = input_vector(2);

f1_x = (sin(5.1*pi*a+0.5)).^6;
f1_y = (sin(5.1*pi*b+0.5)).^6;
f2_x = exp(-4*log(2)*((a-0.0667).^2)/(0.64));
f2_y = exp(-4*log(2)*((b-0.0667).^2)/(0.64));

f = -(f1_x*f2_x*f1_y*f2_y);
end
  • The negative command is used in the program in order to invert the plot as the GA command finds only the minimum point.
  • Then we create a program for stalagmite function -
clear all
close all
clc

% Defining our serach space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_case = 50

% creating a 2Dimensional mesh
[xx,yy] = meshgrid(x,y);

% Evaluating 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);
    end
end

surfc(xx,yy,-f)
shading interp

[x,fval] = ga(@stalagmite,2)

xlabel('X axis')
ylabel('Y axis')
  • Clear all, close all and clc represent it deletes all temporary memory, closes all plots, and clears the command window and workspace.
  • we assume 'x' and 'y' values using linspace command. the uses of linspace command are that if we set lower and upper limits and the number of avalues we need it takes random values.
  • In the next step, the mest grid command is used in order to form as array of row and column values and it is stored in 'xx' and 'yy' variables.
  • Then, for 'for' loop command is used. It repeats the function for the length of 'xx' and 'yy'.
  • Then in the next steps, we call the stalagmite function as 'stalagmite(input_vector)'.
  • In the next steps, 'surfc' command is used in order to get a plot as a surface.
  • Then, 'shading interp' command is used in order to remove the grid-like structure in the plot, and color filling is done.
  • in the next step, the 'ga' command is used. In the 'ga' command, we call the stalagmite function and we need to enter the number of variables. In our problem, we have two variables 'x' and 'y', so we enter it as 2.
  • Then in the next step 'xlabel' and 'ylabel' is used in order to get a clear picture of our plot.
  • Case study 1 - Statistical Behaviour - for this program is -
% study 1 statistical behavior

tic
for i = 1:num_case
[x1,fval1(i)] = ga(@stalagmite,2);
xopt1(i) = x1(1);
yopt1(i) = x1(2);
end
study1_time = toc;
mean1 = (mean(fval1))

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt1,yopt1,-fval1,'marker','o','MarkerFaceColor','g','MarkerSize',5)
title('unbounded inputs')
xlabel('X axis')
ylabel('Y axis')
subplot(2,1,2)
plot(fval1)
xlabel('Iterations')
ylabel('function minimum')
  • In the study, we introduce the number of cases that 'ga' need to perform, and based on the mean value we need to calculate our global maximum value.
  • We define it as 'num_case = 50' (decleared in inputs) in this program. the 50 indicates that 50 times the 'ga' need to repeat and it calculate the values.
  • The 'tic' command is used in order to find out the time taken for then program complete.
  • 'For' loop command is used and the length of it set as the number of cases.
  • The 'ga; command is used as before by calling the function and the number of variable in the program.
  • The calculated 'x' and 'y' values are stored in 'xopt(i)' and 'ypot1(i)' for each study.
  • 'subplot' command is used in order to get n number of plots in the same single figure plot.
  • In the first plot, we the x,y and f as a surface like structure by using the 'surf' command.
  • The negative sign is used in the function (f) while plotting since we invert initially and we need to revert it back to its original structure.
  • Then we plot calculated maximum values as a dot- like structure by using the 'marker opting' and 'marker size'.
  • In the next steps 'title' for the is mentioned using the 'title' command.
  • Then 'subplot' command is used in order to plot in same figure window.
  • In the plot, we plot the values and the number of iterations, and the'xlabel' and 'ylabel' is mentioned.
  • In this study, we get a random values and we didn't get an exact globel maximum values and the seach space of 'ga' is also not within our search space.
  • Thus it indicates we need to have a better study method through which we get out exact global maximum value within our search space.
  • Case study 2 - Statistical Behaviour with upper and lower bound limits - For this study code are
% study 2 statistical behavior with upper and lower bounds


tic
for i = 1:num_case
[x2,fval2(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
xopt2(i) = x2(1);
yopt2(i) = x2(2);
end
study2_time = toc;
mean2 = (mean(fval2))

figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt2,yopt2,-fval2,'marker','o','MarkerFaceColor','g','MarkerSize',5)
title('bounded inputs')
xlabel('X axis')
ylabel('Y axis')
subplot(2,1,2)
plot(fval2)
xlabel('Iterations')
ylabel('function minimum')
  • From the pervious study, we inferred that the search space of the 'ga' is not within our search space so to overcome this error we use the 'bounded script method'.
  • As the name suggests, in this study we will enter the boundary and within that boundary, only the 'ga' will perform.
  • All the command used in this study are also the same as used the pervious study except the 'ga' syntax.
  • In this study, as mentioned above the limit criteria, initially we call the 'stalagmite' function and the number of variables mentioned as done earlier, and we enter the lower and upper boundary limit values.
  • In our program, the lower boundary limit is set as [0,0] and the upper boundary limit is set as [1,1].
  • After this we plot the same way as before and we get our plot.
  • Based on the output we interred that even though this study is better than our pervious study but still we didn't an exact single global maximum value.
  • Case study 3 - Increasing GA iterations - for this code are
% study 3 Increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',400);

tic
for i = 1:num_case
[x3,fval3(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
xopt3(i) = x3(1);
yopt3(i) = x3(2);
end
study3_time = toc;
mean3 = (mean(fval3))

figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt3,yopt3,-fval3,'marker','o','MarkerFaceColor','g','MarkerSize',5)
title('bounded inputs with modified population size')
xlabel('X axis')
ylabel('Y axis')
subplot(2,1,2)
plot(fval3)
xlabel('Iterations')
ylabel('function minimum')
  • All the commands used in this study are also same as used in the pervious study except the 'ga' syntax.
  • In the pervious study, we set the lower and upper boundary limits but we didn't set the initial population size for the 'ga' to perform.
  • Thus in this 'optimization' technique, we will try to set the initial population size that 'ga' needs to perform within our boundary limits.
  • Thus to set the initial population size we use the 'optimoptions' command and in that we mention the 'options, population size'.
  • After this, we plot the same way as before and we get out plot.
  • The population values is randomly increased up to which a single exact global maximum values is found out.
  • By increasing loke this we get a single exact point and the population size of 300. So we stop our program at this point.

Main code -

clear all
close all
clc

% Defining our serach space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_case = 50

% creating a 2Dimensional mesh
[xx,yy] = meshgrid(x,y);

% Evaluating 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);
    end
end

surfc(xx,yy,-f)
shading interp

[x,fval] = ga(@stalagmite,2)

xlabel('X axis')
ylabel('Y axis')

% study 1 statistical behavior

tic
for i = 1:num_case
[x1,fval1(i)] = ga(@stalagmite,2);
xopt1(i) = x1(1);
yopt1(i) = x1(2);
end
study1_time = toc;
mean1 = (mean(fval1))

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt1,yopt1,-fval1,'marker','o','MarkerFaceColor','g','MarkerSize',5)
title('unbounded inputs')
xlabel('X axis')
ylabel('Y axis')
subplot(2,1,2)
plot(fval1)
xlabel('Iterations')
ylabel('function minimum')

% study 2 statistical behavior with upper and lower bounds


tic
for i = 1:num_case
[x2,fval2(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
xopt2(i) = x2(1);
yopt2(i) = x2(2);
end
study2_time = toc;
mean2 = (mean(fval2))

figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt2,yopt2,-fval2,'marker','o','MarkerFaceColor','g','MarkerSize',5)
title('bounded inputs')
xlabel('X axis')
ylabel('Y axis')
subplot(2,1,2)
plot(fval2)
xlabel('Iterations')
ylabel('function minimum')

% study 3 Increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',400);

tic
for i = 1:num_case
[x3,fval3(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
xopt3(i) = x3(1);
yopt3(i) = x3(2);
end
study3_time = toc;
mean3 = (mean(fval3))

figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt3,yopt3,-fval3,'marker','o','MarkerFaceColor','g','MarkerSize',5)
title('bounded inputs with modified population size')
xlabel('X axis')
ylabel('Y axis')
subplot(2,1,2)
plot(fval3)
xlabel('Iterations')
ylabel('function minimum')
  • Function program
function [f] = stalagmite(input_vector)

a = input_vector(1);
b = input_vector(2);

f1_x = (sin(5.1*pi*a+0.5)).^6;
f1_y = (sin(5.1*pi*b+0.5)).^6;
f2_x = exp(-4*log(2)*((a-0.0667).^2)/(0.64));
f2_y = exp(-4*log(2)*((b-0.0667).^2)/(0.64));

f = -(f1_x*f2_x*f1_y*f2_y);
end

Error - While we creating seperate program for Study 1 then we found this error

  • This error comes while we not properly input values for the variables.
  • For this error we assigned the values and then calling the function then error goes.

Result -

1. For base code -

2. Case study 1 - Statistical Behaviour

3. Case study 2 - Statistical Behaviour with upper and lower bound limits

4 . Case study 3 - Increasing GA iterations

  • The time taken for the study, Global Maximum values and the coordinate values x and y are found out for each study and the results are shown below -

Conclusion -

  • Understand how optimization technique is used with the ga command
  • Understand the function of ga and it uses.
  • Understand how to improve our program step by step through different studies.

Referance -

  • Skill-lync help portal.
  • Matlab help centre or GA and optimization function.
  • https://mech.iitm.ac.in/nspch52.pdf
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.