Genetic Algorithm

%stalagmite.m
%stalagmite function
function val = stalagmite(input_vector)
a = input_vector(1);
b = input_vector(2);
f1x = (sin(5.1*pi*a+0.5))^6;
f1y = (sin(5.1*pi*b+0.5))^6;
f2x = exp(-4*log(2)*((a-0.0667)^2)/0.64);
f2y = exp(-4*log(2)*((b-0.0667)^2)/0.64);
val = -f1x*f2x*f1y*f2y;
end


%Optimisation_using_genetic_algorithm.m
%Maxima by Genetic Algorithm
clc
close all
clear all

%Preparing for stalagmite function
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

num_cases = 50;

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

%Forming 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



%Study 1 - Statistical behaviour
tic
for i = 1:num_cases
    [co_ord, fopt(i)] = ga(@stalagmite, 2);
    xopt(i) = co_ord(1);
    yopt(i) = co_ord(2);
end
study1_time = toc;

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
xlabel(\'xx\')
ylabel(\'yy\')
zlabel(\'f(xx,yy)\')
hold on
plot3(xopt,yopt,-fopt,\'ro\',\'markersize\',5)
title(\'Unbounded co-ordinates\')
subplot(2,1,2)
plot(-fopt)
xlabel(\'Iteration\')
ylabel(\'Function maximum\')


%Study 2 - Statistical behaviour with upper and lower bound
tic
for i = 1:num_cases
    [co_ord, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = co_ord(1);
    yopt(i) = co_ord(2);
end
study2_time = toc;
figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
xlabel(\'xx\')
ylabel(\'yy\')
zlabel(\'f(xx,yy)\')
hold on
plot3(xopt,yopt,-fopt,\'ro\',\'markersize\',5)
title(\'Bounded co-ordinates\')
subplot(2,1,2)
plot(-fopt)
xlabel(\'Iteration\')
ylabel(\'Function maximum\')



%Study 3 - Increasing GA population
options = optimoptions(\'ga\');
options = optimoptions(options,\'PopulationSize\', 270);
tic
for i = 1:num_cases
    [co_ord, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = co_ord(1);
    yopt(i) = co_ord(2);
end
study3_time = toc;
figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
xlabel(\'xx\')
ylabel(\'yy\')
zlabel(\'f(xx,yy)\')
hold on
plot3(xopt,yopt,-fopt,\'ro\',\'markersize\',5)
title(\'Bounded co-ordinates and increased population\')
subplot(2,1,2)
plot(-fopt)
xlabel(\'Iteration\')
ylabel(\'Function maximum\')

study1_time
study2_time
study3_time

Explanation of code:

%stalagmite.m

First we create the stalagmite function as per the given definition.

Since the genetic algorithm finds the global minima, we multiply each value of the function by -1. So that we can find the minima of it and multiply by -1 again to find the maxima of the original function.

%Maxima by Genetic Algorithm

Next step is to create a new script in which main programming is done.

For reference purpose the stalagmite function is plotted.

The range of x and y is fixed and an array of 150 equally spaced points is created.

Using ‘meshgrid’ command a 2D mesh is created.

Then using the ‘for’ loop and by definition of stalagmite function, an array is generated containing the value of stalagmite function at every point of the 2D mesh.

These values are later used to plot the stalagmite function using ‘plot3’ command.

For all the 3 studies of ‘ga’, the number of iterations is fixed at 50 in a variable ‘num_cases’.

1^st Study is the statistical behavior

Using basic ‘ga’ command the co-ordinate and value of minima of the modified function is found for 50 iteration.

These points are plotted on the stalagmite function plot to understand better.

One more sub-plot of ‘function_minima vs iterations’ is plotted as well.

2^nd Study is the statistical behavior with upper and lower bound

The same steps as 1^st study are undertaken with a modification – apply upper (0.6) and lower bound (0) for the co-ordinates of the minima. i.e. xmin = 0, ymin = 0, xmax = 0.6, ymax = 0.6

3^rd Study is to include the bounds as well as to increase the initial population.

The same steps as 2^st study are undertaken with a modification – the initial population of the genetic algorithm is increased by using the ‘options’ feature of ‘ga’ and ‘optimotions’ command.

Using the ‘tic’, ‘toc’ command the time required to compute each study is found out.

The global maxima of the given function is negative of the global minima found in the modified stalagmite function.

It is equal to –(-1) = 1. The co-ordinates of global maxima are (0.0688,0.0688).

..............................................................................................................
Results:

There is only small fluctuation in the 7th decimal. Hence it can be safely assumed to be constant = 1.

............................................................................................................................

Errors

The plot of the stalagmite function was made upside down but the minima value was still 0.

As seen above, I gave the negation in the main program.

It was resolved by negating the function value in ‘stalagmite.m’ function script rather than in main program.

..........................................................................................................................

The syntax of ga

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

x = co-ordinates of the minima of the functions. This is the output

fval = value of the minima. This is also an output.

fun = function name which we want to minimize. It is written as ‘@’ followed by function name.

nvars = this indicates the number of variables in the function.

A, b are used if any linear inequalities exists. Set A,b = [] if no linear inequalities exist.

Aeq, beq are used if any linear equalities exists. Set Aeq=[] and beq=[] if no linear equalities exist.

lb = lower bound of the range of the co-ordinate for minima (output of ga).

ub = upper bound of the range of the co-ordinate for minima (output of ga)

1. If lb = (0;2) and ub = (4;6) then the algorithm will find the minima in the search range where xmax = 4, xmin = 0, ymax = 6, ymin = 2.

nonlcon subjects the minimization to the constraints defined in noncoln. Set nonlcon=[] if no nonlinear constraints exist.

‘options’ minimizes with the default optimization parameters replaced by values in ‘options’. Eg: Increasing the initial population size.

.............................................................................................................

Concept of genetic algorithm:

In order to find the minima of a given function, it is not always feasible to calculate value at every co-ordinate and find the minimum amongst them.

Hence the concept of genetic algorithm is used. First a number of random co-ordinates are chosen.

These are called as parents. It then chooses the best of these parents and are passed on to next generation. It also combines genes (or vector entities) of two parents to form a new individual or children of next generation. This is known as cross over.

It also makes random changes to single parents called as mutation.

These three steps result in a new generation of co-ordinates who are now the new parents.

Same procedure is followed again. This goes on until the stop condition is reached. The stop condition can be controlled.

And thus by properly configuring the algorithm, the minima can be found.

..............................................................................................................