Week 4 - Genetic Algorithm

AIM

To write a code in MATLAB to optimize the stalagmite function and to find the global maxima of the function.

GOVERNING EQUATIONS

Formulas for the stalagmite function ,

`f(x,y) = f_1,_x*f_2,_x*f_1,_y*f_2,_y`

`f_1,_x = [sin(5.1pi*x+0.5)]^6`

`f_1,_y = [sin(5.1pi*y+0.5)]^6`

`f_2,_x = exp[-4ln(2)(x-0.0667)^2/0.64]`

`f_2,_y = exp[-4ln(2)(y-0.0667)^2/0.64]`

THEORY

In this program we are using the genetic algorithm(GA) method for optimizing the problems.

Genetic algorithm as the name suggests is based on the biological evolution process.

In this method , it uses the biological processes of mutation,cross-over and selection.

In the selection process the best performing parents are retained for next generation.

In the cross-over process the common similarities between two parents are used to create a child.

And finally in the mutation process , the parent is mutated to get new random variables to form a child.

In MATLAB genetic algorithm solves optimization problems with any typs of constraints. It searches randomly by mutation and cross-over among population members.

In this particular program it is used to find the global maximum of the problem. Genetic algorithm as such does not find maximum value , so we need to slightly modify our function equation by adding a negative sign. Now the GA will find the global minimum which is our required maximum value.

Advantage of using GA is that it can deal with complex problems and can optimize variety of optimization types even if the objective function is stationary or non-stationary, linear or non-linear , continuous or discontinuous.

Disadvantage of GA is that , the selection of fitness function , giving values of population size and selection criteria of the new population has to be done carefully because any mistakes in these would produce undesired outcomes.

SYNTAX FOR GA in MATLAB

[x , fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

Where , ‘x’ is the input values

‘fval’ is the output value

‘ga’ is the inbuilt MATLAB solver for genetic algorithm

‘fun’ is the objective function

‘nvars’ is the dimension of the objective function.

‘A’&’b’,are linear inequalities

’Aeq’&’beq’ are linear equalities

‘lb’ & ‘ub’ are lower bound and upper bound respectively on the design variables

‘nonlcon’ is the non linear constraint values

‘options’ is used to replace default optimization parameters with that stored inside ‘options’.

SYNTAX FOR CREATING OPTIMIZATION OPTIONS in MATLAB

options = optimoptions(solvername)

options = optimoptions(solvername,name,value)

In this program solvername is “ga”

Name is “populationsize” and ‘value’ is the number of individuals in each generation.

OBJECTIVE

To find the global maximum of the given stalagmite function using genetic algorithm in MATLAB.

To find different methods to find the accurate global maximum ,three studies are done and their respective graphs are compared.

PROGRAM

In the program first step is to define the x & y variables as an array.

Then the number of iterations is defined.

After that we use ‘meshgrid’ to form an array with y rows and x columns.

Now we create a for loop to run the stalagmite function.

STUDY 1

After that we move onto the first study , where we execute unbounded genetic algorithm. Here the genetic algorithm is put inside a for loop whose number of iterations is defined earlier ‘num_cases’ in the program.In this for loop we use the ‘ga’ solver for optimizing the stalagmite function. Here ‘fopt’ is the optimized function value , ‘xopt’ is the optimized x coordinate value and ‘yopt’ is the optimized y coordinate value.

Also we measure the time taken for the program to display the output by using ‘tic’ and ‘toc’ MATLAB functions. Where ‘tic’ will start the stopwatch timer and ‘toc’ will read the elapsed time from the stopwatch.

Next step is to plot this stalagmite function and also the graph between function maximum & number of iterations.

To plot these to graphs inside one figure , we use ‘subplot’ function in MATLAB.

Syntax for ‘subplot’ is as follows,

subplot(m,n,p) , where ‘m’ is the number of rows

‘n’ is the number of columns

‘p’ specifies the position of the axes

The first graph is the stalagmite function , for this we use ‘surfc’ function in MATLAB. ‘surfc’ will creates a 3-D surface plot with a contour plot underneath.

Syntax for ‘surfc’ is as follows,

Surfc(x,y,z) , where x,y&z are corresponding coordinate values.

In order to remove the grid lines from the 3-D graph we use another MATLAB function called ‘ shading interp’ , which varies the colour in each line segment and face.

Next step is to plot the coordinates in the 3-D space , for that we use ‘plot3’ function in MATLAB.

Now we move onto the second graph , where we plot function maximum vs number of iterations.

STUDY 2

After finishing the first study , next step is to do the second study. In this second study we specify the lower bound and the upper bound inside the syntax of ‘ga’ solver. This will force the genetic algorithm to be within the provided bounds and will find the solution in that range.

All other steps are similar to that of STUDY 1.

STUDY 3

In this study we specify the number of individuals in each generation by using the ‘options’ function in MATLAB , whose syntax has been explained in the beginning.

Using this we can decide how many individuals has to be there in each generation.

All other steps are similar to that of STUDY 2.

clear all
close all
clc

% defining x & y as arrays
x =linspace(0,0.6,150);
y =linspace(0,0.6,150);

%specifying the number of iterations 
num_cases=100;

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

%for loop for running 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_f(input_vector);
    end
end


%study 1 statistical inputs with unbounded inputs
tic
for k=1:num_cases
    [inputs1,fopt1(k)] = ga(@stalagmite_f,2);
    xopt1(k)=inputs1(1);
    yopt1(k)=inputs1(2);
end
study_time1=toc;

% plotting stalagmite function
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt1,yopt1,fopt1,'marker','o','markersize',5,'markerfacecolor','r')

title('unbounded inputs')
subplot(2,1,2)
plot(fopt1)
xlabel('iterations')
ylabel('function maximum')

%study 2 statistical behaviour with bounded inputs
tic
for k=1:num_cases
    [inputs2,fopt2(k)] = ga(@stalagmite_f,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt2(k)=inputs2(1);
    yopt2(k)=inputs2(2);
end
study_time2=toc;

% plotting stalagmite function
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt2,yopt2,fopt2,'marker','o','markersize',5,'markerfacecolor','r')

title('bounded inputs')
subplot(2,1,2)
plot(fopt2)
xlabel('iterations')
ylabel('function maximum')

%study 3 statistical behaviour by changing population size
options=optimoptions('ga');
options=optimoptions(options,'populationsize',350);

tic
for k=1:num_cases
    [inputs3,fopt3(k)] = ga(@stalagmite_f,2,[],[],[],[],[0;0],[0.6;0.6],[],options);
    xopt3(k)=inputs3(1);
    yopt3(k)=inputs3(2);
end
study_time3=toc;

% plotting stalagmite function
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt3,yopt3,fopt3,'marker','o','markersize',5,'markerfacecolor','r')

title('bounded inputs with modified population size')
subplot(2,1,2)
plot(fopt3)
xlabel('iterations')
ylabel('function maximum')

STALAGMITE FUNCTION PROGRAM

In this program we create a function named “stalagmite_f” which accepts input as ‘input_vector’ and returns output ‘X’.

Then we define the variables ‘x’ and ‘y’ .

Next the formulas for `f_1,_x,f_2,_x,f_1,_y,f_2,_y` , and then the output is found out using these 4 formulas as per the equations provided earlier.

%STALAGMITE FUNCTION
function [X] = stalagmite_f(input_vector)

x = input_vector(1);
y = 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);

X = -f1*f2*f3*f4;
end

CONCLUSION

The stalagmite function has been optimised successfully and the global maxima of the function has been found out.

Three different studies has been carried out and the graphs between function maximum and the number of iterations plotted.