Week 4.1 - Genetic Algorithm

Genetic Algorithm:

Genetic Algorithm is a search based optimisation technique based on the principles of Genetics and natural selection.GAs are a subset of much larger branch of computation known as Evolutionay computation.It is used to find optimal or near optimal solutions to problems which would otherwise take a very long time to resolve. Its application areas include machine learning and research.

Genetic Algorithm working.

GAs have a pool or population of possible solutions to the given problem.These solutions undergo recombination and mutation like in natural genetics to produce new children(generation) and this process is repeated for various generations.Each individual is given a fitness value and higher fitness value individual is given a better chance to mate which results in fitter individuals, according to Darwin's theory of "Survival of fittest".

so in this way we keep evolving better individuals untill we reach a stopping criterion.

The termination condition of a Genetic Algorithm is important in determining when a GA run will end. It has been observed that initially, the GA progresses very fast with better solutions coming in every few iterations, but this tends to saturate in the later stages where the improvements are very small. We usually want a termination condition such that our solution is close to the optimal, at the end of the run.

Usually, we keep one of the following termination conditions −

1.When there has been no improvement in the population for X iterations.
2.When we reach an absolute number of generations.
3.When the objective function value has reached a certain pre-defined value.

For example, in a genetic algorithm we keep a counter which keeps track of the generations for which there has been no improvement in the population. Initially, we set this counter to zero. Each time we don’t generate off-springs which are better than the individuals in the population, we increment the counter.

However, if the fitness any of the off-springs is better, then we reset the counter to zero. The algorithm terminates when the counter reaches a predetermined value.

Like other parameters of a GA, the termination condition is also highly problem specific and the GA designer should try out various options to see what suits his particular problem the best.

Mathworks has adapted this GA into MATLAb function,to give solutions to different kind of problems in terms of 0s and 1s.

we can represent in tems of logic as shown below.

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

Stalagmite Function:

A stalagmite function is a upward growing mound of mineral deposits that have precipitated fromwater dripping onto the floor of a cave. Most stalagmites have round or flattened tips.

A close identical geometrical shape can be obtained by a mathematical model. This model requires two input vectors i.e 2Dimensional values X and Y. This yields in a output f(x,y) which is Z axis of the stalagmite model and provides a 3D model of global maxima and local minimas.

%Genetic Algorithm

close all
clear all
clc

%Defining the search spaces
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
[xx,yy]=meshgrid(x,y);
f=get_stalagmite(x,y)

tic
%Study1_statistical behaviour
for i=1:num_cases
    [inputs,fopt(i)]=ga(@Stalagmite,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 minimum')

tic
%study2_statistical behaviour with upper andlower bounds
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
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 minimum')

%study3_Increasing GA iterations
options=optimoptions('ga');
options=optimoptions(options,'populationsize',150);

tic

for i=1:num_cases
    [inputs,fopt(i)]=ga(@Stalagmite,2,[],[],[],[],[0;0],[0.5;0.5],[],[],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('Increased population size')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')
   

function [f] = get_stalagmite(x,y)
%Evaluating the stalagmite function
[xx,yy]=meshgrid(x,y);
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
end

function [S] = Stalagmite(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);

S= -(f1*f2*f3*f4);
end

Explanation:

Define x and y using linspace command and diversify it to 2D using meahgrid command.

Define the number of iterations (num_cases) to 50.

Get_stalagmite function:

Using nested for loop to store the values of x and y into two input_vectors 1 and 2 matrices.this acts as an input to Stalagmite function to result in f(i,j), i.e ZZ values and can be plotted as a 3D plot to give global maxima and local maximas.

Use tic and toc command to record execution time.

Call the ga function which takes Stalagmite function as an input and we are passing two variables here.this results in two o/ps( inputs) which contains xopt and yopt and fopt contains function minimum value.

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

Ga always returns minimum value,to get maximum value, use negation in stalagmite function to obtain maxima.

There are 3 iterations involved:

1. unbounded limits: where no range for i/p is given and results in random values.

2.Bounded limits: I/P range is given so that we are in the path of getting optimum results.

3.Population size: the set value of population size by default is 120, using options command we modify it to 150 so that we reach optimum results and determine global maxima.

Errors:

Tried multiple iterations ,to change num_cases,population size and range of input values to attain the global maxima.

References:

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm#:~:text=Genetic%20Algorithm%20(GA)%20is%20a,take%20a%20lifetime%20to%20solve.

https://skill-lync.freshdesk.com/support/solutions/articles/43000584189-genetic-algorithm-explained-