Week 4.1 - Genetic Algorithm

close all
clear all
clc

%input
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_spaces=50;

%forming 2d array
[xx, yy]=meshgrid(x,y);
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_fn(input_vector);
    end
end

%study 1-boundary for GA undefined

tic
for i=1:num_spaces
    [results, fopt(i)]=ga(@stalagmite_fn,2);
    xopt (i)=results(1);
    yopt (i)=results(2);
end
study_time1 = toc;
figure(1)
subplot (2,1,1)
surf (x,y,-f)
shading interp
hold on
plot3(xopt,yopt, -fopt, 'marker','o')
subplot (2,1,2)
plot (-fopt)
xlabel('iteration')
ylabel('function maximum')


%study 2- boundary for GA defined

tic
for i=1:num_spaces
    [results, fopt(i)] = ga(@stalagmite_fn,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt (i)=results(1);
   yopt (i)=results(2);
end
study_time2=toc;
figure(2)
subplot(2,1,1)
surf (x,y,-f)
shading interp
hold on
plot3(xopt, yopt, -fopt, 'marker','o')
subplot(2,1,2)
plot (-fopt)
xlabel('iteration')
ylabel('function maximum')

%study3- increasing initial population from 50 to 500 in boundary defined condtion for %GA

tic
options=optimoptions ('ga')
options=optimoptions (options, 'populationsize',500)
for i=1:num_spaces
    [results, fopt(i)]=ga(@stalagmite_fn, 2,[],[],[],[],[0;0], [0.6;0.6],[],[],options)
    xopt (i)=results(1)
    yopt (i)=results(2)
end
study_time3=toc;
figure(3)
subplot (2,1,1)
surf (x,y,-f)
shading interp
hold on
plot3(xopt, yopt, -fopt, 'marker','o')
subplot(2,1,2)
plot (-fopt)
xlabel('iteration')
ylabel ('function maximum')

% Time for excution of each study is obtained using the tic and toc commands

study_time1
study_time2
study_time3

Stalagmite Function

% Function to return the values for the stalagmite numerical expressions
% f(x,y)=(f1*f2*f3*f4)
% where 
% 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);
% here we are ruturing negative value of stalagmite function so as to find
% maxima as GA returns only minima

function A = stalagmite_fn(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

AIM :

Developing a program to optimise a stalagmite function for determination of its Global Maxima by applying Genetic Algorithm on to the code.

THEORY :

Mathematical optimization: Also Known mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives.

Stalagmite Function: A function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function.

Genetic Algorithms: These are techniques used to determine the best possible or optimal solution for extremely hard problems. It is inspired from Charles Darwin’s theory of evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

Phases in Genetic Algorithm:

1. Initialization of Population

The code generates 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 number of iterations performed.

2. Fitness Function

Fitness Functions are optimization functions in which 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 Selection phase is to fittest individuals and let them pass their genes to the next generation it helps in determining the best possible values in such was that chances of getting the best solution are more.

4. Crossover

This is the most significant stage of Genetic Algorithm. During crossover random point is elected while mating a pair of parents to generate offspring. Different types of crossovers include. Single Point, Multi Point and Uniform Crossovers.

5. Mutation

The genes of few new offspring are subjected to mutation with a low random probability, this indicates that some bits in bit chromosomes can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

Syntax of Genetic Algorithm In MATLAB

• x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.

• x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

• x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)

• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

• x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

• x = ga(problem) finds the minimum for problem, a structure described in problem.

• [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

• [x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

• [x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

STEPS :

1. 2D array was generated using the provided values of x and y using mesh-grid function.
2. Stalagmite Function was developed using the provided mathematical equations and the output was modified so as to obtain the maxima values.
3. 3 Case studies were generated so as to obtain an optimised solution each using the Genetic algorithm function inbuilt in MATLAB.
4. The errors during execution were rectified.
5. Graphs Corresponding to the Cases were obtained along with their execution time period.

Code Explanation:

close all

clear all

clc

%input

x=linspace(0,0.6,150);

y=linspace(0,0.6,150);

num_spaces=50;

%forming 2d array

[xx, yy]=meshgrid(x,y);

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_fn(input_vector);

end

end

This part of code is for Initializing the values of x and y by considering 150 values between 0 and 0.6, and a number of iterations as 50 also a 2D array is generated using mesh grid command. Here we are using input vector array to store input of mesh-grid and to be used as argument in function call.

%study 1-boundary for GA undefined

tic

for i=1:num_spaces

[results, fopt(i)]=ga(@stalagmite_fn,2);

xopt (i)=results(1);

yopt (i)=results(2);

end

study_time1 = toc;

figure(1)

subplot (2,1,1)

surf (x,y,-f)

shading interp

hold on

plot3(xopt,yopt, -fopt, 'marker','o')

subplot (2,1,2)

plot (-fopt)

xlabel('iteration')

ylabel('function maximum')

This is the First study conducted with the GA function having undefined boundary and 50 iteration limit. Here the tic and toc are used to find the execution time of the case.

subplot (2,1,1)

surf (x,y,-f)

shading interp

plots the Stalagmite surface for the given range of x,y and z

plot3(xopt,yopt, -fopt, 'marker','o')

subplot (2,1,2)

plots the x, y, &z values foring the corresponding points formed by GA

plot (-fopt)

xlabel('iteration')

ylabel('function maximum')

Plots the 2D graph of maxima vs iterations.

%study 2- boundary for GA defined

tic

for i=1:num_spaces

[results, fopt(i)] = ga(@stalagmite_fn,2,[],[],[],[],[0;0],[0.6;0.6]);

xopt (i)=results(1);

yopt (i)=results(2);

end

study_time2=toc;

figure(2)

subplot(2,1,1)

surf (x,y,-f)

shading interp

hold on

plot3(xopt, yopt, -fopt, 'marker','o')

subplot(2,1,2)

plot (-fopt)

xlabel('iteration')

ylabel('function maximum')

This is the Second study conducted with the GA function having

defined boundary and 50 iteration limit. Here the tic and toc are used to find the execution time of the case.

subplot (2,1,1)

surf (x,y,-f)

shading interp

plots the Stalagmite surface for the given range of x,y and z

plot3(xopt,yopt, -fopt, 'marker','o')

subplot (2,1,2)

plots the x, y, &z values foring the corresponding points formed by GA

plot (-fopt)

xlabel('iteration')

ylabel('function maximum')

Plots the 2D graph of maxima vs iterations.

%study3- increasing initial population in boundary defined condtion for GA

tic

options=optimoptions ('ga')

options=optimoptions (options, 'populationsize',500)

for i=1:num_spaces

[results, fopt(i)]=ga(@stalagmite_fn, 2,[],[],[],[],[0;0], [0.6;0.6],[],[],options)

xopt (i)=results(1);

yopt (i)=results(2);

end

study_time3=toc;

figure(3)

subplot (2,1,1)

surf (x,y,-f)

shading interp

hold on

plot3(xopt, yopt, -fopt, 'marker','o')

subplot(2,1,2)

plot (-fopt)

xlabel('iteration')

ylabel ('function maximum')

This is the third study conducted with the GA function having defined boundary and 50 iteration limit and a increased population limit. Here the tic and toc are used to find the execution time of the case.

subplot (2,1,1)

surf (x,y,-f)

shading interp

plots the Stalagmite surface for the given range of x,y and z

plot3(xopt,yopt, -fopt, 'marker','o')

subplot (2,1,2)

plots the x, y, &z values foring the corresponding points formed by GA

plot (-fopt)

xlabel('iteration')

ylabel('function maximum')

Plots the 2D graph of maxima vs iterations.

study_time1

study_time2

study_time3

this code is used to display the time take for each case to be executed.

RESULT:

The Stalagmite function was analysed and the optimization was carried out with 3 study cases and the plots were obtained.

The Case 3 with increased population size and defined boundaries for Genetic Algorithm function showed results of better accuracy but was much more time consuming. While the Case 1 showed least accuracy.

Errors:

1. Typo errors.
2. Errors due to logical mistakes

Error Resolutions:

1. Typo errors were rectified by referring to syntaxes.
2. Logical errors were rectified by using trial and error methods.

I have attached the Screenshots for your reference.

Resources:

1. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
2. https://in.mathworks.com/discovery/genetic-algorithm.html
3. https://in.mathworks.com/help/optim/ug/optimization-theory-overview.html
4. https://in.mathworks.com/help/gads/ga.html