Week 4 - Genetic Algorithm

Aim - write a matlab programme to optimise the stalagmite function and find the global maxima of the function.

Theory-

Genetic algorithm – it is a method of solving optimization problem both constrained and unconstrained.it is based on the natural selection proposed by john holland based on darwin’s theory of evolution.

Genetic algorithm selects the population and at each step it selects individuals to be parent from current population and uses them to produce the children for the next generation.it requires – a genetic representation of solution domain and fitness function(it the function we want to optimize)

Genetic algorithm does not require any derivative information, it can optimize both continuous and discrete problems and it is faster than traditional methods. Matlab has a built in function - ga(), which calculates minimum of a function using genetic algorithm.

Stopping criteria of ga –

ga stops after the best value of fitness or it can stop after a time limit. There are some other criteria also like – number of generations, function tolerance, constraints tolerance etc.

Syntax for function ga –

x = ga(fun, nvars)

x = ga(fun, nvars, A, b)

x = ga(fun, nvars, A, b, Aeq, beq)

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

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

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

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

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

fun – function name or function handle

nvars – number of variables

a, b - linear inequality constrains

aeq, beq - linear inequality constrains

lb – lower bound

ub – upper bound

nolcon - non linear constrains

intcon – integer constrain

options – optimization option

these are different syntaxes of ga() according to arguments, so in this project we are going to use ga function with different number of arguments for statistical behaviour studies.

Significance of multiple iterations –

Multiple iterations seeks better solution.

Code -

clear all
close all
clc

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

% Creating 2d mesh
[xx yy] = meshgrid(x, y);
tic
% 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  
tic
% study 1 - satistical behaviour
for k = 1:iter
    [input,fval(k)] = ga(@stalagmite,2);
    xopt(k) = input(1);
    yopt(k) = input(2);
end
s_t1 = toc

figure(1)
subplot(2,1,1)
surfc(xx,yy,f)
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,fval,'marker','o','markerfacecolor','r')
shading interp
title("Unbounded inputs")
subplot(2,1,2)
plot(fval)
xlabel('Iterations')
ylabel('Function maximum')

tic
%study 2 - satistical behaviour
for k = 1:iter
    [input,fval(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(k) = input(1);
    yopt(k) = input(2);
end
s_t2 = toc

figure(2)
subplot(2,1,1)
surfc(xx,yy,f)
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,fval,'marker','o','markerfacecolor','r')
shading interp
title("bounded inputs")
subplot(2,1,2)
plot(fval)
xlabel('Iterations')
ylabel('Function maximum')

tic
%study 3 - satistical behaviour
options = optimoptions('ga');
options = optimoptions(options,"PopulationSize",250);
for k = 1:iter
    [input,fval(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(k) = input(1);
    yopt(k) = input(2);
end
s_t3 = toc

figure(3)
subplot(2,1,1)
surfc(xx,yy,f)
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,fval,'marker','o','markerfacecolor','r')
shading interp
title("bounded inputs")
subplot(2,1,2)
plot(fval)
xlabel('Iterations')
ylabel('Function maximum')

Explanation of code –

1. Defined the x and y variables with linspace command which return a row vector with n linearly spaced number between start and end.
2. Fixed the number of iteration and make 2-D grid using meshgrid command.
3. Made a nested for loop which run from 1 to length of meshgrid elements.
4. Loop has stalagmite function which defines the search space.
5. Made another for loop which run from 1 to number of iteration.it has ga(), a built in function which takes function name and number of variables as its argument.
6. We stored the result of ga() function in variables input and fval.
7. Assigned the the values of input in variables xopt and yopt.
8. Made a 3-D surface mesh using surfc command ,a 3-D plot using plot3 command and a plot for fval values.
9. For study 2 of statistical behaviour pass the arguments linear equality constrains, lower bound, upper bound in ga() function .repeat the same procedure we had in study1.
10. To create optimization options for study 3, create variable and define solver as ‘ga’ and population size as 250.
11. For study 3 pass the argument options in ga() function and repeat the procedure we had in study 1.

Code of the stalagmite function –

function [f] = stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);
term1 = (sin(5.1*pi*x + 0.5))^6;
term2 = (sin(5.1*pi*y + 0.5))^6;
term3 = exp(-4*log(2)*((x - 0.0667)^2)/0.64);
term4 = exp(-4*log(2)*((y - 0.0667)^2)/0.64);
f = -1*term1*term2*term3*term4;

end

Conclusion -

study 1 results -

we can see clearly in plot, we got many values of function maximum during the 50 iteration.

study 2 result -

we defined the lower and upper bound so result of function maximum is smoother and it has narrow range.

study 3 result -

we defined the population size to 250 so now function maximum is confined between two values.

we got global maxima at (0.0668,0.0668).

references -

https://en.wikipedia.org/wiki/Genetic_algorithm

https://in.mathworks.com/discovery/genetic-algorithm.html

https://in.mathworks.com/help/gads/ga.html