Week 4 - Genetic Algorithm

Aim:

To find global maxima for the given stalagmite function using genetic algorithm in MATLAB

Theory:

“It is not the strongest of the species that survives, or the most intelligent, but the one most responsive to change.” by Charles Darwin

The entire concept of a genetic algorithm is based on the above line. A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.

Five phases are considered in a genetic algorithm.

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. 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 parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

2. Fitness Function: The fitness function determines how fit an individual is. It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.
3. Selection: The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.
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. For example, consider the crossover point to be 3 as shown below.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

The new offspring are added to the population.

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.

Global Optimization Toolbox provides functions that search for global solutions to problems that contain multiple maxima or minima. Toolbox solvers include surrogate, pattern search, genetic algorithm, particle swarm, simulated annealing, multistart, and global search.

Genetic Algorithm Syntax

[x,fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

• x - Local unconstrained minimum
• fval - Value of the fitness function at x
• fun - Objective function
• nvars - Dimension (number of design variables)
• A & b - Matrices with linear inequalities
• Aeq & beq - Matrices with linear equalities
• lb - Lower bound
• ub - Upper bound
• nonlcon - Nonlinear constraints
• IntCon - Integer constraints
• options - Minimizes with the default optimization parameters replaced by values in options

MATLAB code:

Stalagmite function code

function stal = stalagmite(input_vector)

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

f_1_x = [sin(5.1*pi*x +0.5)]^6;
f_1_y = [sin(5.1*pi*y +0.5)]^6;
f_2_x = exp((-4)*log(2)*((x-0.0667)^2)*(1/0.64));
f_2_y = exp((-4)*log(2)*((y-0.0667)^2)*(1/0.64));

stal = -(f_1_x * f_1_y * f_2_x * f_2_y);

end

Main code with Global optimization toolbox(Genetic algorithm) solver for finding function maximum in stalagmite function code

clear all
close all
clc

%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Creating a 2D mesh
[xx yy] = meshgrid(x,y);

%Number of itreations to evaluate the fitness
num_case = 50;       

%Evaluating the stalagmite function
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

rng default % For reproducibility

% study1- statistical behaviour (unbounded)
tic
for i = 1:num_case
    [inputs,fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_time_1 = toc

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('study1-unbounded')
xlabel('x value')
ylabel('y value')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum value')

% study2- statistical behaviour (bounded)
tic
for i = 1:num_case
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_time_2 = toc

figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('study2-bounded')
xlabel('x value')
ylabel('y value')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum value')


% study3- statistical behaviour (bounded) with increased population
options = optimoptions('ga');
options = optimoptions(options,'Populationsize',200);

tic
for i = 1:num_case
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_time_3 = toc

figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('study3-bounded with increased population')
xlabel('x value')
ylabel('y value')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum value')

Output:

Explanation:

• At first, Stalagmite function code defining the function with function name, input arguments and output variable is written seperately.
• Formulas to calculate the stalagmite function is written in this code.
• In the main code, the search space of x, y is defined by using the linspace command with number of iterations.
• Then a 2D mesh is created using meshgrid command.
• The stalagmite function is evaluated using two ‘for’ loops.

Study1

• This is a unbounded case and here the genetic algorithm does not know where to exactly consider values in order to evalaute and find its minima.
• Two plots as shown above are created using 'subplot' command.
• 'Surf' command is used to create a three-dimensional surfaceplot which contains solid edge and solid face colors.
• 'Shading interp' command is used for smooth display without any grid lines.
• 'Tic' and 'Toc' command is used to check run time.
• In this case, the variation from optimum value is higher and not accurate.

Study2

• In this study, Upper and Lower bounds are provided in 'ga' syntax by which much more optimized results are obtained.
• Commands used in previous study are also followed here.
• Here, the processing time will be less and a much accurate value in comparison to pervious case is obtained.
• But, even after specifying the boundary limits, the value is not optimum.

Study3

• Here, iterations and population size is increased by using 'optimoptions' command.
• And the rest of the procedure is similar to study1 and study2.
• Processing time is higher but a more accurate and precise value is obtained.

Reproducing results:

• Because the genetic algorithm is stochastic—that is, it makes random choices—we get slightly different results each time we run the genetic algorithm. The algorithm uses the default MATLAB pseudorandom number stream.
• To reproduce results exactly, call 'ga' with an output argument that contains the current state of the default stream, and then reset the state to this value before running 'ga' again.
• syntax for controlling random number generation: rng(seed,generator)

• rng(1,'twister') % for reproducibility
  [x,fval,exitflag,output] = ga(@stalagmite, 2);

• Or we can use

• rng default % For reproducibility

Conclusion:

• MATLAB code to optimize the stalagmite function and to find its global maxima is successfully completed by using genetic algorithm available in global optimization toolbox solver.
• inputs = (0.0668 0.0668) is where the given stalagmite function has its global maxima.
• The genetic algorithm solver gives the minimum value of the function.
• 'GA' is used for solving both constrained and unconstrained optimization problems which is based on a natural selection process that mimics biological evolution.
• Even in constrained problems, increasing the population size increases the processing time but on the other hand, function is optimized.

No major errors encountered except for some typo errors

Reference:

1. https://in.mathworks.com/help/gads/ga.html#d122e38604
2. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
3. https://in.mathworks.com/help/gads/reproducing-your-results-1.html