Week 4.1 - Genetic Algorithm

We have to write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function. We have to explain genetic algoritham and its syntax.

Genetic algorithm -

A genetic algorithm (GA) is a heuristic search algorithm used to solve search and optimization problems. This algorithm is a subset of evolutionary algorithms, which are used in computation. Genetic algorithms employ the concept of genetics and natural selection to provide solutions to problems.

Five phases are considered in a genetic algorithm.

• Initial population
• Fitness function
• Selection
• Crossover
• Mutation

1. Initial population - The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.An individual is characterized by a set of variables known as Genes. Genes are joined into a string to form a solution.In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used string of 1s and 0s.

2. Fitness funtion - The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual.

3. Selection - The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.Two pairs of individuals are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

4. Crossover - Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

5. Mutation - In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Applications of GA - Genetic algorithms are used in optimization problems of various kinds but they are frequently used in other areas too like economics, neural networks, parallelization, image processing, scheduling application, parametric design of aircraft, dna analysis, multimodal optimization, etc.

PROGRAMMES FOR GA -

First we gonna create stalagmite function so this function can be later called into the main GA programme. As GA generally gives the minima value in built in MATLAB, but we need maxima value so we can just inverse the stalagmite function by introducing a negative sign. We have to make GA programme to run 3 different iterations with iterations having bounded inputs, unbounded inputs and increasing population size. Also we will calculate the study time required for each iteration and plot the results using surfc and plot command.

Code for stalagmite function for main programme -

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*log(2)*(x-0.0667).^2/0.64);
f4 = exp(-4*log(2)*(y-0.0667).^2/0.64);

f = -(f1*f2*f3*f4;
end

a) 1st iteration programme for GA -

In 1st iteration the algorithm is studied without defining the limits. Hence GA doesn't run within a particular searchspace, since we not defined bounds.

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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

num_cases = 50;
tic
for i=1:num_cases
    [inputs,f_opt(i)] = ga(@stalagmite,2);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
    opt_f(i) = -f_opt(i);
end
iteration_1_time = toc

%plotting
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(opt_f)
xlabel('iterations')
ylabel('funtion maximum')

b) 2nd iteration programme for GA -

In 2nd iteration lower and upper bounds are defined to know the boundaries within which global maxima lies.

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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

num_cases = 100;
tic
for i=1:num_cases
    [inputs,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
    opt_f(i) = -f_opt(i);
end
iteration_2_time = toc

%plotting
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','r')
title('with bounded inputs')
subplot(2,1,2)
plot(opt_f)
xlabel('iterations')
ylabel('funtion maximum')

c) 3rd iteration programme for GA -

In 3rd iteration, population size is increased so global maxima is converged.

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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

num_cases = 150;
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',400);

tic
for i=1:num_cases
    [inputs,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],options);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
    opt_f(i) = -f_opt(i);
end
iteration_3_time = toc

subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs with modified population size')
subplot(2,1,2)
plot(opt_f)
xlabel('iteration')
ylabel('funtion maximum')

Explanation of codes -

• ga(fun,nvars,A,b,lb,ub,options) - In this fun represents nothing but function to be called which is stalagmite function in our case, nvars is number of variables, lb is lower bound, ub is upper bound, options is used to perform additional operations like increasing population size.
• for loop - to executes a group of statements in a loop for a specified number of times.
• linspace - to create values with specified intervals upto specified limits.
• plot - to plot the graph with linewidth and color.
• subplot - to create axes in tiled positions.
• shading interp - to set color shading properties.
• surfc - for contour plot under surface plot
• hold on - for adding new plots in current plots without overwriting the plots.
• xlabel - labelling x-axis.
• ylabel - labelling y-axis.
• legend - creating legend with described label for each data series plot.
• title - to give title to the plot.
• tic toc - to calculate total study time of programme.

Results -

1st iteration -

iteration_1_time = 5.9399

It can be seen that since the inputs are boundless GA algorithm has mapped local maxima points outside our stalagmite function. Also the study time is very less as GA is made to run for 50 iterations.

2nd iteration -

iteration_2_time = 14.0936

It gives more clear and optimised graph as compared to 1st iteration because here are the bounds were defined and we could get values within our range in which our maxima lies.

3rd iteration -

iteration_3_time = 117.7499

Since we increased number of population size we are getting the optimised value of global maxima with accurate range. But time required for study is also increased so much as compared first two iterations cause of increased population size.