Week 4.1 - Genetic Algorithm

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 expectations.

   4. Some of the individuals in the current population who have lower fitness are chosen as elite. These elite individuals are passed on 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.

3. The algorithm stops when one of the stopping criteria is met.

4. The algorithm takes modified steps for linear and integer constraints. 

5. The algorithm is further modified for nonlinear constraints.

Phases in Genetic Algorithm:

1. Initialization of Population (Coding)

The code generates its 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 a new population based on no. of iterations performed.

    2. Fitness Function

It is that function that we have to optimize and its optimization is done with the help of several generations that have been formed by the code by the fitness value of each member-generated, these fitness values are used for the reproduction of the children.

    3. Selection

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

Inspiration for this is from the survival of the fittest.

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

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

Too strong a fitness selection bias can lead to sub-optimal solutions.

Too little fitness bias selection results in an unfocused search.

   4. Reproduction

The generation of offspring happens in 2 ways:

-> a. Crossover

-> b. Mutation

a) Crossover

Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.

There are 3 major types of crossover.

Single Point Crossover: A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’.

Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes.

Uniform Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability. The new offspring are added to the population.

b) Mutation

In a few new offspring formed, some of their genes can be 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 take care of diversity among the population and stop premature convergence.

   5. Convergence (when to stop)

A few rules which are followed which tell when to stop is as follows:

• When there is no improvement in the solution quality after completing a certain number of generations set beforehand.
• When a hard and fast range of generations and time is reached.
• Till an acceptable solution is obtained.

My Study for a Better Understanding:

Before going into the challenge, let's take a look at a simpler function to better understand the genetic algorithm. 

The solution will converge once the sum of the fitness function stops increasing and stays constant for a period of time. 

Stalagmite Function:

The code for the stalagmite function is given below:

function [y] = stalagmite(co_ordinates)
    
    x = co_ordinates(1); 
    y = co_ordinates(2);
    
    f1_x = (sin(5.1*pi*x + 0.5)).^6;
    f1_y = (sin(5.1*pi*y + 0.5)).^6;
    
    temp1 = ((x-0.0667).^2)/(0.64);
    f2_x = exp(-4.*log(2)*temp1);
    
    temp2 = ((y-0.0667).^2)/(0.64);
    f2_y = exp(-4.*log(2)*temp2);
    
    y = -(f1_x.*f2_x.*f1_y.*f2_y);

% The Negative sign denotes the inverse of the Stalagmite function and is added in order to find the Maximum value, as the GA algorithm always gives the Minimum value.

Explanation:

We take a function array named 'stalagmite' which takes input x and y and gives output y. We then shorten our function according to the figure and produce output 'y' as the stalagmite function.

Statistical Behavior without binding the Upper and the Lower Limits:

clear all
close all 
clc 

x = linspace(0, 0.5,150); %x  value inputs
y = linspace(0, 0.5, 150); %y value inputs

%The Genetic Algorithm does not work on this
[XX, YY] = meshgrid(x, y)

for i = 1:length(XX);
    for j = 1:length(YY);
        co_ordinates(1) = XX(i,j);
        co_ordinates(2) = YY(i,j);
    y(i,j) = stalagmite(co_ordinates);
    end
end

%Running Geneteic Algorithm for 50 Iterations
%We use tic toc for time count start and end

iteration_number = 50;
tic

for i = 1:iteration_number;
    [inputs,f_opt(i)]= ga(@stalagmite,2); % GA function is used to run the stalagmite data and give the optimal solutions.
    x_opt(i)=inputs(1);
    y_opt(i)=inputs(2);
    opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.
end

study1_time = toc   % Study Time count end

subplot(2,1,1)
hold on %Holding on to the subplot
surfc(XX,YY,y) %Creating the stalagmite function
shading interp  % Visualizing smooth curve surface without mesh lines
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','b' )%plotting the optimum values with a red dot marker along the stalagmite 3D curves
title('1st Case: Not Defining Lower and Upper Bounds')

subplot(2,1,2)
plot(opt_f) %plot of opt_f for every iterations
xlabel('Number of Iterations')
ylabel('Function Max')

 Result for the 1st case:

Step by Step Explanation:

• clear all
  close all
  clc
  x = linspace(0, 0.5,150); %x value inputs
  y = linspace(0, 0.5, 150); %y value inputs
  %The Genetic Algorithm does not work on this
  [XX, YY] = meshgrid(x, y)
  

We first start by clearing and resetting everything. We then take x and y inputs using 'linspace'. We then use 'meshgrid' to sort our x and y co-ordinates. 

• for i = 1:length(XX);
    for j = 1:length(YY);
       co_ordinates(1) = XX(i,j);
       co_ordinates(2) = YY(i,j);
       y(i,j) = stalagmite(co_ordinates);
    end
  end

We use a for loop to execute the stalagmite function for the generated x and y. 

• %Running Geneteic Algorithm for 50 Iterations
  %We use tic toc for time count start and end
  iteration_number = 50;
  tic
  for i = 1:iteration_number;
  [inputs,f_opt(i)]= ga(@stalagmite,2); % GA function is used to run the stalagmite data and give the optimal solutions.
  x_opt(i)=inputs(1);
  y_opt(i)=inputs(2);
  opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.
  end
  study1_time = toc % Study Time count end

We then run the algorithm 50 times. We view the time required for our calculations by using tic and toc. We then use the genetic algorithm on the stalagmite function data and try to find the optimal solutions. We get the Maxima value by putting a minus ahead.

• subplot(2,1,1)
  hold on %Holding on to the subplot
  surfc(XX,YY,y) %Creating the stalagmite function
  shading interp % Visualizing smooth curve surface without mesh lines
  plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','b' )%plotting the optimum values with a red dot marker along the stalagmite 3D curves
  title('1st Case: Not Defining Lower and Upper Bounds')
  subplot(2,1,2)
  plot(opt_f) %plot of opt_f for every iterations
  xlabel('Number of Iterations')
  ylabel('Function Max')

We then use two different subplots. The first for which we plot in 3D the optimum values. We contour plot under surface plot using 'surfc'. To visualize a smooth curve surface, 'shading interp' is used. The second subplot is utilized to plot the optimum function for the iterations along x and y axis. 

Statistical Behavior binding the Upper and the Lower Limits:

x = linspace(0, 0.5,150); %x  value inputs
y = linspace(0, 0.5, 150); %y value inputs
%The Genetic Algorithm does not work on this
[XX, YY] = meshgrid(x, y)

for i = 1:length(XX);
    for j = 1:length(YY);
        co_ordinates(1) = XX(i,j);
        co_ordinates(2) = YY(i,j);
    y(i,j) = stalagmite(co_ordinates);
    end
end

iteration_number = 100;
tic
for i = 1:iteration_number;
    %Number of variables is 2 for the stalagmite function
    %A,B,Aeq and Beq = [],as there is no Linear equalities and inequalities constraints in this function
    % lower boundary of variables x and y in ga algorithm is set as [0,0]
    % upper boundary of variables x and y in ga algorithm is set as [0.5,0.5]
    [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.5,0.5]);
    x_opt(i)=inputs(1);
    y_opt(i)=inputs(2);
    opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.
end

study2_time = toc   % Study Time count end

subplot(2,1,1)
hold on %Holding on to the subplot
surfc(XX,YY,y) %Creating the stalagmite function
shading interp  % Visualizing smooth curve surface without mesh lines
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','b' )%plotting the optimum values with a red dot marker along the stalagmite 3D curves
title('2nd Case: Defining Lower and Upper Bounds')
subplot(2,1,2)
plot(opt_f) %plot of opt_f for each iterations
xlabel('Number of Iterations')
ylabel('Function Max')

Result for the 2nd case:

Explanation:

The initial portions are similar to the first case. What we additionally do is just add the upper and lower limits.

• iteration_number = 100;
  tic
  for i = 1:iteration_number;
  %Number of variables is 2 for the stalagmite function
  %A,B,Aeq and Beq = [],as there is no Linear equalities and inequalities constraints in this function
  % lower boundary of variables x and y in ga algorithm is set as [0,0]
  % upper boundary of variables x and y in ga algorithm is set as [0.5,0.5]
  [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.5,0.5]);
  x_opt(i)=inputs(1);
  y_opt(i)=inputs(2);
  opt_f(i)= -f_opt(i); %Ga gives us Minima value.Inverse f_opt is taken for Maxima value.
  end

Here, we added the upper and lower limit in the syntax of the ga algorithm.

Statistical Behavior binding the Upper and the Lower Limits and with increase in size of population:

x = linspace(0, 0.5,150); %x  value inputs
y = linspace(0, 0.5, 150); %y value inputs
%The Genetic Algorithm does not work on this
[XX, YY] = meshgrid(x, y)

for i = 1:length(XX);
    for j = 1:length(YY);
        co_ordinates(1) = XX(i,j);
        co_ordinates(2) = YY(i,j);
    y(i,j) = stalagmite(co_ordinates);
    end
end

iteration_number = 100;

options = optimoptions('ga')
options = optimoptions('ga', 'PopulationSize', 450);

tic
for i = 1:iteration_number
    % Number of variables is 2 for the stalagmite function
    % A,B,Aeq and Beq = [],as there is no Linear equalities and inequalities constraints in this function
    % lower boundary of varaibles x and y in ga alogorithmn is set as [0,0]
    % upper boundary of varaibles x and y in ga alogorithmn is set as [0.5,0.5]
    % Population size is defined using options in the algorithm
    [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],options);
    x_opt(i)=inputs(1);
    y_opt(i)=inputs(2);
    opt_f(i)= -f_opt(i); %Ga gives us Minima value. Inverse f_opt is taken for the Maxima value.
end

study3_time = toc   % Study Time count end

subplot(2,1,1)
hold on %Holding on to the subplot
surfc(XX,YY,y) %Creating the stalagmite function
shading interp  % Visualizing smooth curve surface without mesh lines
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','b' )%plotting the optimum values with a red dot marker along the stalagmite 3D curves
title('3rd Case: Defined Lower and Upper Bounds with Increased Population')
subplot(2,1,2)
plot(opt_f) %plot of opt_f for each iterations
xlabel('Number of Iterations')
ylabel('Function Max')

 Result for the 3rd case:

Explanation:

Syntax: 

• options = optimoptions('ga')
  options = optimoptions('ga', 'PopulationSize', 450);

Genetic Algorithm Syntax: [inputs,f_opt(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6],[],options);

And we do the same plotting like earlier to get our required optimizations. 

We used a genetic algorithm to get the optimizations we aim for. In this case, we are getting the optimized value of global maxima with an accurate range, since we increased the number of iterations and population size.

Since the number of iterations and population size is increased the study time is so high compared to the previous two iterations.

Thus it can be concluded that GA gives more accurate results in the case of bounded inputs and by increasing the number of iterations and population size.

It can also be inferred that even if we define a particular search space for GA, the GA doesn't run inside the search space. Only in cases of bounded inputs, we can get interfering-able results.

Errors faced while coding:

Due to being utterly cautious, I didn't quite face any major errors while coding. But one thing I forgot was the select the folder in which my function lied and this resulted in an error that I at first didn't notice. But later I fixed it through observation. 

References:

01. https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html#:~:text=The genetic algorithm is a,a population of individual solutions.

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

03. https://skill-lync.com/student-projects/genetic-algorithm-158

04. https://skill-lync.com/student-projects/week-4-genetic-algorithm-33

05. https://www.sciencedirect.com/topics/engineering/genetic-algorithm

06. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

07. https://en.wikipedia.org/wiki/Genetic_algorithm

08. https://in.mathworks.com/help/gads/ga.html

09. https://in.mathworks.com/help/gads/ga.html

10. https://www.researchgate.net/publication/226462334_Genetic_Algorithms

11. https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.html

12. https://in.mathworks.com/discovery/genetic-algorithm.html