Genetic Algorithm

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

Software Used:MATLAB(online)

Theory:

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

The following outline summarizes how the genetic algorithm works:

1.The algorithm begins by creating a random initial population.

2.The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:

1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
3. Selects members, called parents, based on their expectation.
4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
6. Replaces the current population with the children to form the next generation.

3.The algorithm stops when one of the stopping criteria is met.

Syntax for ga

Stalagmite function

Stalagmite Function is a mathematical function and for this function we need to find the Global Maxima. To find the global maxima of the function we make use of in-built function in MATLAB called Genetic Algorithm (GA). But the limitation with this in-built function GA is it can only provide us the minimum value of the function.

Code for Function

function[f]=stalagmite(input_vector)

x=input_vector(1);
y=input_vector(2);

a=(sin((5.1*pi*x)+0.5))^6;
b=(sin((5.1*pi*y)+0.5))^6;
c=exp((-4*log(2)*((x-0.0667)^2))/(0.64));
d=exp((-4*log(2)*((y-0.0667)^2))/(0.64));
f=-(a*b*c*d);

end

The above code is written for the Stalagmite function. Solving the Genetic algorithm for stalagmite function gives us the minimum value of function. To find the maximum value of the function, we need to change the sign of the function, so that it will give us the maximum value.

Main Program

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

numcase=50;
%creating a 2-D mesh
[xx,yy]=meshgrid(x,y);
 
%Evaluating a stalagmite function
for i=1:length(xx)
  for j=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 behavior
tic
for i=1:numcase
  [inputs,fopt(i)]=ga(@stalagmite,2);
  xopt(i)=inputs(1);
  yopt(i)=inputs(2);
end
study1_time=toc

%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
ylabel('Y Values ')
xlabel('X Values')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

%Study 2-Statistical Behavior- with upper and lower bounds
tic
for i=1:numcase
  [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
  xopt(i)=inputs(1);
  yopt(i)=inputs(2);
end
study2_time=toc

%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
ylabel('Y Values ')
xlabel('X Values')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Statistical Behaviour with upper and lower bounds')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

%Study 3 Increasing GA iterations
options=optimoptions(@ga);
options=optimoptions(options,'populationsize',300);
tic
for i=1:numcase
  [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
  xopt(i)=inputs(1);
  yopt(i)=inputs(2);
end
study3_time=toc

%plotting
figure(4)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
ylabel('Y Values ')
xlabel('X Values')
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Statistical Behaviour with increasing GA iterations')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

Explanation for the code

1.Start the program with clear all, close all and clc commands

2.The x and y array are defined using linspace command

3.A 2D mesh is created using the mesh grid command and the number of iterations that the code should perform is defined i.e. n=50

4.A for loop is used to evaluate the stalagmite function and a plot is created.

5.Now we obtain the results for 3 cases of genetic algorithm. In the first case, the maximum value of function is found out with no bounds

6.This is done using a for loop where we use ‘ga’ syntax to give values for the inputs and optimum maximum value. The stalagmite function is called in the ga syntax and number of variables ‘nvars’ are 2

7.To know the time taken to solve the loop for 50 iterations, ‘tic’ and ‘toc’ command is used before and after the loop respectively

8.The function created in the loop is plotted by using ‘surfc’ command. The ’shading interp’ command is used to neglect the gridlines on the surface and obtain a smooth plot.

9.In the second case we restrict the program with specific bounds namely upper bound and lower bound.The whole procedure for programming this case remains same as that of previous case except the GA syntax .The Plot for this case is obtained.

10.In the third case i.e. Study 3, the number of iterations is increased to 300.This is because the results obtained from the second case are not the same every time the program terminates.In this case,Syntax for GA is different than the previous case i.e it contains 'option' term and rest of the code is same as for study 1 and study 2.

Results:

Study 1-Statistical Behavior

In the above plot we can see that because of random sampling ,there are large numbers of red dots spread all over. Large number of red dots shows, values of coordinates of x,y varies each time the iteration runs.We get different results because of not providing any bounds.

Study 2-Statistical Behavior with upper and lower bounds

In this case ,the number of red dots are less compared to the previous case plot.This is the result of providing the upper and lower bounds .The result is much better than the previous case.

Study 3-Statistical Behavior with Increasing GA iterations

In this case we can see that there is only one red dot. Here in this case,we have increased the number of iterations to 300 so as to converge and find the global maxima of the function.

Errors Obtained:Some simple errors were obtained and were rectified easily.

References: https://in.mathworks.com/discovery/genetic-algorithm.html

https://in.mathworks.com/help/gads/ga.html