Week 4 - Genetic Algorithm

• Selection rules select the individuals, called parents, that contribute to the population at the next generation.

• Crossover rules combine two parents to form children for the next generation.

• Mutation rules apply random changes to individual parents to form children.

Terminology [4] :

• Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.

• Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.

• Selects members, called parents, based on their expectation.

• Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.

• Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.

• Replaces the current population with the children form the next generation.

3. The algorithm stops when one of the stopping criteria is met.

Stopping criteria in Genetic Algorithm [6]:

The genetic algorithm uses the following options to determine when to stop.

The algorithm stops as soon as any one of these conditions is met.

Syntax for GA :

x = ga(function,nvar,A,b,Aeq,beq,lb,ub,nonlcon,options).

1. function refers to the fitness function that has to be mizimized. In our case the fitness function is the Stalagmite function. The fitness function has to be specified as the function handle or function name.

consider x = ga(@stalagmite,2). Here, the stalagmite function is being passed.

2. nvars refers to the number of variables that have to be passed to the function.

In case of the stalagmite function x and y are the variables that have to be passed and hence the value assigned to nvars is 2.

3. A refers to the matrix which contains the coefficients of the variables present in the linear inequalities.

Since A is a matrix, its size is usually M x nvars. M refers to the number of inequalities.

For example, consider the following set of linear inequalities associated with the fitness function.

`3x _1+ 2x_2 <= 10` -------------------(1)

`5x_1 + -1x_2 = -3` ---------------------(2)

The number of linear constraints here are two and hence M is assigned the numerical value 2. Thus the size of the matix A is 2 x 2.

In the syntax, A is written as [3 2; 5 -1].

In our case, the matrix A has to be empty as there aren't any linear constraints specified.

4. b

b is a column vector whose values are assigned to M number of rows.

Consider the linear inequalities presented above, the constituents of the right hand side represent the rows of the vector b.

b = [10 ; -3] for the above mentioned linear inequalities.

In our case of stalagmite function, the vector b is empty as there aren't any linear constraints specified.

5. Aeq refers to the matrix whose elements are the coeffecients of the linear equalities which are constraints to the fitness function.

The size of the matrix Aeq is Me x nvars. Here, Me refers to the number of equalities.

For example, consider the following linear equalities as the constraints,

`-4x_1 + 3x_2 + 7x_3 = -3` ----------------------(1)

`2x_1 + 3x_2 + 5x_3 = 2` ------------------------(2)

`6x_1 + 5x_2 - x_3 = 9` --------------------------(3).

In this case the matrix Aeq = [-4 3 7;2 3 5;6 5 -1]. Here, Me is 3 since there are 3 equalities.

Coming to our case of Stalagmite function, there are no constarints which represent the linear equalities and hence it can be left.

6. beq refers to the column vector which takes in the numerical values present on the R.H.S of the equality sign of the linear equality constraints.

For the above mentioned linear equality constraints, beq = [-3;2;9]. The number of rows for this column vector depend on the number of the linear equality constraints.

7. lb is a vector or an array of elements that represnts the lower bounds of the variables.

For example, let `x(1) >= 0` and `x(3) >=5` be the lower bounds.

Thus lb = [0; -Inf; 5].

8. ub is a vector or an array of elements that represents the upper bounds of the variables.

For example, let `x(5) <= 2` and `x(7) <= -3`be the upper bounds.

Thus ub = [Inf; 2; -3].

9. nonlcon refers to the non-linear constraints. These have to be input as function handle or function name.

Syntax : x = ga(@stalagmite, 2, [ ],[ ],[ ],[ ],[-1 1],[-1 1], @st_con)

In the above syntax, st_con is a function which needs to be defined/ framed earlier in a separate function file.

function [c,ceq] = st_con(k)

c = _____ % compute nonlinear inequalities at x.

ceq = _____ % compute nonlinear equalities at x.

Algorithm to compute the global maxima of the stalagmite function using the ga :

1. create x and y row vectors of 150 elements each whose elements in each row are linearly spaced between 0 and 0.6 using the following lines of code.

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

2. Craete a 2D matrix [X, Y] of 150 x 150 elements whose each row consists of the elements either form vector x or y.

[X, Y] = meshgrid(x,y)

3. The stalagmite function takes in two independent variables X and Y. These values need to be passed to the stalagmite function by calling the function in the main code.

4. The result will be matix f of 150 x 150 elements which are nothing but the function value corresponding to the input variables X and Y.

5. Type in the below syntax which will invoke the ga solver.

options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',600); % A population size of 600 is set.

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

6. The inputs variable stores the values of the independent variables (x and y) for which our stalagmite function has the maximum value.

7. use the surfc and plot3 functions which plot the surface and the maximum values of the stalagmite function respectively.

Code :

% A function file "get_stalagmite that generates the necessary inputs for the stalagmite function

function [f] = get_stalagmite(X,Y)

for i = 1 : length(X)
    for j = 1 : length(Y)
        
        [XX, YY] = meshgrid(X,Y);
        
        input_vector(1) = XX(i,j);
        input_vector(2) = YY(i,j);
        
        f(i,j) = stalagmite(input_vector);
    end
end

% A function file that calculates the value of the stalagmite function when called through main function.

function [fopti] = stalagmite(input_vector)

f1x = sin((5.1*pi*input_vector(1)+ 0.5))^6;
f1y = sin((5.1*pi*input_vector(2) + 0.5))^6;

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

fopti = -1*f1x*f1y*f2x*f2y;

end

Main function file :

clear,close all;
clc;

% creating x and y row vectors
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

f = get_stalagmite(x,y);

num_cases = 150;

%studying the statistical behaviour
tic
for i = 1 : num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2); 
   
end

timer1 = toc
%plotting the results
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('unbounded inputs');
subplot(2,1,2)
plot(fopt)
xlabel('no of iterations')
ylabel('function max.')


% studying the statistical behaviour with lower and upper bounds

tic
for i = 1 : num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2); 
   
end
study_time2 = toc
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('bounded inputs');
subplot(2,1,2)
plot(fopt)
xlabel('no of iterations')
ylabel('function max.')


% increasing the population for GA 

options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',600);
tic
for i = 1 : 150
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2); 
   
end
study_time3 = toc;
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('increased population');
subplot(2,1,2)
plot(fopt)
xlabel('no of iterations')
ylabel('function max.')