Processing a Stalagmite Function using Genetic Algorithm

Processing a Stalagmite Function using Genetic Algorithm

1. AIM:

To optimize the stalagmite function to obtain global maxima

2. THEORY:

- Genetic Algorithm is a optimization technique which is used to solve problems. This technique is based on Darwin's theory of evolution which says, 'Only the fittest survives'.

- Similarly, here in Genetic Algorithm, say `f(x)` is a function which has to be optimized to find global minima.

- So, the optimization starts with a random solution values that are tested against the given function. As per Darwin's theory, only the fittest has to survive. Thus the solutions which are tested against the funcition are checked for their variables which show fitness trends and those solutions further produce a child. That child whill have all the good characteristics of his parents and some of his own. Such multiple children are then created by combining with different parents.

- Similarly, these children again are tested against the function to get a global minima. This process is repeated untill we get a global minima.

- How are offsprings traits generated?

A. Selection B. Crossover C. Mutation

A. Selection: Here, the best performing variables in a parent is directly passed on to the offspring. It is thus favoured for offspring creation.

B. Crossover: Here, the common variables between parents are selected and those will be passed on to the next generation / offspring.

C. Mutation: Here, the non-repeating variables or the diversity in the variables is preserved and passed on to the next generation.

Syntax of ga:

1. z = ga(a,b) : z is the local minima subjected to function a, and b is the no. of variables present in a.

2. z = ga(a,b,c,d,e,f,g,h) : local minima z is restricted in the range, g`<=`z`<=`h. The variables c,d,e,f refer to linear inequalities which in this case are none. thus we can put [] instead.

- How to optimize the function? (FLOW OF THE PROJECT)

1. Start with a population. In this case, we have 150 different solutions which lie equally between 0 and 0.6, both included.

2. Decide what will be the judging criteria. i.e. Decide the way in which you will tell if the variables present in solutions are fit or not.

here, the criteria used is a Stalagmite Function.

In this project,

`f_1x = [sin{5.1pix + 0.5)]^6`

`f_2x = e^(-4ln(2)((x - 0.00667)^2)/0.64`

`f_1y = [sin{5.1piy + 0.5)]^6`

`f_2y = e^(-4ln(2)((y - 0.00667)^2)/0.64`

Stalagmite function `f = f_1x*f_2x*f_1y*f_2y`

3. Proceed with the Selection, Crossover and Mutation processess.

- When does the genetic algorithm stop?

It stops when either of the following happens:

- The current generation value reaches the generation limit.

- The time limit is reached.

- The value of fitness function is very close or equal to the fitness limit

3. OBJECTIVES OF THE PROJECT:

- To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

- To plot graphs for all studies and for F maximum vs no. of iterations.

4. MATLAB CODE:

Code for the function used:

function [g] = stalagmite(input_vector)
   x = input_vector(1);           %input_vector contains the x values of the population taken into consideration
   y = input_vector(2);           %input_vector contains the y values of the population taken into consideration
   
   g1x = (sin(5.1*pi*x+0.5))^6;            %Fitness determining criterias (explained in theory)
   g1y = (sin(5.1*pi*y+0.5))^6;
   g2x = exp(-4*(log(2)/log(exp(1)))*((x-0.0667)^2)/0.64);
   g2y = exp(-4*(log(2)/log(exp(1)))*((y-0.0667)^2)/0.64);
   [g] = [g1x*g2x*g1y*g2y];
end

Code for finding the local minima: (population size is 150)

clear all
close all
clc

%Defining our search space
x = linspace(0,0.6,150);                      %population of 150 equally distributed between 0 and 0.6 both included
y = linspace(0,0.6,150);

%Creating a 2D mesh
[xx, yy] = meshgrid(x,y);                     %Creating a matrix containing only x and only y values

%Evaluating the stalagmite function
for i=1:length(xx)
    for j=1:length(yy)
        input_vector(1) = xx(i,j);            %Assigning a particular value of xx to the input_vector till the length of xx and yy is reached
        input_vector(2) = yy(i,j);
        f(i,j) = stalagmite(input_vector);    %Calcutating the fitness value as per the fitness function.
    end
end

%surface(xx,yy,f)
surfc(xx,yy,f)                                %create a surface to show the x, y and f values
xlabel('x value')
ylabel('y value')
%shadeing instead of lines
shading interp                                %to shade the surface instead of showinf grid lines
[inputs, fval] = ga(@stalagmite, 2)           %to evaluate the function using genetic algorithm and display values.

Result:

Here, We can see that the minimum value is 0 for the values -3.8544 and -30.5274 of x and y.

Now we have to find the maxima. So our fitness function must be modified in order to evaluate maxima.

Thus, the new fitness function is:

function [g] = stalagmite(input_vector)
   x = input_vector(1);           %input_vector contains the x values of the population taken into consideration
   y = input_vector(2);           %input_vector contains the y values of the population taken into consideration
   
   g1x = (sin(5.1*pi*x+0.5))^6;            %Fitness determining criterias (explained in theory)
   g1y = (sin(5.1*pi*y+0.5))^6;
   g2x = exp(-4*(log(2)/log(exp(1)))*((x-0.0667)^2)/0.64);
   g2y = exp(-4*(log(2)/log(exp(1)))*((y-0.0667)^2)/0.64);
   [g] = -[g1x*g2x*g1y*g2y];
end

Only a negative sign is added to the end multiplication so that maxima can be found out.

Now Case 1: The genetic algorithm will now run 50 times

numcases = 50;                           %how many times the genetic algorithm has been run
tic                                      %start the timer for measurement of time
%study1 stat behaviour
for k=1:numcases
    [inputs,fopt(k)] = ga(@stalagmite,2);   %solving the function using genetic algorithm and assigning solution values
    xopt(k) = inputs(1);                    %assigning solution values to x and subsequently y.
    yopt(k) = inputs(2);
end

study1_time = toc                           %end timer.

figure(1)
subplot(2,1,1)                              %Dividing the plot area into 2x1 grid and assigning the plot sequence as 1
hold on
surfc(xx,yy,-f)                             %Surface creation as explained in earlier stage
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded plot')
subplot(2,1,2)                              %Dividing the plot area into 2x1 grid and assigning the plot sequence as 1
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')
hold off

Output:

Case 2: Upper and lower bounds are set so as to reduce variety of offsprings from 0 to 0.5. Iterations are 50.

tic
%study2 - stat behaviuor with upper and lower bounds
for i=1:numcases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[.5,.5]);    %limits set for the range
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc

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

Output:

Case 3: Increased population size to 300, Number of iterations are 50. Upper and Lower limits set

%study3 increase ga iteration
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',300);           %increased population size to 300

tic
for i=1:numcases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[.5,.5],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc

figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded plot')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

Output:

5. ERRORS FACED:

Plot did not show surface plot. Neither of the 3 plots come up.

Fixed by changing the code -

6. RESULTS:

- From Study1 of maxima, we can see that there is too much variation between 0 and 1 thus a global maxima cannot be obtained from here.

- Study2 shows a more clearer objective by giving maxima values in a much smaller range i.e. between 0.7 to 1.

- Study3 clearly tells us that the global maxima is 1 because of decimal accuracy.