Week 4 - Genetic Algorithm

WHAT IS GENETIC ALGORITHM?

It is a method inspired from the Charles darwin's theory of evolution. It is a higher level process, designed to find solution and optimization even with limited/insufficient data. They rely on naturally occuring bioligical processes such as mutation, crossing and selection.

The algorith is actually a cycle of the following processes:

- Population

The first step is to create a population, a set of individuals. Each individual representing a solution to our problem. The initial population is randomly generated, creating a range for the solution.

- Evaluation (via fitness function)

Each individual of the population is graded according to its fitness with reference to the fitness function. They are then ranked according to their fitness.

- Selection

Individuals are selected from the current generation of the population to create offsprings and pass on their traits. This is done with respect to the evaluation. The better the fitness score of the individual ias, the more likely he is to get selected with a fewer random selections from lower scores, to maintain diversity.

- Crossover

After the parents are selected, a crossover point is generated amond their respective genes and the offspring is created by switching of genes between the parents till the crossover point and thus new offspring are added to the population, with inherited traits from their parents. And if parents of high fitness scores are chosen, the offspring produced is of even better fitness.

- Mutation

Some of the offspings can have a set of genes that didnt follow the crossover procedure between the parents. Instead, the genes swapped randomly betrween the parents.

This has a very low chances of occuring and its cause is to create variation among its parents after the crossing over produces offsprings that are too similar to their parents.

TERMINATION:

The above cycle is repeated until the termination conditions are encountered, ie- convergence(offspring do not diverge enough from their parents) or performing the cycle for a set number of times. In other words, the solution has converged and further offspring obtained aftrer crossing wont differ much from their parents.

Or, a certain number crossovers have been completed.

After a set of iterations an offspring is added in the population that has fittness score good enough to solve the solution. Hence a solution is generated and cycle terminates.

It mights also stop after a certain number of iterations, or a certain allocated time has been crossed.

SYNTAX OF GA:

The most general form of the ga function is,

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,Intcon,options)

But, it can also be simply called by,

x = ga(fun,nvars)

where, fun represents the function whose minimum value is to be determined, nvars is the number of inputs

of the funtion.

The parameters A and b are used when the solution is constrained in a 2-D region, governed by a set of linear equations. Since we dont need to constrain the solution for the stalagmite function inside a linear equality region, we can leave it empty by setting [] as input.

Aeq and beq have similar functions as they are useful while constraining the solution in a region governed by a quadratic inequality. But since we dont need any constraints regarding equalities, we can skip these parametes as well.

lb and ub are parameters to set the lower and upper limit. They stand for upper bound and lower bound. They both are arrays whose corresponding elements are the limits. For instance,

ub = [1;4] means,

x(1)<=1

x(2)<=4

The nonlcon parameter stands forr nonlinear constraints. It accepts vector orn array, x as input and gives c(x) and ceq(x) as output. Where, ga attempts to satisfy

c(x)<=0

ceq(x)=0

Lastly, the option parameter, it can be used to optimize the parameters that affect the genetic algorithm process. Here, it can be used to change the population size.

EFFECT OF NUMBER OF ITERATIONS:

By observing the cycle of genetic algorithm, we can conclude that, the next genration is generally always better than its parents. So, by successively increasing the number of iterations, we keep getting an offspring in the population that has a better fittness than its parents. Naturally, the solution obtained after 100 iterations is going to have better accuracy than that obtained after 50 iterations.

Hence, we get to conclude that, by increasing the number of iterations, we get to improve the accuracy of the solution.

MAIN CODE:

% program to find the maximum value of stalagmite function using GA

clear all
close all
clc
 
% creating the sample space range for the stslagmite function
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% assigning the number of iterations and creating a 2D vector
num_cases = 50;
[xx,yy] = meshgrid(x,y);
 
for i = 1:length(xx)
    for j = 1:length(yy)
        input(1) = xx(i,j);
        input(2) = yy(i,j);
        f(i,j) = stalagmite(input);
    end
end
 
%Case 1: Statistical behaviour of Genetic Algorithm
tic
for k = 1:num_cases
    [Inputs, Fopt(k)] = ga(@stalagmite,2);
     xopt(k) = Inputs(1);
     yopt(k) = Inputs(2);
end
 time_study1 = toc
 
% assigning negative values as we have to find the maxima 
Fopt = -Fopt;
f = -f;

% plotting
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
% marking the maximum values on the surfc plot
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x')
ylabel('y')

title('Unbounded Inputs');
subplot(2,1,2)
plot(Fopt)
xlabel('Iterations');
ylabel('Fmax');
 
% Case2: statistical behaviour of GA with upper and lower bounds
 
tic
for k = 1:num_cases    
 [Inputs2, Fopt2(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
     xopt2(k) = Inputs2(1);
     yopt2(k) = Inputs2(2);
end
time_study2 = toc

% assigning negative value
Fopt2 = -Fopt2;

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
% marking the maximum values on the surfc plot
plot3(xopt2,yopt2,Fopt2,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x')
ylabel('y')
title('bounded Inputs');
subplot(2,1,2)
plot(Fopt2)
xlabel('Iterations');
ylabel('Fmax');
 
% Case3: Statistical behaviour of GA by increasing the populationsize
 
options = optimoptions('ga');
options = optimoptions(options, 'PopulationSize',170);
tic
for k = 1:num_cases
 [Inputs3, Fopt3(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
     xopt3(k) = Inputs3(1);
     yopt3(k) = Inputs3(2);
end
time_study3 = toc

% assigning negative value
Fopt3 = -Fopt3;

% plotting
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
% marking the maximum values on the surfc plot
plot3(xopt3,yopt3,Fopt3,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x')
ylabel('y')

title('increased populationsize');
subplot(2,1,2)
plot(Fopt3)
xlabel('Iterations');
ylabel('Fmax');

FUNCTION CODE:

function fxy  = stalagmite(input)
x = input(1);
y = input(2);
fx = (sin(5.1*pi*x+0.5))^6;
fy = (sin(5.1*pi*y+0.5))^6;
gx = exp((-4)*log(2)*(((x-0.0667)^2)/0.64));
gy = exp((-4)*log(2)*(((y-0.0667)^2)/0.64));
fxy= -(fx*gx*fy*gy); 
end

SCREENSHOT OF THE OUTPUT:

CASE-1(unbounded):

Here, the most basic form of GA was used, without altering any of its parameters. And as a result, this case gave out the worst results. Since the search space for the GA was not specified, we get to see a very scattered pattern of solution in the plot graph. And since it was the most basic use of the ga function, it finished the termination process the earliest.

CASE-2(bounded):

Here, we tried to improve the solution, by constraining the the search space in a set of interval. As a result, we cas see that the plot becomes much cleaner, as we instructed the ga where the solution region for the given function is. Compared to the unbounded case, it provides a much better plot, as the soluttions are not scattered unneccesarily. But, setting a boundry needs a lot of attention as we need to have an idea about where the the solution region should lie, else the whole point of bounding becomes pointless.

CASE-3(increased population/iterations):

Here, we used the 'optimoptions' command to change the parameters of the GA and changed the initial population to 170. This creates a better solution as, bigger polulation results in creating better end solution. This enables the GA to work on more number tto individuals and hence, perform more iterations. Naturally providing a better solution than the other cases. But, since the population and iterations has increased, it takes much more time for the GA to solve the same problem. But at the same time, provides a much accurate solution.

HOW THE MAXIMA WAS CALCULATED:

The GA function caalculates the minimum value of a given function by default. But since we have to find the maxima of the stalagmite function, we can instead use the GA to find the minimum value of negative of the stalagmite function which is in turn, the maxima of our required function.

EXPLANATION:

The first step was to create elements for our variable array, that act as the inputs for the stalagmite function. It was done using linspace command and meshgrid function together to create those two matrices.

Then, a for loop was used to access the elements of those matrices and get the corresponding value of those elements by using the sttalagmite function within the same loop.

 
for i = 1:length(xx)
    for j = 1:length(yy)
        input(1) = xx(i,j);
        input(2) = yy(i,j);
        f(i,j) = stalagmite(input);
    end
end

Then, for our first case study, a timer was initiated using the 'tic' command to note the time elapsed to complete the solution.

tic
for k = 1:num_cases
    [Inputs, Fopt(k)] = ga(@stalagmite,2);
     xopt(k) = Inputs(1);
     yopt(k) = Inputs(2);
end
 time_study1 = toc

Another 'for' loop was introduced for a given set of iterations and inside the for loop, the GA funnction was called out with 'inputs' and 'Fopt(k)' as outputs. Where, Fopt(k) stores the solution value for the stalagmite function generated by the GA during each iteration and the input vector is a 1x2 vector that stores the corresponding values for x and y.

after the GA terminates, the solutions(x,y,Fopt) were plotted on the original curve using the plot command. And hence, the solutions of the GA were visualized.

Same procedure was repeated for case-2 and case-3 but instead, the search region was bounded by specifying in the GA parameters and changing the population size.

CASE-2

[Inputs2, Fopt2(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);

CASE-3

[Inputs3, Fopt3(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);

CONCLUSION:

Genetic algorith is a very powerful tool to optimize the data and find the solution that best fits our intrests. But, it can be greatly influenced by its parametes. so, we can always improve the fitness of the solution by increasing the number of iterations, increaasing the population size, and carefully bounding the solution region.