Week 5 - Genetic Algorithm

In this project, I will be generating a stalagmite function in MATLAB and find the global maxima of the function using Genetic Algorithm.

A stalagmite function is a function which generates Stalactites, which are named after a natural phenomenon where rocks rise up from the floor of due to accumulation of droppings of minerals from the ceiling. The opposite, where minerals hang from the ceiling is called Stalactites. These are most frequently found in caves.

Mathematically, the stagalmite function is defined as

`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 [-4ln2 (x-0.0667)^2/0.64]`

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

Genetic Algorithm, which derives its inspiration from Charles Darwin's natural selection algorithm is a method used to generate high quality solutions to optimisation and search problems using natural selection parameters such as evolution, cross breeding and mutations.

The main steps of an optimisation genetic algorithm are as follows:

1. Initialisation: An initial population is randomly generated, comprimising of all input parameters of the required solution.

2. Selection: A score for each "person" in the population is generated, this score relates to the required output of the solution in some way. These scores are allowed to compete with each other in a random way, where the "person" with a higher score is likely to succeed.

3. Genetic Operations: The "winners" from the previous step are allowed to breed with each other, where charecteristics of each "person" is mixed with other selected groups. Additonally, to ensure randomness and heterogeneity, sometimes mutations may also be included during genetic operations.

This process is repeated for a number of times, as the average score of the population increases and eventually reaches close to the required, true value of the solution.

Since the process is entirely random each time the code is excecuted, I will be tweaking the parameters of the algorithm to obtain a constant solution.

The genetic algorithm has its own built-in function in MATLAB, which makes the application of GA in MATLAB fairly straightforward. The syntax (within the scope of the project) is below:

[xy, fval] = ga (@function, nvars, A, b, Aeq, beq, lb, ub, nonlcon, intcon, options)

Where,

xy returns the optimised coordinates of the function (in a 2 x 1 array) (xy (1) would be the x coordinate, xy (2) would be the y coordinate).

fval returns the value of the function at xy.

function is the name of the function to be optimised.

nvars is the number of variables the function is dependent on.

A, b finds a local minimum subject to the linear equalities `Axxx <= b`

Aeq, beq finds a local minimum subject to the linear equalities `Aeqxxx = beq`.

lb, ub defines the lower and upper bounds on the function;s variables like `lb<= x<= ub`.

options is used to define further modification from MATLAB's default algorithm.

Note: if any conditions are not applicable for any current case, the value for that parameter should be [].

By default, the population size is 50 in MATLAB.

Program Algorithm

Step 1: Intialise x, y arrays and create a meshgrid.

Step 2: Calculate stagalmite function for meshgrid using nested for loops.

Step 3: Intialise number of iterations for GA to be calculated for all studies (50).

Step 3: Study 1 - No bounds, purely random sampling. Perform GA for 50 iterations and record data.

Step 4: Plot results of Study 1

Step 5: Study 2 - Solution bounded to 0 and 1 in both axes. Perform GA for 50 iterations and record data.

Step 6: Plot results of Study 2

Step 7: Study 3 - Solution bounded to 0 and 1 in both, increased population size to 170. Perform GA for 50 iterations and record data.

Step 8: Plot results of Study 3

Code (with explanations)

Function staglamite

This function generates the function for a given x and y value. Since the stagalmite function generates curves downwards, and GA in MATLAB can find the minimum value of a function, some variables are multiplied by -1 in some parts of the code to account for the inversion.

function [f_x_y] = stalagmite (input)
    % input (1) is x
    % input (2) is y
    % calculating all terms of the stalagmite function

    f1_x = (sin (5.1*pi*input (1)) + 0.5)^6;
    f1_y = (sin (5.1*pi*input (2)) + 0.5)^6;
    f2_x = exp (-4 * log (2) * (input (1) - 0.0667)^2 / 0.64);
    f2_y = exp (-4 * log (2) * (input (2) - 0.0667)^2 / 0.64);
    % combining all terms to generate stagalmite function

    f = f1_x * f2_x * f1_y * f2_y;

    % inversing function to generate upward stagalmite curves
    f_x_y = -1 * f;
end

Main Program

Since the stagalmite function generates curves downwards, and GA in MATLAB can find the minimum value of a function, some variables are multiplied by -1 in some parts of the code to account for the inversion.

clear all
close all
clc

% creating intial array using linspace
x = linspace (0,0.6,150);
y = linspace (0,0.6,150);
% creating meshgrid from intial arrays
[xx, yy] = meshgrid (x,y);

% generating stalagmite function for mesh grid
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

% number of GAs which will be run
num_iterations = 50;

% Study 1 - no bounds, purely random sampling
tic 
for i = 1:num_iterations
    % calculating and storing x, y, f values for each iteration
    [x_and_y, f_min_study1(i)] = ga(@stalagmite, 2);
    x_min_study1 (i) = x_and_y (1);
    y_min_study1 (i) = x_and_y (2);
end

% ending timer of study 1
study1_time = toc

% plotting results of study 1
figure(1)

subplot(2,1,1)
hold on % to prevent erasure
surfc(x,y,-f) % plotting the stalagmite function
shading interp % erasing axis
plot3 (x_min_study1, y_min_study1, -f_min_study1,'marker','o','MarkerEdgeColor','r') % 3D plot of 50 different minimum values generated by GA
title ('Distribution of global maxima predicted by genetic algorithm')
xlabel ('x value')
ylabel ('y value')
zlabel ('Stalagmite function / Predicted values (red)')

subplot (2,1,2);
plot (1:num_iterations ,-f_min_study1) % plotting
title ('Global maxima predicted by genetic algorithm for each iteration')
xlabel ('Iteration Number')
ylabel ('Global maxima predicted by genetic algorithm')

sgtitle ('Study 1 - no bounds, purely random sampling')

% Study 2 - a little help given to the algorithm by narrowing the search
% region to [ 0 0 1 1 ]
tic 
for i = 1:num_iterations
    % calculating and storing x, y, f values for each iteration
    [x_and_y, f_min_study2(i)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1]);
    x_min_study2 (i) = x_and_y (1);
    y_min_study2 (i) = x_and_y (2);
end

% ending timer of study 2
study2_time = toc

% plotting results of study 2
figure(2)

subplot(2,1,1)
hold on % to prevent erasure
surfc(x,y,-f) % plotting the stalagmite function
shading interp % erasing axis
plot3 (x_min_study2, y_min_study2,-f_min_study2,'marker','o','MarkerEdgeColor','r') % 3D plot of 50 different minimum values generated by GA
title ('Distribution of global maxima predicted by genetic algorithm')
xlabel ('x value')
ylabel ('y value')
zlabel ('Stalagmite function / Predicted values (red)')

subplot (2,1,2);
plot (1:num_iterations ,-f_min_study2)
title ('Global maxima predicted by genetic algorithm for each iteration')
xlabel ('Iteration Number')
ylabel ('Global maxima predicted by genetic algorithm')

sgtitle ('Study 2 - Introduced solution bounds')

% Study 3 - increasing population size to 170, keeping the solution bounds

tic 
% setting population size to 170 using options variable
options = optimoptions ('ga');
options = optimoptions (options, 'PopulationSize',170);
for i = 1:num_iterations
    % calculating and storing x, y, f values for each iteration
    [x_and_y, f_min_study3(i)] = ga(@stalagmite, 2, [],[],[],[],[0;0],[1;1],[],[], options);
    x_min_study3 (i) = x_and_y (1);
    y_min_study3 (i) = x_and_y (2);
end

% ending timer of study 3
study3_time = toc

% plotting results of study 
figure(3)

subplot(2,1,1)
hold on % to prevent erasure
surfc(x,y,-f) % plotting the stalagmite function
shading interp % erasing axis
plot3 (x_min_study3, y_min_study3, -f_min_study3,'marker','o','MarkerEdgeColor','r') % 3D plot of 50 different minimum values generated by GA
title ('Distribution of global maxima predicted by genetic algorithm')
xlabel ('x value')
ylabel ('y value')
zlabel ('Stalagmite function / Predicted values (red)')

subplot (2,1,2);
plot (1:num_iterations ,-f_min_study3)
title ('Global maxima predicted by genetic algorithm for each iteration')
xlabel ('Iteration Number')
ylabel ('Global maxima predicted by genetic algorithm')

sgtitle ('Study 3 - Increased population size to 170 / Introduced solution bounds')

Output

Study 1 - Purely Random Sampling

Most predictions by the algorithm are all over the place, this is because GA is a purely random method.

Study Time: 4.653 seconds

Study 2 - Introduced Solution Bounds (0 to 1)

Since we have essentially helped the algorithm by narrowing its search region, the solution is more precise. Only some predictions predict the local maxima.

Study Time: 4.6532 seconds

Study 3 - Increased Population Size to 170

Increasing the population size to 170 from 50 drastically improves the prediction of the algorithm. All predictions predict that the global maxima of the function lies around ~128.

Study Time: 10.557 seconds

Issues Faced during Programming

Titles of subplots were not appearing

Steps taken to fix Errors

Titles were added to the plots after the plot command.

References

1. https://youtu.be/MacVqujSXWE

2. https://youtu.be/R9OHn5ZF4Uo

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

4. https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html

5. https://www.mathworks.com/help/gads/ga.html