Week 4.1 - Genetic Algorithm

OPTIMIZATION OF A STALGAMITE FUNCTION AND TO FIND GLOBAL MAXIMA OF THE FUNCTION USING GENETIC ALGORITHM WHICH IS EXECUTED IN MATLAB.

AIM:

1. To explain the concepts of Genetic-Algorithm and the syntax of GA used in Matlab.
2. To Write a code to optimize the stalagmite function
3. To Find the global maxima of the function.
4. To make sure that the code gives the same output even if it is made to run several times.

To plot graphs for 3 studies: statistical behavior of Genetic Algorithm

study-2:finding global maxima using lower bound and upper bound

1. and for F maximum vs no. of iterations.

Concepts to know:

1. what is optimization?
2. what are the techniques?
3. what is a Genetic Algorithm(GA)?
4. how does GA work?

• Optimization is a decision-making process that helps to find the best results under a set of prioritized criteria or constraints. It is a procedure that is executed repeatedly by comparing various solutions until an optimal/satisfactory solution is found.

example: Let us consider designing a simply supported beam to withstand a load of 1 tonne, in such a case we need to consider the following parameters = Length, breadth, Width, factory of safety, weight, and stress-induced. Hence optimization helps us get the best values for length, breadth, and width of the beam and that the factor of safety, material consumed and stress-induced are within the limits.

• there are two major techniques involved and they are :

1. deterministic method: in this technique, the output of the model counts on the initial conditions and parameters.
2. Stochastic method: in this technique, the model possesses some built-in randomness. this approach is a probabilistic approach that is gaining popularity over the deterministic method.

The Genetic Algorithm is the Optimization algorithm being used

• What is Genetic-Algorithm(GA)?

1. As shown in the above flowchart, we need to choose an optimization algorithm. Genetic-Algorithm is one of the optimization processes which is a search-based optimization technique based on the principles of genetic and natural selection. it is frequently used to find optimal or near-optimal solutions.
2. It is frequently used to solve optimization problems in research and machine learning

• How does GA work?

It starts with population initialization, which is a number of sample data points taken to perform genetic Algorithm operation, these data points undergo 3 steps:

1. Selection: in this step, the parents are selected from the sample data points and the main objective is to select highly fit individuals.
2. Cross-over: It is the process of taking two parent solutions and producing an offspring (child) from them. i.e ( where a set of genes are taken from Parent A and Parent B and combined together in order to produce a Child).
3. Mutation: Mutation is carried out to maintain genetic diversity from one generation of the population to another. if Mutation does not take place. The chromosomes become too similar to each other and convergence takes place soon and this results in local minima

These 3 steps are repeated iteratively to produce a new offspring by replacing the parent until an optimal solution is found.

Aim of the Program

Reference:https://skill-lync.com/knowledgebase/genetic-algorithm-explained

SYNTAX OF GA:

Used to find a minimum of a function.

1. problem description:

• [nvars]=Number of design variables;
• [A] =A matrix for linear inequality constraints;
• [B]=b vector for linear inequality constraints;
• [Aeq]=Aeq matrix for linear equality constraints;
• [Beq]=beq vector for linear equality constraints;
• [lb] =Lower bound on x;
• [ub] =Upper bound on x

II.Syntax used:

• x = ga(fun,nvars)
• x = ga(fun,nvars,A,b)
• x = ga(fun,nvars,A,b,Aeq,beq)
• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
• x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)
• x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
• [x,fval] = ga(___)
• [x,fval,exitflag,output] = ga(___)
• [x,fval,exitflag,output,population,scores] = ga(___)

III.Stopping criteria of ga:

• ga stops when the maximum number of generations is reached; by default this number is 100 times the number of variables.
• ga also detects if there is no change in the best fitness value for some time given in seconds(stall time limit), or for some number of generations , maximum stall generations.
• when it reaches maximum time limit in seconds.

Modify the stopping criteria to increase the maximum number of generations to 300 and the maximum stall generations to 100.

Reference:https://in.mathworks.com/help/gads/ga.html#mw_5430547e-4111-4753-a80d-727f85b8f63e

____________________________________________________________________________________________________________________________________________________________________________________________________________________

Program:

%stalagmite function

function A=stalagmite_f(input_vector)
x=input_vector(1);
y=input_vector(2);
f1=(sin(5.1*pi*x+0.5)).^6;
f2=exp(-4*log(2)*((x-0.0667).^2/0.64));
f3=(sin(5.1*pi*y+0.5)).^6;
f4=exp(-4*log(2)*((y-0.0667).^2/0.64));
A=-(f1*f2*f3*f4);
end

main code:

study1: statistical behavior of Genetic Algorithm

clear all 
close all 
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx, yy]=meshgrid(x,y);
%evaluating the stalagmite func
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_f(input_vector);
    end
end
%statistical behavior of Genetic Algorithm
nums=50;
tic
for i=1:nums
[inputs,fopt(i)]=ga(@stalagmite_f,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study1_time=toc;
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
xlabel('x axis')
ylabel('y axis')
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('statistical behaviour of GA')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')​

conclusion:

gets all maximum values that ga is trying to predict. and iterations of values is between 0 to 1.

study-2:finding global maxima using lower bound and upper bound

clear all
close all
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
%evaluating stalgamite function
for i=1:length(x)
for j=1:length(y)
input_vector(1)=xx(i,j);
input_vector(2)=yy(i,j);
f(i,j)=stalagmite_f(input_vector);
end
end

%finding global maxima using lower bound and upper bound
nums=50;
tic
for i=1:nums
[inputs,fopt(i)]=ga(@stalagmite_f,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study2_time=toc;

figure(1)
subplot(2,1,1)
surfc(x,y,-f)
xlabel('x axis')
ylabel('y axis')
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('finding global maxima using lower bound and upper bound')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')

Explanation:

• creating x and y input arrays. x=linspace(0,0.6,150);y=linspace(0,0.6,150);
• meshing both x and y variables to get equal rows and columns at xx and yy. [xx,yy]=meshgrid(x,y);
• giving parameter as number of cases (nums=50) meaning I'm going to run the genetic-algorithm 50 times
• evaluating the stalagmite function using 'for loop

For study 2:

• I'm passing the "tic; toc" command to note the time to execute the program.
• Next, pass in the ga (call the function, give inputs of [nvars], [A] A matrix for linear inequality constraints, [B] B matrix for linear inequality constraints,[Aeq] Aeq matrix for linear equality constraints,[Beq] Beq matrix for linear equality constraints and finally mention the lower bound values [0;0], and upper bound values [0.6;0.6]).
• Then I'm storing the x and y values (xopt, yopt) and also the optimum value that the function predicts(fopt)
• Next, open a figure window and use the plot3 command in order to get multiple plots inside the same figure window.
• first create the surface of the stalagmite function =surfc(x,y,-f); then use plot3 command to plot (xopt,yopt,-fopt) which helps us visualize how the algorithm performs over the 50 studies.
• Then create 2nd subplot and directly plot the optimum value that the function predicts with respect to the total iteration(50).

conclusion:

we get a clear and a much better maximum optimal values when we use lower and upper bounds and the iteration also seems to be much better when compared to statistical behaviour iteration with a value of range '1 to 0.7'

study-3:increasing the initial population size to find the global maxima

clear all 
close all 
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx, yy]=meshgrid(x,y);
%evaluating the stalagmite func
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_f(input_vector);
    end
end
%increasing the initial population size to find the global maxima:
options=optimoptions('ga');
options=optimoptions(options,'populationsize',250);%options =optimoptions(SolverName,Name,Value) 
nums=50;
tic
for i=1:nums
[inputs,fopt(i),exitflag,output,population,scores]=ga(@stalagmite_f,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);          %x = ga(fun,nvars,A,b,[Aeq],[Beq],lb,ub,nonlcon,IntCon,options)
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time=toc
subplot(2,1,1)
surfc(x,y,-f)
xlabel('x axis')
ylabel('y axis')
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')

Explanation:

• creating x and y input arrays. x=linspace(0,0.6,150);y=linspace(0,0.6,150);
• meshing both x and y variables to get equal rows and columns at xx and yy. [xx,yy]=meshgrid(x,y);
• giving parameter as number of cases (nums=50) meaning I'm going to run the genetic-algorithm 50 times
• evaluating the stalagmite function using 'for loop'

for study 3:

• first increase the initial population size by using options = optimoptions(SolverName, Name, Value) returns options with the named parameters altered with the specified values.
• Next passing the "tic; toc" command to note the time to execute the program.
• Next, pass in the ga (call the function, give inputs of [nvars], [A], [B], [Aeq],[Beq], lower bound values [0;0], upper bound values [0.6;0.6], non-linear constraints[] and the optimization options);
• Then I'm storing the x and y values (xopt, yopt) and also the optimum value that the function predicts(fopt).
• Next, open a figure window and use the plot3 command in order to get multiple plots inside the same figure window.
• first create the surface of the stalagmite function =surfc(x,y,-f); then use plot3 command to plot (xopt,yopt,-fopt) which helps us visualize how the algorithm performs over the 50 studies.
• Then create 2nd subplot and directly plot the optimum value that the function predicts with respect to the total iteration(50).

conclusion:

By increasing the syntax constraints and population size we can make sure that the code gives the same output even if it is made to run several times. we get the best optimal value / the global maximum.

________________________________________________________________________________________________________________________________________________________________________________________________