Week 4.1 - Genetic Algorithm

Genetic Algortihm:

It is a model or abstraction of biological evolution based on Charles Darwin's thoery of Natural selection.

Genetic algorithms are a class of numerical and combinational optimizers which are especially useful for solving complex nonlinear and nonconvex problems.

1. Selection

Selection process is nothing but 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 area where the chances of getting the best solution are more.Inspiration for this is from the survival of the fittest.Too strong fitness selection bias can lead to sub-optimal solutions.Too little fitness bias selection results in unfocused search.

2. Crossover

During crossover, a random point is selected while mating a pair of parents to generate offspring.

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

Stalagmite:

Stalagmites are convex deposits that grow upward, commonly fed by an overhanging stalacite, and show flat, rounded, or slightly hollow tops, but not a central canal.

Stalagmites in caves act as climate sensor.Dating different sections of a stalagmite can therefore show how climate has changed during glacial and interglacial periods.

Program to find the global maxima of the stalagmite function:

%Stalagmite function defenition
function [f] = Stalagmite(input_vector)
     x = input_vector(1);
     y = input_vector(2);
     f1 = (sin(5.1*pi.*x+0.5)).^6;
     f2 = (sin(5.1*pi.*y+0.5)).^6;
     f3 = exp(-4*0.6931.*(x-0.0667).^2/0.64);
     f4 = exp(-4*0.6931.*(y-0.0667).^2/0.64);
     f = -(f1.*f2.*f3.*f4);
end

Syntax for GA:

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

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').

plot3(x,y,z) plots coordinates in 3-D space.

optimoptions():

options = optimoptions(SolverName,Name,value) returns options with specified parameters set using one or more name-value pair arguments

clear all
close all
clc

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

%No. of iterations
num_cases = 50;


%creating a 2D mesh
[xx,yy] = meshgrid(x,y);

%Evaluating the stalagmite function
for i = 1:length(xx)
    for j = 1:length(yy)
        input_vec(1) = xx(i,j);
        input_vec(2) = yy(i,j);
        f(i,j) = Stalagmite(input_vec);
    end
end

tic
%Study 1 : Statistical behavior
for i = 1:num_cases;
  [inputs,fopt(i)] = ga(@Stalagmite,2);
   xopt(i) = inputs(1);
   yopt(i) = inputs(2);
end
study1_time = toc

%plotting
figure(1)
subplot(2,1,1)
hold on
surf(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','g')  
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('Function maxima')



tic
%Study 2 : Statistical behavior
for i = 1:num_cases;
   [inputs,fopt(i)] = ga(@Stalagmite,2,[],[],[],[],[0,0],[1,1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc
%plotting
figure(2)
subplot(2,1,1)
hold on
surf(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','g')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('Function maxima')

%Increasing GA iteration
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',300);

tic
%Study 3 : Statistical behavior
for i = 1:num_cases;
   [inputs,fopt(i)] = ga(@Stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc
%plotting
figure(3)
subplot(2,1,1)
hold on
surf(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','g')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('Function maxima')

In case 1 the optimal values go outside the values of x and y resulting in deviating away from the stalagmite surface. So we failed to reach the global maxima in this case.

In case 2 the values are bounded even though the exact maxima values are not founded.

In case 3 the initial population size of the ga is increased using the optimoptions command with that the global maxima of the stalagmite function is found.

The study time values for all 3 studies are given in the screenshot of the workspace.

Errors:

Typical program errors such as missing paranthesis were faced.

Reference:

1. https://riadalam323.medium.com/aim-genetic-algorithm-write-a-code-in-matlab-to-optimise-the-stalagmite-function-and-find-the-9a4373ffee93

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

3. https://www.sciencedirect.com/topics/earth-and-planetary-sciences/stalagmite

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

5. https://in.mathworks.com/help/matlab/ref/plot3.html

6. https://in.mathworks.com/help/optim/ug/optim.problemdef.optimizationproblem.optimoptions.html