Week 4.1 - Genetic Algorithm

Aim:-

To optimise the stalagmite function and find the global maxima of the function.

Objective:-

Explaining the concept of genetic algorithm and also explain the syntax for ga in matlab.

Plot graph for all 3 studies and for F maximum vs no.of iterations.

Introdution:

A Genetic Algorithm is a search experiential that is stimulated by Charles Darwin's theory of natural evolution. This algorithm reproduces the process of natural selection where the appropriate individuals are selected for reproduction in order to produce offspring of the next generation.

The genetic algorithm is a technique for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The genetic algorithm constantly modifies the population size of individual solutions.

Phases in Genetic Algorithm:-

1. Initialization of population(coding)

The code generates its random population of defined size and form that population the code evaluates the fitness of the members of the population based on no. of iterations performed,

2. Fitness Function:-

It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with 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 form the survival of the 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 fitness selection bias can lead to sub-optimal solutions.

Too little fitness bias selection results inn unfocused search.

4.Reproduction:

Generation of offspring happen 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 probabbility. 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 probaility. This indicates that some of the bits chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

FLOW CHART:

Syntax for GA:

[x,fval,exitflag,output,population,scores] = ga(func,nvars,A,b,Aeq,Beq,ib,ub,nonlcon,intcon,options)

x = optimum solution

exitflag = reason ga stopped

output = information about optimization process

population = final population

scores = final scores

f = ga(fun,nvars,A,b,[],[],ib,ub,nonlcon,intcon,options)

fun - fitness function

nvars - number of variables

A,b = Linear inequality constrains

Aeq,Beq = Linear equality constraints

ib - Lower bound(limits)

ub - Upper bound(limits)

nonlcon : Use for nonlinear constraints

intcon : to get solution inn integer

options - To set population size minimize with non-default options.

Main Body:-

Firstly, creating the mesh from the two vector which will be acting as a search space to find the maxima of the function.

Creating the mesh of these two vector using the 'mesh' command and defining the no. of iterations as num_cases to iterate the values of the optimum values of the function.

Now calculating the values of fitness function at each point of the mesh grid formed.

Now creating its surface through 'surfc' command which will also provide the contour of the generated surface.

While using surfc applying the -ve sign to that function will generate the surface upside down which wiil be quite good to get the maxima of the function, as it will provide positive value for the maxima using the -ve sign.

1. Statistical Study Without Boundation:

In this evaluating the optimum value of fitness funtion at each iteration and calcualting it using the above mentioned syntax in intro part (Which gives the inputs ie. Values of x and y at which the stalagmite function is minimum)

Then plotting it into the surf command and also providing the optimum values of the function that how it is varying.

Also using the tic and tok command to evaluate the time used for optimizing the function.

2. Statistical Study With Boundation:

The difference over here is in providing the upper and the lower limit in the ga so that the search space is reduced with the upper and lower boundary.

And then plotting it as similar to the above study.

3. Statistical Study With Increase in size of population:

In this study using the 'optimoptions' command to increase the size of population.

The benefit of that will be it will be working on the large set of numbers and which will be led to increase the possibilities of finding the better fitness of the function.

The drawback is that the time for evaluation will increase.

Main Code:

close all
clear all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

[X,Y] = meshgrid(x,y);

num_cases = 50;

for I = 1:length(X)
    for J = 1:length(Y)
       input_vector(1) = X(I,J);
       input_vector(2) = Y(I,J);
       f(I,J)=stalagmite(input_vector);
    end
end

surfc(X,Y,f)
shading interp

%[X,fval] = ga(@stalagmite,2);

% statistical behaviour unbounded

tic

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)

surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
xlabel('x')
ylabel('y')
grid on
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function min value')

% Statistical Behaviour bounded

tic
for j = 1:num_cases

    [inputs,fopt(j)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1:1]);
    xopt(j) = inputs(1);
    yopt(j) = inputs(2);

end
study2_time = toc

figure(2)
subplot(2,1,1)

surfc(X,y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
xlabel('x')
ylabel('y')
grid on
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function min value')

% modifying the number of population
options = optimoptions('ga','populationsize',300)
tic
for k=1:num_cases
    [inputs,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
study3_time = toc

figure(3)
subplot(2,1,1)

surfc(X,Y,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
xlabel('x')
ylabel('y')
grid on
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function min value')

function [f] = stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);

f1_x = (sin(5.1*pi*x + 0.5)).^6;
f1_y = (sin(5.1*pi*y + 0.5)).^6;

t1 = ((x-0.0667).^2/0.64);
f2_x = exp(-4.*log(2)*t1);

t2 = ((y-0.0667).^2/0.64);
f2_y = exp(-4.*log(2)*t2);

f = -(f1_x.*f2_x.*f1_y.*f2_y);
end 

Results:-

Conclusion:

ga is useful for optimizing the function but still the result are not accurate as the maximum value for the function lies at -1.