Week 4 - Genetic Algorithm

Objective: Generating stalagmite function and optimising it using Genetic algoritm.Finding global maxima.

Theory: Genetic Algorithm-> It is an optimisation technique based on priciples of 'Genetics & Natural Selection'.

It is freequently used to find optimal solutions though some times for complex problems with proper selection of initial population we can land to near optimal solution.

The main aim of GA is to find the inputs in such a way that we get the best outputs. The algoritm repeatedly modifies a population of Individual solutions. These solutions then undergo recombination & mutation,producing new children & the process is repeated over various generations. Each individual is assigned a fitness value & the fitter individual i.e Elite groups are given higher chance to pass or mate & yield more effective results.

Now with reference to our objective.We have to use GA to find global maxima.But inbuilt GA in matlab only minmizes a function i.e on solving the function we may end up getting Global minima while our requirement is Global maxima.

So here we will be changing the function part little bit so that GA's minima is our maxima.

Defining problem through coding:

Writing a code for given Stalagmite Function.

Our main function let Z(f1,f2,f3,f4) this individual functions multication will give main stalagmite function.

Below is the code for same.

function [z] = stalagmite(input_vector)


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

x=input_vector(1); % input variable to stalagmite function
y=input_vector(2); % input variable to stalagmite function

%input_vector=[input_vector(1) input_vector(2)];
 
f1=sin(5.1*pi.*x+0.5).^6;


f2=sin(5.1*pi.*y+0.5).^6;

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

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




z=-(f1.*f2.*f3.*f4);  % stalagmite function (- sign is included sinces GA always minimise the function)

end

Since GA only minimizes a function we have used a Negative sign for same intentionally.

Let us use a script to generate the function and find it's global minima.

clear all
close all
clc
% defining our search space

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
% creating a 2 d mesh
[xx,yy]=meshgrid(x,y);

%evaluating the stalagmite 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(input_vector);  % passing input vector into function and generating 
                                         the stalagmite function
    end
end

surf(xx,yy,f) % creating a 3-d surface plot
xlabel('x value')
ylabel('y value')
shading interp % Interupting grids on surface plot
[inputs,fval]=ga(@stalagmite,2) % Passing the function into an inbuilt GA.
                                % Storing optimum value in 'fval'

By taking inputs from input_vector array we have successfully get a stalagmite function with many peaks and valleys. We pass that fucnton in ga to optimise. The results we get is stored in fval with respective inputs.

One thing we noticed that each time we run the code we will get different values of inputs and fval. This is because

Each time GA runs the inital poulation sets it considers are different.

Now we can overcome this by iterations.That is solving the equation number of time till it coverges i.e the solution is not changing with the further iterations.

Next code is given below with iterations

i.e Solving same equation again & again. Till solution converges to a single point or we get same results again.

clear all
close all
clc
% defining our search space( but GA doesn't consider it as a search space)

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

num_cases=50;
f=get_stalagmite(x,y); % Getting a stalagmite function

tic  
% tic & toc command for calculation of the study time to reach optimal solution

% I Statistical behaviour( Running GA 50 times)
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study1_time=toc

% plotting the inputs and results obtained
figure(1)
subplot(2,1,1) % subplot to have multiple plot in same figure window
hold on
surfc(x,y,f)  % creating a 3-d surface plot
xlabel('x value')
ylabel('y value')
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
% plot3 plots coordinates in 3d space
title('Unbounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

This time we can clearly see that for each iteration we get a different results due to random sampling. And the result is quite messy to even infer a local minima.

From the second sub plot we can see the solution range lies between 0 & -1. So next we can use this information to set upper and lower bounds of variables x & y in GA syntax.

Syntax of GA:

x=ga(fun,nvars)

Minimzes the fuction(fun) and find unconstrained minimum x. 'nvars' refers to the number of variables in the function.

x=ga(fun,nvars,A,b,Aeq,Beq)

Finds local minima x subjected to linear inequalities(A*x<=n) and linear equalities(Aeq*x=beq)

x=ga(fun,nvars,A,b,Aeq,Beq,lb,ub)

In addition to previous caes we can add upper and lower bound( ub,lb) to find solution in a given range.

If passing parameters doesnot exist set it to [].

Below is the code after setting bounds.

clear all
close all
clc
% defining our search space

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

num_cases=50;
f=get_stalagmite(x,y);

tic
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.5;0.5]);
    % lower bound for x&y both is 0 and upper bounds are 0.5
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study2_time = toc

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

Now we can see from above plot for most of that now a solution is more converged then the previous study.Since we have got only 4 points this time. But still we haven't find the solution.

And more number of iterations have convergerd to near -1. Because GA has ran for a certain range of variables.

The time taken by ga to run is around 4.66 s.

Population size

In next study let us increase the initial population size.More the number of samples more is the chance of convergence to solution. Since GA by default takes 50 sets of values as initial population sometimes small population for complex problems may not converge to minima. We will use optimzation tool for ga to set initial poulation to 170. And we may also reset upper and lower bounds.

Below is code for study 3

clear all
close all
clc
% defining our search space

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

num_cases=50;
f=get_stalagmite(x,y);

options = optimoptions ('ga');
options = optimoptions(options,'PopulationSize',170);  % repalacing the default optimization parameter.
tic
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
    % syntax for optimization
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study3_time=toc

% plotting the inputs and results obtained
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)  % creating a 3-d surface plot
xlabel('x value')
ylabel('y value')
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
% plot3 plots coordinates in 3d space
title('Bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function minimum')

From above plot we can see that. We have found the Global minima. And most of the iterations has converged to same value. The minimum value is -1.

The drawback this time is that GA has taken more time to evaluate the fuction because of increased population size.

Time taken= 11.23 s.

The inputs points x&y at which function approaches the global minima value -1 are (0.0668,0.0668).

But our desire or objective is to find maxima.

That can be easily achieved by putting -ve sign in our plot before optimized result.

And we can get the Global maxima.

Below is the copy of study3 with minor change

clear all
close all
clc
% defining our search space

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

num_cases=50;
f=get_stalagmite(x,y);

options = optimoptions ('ga');
options = optimoptions(options,'PopulationSize',170);  % repalacing the default optimization parameter.
tic
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
    % syntax for optimization
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study3_time=toc

% plotting the inputs and results obtained
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)  % creating a 3-d surface plot and inverting it by -ve sign
xlabel('x value')
ylabel('y value')
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
% plot3 plots coordinates in 3d space
title('Setting initial population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function minimum')

The Global maxima is 1. At points (0.0668,0.0668).

Stopping condition:

In our case the optimization is terminated since , there is no change to the population best fitness for a specified number of generations.

References: MathWork.in

Stack overflow

Tuturialspoint.com