Genetic Algorithm to find the Global Maxima of a Stalagmite function using Matlab

Optimisation of Stalagmite function to find the global maxima using Genetic Algorithm

Aim & Objectives:

1. To understand the concept of Genetic Algorithm (GA)
2. To write MATLAB code to optimise the stalagmite function and find the global maxima of the function.
3. To investigate on the different statistical behaviour.
4. To explain the concept of the genetic algorithm and the syntax for ga in MATLAB.

Stalagmite Function for which the Global Maxima needs to be found:

Genetic Algorithm (GA):

Genetic algorithms are commonly used to generate high-quality solutions to optimisation and search problems by relying on biologically inspired operators such as mutation, crossover and selection. In a genetic algorithm, a population of candidate solutions to an optimization problem is evolved toward better solutions.

GA In Matlab:

In Matlab, 'ga' function calculates the minima for any given function.

Syntax:

1. x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun.nvars is the dimension (number of design variables) of fun.

2. x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

3. x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

4. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)

5. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

6. x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

7. x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

8. x = ga(problem) finds the minimum for problem, where problem is a structure.

9. [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
10. [x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

11. [x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

Methodology:

The optimisation of the Stalagmite function and comparison of its statistical behaviour is done in three ways:

1. Without upper and lower limits - Unbounded
2. With upper and lower limits - Bounded
3. By increasing the number of iteration by increasing population size.

Matlab Script:

clear all
close all
clc

% Input Arrays
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% 2D Mesh
[xx,yy] = meshgrid(x,y);
iterations = 50;

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

figure(1)
hold on
surfc(xx,yy,-f)
shading interp
[inputs,f_val] = ga(@Stalagmite,2);

% Study 1 Statistical behaviour - Unbounded 

for i = 1:iterations
    [inputs,f_max(i)] = ga(@Stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
colorbar
plot3(xopt,yopt,-f_max,'marker','o','markersize',5,'markerfacecolor','r')
title('Statistical Behaviour - Unbounded inputs')
subplot(2,1,2)
plot(-f_max)
xlabel('Iterations')
ylabel('Function Maxima')

% Study 2 Statistical behaviour - Bounded 

for i = 1:iterations
    [inputs,f_max(i)] = ga(@Stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
colorbar
plot3(xopt,yopt,-f_max,'marker','o','markersize',5,'markerfacecolor','r')
title('Statistical Behaviour - With upper and lower limit (Bounded)')
subplot(2,1,2)
plot(-f_max)
xlabel('Iterations')
ylabel('Function Maxima')

% Study 3 Statistical behaviour - With Increased Population Size

options = optimoptions('ga')
options = optimoptions(options,'PopulationSize',250);

for i = 1:iterations
    [inputs,f_max(i)] = ga(@Stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

figure(4)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
colorbar
plot3(xopt,yopt,-f_max,'marker','o','markersize',5,'markerfacecolor','r')
title('Statistical Behaviour - With Increased Population Size')
subplot(2,1,2)
plot(-f_max)
xlabel('Iterations')
ylabel('Function Maxima')
% Stalagmite Function

function [S] = Stalagmite(input_vector)

x = input_vector(1);
y = input_vector(2);

f1_x = (sin(5.1*pi*x+0.5))^6;
f1_y = (sin(5.1*pi*y+0.5))^6;
f2_x = exp(-4*log(2)*((x-0.0667)^2/0.64));
f2_y = exp(-4*log(2)*((y-0.0667)^2/0.64));

S = -(f1_x*f2_x*f1_y*f2_y);

end

Explanation of the code:

1. A function named Stalagmite is created

2. Returning function is given a negative sign which helps in finding the global maxima since 'ga' normally finds minima of a function.

3. Input arrays were initialised which defines the search space.

4. Created a 2D Array with the input array values.

5. No. of iteration was set.

6. The stalagmite function is evaluated and checked whether providing the maxima value for a particular set of inputs.

Study-1:

6. Using the syntax x = ga(fun,nvars) as [inputs,f_max(i)] = ga(@Stalagmite,2), statistical behaviour of the function without defining upper and lower limit is studied.

Study-2:

7. Using the syntax x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) as [inputs,f_max(i)] = ga(@Stalagmite,2,[],[],[],[],[0;0],[1;1]), statistical behaviour of the function by defining upper and lower limit is studied.

Study-3:

8.Using the syntax x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) as [inputs,f_max(i)] = ga(@Stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options), statistical behaviour of the function by modifying or increasing the population size is studied.

9. New population size option is defined using the syntax, options = optimoptions(SolverName) and options = optimoptions(prob,Name,Value) as options = optimoptions('ga') and options = optimoptions(options,'PopulationSize',250) respectively.

10. For all the three studies, surface for the function is created and global maxima values were marked by creating a 3D plot.

11. One more graph is created for '-f_max', which is actually the global maxima value for each set of input plotted against iterations (50).

Results:

Stalagmite function evaluated with ga without limits (unbounded):

Study-1:

Statistical Behaviour-Without limits (Unbounded)

Study 2 :

Statistical Behaviour - Bounded ( With upper and lower limits)

Study 3:

Statistical Behaviour - After increasing the population size

Conclusion:

1. In Study-3, the global maxima is close to 1 for almost every iteration except for one where the global maxima value is shown as 0.84 approx.
2. Study 3 gives better results when compared to study 1 and study 2.