Week 5 - Genetic Algorithm

Aim:

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

Objectives:

• Explaining the concept of genetic algorithm and also explain the syntax for ga in MATLAB.
• Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Introduction:

Optimization is the process of making something better In any process, we have a set of inputs and a set of outputs as shown in the following figure.

Optimization refers to finding the values of inputs in such a way that we get the “best” output values. The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.

The set of all possible solutions or values which the inputs can take make up the search space. In this search space, lies a point or a set of points which gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.

Phases in genetic algorithm:

Initialization of population (coding):

The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on no. of iterations performed.

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.

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 from the survival of 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 in unfocused search.

Reproduction:

Generation of offspring happen in 2 ways:

Crossover

Mutation

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

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.

Flow chart:

Body of the content:

Fitness function:

MATLAB code:

Main body code:

clear all
close all
clc

% defining our serach space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
n = 50; 
% Greating a 2D meshgrid
[xx,yy] = meshgrid(x,y);

% evalvating the stalagmite function
for i = 1: length(xx)
    for j = 1 : length(yy)
        inputs(1) = xx(i,j);
        inputs(2) = yy(i,j);
        f(i,j) = stalagmite(inputs);
    end
end
figure(1)
surfc(xx,yy,-f)
xlabel('x');
ylabel('y');
shading interp
[input,fval] = ga(@stalagmite,2);

% study 1 - statistical behavior (unbounded)
tic
for k = 1:n
    [inputs,f_opt(k)] = ga(@stalagmite,2);
    xopt(k) = inputs(1);
    yopt(k) = inputs(2);
end
study_1 = toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-f_opt,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
title('unbounded inputs')
subplot(2,1,2)
plot(-f_opt)
xlabel('iteration');
ylabel('function min value');

tic % start of timer
% study 2 - statisitcal behavior -with upper and lower bounds
for k = 1: n
    [inputs2,f2(k)] = ga (@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt2(k) = inputs2(1);
    yopt2(k) = inputs2(2);
end
study2_time = toc;

figure(3)
subplot(2,1,1)
hold on 
surfc(xx,yy,-f)
shading interp
plot3(xopt2,yopt2,-f2,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
title('bounded input')
subplot(2,1,2)
plot(-f2)
xlabel('iteration');
ylabel('function min value');

% study 3 - increasing GA iteration
options = optimoptions('ga','populationsize',500)
tic
for k = 1: n
    [inputs3,fopt3(k)] = ga (@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt3(k) = inputs3(1);
    yopt3(k) = inputs3(2);
end
study3_time = toc;

figure(4)
subplot(2,1,1)
hold on 
surfc(xx,yy,-f)
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','MarkerSize',5,'MarkerFaceColor','r');
xlabel('x');
ylabel('y');
grid on
title('bounded input')
subplot(2,1,2)
plot(-fopt3)
xlabel('iteration');
ylabel('function min value');

Function code:

% stalagmite function
function [f] = stalagmite(input)
x = input(1);
y = input(2);

x1 = (sin((5.1*pi*x)+0.5))^6;
x2 = exp(-4*log(2)*((x-0.0667)^2)/0.64);
y1 = (sin((5.1*pi*y)+0.5))^6;
y2 = exp(-4*log(2)*((y-0.0667)^2)/0.64);


f = -(x1.*x2.*y1.*y2);
end

Procedure:

• We defined the search space using linspace and 2D array created using meshgrid
• Sub program is created for stalagmite function, function evaluated and results stored in f variable
• 

Study 1 – statistical behavior (unbounded):

• The function is iterated to 50 times (random search so results will vary each time)
• The results are stored, using surfc command we create 3 dimensional plot of the result space
• Shading interp is used to shade the plot instead of gridding (default)
• Over that optimization results where plotted, “-ve” sign used to invert the graph
• Below that run plot of each run is plotted
• There is no search bound here so the algorithm searching outside of the function output space
• We can’t able to get reliable result in this search, for each run it gives different result.

Study 2 – with upper and lower bound:

• Here we included the upper and lower bound for the search space
• So the algorithm now search with in the bound for the optimization result
• Remaining process are same here
• These results are improved but still stuck with local maxima instead of global maxima

Study 3 – increased GA iteration (population size);

• Here population size increased to 500, it will consume more time (“346 sec” where previous study takes “29 sec”)
• In this case the results much reliable, the optimization algorithm is not stuck with local maxima
• For 50 repeated run we have very slight change (negligible) in the outcome each time