Optimisation of stalagmite function using Genetic Algorithm

In this challenge we are writing code to calculate the global maxima of a stalagmite fuction

Theory:

Genetic algorithm heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Natural selection:

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

There are five phases to genetic algorithm

1)Population

2)Fitness function

3)selection

4)crossover

5)mutation

1)Population: Set of individuals are called a population. Every individual is a solution to the problem you want to solve.

2)Fitness function: This function determines the fitness of each individual and the individual will be selected based on there fitness score

3)Selection: Genetic algorithm selects the fittest individual and passes there genes to the the next generation.Two pairs of individuals(parents) are selected based on their fitness scores and there genes are passed to the next generation

4)Crossover: offspring is created by exchanging the genes of the parents and now the offspring is the fittest and he is added to the population

5)mutation: the newly created offspring is mutated that is there genes are flipped a bit to maintain diversity within the population and to prevent premature convergence.

The algorithm gets terminated once no more offsprings are created,then we are left with set of offsprings who are the fittest of all othere previous generations.

The same is used in various programming language like java,matlab,etc

Problem statements:

1)optimise the stalagmite function and find the global maxima of the function.

2)explain the syntax for ga

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

4)Plot graphs for 3 studies and for F maximum vs no. of iterations. Title and axes labels are a must.

Genetic algorithm in matlab:

\'ga\' is in-built function in matlab, it always minimises the function in matlab.

Now the syntax for \'ga\' is

[inputs, fval]= ga (fitness function, nvars, A, b, Aeq, beq, LB, UB, ).

inputs gives us the input values

fval returns the value of the fitness function.

fitness function is the function which determines the fitness score of the individual and ga minimises it

nvars are the number of variables in the function.

A and b is the linear inequality constraint

Aeq and beq is the equality constraint

LB and UB are the lower and upper bounds for the ga.

when there are no contraints then we have to leave the brackets empty in places of A,b,Aeq and beq([],[],[],[]).

In this program we have used optimoptions which is used when we want to change the default options example in this program the default population is 50 so we change it to 100.With more population we will have more options for the ga to get a fittest individual.

Fitness Function:-

function [f] = stalagmite(input_vector)

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

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

end

ga minimises the function but we need global maxima not minima,so we are multiplying minus with the function which gives inverted stalagamite function and the function values are negative and ga finds the minima of the negative function there by we are getting global maxima.

Main program:

clc
clear all
close all

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

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

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);
    end
end
num_cases = 100;

tic

for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study_time = toc
%plotting
figure(1);
subplot(2,1,1);
surfc(x,y,f);
shading interp;
xlabel(\'x-Values\'); 
ylabel(\'y-Values\');
zlabel(\'fitness fuction values\');
hold on
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Unbounded inputs\')
subplot(2,1,2)
plot(fopt)
xlabel(\'iterations\');
ylabel(\'function maximum\');

tic
%study 2 - Statistical behaviour with upper and lower bounds
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(x,y,f)
shading interp
xlabel(\'x-Values\'); 
ylabel(\'y-Values\');
zlabel(\'fitness fuction values\');
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Bounded inputs\')
subplot(2,1,2)
plot(fopt)
xlabel(\'Iterations\')
ylabel(\'Function maximum\') 

%study 3 increasing ga iterations
options = optimoptions(\'ga\');
options = optimoptions(options,\'PopulationSize\',200);

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(x,y,f)
shading interp
xlabel(\'x-Values\'); 
ylabel(\'y-Values\'); 
zlabel(\'fitness fuction values\');
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Bounded inputs\')
subplot(2,1,2)
plot(fopt)
xlabel(\'Iterations\')
ylabel(\'Function maximum\')
fopt(i) = -(min(fopt(i)));

graphs:

Study1:

time taken: 5.4735

Study2:

time taken: 7.2451

Study3:

time taken: 20.4970

the global maxima is at (0.0668,0.0668)

at fitness function value 1.000