Week 4 - Genetic Algorithm

AIM:

To write a MATLAB program to optimise the stalagmite function and find the global maxima of the function.

THEORY:

Genetic Algorithm:

It is a nontraditional search and optimization algorithm, inspired by the principles of natural genetics and selection (Darwin’s principle of natural evolution or selection).

Steps:

1. Initialization: It starts with the generation of an initial set of population.

2. Fitness Evaluation: The fitness function value of the set of the population is calculated.

3. Selection/Reproduction: Out of these set of the population, some are selected for the Mating Pool by various selection procedure, such as Tournament Selection, Roulette Wheel Selection, Rank Selection, etc.

4. Crossover: Two solutions are selected randomly from the Mating Pool known as parents and crossover is done(based on the crossover probability) to generate two new solutions known as offspring.

5. Mutation: It changes some characteristic(gene) of the solution to generate a new solution (based on mutation probability). It helps in obtaining global optima.

6. Best solutions from the combined set of initial populations and from the set of offsprings are selected as the initial set of the population for the next generation. This completes one generation of the population(one iteration of Genetic Algorithm).

Stopping criteria:

1. After a predefined number of generations.
2. When the objective function value has reached a certain predefined value.
3. When there has been no improvement in the population for X iterations.

Syntax of Genetic Algorithm in MATLAB:

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

fun : objective function

nvars : number of design variables of fun

Optimize : fun

subjected to,

linear inequalities, `A*x<= b`

linear equalities, `Aeq*x = b`

`lb <= x <= ub`

nonlcon represents Nonlinear constraints

options: it defines some parameters such as initial population size.

Generally, GA minimizes an objective function. Therefore, to maximize a function using GA we need to convert the maximization problem into a minimization problem.

Eg,

max `f(x)`------> min `(-f(x))`

max `f(x)`------> min `(1/(1 + f(x)))`

Stalagmite Function:

`f(x, y) = f_(1,x)*f_(2,x)*f_(1,y)*f_(2,y)`
where,

`f_(1,x) = [sin(5.1pix + 0.5)]^6`

`f_(1,y) = [sin(5.1piy + 0.5)]^6`

`f_(2,x) = exp[-4ln(2)(x - 0.0667)^2/0.64]`

`f_(2,y) = exp[-4ln(2)(y - 0.0667)^2/0.64]`

OBJECTIVES:

1. To study the Genetic Algorithm for unbounded sampling, bounded sampling and with increasing initial population size.
2. To find the global maxima of the stalagmite function.
3. To plot the graph of f(max) v/s number of iterations.

MATLAB CODE:

Main Script:

clear all
close all
clc

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

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

% Evaluating the stalagmite function
f = zeros(length(x), length(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
fopt = zeros(length(num_cases));
xopt = zeros(length(num_cases));
yopt = zeros(length(num_cases));


%% Study 1 - Statistical behaviour with Unbounded Sampling
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)
hold on
surfc(x, y, -f);
xlabel('x value');
ylabel('y value');
shading interp;

plot3(xopt, yopt, -fopt, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r');
title('Unbounded Inputs');

subplot(2,1,2)
plot(-fopt);
xlabel('Iterations');
ylabel('Function maximum');
title('Function maximum v/s number of iterations');


%% Study 2 - Statistical behaviour with upper and lower bounds
tic
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite, 2, [], [], [], [], [0;0], [0.6; 0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc;

figure(2)
subplot(2,1,1)
hold on
surfc(x, y, -f);
xlabel('x value');
ylabel('y value');
shading interp;

plot3(xopt, yopt, -fopt, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r');
title('Bounded inputs');

subplot(2,1,2)
plot(-fopt);
xlabel('Iterations');
ylabel('Function maximum');
title('Function maximum v/s number of iterations');

%% Study 3 - increasing population size
options = optimoptions('ga');
options = optimoptions(options, 'PopulationSize', 200);

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

figure(3)
subplot(2,1,1)
hold on
surfc(x, y, -f);
xlabel('x value');
ylabel('y value');
shading interp;

plot3(xopt, yopt, -fopt, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r');
title('Bounded inputs with increasing population size');

subplot(2,1,2)
plot(-fopt);
xlabel('Iterations');
ylabel('Function maximum');
title('Function maximum v/s number of iterations');

% Printing optimum point

[fmaximum, n] = max(-fopt);
xmaxima = xopt(n);
ymaxima = yopt(n);

fprintf('\nThe optimum point which maximize the stalagmite function is (%f, %f) \n', xmaxima, ymaxima); 

fprintf('The maximum value is %f\n', fmaximum);  

Stalagmite Function:

function fval = stalagmite(input)
x = input(1);
y = input(2);

f1x = (sin(5.1*pi*x + 0.5))^6;
f1y = (sin(5.1*pi*y + 0.5))^6;

f2x = exp(-4*log(2)*(x - 0.0667)^2 / 0.64);
f2y = exp(-4*log(2)*(y - 0.0667)^2 / 0.64);

fval = - ( f1x * f2x * f1y * f2y);
end

In line number 10 of stalagmite, i.e; fval = - ( f1x * f2x * f1y * f2y); minus(-) sign is used to convert the maximization problem into a minimization problem.

GRAPHS:

Case 1: Unbounded

Case 2: Bounded

Case 3: Increasing Population size

OUTPUT:

The optimum point which maximizes the stalagmite function is (0.066832, 0.066831)
The maximum value is 1.000000

REFERENCES:

1. Tutorials Point, (https://www.tutorialspoint.com/genetic_algorithms/index.htm).
2. Mathworks, (https://in.mathworks.com/help/gads/ga.html?docviewer=null#mw_4a8bfdb9-7c4c-4302-8f47-d260b7a43e26)
3. Optimization for Engineering Design by Kalyanmoy Deb