Finding Global maxima of a Stalagmite function using Genetic Algorithm in MATLAB

OBJECTIVE

To find the global maxima of a stalagmite function using MATLAB and to get the same output on all iterations using Genetic Algorithm command

STALAGMITE FUNCTION

Stalagmite is a type of formation of rocks in caves due to the sediments which has more number of peaks and valleys.The stalagmite function can be determined by the formula given below which is used to find the global maxima

PROGRAM : STALAGMITE FUNCTION

%stalagmite function

function[func] = stalagmite(input_vector)

a1 = 5.1*pi*input_vector(1) + 0.5;
b1 = 5.1*pi*input_vector(2) + 0.5;
a2 = (input_vector(1)-0.0667)^2 / 0.64;
b2 = (input_vector(2)-0.0667)^2 / 0.64;

x1 = (sin(a1))^6;
y1 = (sin(b1))^6;
x2 = exp(-4*log(2)*(a2));
y2 = exp(-4*log(2)*(b2));

%Func gives the values of stalagmite function
%Negative sign is to get the global maxima 

func = -(x1*y1*x2*y2);

end

This is function definition program where this can be called using the name stalagmite.The function consists of an input vector which has the input values of x and y where x is the first row and the y values in the second row

The final value of the stalagmite function is stored in \'func\' variable and is used in the main program which is saved as an array

\'Genetic Algorithm\' in Matlab is a default function and is denoted by the command \'ga\'.The main thing is that this function which is pre-determined in matlab always gives only the minimum values But it doesnt computes the global maxima

So for this we are going to make changes in the stalagmite function so that the value which is founded will be the global maxima of the stalagmite function.

In the final formula there is an \'-\' sign which is added .This is used to calculate the global maxima.If the sign is not included the plotting is done above and the minimum value is found for the function.The \'-\' sign which is included gives an inverted plot where the minimum value which is founded will be the global maxima.

Hence the stalagmite function is altered in such a way that the default \'ga\' code in Matlab gives the required global maxima

GENETIC ALGORITHM

The genetic algorithm is a method used for solving optimization problems, the process derived from genetic evolution.

The GA randomly repeatedly modifies the initial population which is derived from random samples to form new generations.It randomly selects a number of samples as its initial population and from which it generates the next set of samples by mutation , crossover and with the help of the fitness value.

The values which has the best fitness range are selected as the Elite values and it is moved directly to the next generation.From the set of elite values by mutation and crossover a series of samples are generated which is the generation.By the same repeated process the iterations goes on and on each iteration the minimum value becomes more specific and on increasing the number of iterations a particular minimum value can be obtained.

The Crossover children are created by combining the values of a pair of parents , which results in the population for the second generation.These parents are the one with best fitness values same as the Elite values.

The Mutation children are formed by altering the genes of the parents from the current population to form the population of the next generation.

By this way on each step the new population is created from the current population and the final minimum value for the function can be found.

GA Syntax

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

fun = The name of the function to be minimized

nvars = The number of variables that the function contains

A,b = These are the linear inequalities and it is given as \'[]\', if there are no inequalities

Aeq,beq = These are the linear equalities and it is given as \'[]\',if there are no linear equalities

lb = The values of x and y for the lower boundaries

ub = The values of x and y for the upper boundaries

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

options = This represents the parameters that are manually defined

Stopping Conditions

The stopping conditions of ga is to terminate or to increase the parameters of the ga as required so that the best optimal value can be found

Generations - stops when the number of generations reaches the value of generations

Time limit - stops after running for an amount of time in secondsequal to time limit

Fitness limit - stops when the value of the fitness function of the best point in the current function is less than or equal to the Fitness limit

There are more stopping conditions which can be used to change the parameters of the ga to get the global maxima of the required function

PROGRAM : Determining Global maxima by using GA

clear all
close all
clc

%input values
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 100 ;

[xx , yy] = meshgrid(x,y);

%Evaluation of 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) = stalgamite(input_vector);
    end
end

%case study  1 statistical behaviour

tic
for i = 1:num_cases
    [inputs,fopt1(i)] = ga(@stalgamite,2);
    xopt1(i) = inputs(1);
    yopt1(i) = inputs(2);
end
studytime_1 = toc

%Negative sign is used to plot the global maxima (inverting the plot)

figure(1)
subplot(2,1,1)
hold on
surfc(-xx,-yy,-f)
shading interp
plot3(-xopt1,-yopt1,-fopt1,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
xlabel(\'x axis\');
ylabel(\'y axis\');
title(\'unbounded inputs\')
subplot(2,1,2)
hold on
plot(-fopt1)
xlabel(\'Iterations\');
ylabel(\'Optimal values\');

%case study 2 with lower and upper bound

tic
for i = 1:num_cases
    [inputs,fopt2(i)] = ga(@stalgamite,2,[],[],[],[],[0 0],[1 1]);
    xopt2(i) = inputs(1);
    yopt2(i) = inputs(2);
end
studytime_2 = toc

%Negative sign is used to plot the global maxima (inverting the plot)

figure(2)
subplot(2,1,1)
hold on
surfc(-xx,-yy,-f)
shading interp
plot3(-xopt2,-yopt2,-fopt2,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
xlabel(\'x axis\');
ylabel(\'y axis\');
title(\'Bounded inputs\')
subplot(2,1,2)
hold on
plot(-fopt2)
xlabel(\'Iterations\');
ylabel(\'Optimal values\');


%case study 3 increasing ga iterations
%defining the paramteres of the default ga function

options = optimoptions(\'ga\');
options = optimoptions(options,\'PopulationSize\',400);

tic
for i = 1:num_cases
    [inputs,fopt3(i)] = ga(@stalgamite,2,[],[],[],[],[0;0],[1;1],[],options);
    xopt3(i) = inputs(1);
    yopt3(i) = inputs(2);
end
studytime_3 = toc

%Negative sign is used to plot the global maxima (inverting the plot)

figure(3)
subplot(2,1,1)
hold on
surfc(-xx,-yy,-f)
shading interp
plot3(-xopt3,-yopt3,-fopt3,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
xlabel(\'x axis\');
ylabel(\'y axis\');
title(\'Increased GA iterations\')
subplot(2,1,2)
hold on
plot(-fopt3)
xlabel(\'Iterations\');
ylabel(\'Optimal values\');

The above program gives the value of the global maxima for the stalagmite function.In addition to that 3 case studies are done to know about the statistical behaviour of the Genetic algorithm for a better understanding of the algorithm.

Evaluation of Stalagmite Function

The x and y values are defined with 150 values starting from 0 to 0.6 by using the linspace command

x = linspace(0,0.6,150)

Y = linspace(0,0.6,150)

Then an array is generated with the values of x and y and it is done using the meshgrid command

[xx yy] = meshgrid(x,y)

Then the loop is used to compute the stalagmite funcion for each values of x and y. Here the function call is done to compute the values and then all the values are stored in an array which is denoted by the variable \'f\'

As this part is evaluated we can see the value of \'f\' to be -1 for a set of input values which are found.But when it is computed repeatedly we could see that it gives a different set of inputs for a minimum value of \'f\' and this keeps on changing while it is iterated.

To analyse and to get the final optimized value for the stalagmite function 3 case studies are done

Csae Study 1 : This is to understand the statistical behaviour of the Genetic Algorithm and to see how it works on each iteration

Case Study 2 : The change occured when the boundary conditions are defined are analysed in this case

Case Study 3 : To get a single optimum value foe the stalagmite function which is achieved by mannually defining the Genetic algorithm

CASE STUDY 1 : Statistical behaviour

%case study  1 statistical behaviour
tic
for i = 1:num_cases
    [inputs,fopt1(i)] = ga(@stalagmite,2);
    xopt1(i) = inputs(1);
    yopt1(i) = inputs(2);
end
studytime_1 = toc

Here the \'ga\' command is executed for 50 times to get a set of input values and the minimum value for each set of inputs. The size of the input values and the fopt value remains (1*50) as it is iterated

This value is plotted using the \'plot3\' command which takes in the value for x , y and z and plots in the 3D space

The \'subplot\' command is used to seperate and plot two graphs one with the stalagmite function and the optimized valyues of the 50 iterations and the other for Fopt value and the number of iterations

subplot(n,m,p)

n = rows

m = columns

p = position

As we want to know how much time the ga takes to compute we are using the \'tic toc\' command and saving it in \'studytime\' variable

From the above graph we could see that there are different fopt values which are plotted for each iteration of the ga function

In the below plot on each iteration we are getting different outputs and this can be sorted out by adding the bound conditions

CASE STUDY 2 : With lower and upper bounds

%case study 2 with lower and upper bound

tic
for i = 1:num_cases
    [inputs,fopt2(i)] = ga(@stalagmite,2,[],[],[],[],[0 0],[1 1]);
    xopt2(i) = inputs(1);
    yopt2(i) = inputs(2);
end
studytime_2 = toc

We could see that the only change which is made here is that the ga command is given additional conditions

Here [0 0] gives the x and y values for the lower bound and [1 1] gives the value for the upper bounds

By defining the boundary condition, we are defining the search space for the ga function within which the values has to be computed

In the above plot we could see that the fopt values gets constant for and it is still variating between the boundary conditions . We could get a minimum number of fopt values.

CASE STUDY 3 : By increasing the iterations of ga

%case study 3 increasing ga iterations
%manual definition of parameters of inbuilt ga function

options = optimoptions(\'ga\');
options = optimoptions(options,\'PopulationSize\',400);

tic
for i = 1:num_cases
    [inputs,fopt3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],options);
    xopt3(i) = inputs(1);
    yopt3(i) = inputs(2);
end

In this case we are changing the parameters of the ga which is pre-determined. For which the \'optimoptions(name)\' command is used . While it is executed we could see the pre-determined parameters of the ga function and then we are manually changing the \'populationsize\'

By increasing the population size the initial sample that the \'ga\' takes is increased and so it is easy for the ga to find the values within the search space and to deliver the global maxima but the time increases as the population size is increased

Studytime_1 =6.8

Studytime_2 =11.2

Studytime_3 =32.5

This plot gives away the global maxima ,the point at which the \'f\' value is equal to 1

The significance of the num_cases is to check over the consistancy of the output values of the ga whether it gives the same output for all the iterations that it undergoes so that the optimal value i.e, the global maxima can be found

RESULTS

The stalagmite function is evaluated with which the global maxima is found using the genetic algorithm and the required graphs are plotted