Week 4.1 - Genetic Algorithm

Week 4.1- Genetic Algorithm

Aim: To find the global maxima of a stalagmite function using an optimisation tool (in this case genetic algorithm)

1. Creating a stalagmite function.

Firstly, two 1D arrays for the x and y values were created using the ‘linspace’ command with upper and lower bounds of 0.6 and 0 respectively.

These were then used to create 2D arrays using the mesh grid command and the arrays were stored in the variables ‘xx’ and ‘yy’.

The 2D variables were then passed onto the ‘stalagmite’ function which returns a 1D array of the function values in the variable ‘func_val’.

Stalagmite function

The ‘stalagmite’ function takes in an array 2D array consisting of all the ‘xx’ and ‘yy’ values as inputs and passes them onto the variable ‘x’ inside the function.

Inside the function, the f1, f2, f3 and f4 values are calculated as per the code below and they are used to calculate the function value and stored in the variable ‘func_val’.

In the last line of the code, the function value is given a minus sign so the entire plot which will be created would come in the negative axis which will make it easier to find the minimum value using the genetic solver.

f1x= sin(5.1*pi*x(:,1)+0.5).^6;

f2x= exp(-4*log(2)*((x(:,1)-0.0667).^2/0.64));

f1y= sin(5.1*pi*x(:,2)+0.5).^6;

f2y= exp(-4*log(2)*((x(:,2)-0.0667).^2/0.64));

func_val=-f1x.*f2x.*f1y.*f2y;

The function returns the variable ‘func_val’ back to the main program.

Creating a stalagmite function (contd).

The function value is then used to create a 3D plot using the ‘surfc’ command.

The keyword ‘shading interp’ is used to remove the gridlines and to make the plot look smooth.

2. The explanation for different cases/steps of calling genetic algorithm in the code and results,

• Step 1 (genetic algorithm using random samples)

For the first step, the genetic algorithm is called 50 times using a for loop statement.

The ga solver returns the optimal function value and the input coordinates for that value into the variables ‘fval_1’ and ‘inputs’ respectively.

The x and y coordinates of the minimum function values are then stored in the variables ‘x_opt’ and’y_opt’ respectively.

Here the number of the initial population is taken to be the default value of 50.

The run time of the program is calculated using the tic- toc command.

Plotting the function and min values provided by the ga solver.

A subplot is created with 2 rows and 1 column.

In the first figure of the sub plot, the stalagmite function is shown and within the same plot, the minimum values returned by the ga solver are plotted in it using the plot 3 command.

From the figure is it clear that ga takes values outside the upper and lower bounds specified to the stalagmite function.

In the second figure of the subplot, the minimum value returned by the ga solver is plotted against the number of iterations. From the figure, it is quite evident that the value changes quite drastically for each subsequent iteration.

• Step 2 (genetic algorithm using samples with specified upper and lower bounds)

For the second step, the genetic algorithm is called 50 times using a for loop statement with specified upper and lower bounds 1 and 0 respectively for both the x and y variables so that the solver gives more accurate values.

The ga solver returns the optimal function value and the input coordinates for that value into the variables ‘fval_1’ and ‘inputs’ respectively.

The x and y coordinates of the minimum function values are then stored in the variables ‘x_opt’ and’y_opt’ respectively.

Here the number of the initial population is taken to be the default value of 50.

The run time of the program is calculated using the tic- toc command.

Plotting the function and min values provided by the ga solver.

A subplot is created with 2 rows and 1 column.

In the first figure of the subplot, the stalagmite function is shown and within the same plot, the minimum values returned by the ga solver is plotted in it using the plot 3 command.

In the second case, the solver gives more accurate values with some function values lying in the local minima.

In the second figure of the subplot, the minimum value returned by the ga solver is plotted against the number of iterations. From the figure, it is quite evident that even though bounds were given to the variable, the value changes quite drastically for each subsequent iteration between the local and global minima.

• Step 3 (genetic algorithm using samples with specified upper and lower bounds with specified initial population size)

For the second step, the genetic algorithm is called 50 times using a for loop statement with specified upper and lower bounds 1 and 0 respectively for both the x and y variables so that the solver gives more accurate values with an initial population size of 250.

The ga solver returns the optimal function value and the input coordinates for that value into the variables ‘fval_1’ and ‘inputs’ respectively.

The x and y coordinates of the minimum function values are then stored in the variable ‘x_opt’ and’y_opt’ respectively.

Here the number of the initial population changes from the default value of 50 to a specified value of 250.

The run time of the program is calculated using the tic- toc command.

Plotting the function and min values provided by the ga solver.

A subplot is created with 2 rows and 1 column.

In the first figure of the sub plot, the stalagmite function is shown and within the same plot the minimum values returned by the ga solver is plotted in it using the plot3 command.

In the second case the solver gives more accurate values with most if not all function values lying in the global minima.

In the second figure of the subplot the minimum value returned by the ga solver is plotted against the number of iterations. From the figure it is quite evident that even though bounds were given to the variable, the value remains almost constant to a value of almost -1 for all iterations.

The value of the global maximum is calculated by inverting the sign of the function value at the global minima found by the ga solver.

• Significance of running multiple iterations:

If the ga solver is not optimised properly, the solver will give different values for minima during each call. Running multiple iterations is a good way to check if the solver converged to the global minima properly.

3. Genetic algorithm (brief working)

• It is a class of algorithms called classical algorithms.
• It is mainly used for solving optimisation problems.

The steps involved in the process are as follows,

1. Initialization
2. Select parents and cross over to create offspring
3. Mutate offspring
4. Merge main population and offspring
5. Evaluate, sort and select the best offspring
6. Go to step 2, if it is needed

• Types of cross over used in genetic algorithm

1. Single cutting point
2. Double cutting point
3. Uniform cross over

• Mutation

Mutation adds some level of error to the parents which makes it possible to create innovative and revolutionary solutions.

It also helps to get out of local minima in a function.

• Parent selection

1. Random selection

All the individuals have an equal chance of getting selected.

1. Tournament selection

In this case a random number of initial members from the main population is first selected and then each member is assigned a probability of selection based on their function value.

1. Roulette wheel selection

All the members are given a certain probability of getting selected based on their function values.

• Significance of running multiple iterations:

If the ga solver is not optimised properly, the solver will give different values for minima during each call. Running multiple iteration is a good way to check if the solver converged to the global minima properly.

4. Syntax for genetic algorithm,

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

fun – function

nvar – number of variables in the function

A, b, Aeq and beq - sets inequalities for the function variables

lb – lower bounds for the input variables

ub – upper bounds for the input variables

options - can be used to change the number of generations, initial population size, tolerance of the function etc

example of syntax used in the code:

[inputs, fval_1(i)] = ga(@stalagmite, 2, [], [], [], [], [0;0], [1;1], [], [], options );

References,

1) https://de.mathworks.com/help/gads/ga.html

2) https://de.mathworks.com/help/gads/genetic-algorithm-options.html#responsive_offcanvas

3) https://www.youtube.com/watch?v=1i8muvzZkPw&ab_channel=MATLAB

4) https://www.youtube.com/watch?v=FuWPDQz6Oe0&ab_channel=Yarpiz

Main Code

% optimisation of stalagmite function
clear all
close all
clc

%creating 2D array inputs for the function
x= linspace(0,0.6,150);
y= linspace(0,0.6,150);
[xx, yy]= meshgrid(x, y);

%creating and plotting the stalagmite function
func_val= stalagmite([xx(:), yy(:)]);
func_val= reshape(func_val, size(xx));
surfc(xx,yy,func_val);
shading interp
xlabel('x value');
ylabel('y value');
zlabel('function value');


num_cases= 50; %setting number of iterations for the gen algo

%% Step 1 genetic algo using random samples

tic;
for i=1:num_cases
[inputs, fval_1(i)] = ga(@stalagmite, 2);
x_opt(i)= inputs(1);
y_opt(i)= inputs(2);
end
stop_time_1= toc

%plotting the function and the min values provided by the ga solver
figure(1);
subplot(2,1,1);
surfc(xx,yy,func_val);
shading interp
xlabel('x value');
ylabel('y value');
zlabel('function value');
hold on
plot3(x_opt,y_opt,fval_1,'-o','MarkerSize',5,'MarkerFaceColor','r');
title('random input samples');
subplot(2,1,2);
plot(fval_1);
xlabel('iterations');
ylabel('minimum function value');



%% Step 2 genetic algo using upper and lower bounds

tic;
for i=1:num_cases
[inputs, fval_1(i)] = ga(@stalagmite, 2, [], [], [], [], [0;0], [1;1]);
x_opt(i)= inputs(1);
y_opt(i)= inputs(2);
end
stop_time_1= toc

%plotting 
figure(1);
subplot(2,1,1);
surfc(xx,yy,func_val);
shading interp
xlabel('x value');
ylabel('y value');
zlabel('function value');
hold on
plot3(x_opt,y_opt,fval_1,'-o','MarkerSize',5,'MarkerFaceColor','r');
title('random input samples (default:50) with lb and ub');
subplot(2,1,2);
plot(fval_1);
xlabel('iterations');
ylabel('minimum function value');

%% Step 3 genetic algo using larger sample space to get out of local minima

%setting sample size or initial population to 200
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',250);

tic;
for i=1:num_cases
[inputs, fval_1(i)] = ga(@stalagmite, 2, [], [], [], [], [0;0], [1;1], [], [], options );
x_opt(i)= inputs(1);
y_opt(i)= inputs(2);
end
stop_time_1= toc

%plotting 
figure(1);
subplot(2,1,1);
surfc(xx,yy,func_val);
shading interp
xlabel('x value');
ylabel('y value');
zlabel('function value');
hold on
plot3(x_opt,y_opt,fval_1,'-o','MarkerSize',5,'MarkerFaceColor','r');
title('specificed number of input samples (200) with lb and ub');
subplot(2,1,2);
plot(fval_1);
xlabel('iterations');
ylabel('minimum function value');
global_maximum= -min(fval_1);

Function Stalagmite

%stalagmite function

function func_val= stalagmite(x)
f1x= sin(5.1*pi*x(:,1)+0.5).^6;
f2x= exp(-4*log(2)*((x(:,1)-0.0667).^2/0.64));
f1y= sin(5.1*pi*x(:,2)+0.5).^6;
f2y= exp(-4*log(2)*((x(:,2)-0.0667).^2/0.64));
func_val=-f1x.*f2x.*f1y.*f2y;%reversing the sign 
end

5. Errors faced

• Error 1

Incorrect use of syntax for the ga function call.

Correction: syntax was corrected properly.

• Error 2

Incorrect variables passed into the function stalagmite.

Correction: correct variables were passed onto the function call

• Error 3

The incorrect formula used while writing the stalagmite function

Correction: formulas used were corrected and the function value calculated