Week 4.1 - Genetic Algorithm

GENETIC ALGORITHM

AIM:To write a program in MATLAB to optimise the stalagmite function and to find the global maxima of the function.

THEORY:
STALAGMITE FUNCTION IN MATLAB:
A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function.For this in Matlab we are using a method called 'Optimization'.
OPTIMISATION:
1.Optimization refers to finding the values of inputs in such a way that we get the “best” output values.
2.The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.
3.The set of all possible solutions or values which the inputs can take make up the search space.
4.In this search space, lies a point or a set of points which gives the optimal solution.
5.The aim of optimization is to find that point or set of points in the search space.

GENETIC ALGORITHM:
1.Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics.
2.GAs are a subset of a much larger branch of computation known as Evolutionary Computation.
3.In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.
4.In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well.

The components of genetic algorith includes:
*INITIAL POPULATION:It is a subset of all the possible solutions to the given problem. The population for a GA is analogous to the population for human beings except that instead of human beings, we have Candidate Solutions representing human beings.An individual is characterised by a set of parameters known as GENES.Genes are joined into a string to form a chromosome.

*FITNESS FUNCTION:The fitness function simply defined is a function which takes a candidate solution to the problem as input and produces as output how 'fit' our how 'good' the solution is with respect to the problem in consideration.

*SELECTION:Individuals in a population are selected for reproduction according to their fitness values. In biology, fitness is the number of offspring that survive to reproduction. Given a population consisting of individuals identified by their chromosomes, selecting two chromosomes as parents to reproduce offspring is guided by a probability rule that the higher the fitness an individual has, the more likely the individual is selected. There are many selection methods available including weighted roulette wheel, sorting schemes, proportionate reproduction, and tournament selection.

*CROSSOVER: Selected parents reproduce the offspring by performing a crossover operation on the chromosomes (cut and splice pieces of one parent to those of another). In nature, crossover implies two parents exchange parts of their corresponding chromosomes. In genetic algorithms, crossover operation makes two strings swap their partial strings. Since more fit individuals have a higher probability of producing offspring than less fit ones, the new population will possess on average an improved fitness. The basic crossover is a one-point crossover.

*MUTATION: Mutation is an insurance policy against lost bits. It works on the level of string bits by randomly altering a bit value. With small probability, it randomly selects one bit on a chromosome then inverts the bit from 0 to 1 or vice versa. The operation is designed to prevent GA from premature termination, namely converging to a solution too early.

The GA syntax in MATLAB is given by,

EQUATIOS USED:
The function of the genetic algorithm is to generate minimum solution.So,the value of the stalagmite funtion is taken as negative to obtain the global maxima.
f(x,y)= f1.x*f1.y*f2.x*f2.y
where,
f1.x = (sin((5.1*pi*x)+0.5))^6
f1.y = (sin((5.1*pi*x)+0.5))^6
f2.x = exp(((-4*log(2))*(x-0.0667)^2)/0.64)
f2.y = exp(((-4*log(2))*(y-0.0667)^2)/0.64)
The global maxima is given by
f(x,y) = -(f1_x.*f1_y.*f2_x.*f2_y)

PROGRAM

FOR FUNCTION:

function[f]= stalagmite_func (input_vector)
x=input_vector(1);
y=input_vector(2);

f1_x = (sin((5.1*pi*x)+0.5)).^6;
f1_y = (sin((5.1*pi*x)+0.5)).^6;

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

[f] = -(f1_x.*f1_y.*f2_x.*f2_y);
end

FOR MAIN FUNCTION:

close all 
clc

%defining the search space

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

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

count=50; %no of count/iterations for the optimisation
tic  %tic starts the clock time for the 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_func(input_vector);
    end
end

%study 1-unbounded inputs
tic
for i=1:count
    [inputs,fopt(i)]=ga(@stalagmite_func,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

study_time1=toc  %toc stops the clock time and shows the end time

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('unbounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'MarkerFaceColor','r')

subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')


%study 2-bounded inputs

tic
for i=1:count
    [inputs,fopt(i)]=ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

study_time2=toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('Bounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'MarkerFaceColor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')


%study 3-bounded inputs with modified population size 

options=optimoptions(@ga)
options=optimoptions(options,'populationsize',200)

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

study_time3=toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('Bounded inputs with modified population size')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'MarkerFaceColor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')

PROCEDURE:

• 'close all' and 'clc' commands were used which is used to close all the matlab figure windows and used to clear all the texts from the command window respectively.
• we initialise the values of x and y by taking 150 values between the interval 0 and 0.6.
• 'count' command was used which denotes the number of iterations which we have considered as 50.
• Since we need to create a 3D surface plot, we take the 2D array of x and y using the meshgrid command and store them in the input_vector array.
• The 'Input_array' is used as an argument to call the stalagmite function.
• we create another function file for the stalagmite function.
• The value of stalagmite function is taken as negative since the genetic algorithm minimises the given function.
• The outputs is tored into results which contain maximas and fopt which contain the value at which the maxima is obtained.
• Now,the results are stored into xopt and yopt.
• The surface of x,y,-f is plotted to get the 3D plot.
• 'plot3' command was used which is used to make the plot of xopt,yopt and -fopt to plot the maximas.
• The 'tic' function is used which records the current time.
• The 'toc' function is used where the recorded value is used to calculate the elapsed time.
• Totally we make 3 studies namely unbounded inputs,bounded inputs,bounded inputs with modified population.

WORKSPACE:

OUTPUT:

UNBOUNDED INPUTS:

BOUNDED INPUTS:

BOUNDED INPUTS WITH MODIFIED POPULATION SIZE: