Optimisation of stalagmite function using Genetic Algorithm

AIM- Optimisation of stalagmite function using Genetic Algorithm

GOVERNING EQUATIONS-

The stalagmite function to be optimised is given below.

number of variables = 2

OBJECTIVES-

Write a code in MATLAB to optimise the stalagmite function.

Case 1 – Statistical behaviour study of ga

Case 2 - Statistical behaviour study of ga with bounds (upper and lower)

Case 3 - Statistical behaviour study of ga with bounds and increase of population

THEORY-

Genetic algorithm is a method to solve smooth or non-smooth optimisation problems with any types of constraints including integral constraints. It is based on natural selection process from Darwin’s evolution theory. At every iteration, the algorithm produces parents to produce children of three categories, namely ELITE, CROSSOVER and MUTATION. These will be explained later.

OPTIMISATION – optimisation is the decision making process to provide the best result under certain constraints. It is done by two methods. Several iterations are done to find the most feasible and reliable solution for the set of problems.

It is done by 2 techniques-

• Deterministic Method: dependent on end conditions
• Stochastic Method: dependent on probability method

Flow Chart for working of optimisation-

Further study on Genetic Algorithm

Terminologies in Genetic Algorithm-

Fitness Functions

The fitness function is the function to be optimized. This function has to be created separately and then called in the GA function wherever needed

Individuals

An individual is any point to which you can apply the fitness function. Score is the value we get after putting individual in fitness function. An individual is sometimes referred to as a genome and the vector entries of an individual as genes.

Populations and Generations

A population is an array of individuals. The same individual can appear more than once in the population.

At each iteration, the genetic algorithm performs computations on the current population to produce a new population, called a new generation.

Diversity

Diversity refers to the average distance between individuals in a population. A population has high diversity if the average distance is large; otherwise it has low diversity. Diversity is essential to the genetic algorithm because it enables the algorithm to search a larger region of the space.

Fitness Values and Best Fitness Values

The fitness value of an individual is the value of the fitness function for that individual. Since the genetic algorithm is for the minimum of the fitness function, the best fitness value for a population is the smallest fitness value for any individual in the population.

Parents and Children

To create the next generation, the genetic algorithm selects certain individuals in the current population, called parents, and uses them to create individuals in the next generation, called children. The algorithm selects parents that have better fitness values.

Understanding the steps in Genetic Algorithm-

The algorithm creates a random population (a set of individuals). This population contains parents which are to create next generation. The generation is created in a specific way. The algorithm is first taking some members and compute fitness value for them. This is called the raw fitness value. These raw fitness values are scaled to form expectation value which is basis of selection for parents. Now the children are to be formed on the basis of fitness value.

• Elite - individuals in the current generation with the best fitness values. These individuals automatically survive to the next generation.

• Crossover - created by combining the vectors of a pair of parents. Two random parents are chosen to create children.

• Mutationchildren - created by introducing random changes, or mutations, to a single parent. The changes are random so to insure the stability of children.

The algorithm stops when stopping conditions as time limit, fitness limit, numbers of generations, stall generations, stall time limit etc. are reached.

COMMANDS USED –

ga (@function, no of variables) – this function is used for the minimizing the fitness function.

Optimoptions(options,’populationsize’, number)- this is to fix the amount of populations(or any other parameter) taken for one iteration.

tic and toc – to note the time lapsed while running a syntax.

subplot (2,1,1) – to produce more than one graph in a figure.

mesh grid (x, y)- to make a matrix out of given parameters

surf (x, y, function)- to produce the surface graph for fitness function

shading interp - to remove grids from the produced surface.

plot3(x, y, z) - to plot a graph in 3D

PROCEDURE-

The procedure consists of two scripts. One is to produce the stalagmite function (fitness function) and another is for applying the Genetic Algorithm (ga) to the fitness function. The input for the Genetic Algorithm code is given as ‘inputs’ which is defined to be a matrix of x and y components.

For the stalagmite function, the inputs are created and hence the coded specially to take inputs from the matrix created for X and Y components. The equations are provided as functions. The set of functions were merged for resultant function which acted as the fitness function. Negative sign is provided as we are to maximise the stalagmite function. The code is as shown below.

function[res]=equations(input)

%values of x and y
x= input(1);  
y= input(2);

%stalagmite function
fx = (sin((5.1*pi.*x) + 0.5)).^6;
fy = (sin((5.1*pi.*y) + 0.5)).^6;

gx = exp((-4)*log(2)*((x - 0.0667).^2)/0.64);
gy = exp((-4)*log(2)*((y - 0.0667).^2)/0.64);

res = -( fx*gx*fy*gy );

end

The code for ‘genetic algorithm’ has been given below. The steps consist of making an input array for x and y components. Then these components are regrouped as a mesh using meshgrid(x,y) command. This is the input which stalagmite function has to recognise. Now we created two ‘for’ loops for inputting the values of grids as the inputs for stalagmite function and applied for the length of grid for size of separate array of mesh (xx and yy). The stalagmite function is called using the function f ( i, j). After the end of cycle, surface graph is plotted to show the behaviour of function.

Note : The 2nd code script has been splitted into parts according to different cases. however all the sections are to be merged together for proper functioning of code.

clear all
close all
clc

%arrays for x and y values

x= linspace(0,0.6,150);
y= linspace(0,0.6,150);

%to form 2D mesh

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

%evaluating the fitness function

for i= 1:length(xx)
    for j= 1:length(yy)
        input(1)= xx(i,j);
        input(2)= yy(i,j);
        
        f(i,j)= equations(input);
    end
end

figure(1)
surf(xx,yy,-f);
shading interp
title('stalagmite function')

CASE 1 – In case 1, the for loop is formed for a range of 50 iterations. The loop consists of calling of function ‘ga’ for fitness function ‘equations’ and number of variables are 2. The LHS consists of ‘inputs’ and optimum value as ‘fval(i)’ which are later provided the input from ‘x_opt’ and ‘y_opt’. Not to mention, ga takes inputs at random, despite of providing the range of initial points.

%case 1 - unbounded inputs
tic                %for time calculation of section - start
num_cases= 50
for i=1:num_cases
    [inputs,fopt(i)]= ga(@equations,2);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
end
case1=toc         %for time calculation of section - start

figure(2)
subplot(2,1,1)      %for more than one plot in a figure
surf(xx,yy,-f)
xlabel('x value')
ylabel('y value')
zlabel('function value')
title('unbounded inputs')
shading interp       %to remove the grid lines from graph
hold on
plot3(x_opt,y_opt,-fopt,'marker','o','markersize',5)   %to denote the points for 
                                                           optimised values

subplot(2,1,2)
plot (-fopt);               % to denote the points in a plot against iterations
xlabel('number of iterations')
ylabel('max value')

The graph is plotted using ‘surf(x,y,-f)’ and shading interp commands. Further plot is given by ‘plot3(x_opt,y_opt, -fval)’ command for points in 3D and to study the random point selection with optimal value of ga. A separate plot for maximum value against no of iteration is provided using ‘plot’ command in same figure by using ‘subplot (2,1,2)’ command.

RESULT ANALYSIS – The minus signs in the plotted graphs are to provide the maximum optimised solution rather than the minimised as ‘ga’ gives in normal conditions. The results show how a ‘ga’ takes random values as input. The individuals chosen for population are even out of provided range. The optimum values show a great variation with every iteration between 0 to 1.

CASE 2 – In case 2, the same loop as case 1 is repeated for 50 iterations except the working of ga in which upper and lower bounds are induced. The lower bound was kept as (0;0) whereas the upper bound was fixed at (1;1). The bounds are in the order (x, y). The ga code is explained below –

ga(@equations,2,[],[],[],[],[0;0],[1;1]) - defines a set of lower and upper bounds on the variables, x and y, so that a solution is found in the range 0 ≤ x ≤ 1. Since no linear equalities or inequalities are present for the function, the four void brackets are present.

%case 2 - bounded inputs

tic
num_cases= 50
for i=1:num_cases
    [inputs,fval(i)]= ga(@equations,2,[],[],[],[],[0;0],[1;1]);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
end
case2=toc

figure(3)
subplot(2,1,1)
surf(xx,yy,-f)
xlabel('x value')
ylabel('y value')
zlabel('function value')
title('bounded inputs')
shading interp
hold on
plot3(x_opt,y_opt,-fval,'marker','o','markersize',2,'markerfacecolor','r')

subplot(2,1,2)
plot (-fval);
xlabel('number of iterations')
ylabel('max value')

The graphs are plotted in the same manner as 1.

RESULT ANALYSIS- The results show how a ‘ga’ takes random values as input from the range [0,1] for both x_opt and y_opt. The optimum values show a great variation with every iteration between 0.4 to 1. The number of fuction value points has decreased which signifies that optimum value's range has decreased. The computation time increased but so did the accuracy.

CASE 3 - In case 3, the same loop as case 1 and 2 is repeated for 50 iterations except the working of ga in which upper and lower bounds along with population size has been fixed. The lower bound was kept as (0;0) whereas the upper bound was fixed at (1;1). The bounds are in the order (x, y). The population size has been splitted in two sections with size of 120 and 420. ga code is explained below –

options=optimoptions(ga) – to activate the function optimoptions. It is used for manually control parameters for optimisation.

options=optimoptions(options,’populationsize’, number)- to set the parameter manually. The function name along with parameter code name and value is inserted here.

ga(@equations,2,[],[],[],[],[0;0],[1;1],[],[],options) –

• The first 4 brackets after “no. of variables” are for local minimum of linear equalities and inequalities. Since, no linear equalities or inequalities are present for the function, the four void brackets are present.
• A set of lower and upper bounds on the variables, x and y, so that a solution is found in the range 0 ≤x ≤ 1.
• The nonlinear equalities and inequalities are solved using “nonlcon” as two vectors Ceq and C respectively. Here no inequalities are present, so it is left void.
• Now, the linear equalities and inequalities are solved by IntCon and since no linear inequality is present, it’s void too.
• Finally, we apply the options which contains parameter change. Here the parameter is population size kept as 120 and 420 in two different subcases.

%case 3.1 - bounded inputs with population size 120

options = optimoptions('ga');
options = optimoptions(options, 'populationsize',120);
tic
num_cases= 50
for i=1:num_cases
    [inputs,fval(i)]= ga(@equations,2,[],[],[],[],[0;0],[1;1],[],[],options);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
end
case3_1=toc

figure(4)
subplot(2,1,1)
surf(xx,yy,-f)
xlabel('x value')
ylabel('y value')
zlabel('function value')
title('bounded inputs with population size = 120')
shading interp
hold on
plot3(x_opt,y_opt,-fval,'marker','o','markersize',5,'markerfacecolor','r')

subplot(2,1,2)
plot (-fval);
xlabel('number of iterations')
ylabel('max value')

%case 3.2 bounded inputs with population size= 420

options = optimoptions('ga');
options = optimoptions(options, 'populationsize',420);
tic
num_cases= 50
for i=1:num_cases
    [inputs,fval(i)]= ga(@equations,2,[],[],[],[],[0;0],[1;1],[],[],options);
    x_opt(i) = inputs(1);
    y_opt(i) = inputs(2);
end
case3_2=toc

figure(5)
subplot(2,1,1)
surf(xx,yy,-f)
xlabel('x value')
ylabel('y value')
zlabel('function value')
title('bounded inputs with population size = 420')
shading interp
hold on
plot3(x_opt,y_opt,-fval,'marker','o','markersize',5,'markerfacecolor','r')

subplot(2,1,2)
plot (-fval);
xlabel('number of iterations')
ylabel('max value')

The graphs are plotted in the same manner as 1 and 2.

RESULT ANALYSIS-

For Population Size = 120: - The results show how a ‘ga’ takes random values as input from the range [0,1] for both x_opt and y_opt. The optimum values show a great variation with every iteration between 0.85 to 1. The number of optimum selected points has decrease to 4. The computation time increased but so did the accuracy.

For Population Size = 420: - The results show how a ‘ga’ takes random values as input from the range [0,1] for both x and y. The optimum values show a great variation with every iteration closer to 1. The number of random selected points has decrease to 1 which is the optimum point for maximum value. The computation time increased but so did the accuracy.

CONCLUSION-

Case 1 is not feasible as the number of optimum points are too high and range of optimum value is also high.

Case 2 is preferable over case1 as the number of optimum points decreased drastically and hence finding the maximum value gets better. Hence limiting the boundary condition gives better results by ga. But the computation time increased by 1.5 seconds.

Case 3 can be said to be most preferred than previous 2 cases when comes to accuracy. But the computation time is increasing which is not so feasible. The number of optimum points decreased to 4 (case with 120 population size) and 1 (case with 420 population size). Hence, providing control over parameters has proven to be effective for ga. The global maximum value for the stalagmite function is closer to 1.

fig. time taken by each case

Conclusion was also that increasing population size increases the accuracy. Also every run for the codes provide a different approach of ga but the ultimate answer for global maxima remains constant.

So increasing the accuracy with decreasing the upper and lower bounds can increase further accuracy with time.

the maximum value of the stalagmite function at (0.06683,0.06683).

We learned how Genetic Algorithm works and how it can be improved while working in sectors like -

• optimisation
• economics
• neural networks
• image processing

ERRORS – no major errors other than forming of stalagmite functions.

SOURCES -

https://skill-lync.freshdesk.com/support/solutions/articles/43000584189-genetic-algorithm-explained-

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

https://in.mathworks.com/help/gads/some-genetic-algorithm-terminology.html