Genetic Algorithm using MATLAB to calculate the global maxima of a stalagmite function

Aim : To optimise the stalagmite function and find the global maximaof the function.

Introduction : Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

• Optimization :

Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs as shown in the following figure.

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.

The set of all possible solutions or values which the inputs can take make up the search space. In this search space, lies a point or a set of points which gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.

• Genetic Algorithms :

Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.

GAs were developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg and has since been tried on various optimization problems with a high degree of success.

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”.

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.

Procedure :

1) First defining the search space for x and y using \'linspace\' command and giving the \'num_cases\'

2) \'meshgrid\' command is used to create two dimensional mesh.

3) Function is written seperately in a new window in code.

Stalagmite function code :

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

f1_x = (sin(5.1*pi*x+0.5)).^6;
f2_x = (sin(5.1*pi*y+0.5)).^6;
f1_y = 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*f2_x*f1_y*f2_y); %To find the Maxima
end

4) Three types of studies are done by changing the stalagmite function.

5) Study 1 is based on statistical behaviour, study 2 on behaviour of upper and lower boundaries and study 3 on finding the global maxima.

6) \'surfc\' command is used to create contour plot under three dimensional shaded surface. Shading \'interp\' is used to interpolate the frequencies. \'tic\' starts a stopwatch timer to measure performance and it displays the elapsed time with \'toc\'.

clear all
close all
clc

% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;


%Creating a 2Dimensional 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);
    end
end
% STUDY 1 : Statistical Behaviour

surfc(xx,yy,-f)
xlabel(\'X\')
ylabel(\'Y\')
shading interp
hold on

[inputs,fval] = ga(@stalagmite,2);

tic 
for i = 1:num_cases
    [inputs,fopt1(i)] = ga(@stalagmite,2);
    xopt1(i) = inputs(1);
    yopt1(i) = inputs(2);
end
study_time1 = toc;

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
xlabel(\'X\')
ylabel(\'Y\')
shading interp

plot3(xopt1,yopt1,-fopt1,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Unbounded inputs\')
subplot(2,1,2)
plot(-fopt1)
xlabel(\'Iteration\')
ylabel(\'Function_minimum\')

% STUDY 2 : Behaviour under upper and lower boundaries
  tic
  for i = 1:num_cases
      [inputs,fopt2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
      xopt2(i) = inputs(1);
      yopt2(i) = inputs(2);
  end
  study_time2 = toc;
  
  figure(2)
  subplot(2,1,1)
  hold on 
  surfc(xx,yy,-f)
  xlabel(\'X\')
  ylabel(\'Y\')
  shading interp
  
  plot3(xopt2,yopt2,-fopt2,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
  title(\'bounded inputs\')
  subplot(2,1,2)
  plot(-fopt2)
  xlabel(\'Iteration\')
  ylabel(\'Function_minimum\')
  
  % STUDY 3 : Increasing the population
  options = gaoptimset(@ga);
  options = gaoptimset(options,\'populationsize\',300);
  tic
  
  for i = 1:num_cases
      [inputs,fopt3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
      xopt3(i) = inputs(1);
      yopt3(i) = inputs(2);
  end
  study_time3 = toc;
  figure(3)
  subplot(2,1,1)
  hold on 
  surfc(xx,yy,-f)
  xlabel(\'X\')
  ylabel(\'Y\')
  shading interp
  
  plot3(xopt3,yopt3,-fopt3,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
  title(\'At one point\')
  subplot(2,1,2)
  plot(-fopt3)
  xlabel(\'Iteration\')
  ylabel(\'Function_minimum\')
  

Results :

1) STUDY 1 : Number of lines over the maxima and minima all over the plot which is insignificant

2) STUDY 2 : Under upper and lower bounds given there are lesser lines formed.

3) STUDY 3 : The global maxima is found with the help of population size and bounds

Conclusion : In the third study, the GA value is concentrated in one area/point which is known to be the global maxima.