Finding the maxima of a function using genetic algorithm in MATLAB

1. AIM

To obtain global maxima using the optimized stalagmite function

2.OBJECTIVES

1. To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
2. To plot graphs for all studies and for F maximum vs no. of iterations.

3. THEORY

1. 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'.
2. Similarly, here in Genetic Algorithm, say `f(x)`is a function which has to be optimized to find global minima
3. 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.
4. The process of natural selection starts with the selection of fittest individuals from a population.
5. They produce offspring which inherit the characteristics of the parents and will be added to the next generation.
6. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving.
7. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.
8. This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.
9. Five phases are considered in a genetic algorithm.

• Initial population
• Fitness function
• Selection
• Crossover
• Mutation

4. Syntax of Genetic Algorithm

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 bounded within its range.

5.FLOW

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.
3. Following functions are used
   1. `f1 x = [sin (5.1 π x + 0.5 )]^6`
   2. `f2x = e ^(− 4*ln ( 2 )*( x − 0.00667 )^2/0.64`
   3. `f1y = [ sin(5.1 π y + 0.5)] ^6`
   4. `f 2 y = e ^(− 4 ln ( 2 ) ( y − 0.00667 )^2/ 0.64`
   5. `f = f 1 x ⋅ f 2 x ⋅ f 1 y ⋅ f 2 y`
4. Proceed with the selction,Crossover and mutation

5.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

6.MATLAB CODE

clear all
close all
clc
%Creating a search space
x = linspace(0,0.5,150);
y = linspace(0,0.5,150);
num_cases = 50;
%Creating a 2D mesh
[xx,yy] = meshgrid(x,y);
%Formulating 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);  % stalagmite function; 
    end
end
surfc(f)
xlabel('x value')
ylabel('y value')
shading interp
[inputs, fval] = ga(@stalagmite,2);   % genetic algorithm function

Explanation:

1. Initially we create a search space from which the points have to be picked up
2. The total number of cases or the iterations are predefined as 50. Even if the number of iterations are not mentioned, the genetic algorithm self-assumes the iterations as 50.
3. Then, by using the meshgrid command, all the values of x and y are saparately stored in a matrix form.
4. The various values of x and y thus obtained are substituted in the stalagmite function.
5. Once the values are obtained, the plot, i.e. the surface of all the values can be generated. The mathematical formulae are given in the stalagmite function which will be discussed below.

The result of the above function is:

Here, We can see that the minimum value is -0.7211 for the values 0.2477 and 0.0691 of x and y.

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

Stalagmite Function:

Explanation:

1. The function produces an output f. The name of the function is staagmite, which accepts input_vector as the input.
2. The 4 formulae are represented by f1x, f1y, f2x, f2y respectively
3. The final function f is the negative product of all the functions multiplied together.

function [f] = stalagmite(input_vector)

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

    f1x = (sin((5.1*pi.*x)+0.5)).^6;
    f1y = (sin((5.1*pi.*y)+0.5)).^6;
    f2x = exp(-4*log(2).*(((x-0.0667).^2)/0.64));
    f2y = exp(-4*log(2).*(((y-0.0667).^2)/0.64));

    f = -(f1x.*f1y.*f2x.*f2y);
end

Case Study 1:

tic
%Study 1 - Statistical behavior for default number of iterations, i.e. 50
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study1_time = toc
figure(1)
subplot(2,1,1)   %To make subplot alongwith the main plot;
hold on
surfc(xx,yy,f)
shading interp

% Plot3 command plots the x-value,y-value,f_optimum-value that genetic algorithm predict over 100 interations. 
plot3(xopt,yopt,fopt,'marker','o','markersize',4,'markerfacecolor','b') 
title('Unbounded Inputs')
subplot(2,1,2) %This function plots the optimum value over the iteration numbers
plot(fopt)
xlabel('Iterations')
ylabel('Function minima')
hold off

In case 1, the genetic algorithm will run for 50 iterations. Even if the number of cases are not mentioned, the GA runs for 50 times only by default.

The tic and toc command basically shows the amount of time required for the GA to compute the results.

OUTPUT FOR CASE STUDY 1:

Case Study 2:

%study 2 - Statistical behavior with upper and lower bounds
num_cases = 50;
options = gaoptimset('ga');
options = gaoptimset(options,'populationSize',200);
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
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','x','markersize',4,'markerfacecolor','b')
title('Unbounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minima')
hold off

The second case study sets the upper and lower bounds given to the function to reduce the number of offsprings.

OUTPUT FOR CASE STUDY 2:

Case Study 3:

%Study 3 - Statistical behavior -  increasing GA iterations
num_cases = 100;
options = gaoptimset('ga');
options = gaoptimset(options,'populationSize', 300);

tic
for i = 1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study3_time = toc

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)

The case study 3 refines the algorithm in order to obtain the maximum value. As shown in the plot, the peak of the function is represented by a red dot. This represents the global maxima of the function. As the number of iterations are increased in this case study, the time required for the computation is comparatively high, i.e. 20.4171 seconds.

OUTPUT FOR CASE STUDY 3:

ERRORS FACED:

The syntax of the Genetic Algorithm was written wrongly. I missed the '@' symbol in ga syntax, which was its integral part.

6. RESULTS:

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

- Case Study 2 shows a more clearer objective by giving maxima values in a much smaller range.

- Case Study 3 clearly tells us that the global maxima is close to 1 because of decimal accuracy, by increasing the number of iterations.