Genetic Algorithm and Global Maxima of a Function in MATLAB/OCTAVE

AIM:- Write a program code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

Software Used:- MATLAB

Objective:-

1. To find the optimum solution(global maxima) of the stalagmite function
2. To compare statistical behavior of function while constrained lower and upper boundaries and also increasing the population size.

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 that otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. We can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, non-differentiable, stochastic, or highly nonlinear.

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

• Selection rules select the individuals, called parents that contribute to the population at the next generation.
• Crossover rules combine two parents to form children for the next generation.
• Mutation rules apply random changes to individual parents to form children.

Optimization is the process of making something better.

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.

Local minima and local maxima are the minimum and maximum values in a selected region of the curve. If we consider the whole graph then the minimum and maximum values are called global or absolute values.

The global minimum is also the local minimum of the particular region where it is located. Similarly global maximum is also the local maximum of that particular region.

The global minimum is the minimum of minimum values and the Global maximum is the maximum of maximum values.

Advantages of GAs

GAs have various advantages that have made them immensely popular.

These include −

• It does not require any derivative information (which may not be available for many real-world problems).
• It is faster and more efficient as compared to traditional methods.
• It has very good parallel capability.
• Optimizes both continuous and discrete functions and also multi-objective problems.
• It provides a list of “good” solutions and not just a single solution.
• Always gets an answer to the problem, which gets better over time.
• Useful when the search space is very large and there are a large number of parameters involved.

Limitations of GAs:

Like any technique, GAs also suffers from a few limitations.

These include −

• GAs are not suited for all problems, especially problems that are simple and for which derivative information is available.
• The fitness value is calculated repeatedly which might be computationally expensive for some problems.
• Being stochastic, there are no guarantees on the optimality or the quality of the solution.
• If not implemented properly, the GA may not converge to the optimal solution.

Governing Equation:- In stalagmite function, the given below equations have been used.

`f(x,y)=f1x*f2x*f1y*f2y`

`f1x=[sin(5.1*pi*x + 0.5)]^6`

`f1y=[sin(5.1*pi*y + 0.5)]^6`

`f2x=exp[-4*ln(2)(x-0.0667)^2/0.64]`

`f2y=exp[-4*ln(2)(y-0.0667)^2/0.64]`

Work Flow of the Algorithm:-

1. Initially, the algorithm creates an initial random population.
2. The algorithm uses the individuals in the current generation to create the next population for calculation and optimization.
3. To calculate the initial population algorithm performs the following task:

• The algorithm calculates the fitness value of the initial population.
• Those individuals having the least fitness value are chosen as the parents for the next generation. Those having very few fitness values are chosen as the elite and are transferred to the next generation without any modification.
• The rest of the parents undergo some changes to produce children. Children are produced either by making random changes to a single parent which is called mutations or by combining the vector entries of a pair of parents which is called crossover.
• The current population is replaced by the children produced for the present generation.

4. The algorithm terminates when the optimal solution is obtained that is the deviation of the values of the fitness function is within the tolerance limit.

Stopping Conditions for the Algorithm

The genetic algorithm uses the following conditions to determine when to stop:

• Generations— The algorithm stops when the number of generations reaches the value of Generations.
• Time limit— The algorithm stops after running for an amount of time in seconds equal to the Time limit.
• Fitness limit— The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to the Fitness limit.
• Stall generations— The algorithm stops when the average relative change in the fitness function value over Stall generations is less than Function tolerance.
• Stall time limit— The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to the Stall time limit.
• Stall test— The stall condition is either average change or geometric weighted. For geometric weighted, the weighting function is 1/2ⁿ, where n is the number of generations prior to the current. Both stall conditions apply to the relative change in the fitness function over Stall generations.
• Function tolerance— The algorithm runs until the average relative change in the fitness function value over Stall generations is less than Function tolerance.
• Constraint tolerance— Constraint tolerance is not used as a stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints. Also, max(sqrt (eps), Constraint Tolerance) determines feasibility with respect to linear constraints.

Program Code:-

Note:- The ‘ga’ function minimizes the function to obtain global minima but in this program we have to find global maxima, therefore we just used the negative of the function for optimization.

Stalagmite Function Code:-

function f= stalagmite(input_v)
  x=input_v(1);
  y=input_v(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);
end

Main Function Program Code:-

close all
clear all
clc
%defining our search space
x=linspace(0,0.5,120); %120 random elements between 0 and 0.5
y=linspace(0,0.5,120); %120 random elements between 0 and 0.5
%iteration count
num=50; %number of iterations
% creating a 2 dimensional mesh
[xx,yy]=meshgrid(x,y);
%evaluating stalagmite function
for i=1:length(xx)
 for j=1:length(yy)
  input_v(1)=xx(i,j); %input row vector
  input_v(2)=yy(i,j);%input row vector
  f(i,j)=stalagmite(input_v);
end
end
figure(1)
surfc(xx,yy,-f)
xlabel('X axis')
ylabel('Y axis')
zlabel('Fval')
shading interp %removes grid lines from surface plot
title("Stalagmite Function")
[inputs,fval]=ga(@stalagmite,2)


%study 1-behaviour without boundary conditions
tic
for i=1:num
  [inputs,fval(i)]=ga(@stalagmite,2);
  ox(i)=inputs(1);
  oy(i)=inputs(2);
end
study1_time=toc

figure(2)
subplot(2,1,1) % 2 plots in a single figure window
surfc(xx,yy,-f)
hold on

shading interp %remove grid lines
plot3(ox,oy,-fval,'marker','o','markersize',3,'markerfacecolor','r')
title("Unbounded Inputs")
subplot(2,1,2)
plot(-fval)
colorbar % colorbar to the side of plot
xlabel("Number of Iterations")
ylabel("F Maxima")

%study 2-bounded inputs(lower and upper boundary constrains)
tic
for i=1:num
    %lower boundary(0;0) and upper boundary(0.1;0.1)
  [inputs,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.1;0.1]);
  ox(i)=inputs(1);
  oy(i)=inputs(2);
  
end
study2_time=toc

figure (3)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('X axis')
ylabel('Y axis')
hold on

shading interp
plot3(ox,oy,-fval,'marker','o','markersize',3,'markerfacecolor','r')
title("Bounded Inputs")
subplot(2,1,2)
plot(-fval)
colorbar
xlabel('Number of Iterations')
ylabel('F Maxima')

% study 3-bounded inputs with altered population size
options=optimoptions('ga'); %generate options for function
options=optimoptions(options,'PopulationSize',300); % population size increased
tic
for i=1:num
  [inputs,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.1;0.1],[],options);
  ox(i)=inputs(1);
  oy(i)=inputs(2);
  
end
study3_time=toc

figure(4)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('X value')
ylabel('Y value')
hold on

shading interp
plot3(ox,oy,-fval,'marker','o','markersize',3,'markerfacecolor','r')
title("Bounded Inputs with Altered Population Size")
subplot(2,1,2)
plot(-fval)
colorbar
xlabel('Number of Iterations')
ylabel('F Maxima')

Program Description:-

• The program starts with clear all, close all, clc to clear the workspace and old plots.
• x & y are input 1D arrays, linspace is used to have 120 elements within 0 to 0.5.
• n is the initial population sample size, which is one of the crucial parameters in Genetic algorithms.
• meshgrid is used to create 2D arrays with 1D arrays.
• for loops are used to evaluate the stalagmite function ie; for length of 2D matrix xx & yy. for every value of xx & yy we have defined an input vector(1) & input vector(2), which then changes at every iteration performed untill the for loop terminates.
• The values for x & y at function program is taken from these input vectors.
• f(i,j) is the solution vector/array which is now an 2D matrix, whose values are calculated by function program.
• surfc is used to plot our stalagmite curve in 3D.
• shaping interp gives the smooth curve and also eliminates the lines on curves.
• [inputs, fval]=ga(@stalagmite,2) it refers that fval is the function value at respective inputs, ga is the algorithm solver & stalagmite is our function program call followed by 2 stands for number of variables.
• tic & toc are used to calculate the time taken to perform the simulations.
• [inputs, fval(i)]=ga(@stalagmite,2) it refers that fval(i) is the function value at respective inputs, ga is the algorithm solver and stalagmite is our function program call followed by 2 stands for the number of variables.
• The same has been plotted in a single figure using subplot command.
• plot3 command is used to mark points on 3D space at every intersection of ga calculated ox,oy, fval.
• plot(-fval) is plotted to indicate the maxima values at every iteration.
• -f & -fval are used in the plot command to obtain maxima because usually ga function determines the minima of a function.

Output/Result:-

Workspace:-

Command Window:-

Plots/Graphs:-

Stalagmite Surface Function:

Study 1- Unbounded Inputs(No Feasible Solution Visible)

Study 2-Bounded Inputs

F Maxima lies between 1 and 0.999998 which is better than the Unbounded Inputs Plot.

Study 3- Bounded Inputs with Increased Population Size for Better Solution

Here F maxima lie mostly along 0.99999985, Hence this is the Optimal Solution for this function.

Conclusion:-

1. To obtain a global optimal solution, population size is increased.
2. The optimal solution does not depend on varying number of iterations the ‘ga’ function is run, but it is helpful to visualize the occurrence of optimal values for a maximum number of times.

Reference:-

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm

https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html

https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html#f6243