Week 4 - Genetic Algorithm

Aim: Find the Global Maxima of the Stalagmite Function using the Genetic Optimization Algorithm on Matlab.

Theory:

• Stalagmite Function:
• The Stalagmite function gives out Local and global maxima and minima.

• Genetic Algorithm(GA):

• The algorithm is based on the natural process of evolution and survival of the fittest.
• At every iteration, a population of points are generated and is checked for optimum fitness solution. If found, then the algorithm is terminated or else there is a selection of the superior from the existing population, and then is crossed over for a new population of offsprings by mutation.
• This cycle is continued until the optimum solution is found.
• The Genetic Algorithm function (ga) in Matlab by default gives out the Global and Minima of the function.
• Since in the Problem we need to find the Global Maxima, the stalagmite function is negated to match the GA function in Matlab.

The syntax for Genetic Algorithm function (ga)

• [x,fval ]= ga(fun,nvars)
  • The above finds a local unconstrained minimum, x, and also returns fval, the value of the fitness function at x to the objective function, fun. nvars is the dimension (number of design variables) of fun.
• The above syntax is the most basic GA syntax. The further complex inputs can be referred from https://www.mathworks.com/help/gads/ga.html (Ref A )

Main Code:

% ------------Section 1-----------------------------------
clear all 
close all 
clc

%--------------section 2---------------------------------------
%preparing input data for stalagmite funtion
x=linspace(0,0.6,150);     
y=linspace(0,0.6,150);

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

for i=1:length(xx)
    for j=1:length(yy)
        input_value(1)=xx(i,j);
        input_value(2)=yy(i,j);
        f(i,j)=stalagmite(input_value);
    end
end

iter=50;      % declaring the no of iterations to be carried

%-----------------Section3--------------------------------------------
%-------------Case Study 1------------------------------------------------

tic
for i=1:iter          %genetic algorithm is run for 50 iterations 
  [opt_val,fopt(i)]=ga(@stalagmite,2);
  x_opt(i)=opt_val(1);
  y_opt(i)=opt_val(2);
end        %the output x and y coordinate along with the value of funtion is recorded

Study_1=toc

figure(1)
subplot(2,1,1);    % the figure is divided to created multiple plots in same figure
hold on
surfc(xx,yy,f);       %the stalagmite funtion is plotted
shading interp;       %removal of grid for better visualization
ylabel('y data');
xlabel('x data');
%the co-ordinates and function minimum values are plotted 
plot3(x_opt,y_opt,fopt,'marker','*','markersize',3,'markerfacecolor','k');
title('Study 1 : open inputs');
subplot(2,1,2);
plot(fopt);         %the funtion minima is plotted against the iteration no.
xlabel('Iterations');
ylabel('Function Max ');

%---------------Section4--------------------------------------------------
%-------------Case Study 2-------------------------------------------------

tic
for i=1:iter
    %bounds of 0 to 0.6 on bith x and y axis are provided 
  [opt_val,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0 0],[0.6 0.6]);
  x_opt(i)=opt_val(1);
  y_opt(i)=opt_val(2);
end

study_2=toc

figure(2)
subplot(2,1,1);
hold on
surfc(xx,yy,f);
shading interp;
ylabel('y data');
xlabel('x data');
plot3(x_opt,y_opt,fopt,'marker','*','markersize',3,'markerfacecolor','k');
title('Study 2 : closed inputs');
subplot(2,1,2);
plot(fopt);
xlabel('Iterations');
ylabel('Function Maximum');

%---------------section5-------------------------------------------
%------------------Case Study 3------------------------------------------

%default population size of 50 is altered to 450
options=optimoptions('ga');
options=optimoptions(options,'populationsize',450);

tic
for i=1:iter
    % along with bounds the increased population size is given in.
  [opt_val,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0 0],[0.6 0.6],[],[],options);
  x_opt(i)=opt_val(1);
  y_opt(i)=opt_val(2);
end
study_3=toc

figure(3)
subplot(2,1,1);
hold on
surfc(xx,yy,f);
shading interp;
ylabel('y data');
xlabel('x data');
plot3(x_opt,y_opt,fopt,'marker','o','markersize',6,'markerfacecolor','k');
title('bounded inputs with increase population size');
subplot(2,1,2);
plot(fopt);
xlabel('iterations');
ylabel('Function maximum');

%------------------------Section6-------------------------------------
max_value=fopt;   %the global maxima is recorded

User-Defined Stalagmite Function:

function [f]= stalagmite(input_value)
x=input_value(1);
y=input_value(2);

f1x=(sin(5.1*pi*x + 0.5)).^6;
f1y=(sin(5.1*pi*y + 0.5)).^6;

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

f =-(f1x .* f2x .* f1y .* f2y);   %function is negated

end

Main code Explanation:

Section 1:

• The set of code clears all the variables and text from the workspace and the command window respectively. It also clears the figures generated by the codes run prior to the commands.

Section2:

• The input data for the Stalagmite function is generated. The function is to be defined between 0 to 0.6 on both x and y-axis. The meshgrid function is used to create a 2D array based on the 2-1D arrays.
• A for loop is used to give in the x and y coordinate as an array ‘ input_value’ to the user-defined stalagmite function.
• The output at each input is recorded in a 2D array ‘ f ’.
• The iteration counter (iter) for the further Genetic Algorithm is set to 50.

Section3:

• The study contains 3 cases of different calculating parameters. In this section, the code for Case Study 1 is written down.
• A for loop is used to carry down the iterations of ‘ga’ function. The stalagmite function handle (@stalagmite) along with the no of variables (2) is passed to the ga function.
• In each iteration, the ga function gives out an optimum solution along with its coordinates which is then segregated to x and y coordinate respectively. The FOR loop execution creates an array of these output values.
• The stalagmite function is plotted using the ‘ surfc ‘ command.
• The output coordinates and optimum value arrays are also plotted on the same plot for visual analysis.
• Also, a subplot is created with the optimum function solution value vs the no of iterations.

Section 4:

• All the code details remain the same from section 3.
• This section shows the case study 2, where the bounds are declared in the GA function to restrict the selection from the bounded set.
• The syntax used is from reference A.

Section 5:

• All the code details remain the same from section 3.
• This section shows the case study 3, where along with the bounds, the default population size of 50 is altered using the ‘optimoptions’ function to 450 and the ga function is updated using the syntax from reference A.

Section 6:

• The final result which is minima from the ga function, but as per the code is the Global Maxima, is recorded.

Stalagmite Function:

• Stalagmite function is defined using the Equations governing Stalagmite function.
• It takes in input values of x and y coordinate generated in section 2.
• Since the GA function optimizes for Global minima and since we need to find the global maxima in the following exercise, the Function is negated to invert the plot. This will get the maxima of the function to the minima position on the defined grid and hence serving the purpose.
• Result:

Plot 1:

Since there are no bounds provided, the ga function utilizes random spaces and hence the result is very scattered and outside the domain of the stalagmite function.

Plot 2:

From observing figure 1, bounding conditions for x and y values were provided and thus the search became more specific and hence the randomness decreased and 4 different points were plotted as optimum.

Plot 3:

After implying the bounding conditions the no of optimum values was very close and hence to refine the optimization, the population size was increased from a default value of 50 to 450. This resulted in a single value of global maxima irrespective of the number of runs, which was not the case until Case Study 2.

Conclusion:

The global optima value of 1 is achieved at the coordinate ( 0.668, 0.668 ). By stepwise assumption from theoretical knowledge and educated assumption, Optimization using the Genetic Algorithm is carried out to find the Global Maxima of the Stalagmite Function.

Reference:

1. https://www.researchgate.net/figure/Flowchart-of-Genetic-Algorithm-GA-optimization_fig5_321985815