Week 4 - Genetic Algorithm

Genetic Algorithm:

Genetic Algorithm (‘ga’) is an optimization process which uses natural selection that mimics biological evolution. The algorithm repeatedly modifies a set of population by randomly selecting individuals from the current population and use them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

How genetic Algorithm Works:

1. The algorithm begins by creating a random initial population.
2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
   1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
   2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
   3. Selects members, called parents, based on their expectation.
   4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
   5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
   6. Replaces the current population with the children to form the next generation.

Syntax:

fval = ga(fun,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,intcon,options)

where,

‘fval’ is the function value returned by the genetic algorithm

‘fun’ is the fitness function for which we need the minimum value

‘nvars’ is the number of variables in the fitness function

‘A’ and ‘B’ are the linear equalities constraint such that A*x ≤ b

‘Aeq’ and ‘Beq’ are the equality constraint such that Aeq*x = b

‘lb’ is the lower bound for genetic algorithm

‘ub’ is the upper bound for the genetic algorithm

‘nonlcon’ is used to set non-linear constraints

‘intcon’ is used to set integer constraints

‘options’ is used to change the MATLAB’s default GA functioning

If we don’t want to use a specific input variable in the ‘ga’ algorithm such as Aeq and Beq we simply put [] in their place.

For eg: fval = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,intcon,options)

Similarly we can do this for other input variables as well.

Stalagmite function equations provided:

For simplification let,

f(x,y) = xy

Therefore, xy = a*b*c*d

Stalagmite Function Code:

%Stalagmite function which needs to be optimized
function [xy] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
a = (sin(5.1*pi*x + 0.5))^6; %f(1,x)
b = (sin(5.1*pi*y + 0.5))^6; %f(1,y)
c = exp(-4*log(2)*(((x-0.0667)^2)/0.64)); %f(2,x)
d = exp(-4*log(2)*(((y-0.0667)^2)/0.64)); %f(2,y)
xy = a*b*c*d; %f(x,y);
xy = 1/(1+xy);
end

Code for optimizing stalagmite function and find global maxima of the function:

Since Genetic algorithm chooses a random path and then calculates the probability of finding minimum along that path and then decides to change the path or not, it usually gives us local minimum value of any function but we can use it to find global maximum by adding a negative sign before calling the function and also bounding the lower and upper limits towards the known region of global maxima.

clear all
close all
clc
 
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
%Creating a 2Dimensional Mesh
[xx, yy] = meshgrid(x,y);
 
num_case = 150;
 
%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
 
tic
for i =1:num_case
[inputs,fval(i)] = ga(@stalagmite,2);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
time_taken = toc; %Used to Calculate Time taken since ‘tic’ was called and end when it reaches toc (Stopwatch)
 
%Plotting
figure(1)
subplot(2,1,1)
hold on
surf(xx,yy,f) %Creating a surface plot
shading interp %Used to color the surface plot with varying color
xlabel('X')
ylabel('Y')
grid on
plot3(x_opt,y_opt,fval,'marker','o','markersize',5,'markerFacecolor','k'); %path plotting
title('Unbounded Inputs');
subplot(2,1,2)
plot(fval); %Iteration Plotting
xlabel('Iterations');
ylabel('Function Maximum');
grid on

Unbounded Inputs Output:

Time Taken: 6.4689 sec

Now with Bounded Inputs:

clear all
close all
clc
 
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
%Creating a 2Dimensional Mesh
[xx, yy] = meshgrid(x,y);
 
num_case = 150;
 
%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
 
tic
for i =1:num_case
[inputs,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
time_taken = toc;
 
%Plotting
figure(1)
subplot(2,1,1)
hold on
surf(xx,yy,f)
shading interp
xlabel('X')
ylabel('Y')
grid on
plot3(x_opt,y_opt,fval,'marker','o','markersize',5,'markerFacecolor','k');
title('Bounded Inputs');
subplot(2,1,2)
plot(fval);
xlabel('Iterations');
ylabel('Function Maximum');
grid on

Bounded Inputs Plot:

Time Taken: 8.4218 sec

Now with Bounded Inputs and Increased population size:

clear all
close all
clc
 
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
 
%Creating a 2Dimensional Mesh
[xx, yy] = meshgrid(x,y);
 
num_case = 150;
 
%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
 
options = optimoptions('ga');
options = optimoptions(options,'populationsize',500);
tic
for i =1:num_case
[inputs,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
Study_time_2 = toc;
 
%Plotting
figure(1)
subplot(2,1,1)
hold on
surf(xx,yy,f)
shading interp
xlabel('X')
ylabel('Y')
grid on
plot3(x_opt,y_opt,fval,'marker','o','markersize',5,'markerFacecolor','k');
title('Bounded Inputs and Increased Population Size');
subplot(2,1,2)
plot(fval);
xlabel('Iterations');
ylabel('Function Maximum');
grid on

Bounded Inputs and Increased Population Size Plot:

Time Taken: 55.993 sec

References:

https://www.mathworks.com/videos/tips-and-tricks-getting-started-using-optimization-with-matlab-81594.html

https://www.mathworks.com/discovery/genetic-algorithm.html#:~:text=Find%20global%20minima%20for%20highly,a%20population%20of%20individual%20solutions.

https://www.mathworks.com/help/gads/genetic-algorithm.html?category=genetic-algorithm&s_tid=CRUX_gn_documentation_genetic-algorithm

https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html

https://www.mathworks.com/help/gads/some-genetic-algorithm-terminology.html

https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html

https://www.mathworks.com/help/gads/ga.html#d120e39323