Week 4 - Genetic Algorithm

OBJECTIVE:

Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Clearly explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.

Make sure that your code gives the same output, even if it is made to run several times.

Plot graphs for all 3 studies and for F maximum vs. no. of iterations. Title and axes labels are a must, legends could be shown if necessary.

SOLUTION:

A Genetic Algorithm (GA) is a search algorithm, inspired by Charles Darwin’s Evolution Theory and Random Sampling method, used to produce the best offspring of next generation. The algorithm is analogous to the process of naturally selecting the fittest individuals in a population, who then produces the next generation offspring, having better fitness. The process keeps on iterating till the fittest individuals are found. The same principle can be applied for a search problem, where we consider a set of solutions, out of which the best solutions are found out.

The process happens over six steps:

1. Initial population: The process starts with a set of individuals, collectively called as the population, and each of it is a solution to the problem to be solved. The singular parameters in the individuals (also called chromosomes) are called Genes. To better understand the concept, each variable in a problem is the gene, a combination of these variables give us the solution and a collection of the solutions give us the population.

2. Fitness function: Fitness function is used to determine the fitness of an individual (or solution). Each solution is given a fitness score and those with the highest score will be selected to find the best solution.

Selection: In this step, the fittest of the solutions are selected and passed to the next step. A pair of the solution is selected, considering the highest score, and this pair has the highest probability of finding the best solution.

Crossover: When the pair of solution is used to find the best solution, some variables are exchanged between them, depending on a randomly selected crossover point. This exchange creates offspring of these solutions.

5. Mutation: In this step, the variables in a solution is randomly flipped among each other, but this has low probability.

6. Termination: Finally, the algorithm is terminated when the newly created offspring does not differ significantly from each other and the population (or solution) is said to be converged. These final offspring are the solution to the problem.

Aim:

The aim of the project is to find the global maxima of the function f(x,y) as defined below. Now the ‘ga’ command calculates the global minima of a function by default. Hence to find the global maxima of this function, we put a negative sign before the function, such that the ‘ga’ command finds the global minima of -f(x,y), which is the global maxima of f(x,y).

In order to find the global maxima of f(x,y), we find the global minima of function ‘y’.

Program:

clear all
close all
clc

%Defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

num_cases = 50;        %defining number of iterations of GA

%creating 2D mesh
[xx, yy] = meshgrid(x,y);

%Evaluating the stalagmite function for all combinations of xx and yy

for i = 1:length(xx)
    for j = 1:length(yy)
        input_value(1) = xx(i, j);
        input_value(2) = yy(i, j);
        f(i,j) = stalagmite(input_value);    %calling the stalagmite fuction
    end
end

%Study 1 - Statistical Behaviour with no bounds

tic
for i = 1:num_cases
    [input1,fmax1(i)] = ga(@stalagmite, 2);    %invoking the ga algorithm
    xopt1(i) = input1(1);
    yopt1(i) = input1(2);
end

study1_time = toc;     %measurement of time taken for computation of study 1

figure(1)
subplot(2,1,1);   %creating subplots in the figure
hold on
surfc(xx, yy, -f);    %creation of surface profile
shading interp;       %eliminating shading lines in he surface profile
plot3(xopt1, yopt1, -fmax1, 'marker','o', 'markersize', 5,'markerfacecolor','r');
title('Unbounded inputs');
xlabel('x optimum');
ylabel('y optimum');
subplot(2,1,2);            %creating 2nd subplot
plot(-fmax1);
xlabel('Iterations');
ylabel('Function maximum');

%Study 2 - Statistical behaviour with upper and lower bounds

tic
for i = 1:num_cases
    [input2,fmax2(i)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[1;1]);
    xopt2(i) = input2(1);
    yopt2(i) = input2(2);
end

study2_time = toc;

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

%Study 3 - Increasing GA iterations

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

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

study3_time = toc;

figure(3)
subplot(2,1,1);
hold on
surfc(xx, yy, -f);
shading interp;
plot3(xopt3, yopt3, -fmax3, 'marker','o', 'markersize', 5,'markerfacecolor','r');
title('Plot with increased GA iterations');
xlabel('x optimum');
ylabel('y optimum');
subplot(2,1,2);
plot(-fmax3);
xlabel('Iterations');
ylabel('Function maximum');

%Printing all output results

clc

fprintf ('\n Study 1 : Unbounded Statistical Behvaiour');
fprintf ('\n The Time taken for the study 1 is : %f',study1_time);
fprintf ('\n X and Y coordinates for maximum value: %f,%f',input1(1),input1(2));
fprintf ('\n The Global Maxima of the Function is : %f',-(mean(fmax1)));

fprintf ('\n\n Study 2 : Statistical Behvaiour with upper and lower bounds');
fprintf ('\n The Time taken for the study 2 is : %f',study2_time);
fprintf ('\n X and Y coordinates for maximum value: %f,%f',input2(1),input2(2));
fprintf ('\n The Global Maxima of the Function is : %f',-(mean(fmax2)));

fprintf ('\n\n Study 3 : Statistical Behvaiour with increased iterations');
fprintf ('\n The Time taken for the study 3 is : %f',study3_time);
fprintf ('\n X and Y coordinates for maximum value: %f,%f',input3(1),input3(2));
fprintf ('\n The Global Maxima of the Function is : %f',-(mean(fmax3)));

function [f] = stalagmite(input)

f1x = (sin(5.1*pi*input(1)+0.5))^6;

f1y = (sin(5.1*pi*input(2)+0.5))^6;

f2x = exp(-4*log(2)*((input(1)-0.0667)^2/0.64));

f2y = exp(-4*log(2)*((input(2)-0.0667)^2/0.64));

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

end

Output:

Explanation:

The aim of the program is to find the global maxima of the stalagmite function using the Genetic Algorithm function in MATLAB. The first step is to define the search space in which the global maxima should be found out. Two arrays x and y were defined using the linspace command and a 2D matrix was created from these inputs using the meshgrid command. The next step is to find the function values at each of these inputs and we use the for loop command. This study involves evaluating the global maxima using three different statistical approach; unbounded inputs, inputs with upper and lower bounds and increasing the number of GA iterations. A function named stalagmite was defined, which when called, calcultes the function value at each study point and returns this value.

For each of the studies, the genetic algorithm was invoked for the stalagmite function and the outputs were stored in xopt1, yopt1 and fmax1. The time taken for the computation was measured using the tic toc function. The results obtained in each study was displayed using multiple plots.

Syntax of ga:

We have used 3 different syntax for ga in the above program.

1. Unbounded Inputs:

[x, fval] = ga(fun,nvars)

It finds an unconstrained minimum for the objective function ‘fun’ having number of design variables equal to ‘nvars’. The coordinates, at which the minimum value is found, is stored in ‘x’ and the value is stored in ‘fval’.

2. Upper and lower bounds:

[x, fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

Here it find the minimum value when a set of lower and upper bounds are defined on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub.

Set A=[] and b=[] Aeq=[] and beq=[] if no linear equalities exist.

3. Increased GA iterations

[x, fval] = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

It minimizes the function with the default optimization parameters replaced by values in options. Set nonlcon=[] and IntCon=[] if no nonlinear constraints exist. Create options using optimoptions.

References:

1. Introduction to Genetic Algorithms — Including Example Code : https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

2. https://in.mathworks.com/help/gads/ga.html#d120e39488