Week 4 - Genetic Algorithm

Aim: To optimize the stalagmite function and find the global maxima of the function.

Theory:

Genetic Algorithm: A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions.

You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

The Genetic Algorithm works in the following way:

1. The Algorithm creates a random initial population.
2. A sequence of new populations is created by the algorithm. The individuals in the current generation are used to create the next population. The creation of new population requires these additional steps:
   1. Each member of the current population is given a score by calculating its fitness value. They are called as raw fitness scores.
   2. The raw fitness scores are scaled to convert them into a usable range of values. These values are called expectation values.
   3. The members that are also called as the parents are selected based on their expectation.
   4. Individuals called elite are selected in the current population that has lower fitness. These individuals are passed on to the next population.
   5. It produces children from parents. Children are produced either by making random changes to a single parent i.e mutation or by combining the vector entries of a pair of parents i.e crossover.
   6. The current population is replaced with these children to form the next generation.
3. The algorithm comes to a halt when one of the stopping criteria is met.

Formulae:

Syntax:

The syntax is:

[x fval] = ga(@fitnessfun, nvars, options)

1. @fitnessfun is a handle to the fitness function.
2. nvars is the number of independent variables for the fitness function.
3. options is a structure containing options for the genetic algorithm. If you do not pass in this argument, ‘ga’ uses its default options.

The results are given by:

1. x — Point at which the final value is attained
2. fval — Final value of the fitness function

Program:

Code for the main file:

clear all;
close all;
clc;

% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% Defining  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_function(input_vector);
    end
end

num_cases = 50;


tic
% Case Study 1: Statistical Behaviour with Unbounded Values
for i = 1:num_cases
   [inputs,fopt(i)] = ga(@stalagmite_function, 2);
   xopt(i) = inputs(1);
   yopt(i) = inputs(2);
end
study1_time = toc

figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function Maxima')

tic
% Case Study 2: Statistical Behaviour with Upper and Lower Bounds
for i = 1:num_cases
   [inputs,fopt(i)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[1;1]);
   xopt(i) = inputs(1);
   yopt(i) = inputs(2);
end

study2_time = toc

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function Maxima')

% Case Study 3: Increasing GA Iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',500);

tic
for i = 1:num_cases
   [inputs,fopt(i)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[1;1],[],[],options);
   xopt(i) = inputs(1);
   yopt(i) = inputs(2);
end    

study3_time = toc

figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs with modified population size')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function Maxima')

Steps Involved:

1. First, we start off by defining the search space.
2. The meshgrid can be created by using the existing function by using this search space.
3. Then for evaluating for the stalagmite function we use for loop with the variables created, loop through the stalagmite function, and obtain the desired values.
4. The number of iterations is considered to be 50 and it is stored in a variable called num_cases.
5. In the following steps, we use the tic and toc to assess the time taken by the three cases to be evaluated.
6. In Case 1, we try to study the statistical behavior with unbounded values by looping through the iterations with the genetic algorithm included in it. Here, the 'fopt' is returned, the value of the fitness function at 'inputs'.
7. In Case 2, we try to study the statistical behavior with upper and lower bounds(refer to changes made in the 'ga' function) by looping through the iterations with the genetic algorithm included in it. Here, the 'fopt' is returned, the value of the fitness function at 'inputs'.
8. In Case 3, we try to study the statistical behavior with bounded inputs with modified population size(refer to changes made in the 'ga' function) by looping through the iterations with the genetic algorithm included in it. Here, the 'fopt' is returned, the value of the fitness function at 'inputs'.
9. In each case after the loop ends we plot the values of xopt,yopt and fopt using the 'surfc' to plot a 3D representation of the stalagmite function. We use subplot to divide the figure into two plots one of them being the representation of the population dispersed and the other being the relation between the Function Maxima and Iterations.
10. The xlabel,ylabel, title are also added to provide the viewer with precise information regards to the plot.
11. Make sure that the main program is run and not the one containing the function as it would result in an error.

Code for function:

function f = stalagmite_function(input_vector)
a = input_vector(1);
b = input_vector(2);
f1x = (sin((5.1*pi.*a)+0.5)).^6;
f1y = (sin((5.1*pi.*b)+0.5)).^6;
f2x = exp((-4*log10(2)).*((a-0.0667).^2)/0.64);
f2y = exp((-4*log10(2)).*((b-0.0667).^2)/0.64);
f = -f1x*f2x*f1y*f2y;
end

Steps Involved:

1. The stalagmite_function is created and the file is saved with an identical name i.e, 'stalagmite_function.m'.
2. Then, we use the above-mentioned formulae to convert them into usable code.
3. We can use the existing mathematical features provided by MatLab to use the sine function, exponent and the natural logarithm.
4. Make sure that you don't run this file as it would result in an error as the input parameters are not passed here.

Errors:

This error has occurred because the file has been run from the stalagmite.m file and there are no input arguments that are called, so the MatLab shouts an error. To avoid this run the file from the main file where the primary code is written.

Result:

These two plots represent the first case where the population is distributed without any bounds. The markers indicate the population spread at various points. Few of them being out of the surface plot which is because they are not constrained. The Second plot explains the various iterations the function assumes to be the Maxima.

These two plots represent the stalagmite function with their behavior when they consist of bounded inputs. As we can see from the earlier case there's a major change in the plot as the plot is not dispersed randomly and are included in the plot. The number of iterations which are close to function maxima is reduced in this case. This is the second stage of filtration where the points that are not valid Function Maxima are being truncated.

In case 3, we get the final desired result with the first plot showing the point at the Function Maxima and the second plot displaying where the iteration reaches the Function Maxima. This has been achieved by optimizing the function and increasing the population size to 500.

We can observe from these cases that when the population is unbounded and there aren't any constraints involved the computation time is significantly less. As we keep adding constraints in the next two cases the time taken to display the result also increases.

References:

https://www.mathworks.com/discovery/genetic-algorithm.html#:~:text=A%20genetic%20algorithm%20(GA)%20is,a%20population%20of%20individual%20solutions.

Project Link:

https://skill-lync.com/projects/genetic-algorithm-155