Week 4.1 - Genetic Algorithm

Finding the Global maxima of a function using the Genetic Algorithm via MATLAB.

Aim: The aim of the challenge is to solve a Global optimization problem by understanding the working of the Genetic Algorithm in Matlab and finding the Global maxima of a function.

Principle Theory:

Optimization is a procedure that is executed iteratively by comparing various solutions until an optimum or a satisfactory solution is found.

Optimization refers to finding the values of inputs in such a way that we get the “best” output values. 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.

CODING:

clear all
close all
clc

%inputs

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


%asigning values to inputs
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


%function call

[f]=stalagmite(input_vector)

%case1[unbounded GA study]
tic
for i=1:n
    [inputs,fopt(i)]=ga(@stalagmite,2);
    xopt(i)=input(1);
    yopt(i)=input(2);
end
study1_time=toc

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('X axis')
ylabel('Y axis')
title('statistical behaviour with unbound inputs')
plot3(xopt(i),yopt(i),-fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('no.of iterations')
ylabel('function maximum')


%case2[bounded ga study]
tic
for i=1:n
    [inputs,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
    xopt(j)=input(1)
    yopt(j)=input(2)
end
study2_time=toc

figure(2)

hold on
surfc(xx,yy,-f)
shading interp
xlabel('x axis')
ylabel('y axis')
title('statistical behaviour with upper and lower bounds')
plot3(xopt(j),yopt(j),-fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('no.of iterations')
ylabel('function maximum')





%case3[bounded GA with known population size of270]

options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',270);
tic
for i=1:n
    [inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
    xopt(k)=input(1);
    yopt(k)=input(2);
end
study3_time

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('x axis')
ylabel('y axis')
title('statistical behaviour with increasing iterations')
plot3(xopt(k),yopt(k),-fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('no.of iterations')
ylabel('function maximum')

FUNCTION IN NEW SCRIPT



function [f]=stalagmite(input_vector)
    a=input_vector(1)
    b=input_vector(2)
    term1=(sin((5.1*pi*a)+0.5))^6;
    term2=(sin((5.1*pi*b)+0.5))^6;
    term3=exp(-4*log(2)*(((a-0.0667)^2)/0.64));
    term4=exp(-4*log(2)*(((b-0.0667)^2)/0.64));
    
    [f]=-(term1*term2*term3*term4);
end
%%GA SYNTAX

Syntax of Genetic Algorithm in Matlab:

x=ga(@fun,nvars,A,B,Aeq,Beq,Lb,Ub,nonlcon,intcon,options)

fun= The fitness function in our case the Stalagmite function.
nvars= number of variables (2)
A and B= Linear inequalities of the Form A*x<=B
Aeq and Beq=Linear equalities of the form A*x=B
LB and UB=Lower and Upper bound that is the region in which Ga will search for the result.
nonlcon=non Linear inequalities
intcon=Integer constrained
options= Helps to add constrain tolerance by increasing the population size.
For our first case, all the above options are not used so Ga will assume the default values

%EXPLANATION

FOR UNBOUNDED 

We will be creating two plots so we will be applying the subplot command. The surfc is used to view the 3-D graph of the points xx,yy,-F, Here the -F is to represent the graph in the positive axis. Hold on is used to views all the plots. Sharp interp is used so that the 3-D graph is more representable.

 Plot 3 is used to plot all the three values xopt,yopt and -fopt in the 3-Graph and the second Subplot only views the fopt in a 2-D graph.

The Red points represent the Maxima value that the function is trying to predict in 50 iterations. You can see that it is searching over a range of areas in the x-axis and y-axis as we have not given the upper and lower bounds.

In the second graph, you can see that the Fopt value range from 0 to 1 but with various peaks hence this method is not enough to find the maximum value. In this case, we are not able to find the Global maxima as the Algorithm is not able to predict it correctly.

The time is taken for this study to run is 2.9042s

%FOR BOUNDED

Only this region of the code will be modified in the second case study. You can see that we are giving the upper and lower bounds value (0,0) and (.5,.5). We are instructing the algorithm that the maximum will be under that region. The Population for this study will be 50 which is the default value
You can see that after we applied the Lower and Upper bound the results are much better. The Algorithm has reduced down the Global maxima between 4 points. This is because we have reduced the search space. This result is okay considered to the previous result but we need to find only the single global maxima.

You can also see from the second graph that the Maximum value range is from 0.5 to 1. The Time taken for this run is 4.0093 which has increased from the first case study.

%BOUNDED WITH POPULATION
In this case study, we will be increasing the population number from 50 which is the default value a to 250. The higher the number of the population it increases the probability of us finding the optimum function.

There are several things to be kept in mind when dealing with GA population −

The diversity of the population should be maintained otherwise it might lead to premature convergence.

The population size should not be kept very large as it can cause a GA to slow down, while a smaller population might not be enough for a good mating pool. Therefore, an optimal population size needs to be decided by trial and error.

So in this case the Population is 250 and the other values are the same as of the second case study. So the time taken to run the program will be more foR THIS CASE