Week 4 - Genetic Algorithm

OPTIMISATION OF A STALAGMITE FUNCTION

AIM: Writing a MATLAB code for optimisation of a stalagmite function using Genetic Algoritm

OBJECTIVES:

• To find the global and local maxima of a given function
• To obtaing a a single solution for the given problem irrespective of number of execution
• Optimize the function by adding various parameters and compare the result

GOVERNING EQUATIONS:

• `f_(1,x) = [sin(5.1*pi*x + 0.5)]^6`
• `f_(1,y) = [sin(5.1*pi*y + 0.5)]^6`
• `f_(2,x) = exp(-4*log(2)*((x-0.0667)^2)/0.64)`
• `f_(2,y) = exp(-4*log(2)*((y-0.0667)^2)/0.64)`

EXPLAINATION:

Genetic ALgorithm: Genetic algorithm is the method of finding optimum solutions for the problems based on the theory of evolution by Charles Darwin. It reflects the process of natural selection of the fittest individuals (parents) from the current generation (population) to produce an individual (child) of the next generation (population).

Phases in genetic algorithm are :-

1) Generation of initial population - Initially, individuals are randomly selected by algorithm and current population is generated which become parents for the next generation. In genetic algorithm, the set of genes of an individual is represented by a string. Usually, string is a set of binary values (1's and 0's).

2) Evaluation using Fitness Function - Fitness of every individual of the current population is evaluated using the fitness function f(x, y).

3) New Population - The process 1 and 2 are repeated until the required no of individulas are selected and the current population is generated.

4) Selection - Individuals from the current population are selected on the basis of their fitness value.

5) Crossover - It is the most significant phase in genetic algorithm. For each pair of parents, a crossover point is chosen at random. Everything before this point is copied from first parent and then everything after a crossover point from the second parent.

6) Mutation - Mutation is performed to prevent falling all solutions in population into a local optimum of solved problem. In mutation, some bits of the string are flipped (0 change to 1 and vice versa).

7) Termination - When two conditions are satisfied either fixed number of generations reached or the highest ranking solution's fitness is reaching or such that successive iterations no longer produce better results or both

Genetic Algorithm (GA) in Matlab :-

Genetic algorithm is run in matlab using solver name 'ga'. In Matlab, genetic algorithm gives minimum value of the function, but it can be used to calulate both minimum/maximum value of the function.

Syntax for ga - ga(function, nvars, A, b, Aeq, beq, lb, ub, nonlcon, IntCon, options)

ga - solver inbuilt in matlab

function - objective function (i.e function to be minimized or maximized)

nvars - number of design

A and b are matrix which represents linear inequality constraint such that A*x ≤">≤≤ b (if linear inequality constraints are not mentioned in the problem then defined as A=[] and b=[])

Aeq and beq are matrix which represents equality constraint such that Aeq*x = b (if equality constraints are not mentioned in the problem then defined as Aeq=[] and beq=[])

lb - lower bound/limit for the design variables (in matrix form)

ub - upper bound/limit for the design variables (in matrix form)

nonlcon - sets nonlinear constraints, if any

IntCon - sets integer constraint, if any

options - these are the attributes with which we can change the default functioning of ga, for example population size, which if not mentioned, ga takes random value.

Stopping Conditions for the Algorithm:

The genetic algorithm uses the following conditions to determine when to stop:

Modify Stopping Criteria:

ga uses four different criteria to determine when to stop the solver. ga stops when the maximum number of generations is reached; by default this number is 100 times the number of variables. ga also detects if there is no change in the best fitness value for some time given in seconds (stall time limit), or for some number of generations (maximum stall generations). Another criteria is the maximum time limit in seconds. Modify the stopping criteria to increase the maximum number of generations to 300 and the maximum stall generations to 100.

Maximizing vs Minimizing

Global Optimization Toolbox optimization functions minimize the objective (or fitness) function. That is, they solve problems of the form `min_x f(x)`

If you want to maximize f(x), minimize –f(x), because the point at which the minimum of –f(x) occurs is the same as the point at which the maximum of f(x) occurs.

CODE AND LINEWISE-EXPLAINATION:

clear all                   % clear all the variables stored 
close all                   % close all the figures and plot
clc                         % clear the workspace
 
%% Defining Search Space
x = linspace(0, 0.6, 150);  % creates x 1-D array of elements from 0- 0.6 of 150
y = linspace(0, 0.6, 150);  %% creates y 1-D array of elements from 0- 0.6 of 150

%% Creating a 2D mesh
[xx yy] = meshgrid(x, y);    % this cmd creates a 2_d array of above vectors

% Evaluation of stalagmite function
for i = 1:length(xx)            % loops for the given number of times
    for j = 1:length(yy)        % a nestef for loop (same)
        input_vector(1) = xx(i, j);    % assign value to the variable
        input_vector(2) = yy(i, j);    % assign value   to the variable
        F(i, j) = stalagmite(input_vector); %calling a function and giving input to it
    end 
end

% Number of iterations
num_cases = 50;       % setting number of iterations

% Optimization of Stalagmite Function for Global Maxima 
%% Study 1 - Statistical Behaviour 
tic                                  % helps to start the stopwatch timer
thestate = rng;                      % the state variable save to random number stream
for i = 1:num_cases                  % iterates through each number cases
    [inputs1, fval1(i)] = ga(@stalagmite, 2);%assigning the parameters to func 'ga'
    xopt1(i) = inputs1(1);                 % assing variable to outputs obtained
    yopt1(i) = inputs1(2);                 % assing variable to outputs obtained
end
rng(thestate);                       % Reset the stream and rerun ga
study1_time = toc                    % end the stopwatch and assign time to given var

figure(1)                          % to create a figure window
subplot(2, 1, 1)                   % to plot multiple figure
hold on                            % it helds the previous plot
surfc(xx, yy, F)                   % helps to create a surface contour plot
xlabel('X-value')                  % assigns name to x axis
ylabel('Y-value')                  % assigns name to y axis
shading interp                     % shades the surface contour to avoid complexity
% to plot the markers on the optimum function value points
plot3(xopt1, yopt1, fval1, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r')
title('Study 1 : Unbounded Inputs')   % gives title to constructed plot
subplot(2, 1, 2)                   % to create another plot on same window
plot(fval1) 
xlabel('Iterations')               % assigns name to x axis
ylabel('Function Maximum')         % assigns name to y axis

tic
%% Study 2 - Statistical Behaviour with Bounded Inputs
tic 
thestate = rng;
for i = 1:num_cases     % helps to allocate the upper and lowe bound to the 'ga'
    [inputs2, fval2(i)] = ga(@stalagmite, 2, [], [], [], [], [0; 0], [0.6; 0.6]);
    xopt2(i) = inputs2(1);
    yopt2(i) = inputs2(2);
end
rng(thestate);

               % MOST OF THE FUNCTIONS ARE REPEATED AS ABOVE IN THIS CASE
figure(2)
subplot(2, 1, 1)
hold on
surfc(xx, yy, F)
xlabel('X-value')
ylabel('Y-value')
shading interp
plot3(xopt2, yopt2, fval2, 'marker', 'o', 'Markersize', 5, 'markerfacecolor', 'r')
title('Study 2 : Bounded Inputs')
subplot(2, 1, 2)
plot(fval2)
xlabel('Iterations')
ylabel('Function Maximum')
study2_time = toc
 
%% Study 3 - Increasing population size    % optimpotions helps to add addition 
options = optimoptions('ga','PopulationSize',180)  %-parameters to the 'ga'
tic                             % increases the populatoon size or sample number
thestate = rng;
for i = 1:num_cases            % refer above syntax section for following:
    [inputs3, fval3(i)] = ga(@stalagmite, 2, [], [], [], [], [0; 0], [0.6; 0.6],[],[],options);
    xopt3(i) = inputs3(1);
    yopt3(i) = inputs3(2);
end
rng(thestate);
figure(3);
subplot(2, 1, 1);
hold on
surfc(xx, yy, F);
xlabel('X-value');
ylabel('Y-value');
shading interp;
plot3(xopt3, yopt3, fval3, 'marker', 'o', 'Markersize', 5, 'markerfacecolor', 'r')
title('Study 3 : Bounded Inputswith given population size');
subplot(2, 1, 2);
plot(fval3);
xlabel('Iterations');
ylabel('Function Maximum');
study3_time = toc

%% to find the  Maxima at a iteration    
[Max Ival] = max(abs(fval3)) % max function helps to find the maximum value of fval
                                 % and the corresponding iteration(Ival)

FUNCTION CODE:

function[F] = stalagmite(input_vector)
    x1 = input_vector(1);
    y1 = input_vector(2);
    f1_x = (sin(5.1*pi*x1 + 0.5)).^6;
    f2_x = exp(-4*log(2).*((x1-0.0667)^2)/0.64);
    f1_y = (sin(5.1*pi*y1 + 0.5)).^6;
    f2_y = exp(-4*log(2).*((y1-0.0667).^2)/0.64);
    F = -(f1_x.*f2_x.*f1_y.*f2_y);

** NOTE: NO MATTER HOW MANY TIMES THE PROGRAM IS EXECUTED THE RESULTA WILL ALWAYS BE THE SAME **

OUTPUT:

Study 1:

• This shows that when no constrains and options are set the graph is irregular and many maxima points are obtained
• And study time required is less due to no constrains and hence irregular points are scattered all over places

Study 2: Setting Bound

• As we could see much better plot is obtained and the points are nearly confined to a closer space
• this could be optimised more by adding more parameters to genetic algorithm function

Study 3: Setting population size

• As we could see that the time required for this plot is much more than hte previous cases
• Setting population number helps to obtain Local and Global Maxima
• We could get the global Maxima and the number of the iteration

PROBLEMS OR ERRORS FACED:

This Error are the result of Typos or use of incorrect commands and were solved by Manual Debugging

Major problem faced was obtaining different results for each run od the program, which was solved by using 'rng' function to get same results

CONCLUSION:

1. We could obtain the global and local maxima of the function and hence undertake various ways to improve our result
2. We learnt about the optimisation of a function and understand the working of Genetic Algorithm in MATLAB
3. As we increase the iteration or number of cases we get the clear idea of the functionality and hence helps in obtaining the local and global maxima

REFERENCES:

• https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f6243
• https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f6243