OPTIMIZING THE STALGAMITE FUNCTION USING GENETIC ALGORITHM IN MATLAB

Aim : To find the global maxima of the stalgaite function using Genetic algorithm

Stalgamite function : 

figure : 

Genetic Algorithm :

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.

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

Flow Chart : 

Individual - Any possible solutionPopulation - Group of all individuals
Fitness – Target function that we are optimizing (each individual has a fitness)
Trait - Possible aspect (features) of an individual
Genome - Collection of all chromosomes (traits) for an individual

Fitness function :

A fitness function value quantifies the optimality of a solution.The value is used to rank a particular solution against all the other solutions.A fitness value is assigned to each solution depending on how close it is actually to the optimal solution of the problem

Selection :

The process that determines which solutions are to be preserved and allowed to reproduce and which ones deserve to die out. The primary objective of the selection operator is to emphasize the good solutions and eliminate
the bad solutions in a population while keeping the population size constant.

There are different techniques to implement selection in Genetic Algorithms.

They are:

1) Tournament selection : 

In tournament selection several tournaments are played among a few individuals. The individuals are chosen at random from the population.The winner of each tournament is selected for next generation.Selection pressure can be adjusted by changing the tournament size.Weak individuals have a smaller chance to be selected if tournament size is large.

2) Roulette wheel and Proportionate selection :

Parents are selected according to their fitness values.The better chromosomes havemore chances to be selected

Crossover  :

It is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

The new offspring is added to the population

Mutation :

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Mutations occurs to maintain diversity within the population and prevent premature convergence.

Termination :

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

Syntax for Genetic algorithm in Matlab :

[x,fval,exitflag,output,population,scores]=ga(func,nvars,A,b,Aeq,Beq,lb,ub,nonlcon,lntcon,options)

x = Optimim solution

exit flag = reason ga stopped

output = Information about optimization process

population = final population

scores = final scores

fun = fitness function

nvars = number of variables

A,b= Linear Inequality constriants

Aeq, Beq = Linear Equality constraints

lb = Lower bound

ub = Upper bound 

nonlcon = Use for non linear constraints

lntcon = To get solution in Integer

options = To set population size minimize with non-default options

Constructing the stalgamite function in Matlab :

Code :

 function [f]=stalgamite(inputvector)
 x=inputvector(1);
 y=inputvector(2);
 f1x=(sin(5.1*pi*x+0.5)).^6;
 f1y=(sin(5.1*pi*y+0.5)).^6;
 t1=((x-0.0667).^2)/(0.64);
 t2=((y-0.0667).^2)/(0.64);
 f2x=exp(-4*log(2)*t1);
 f2y=exp(-4*log(2)*t2);
%keep a negative size to maximize the function
 f=-(f1x.*f2x.*f1y.*f2y);
 end
 

Explanation :

Basically ga is used for getting minimization but our objective is to maximize the stalgamite function for that we have to take "-" sign before the function output.

This function is called in the main program and the results are executed.

To understand the genetic algorithm different case studies are being done 

Case 1 : Statistical study without any boundation

CODE :

clear all
close all 
clear all
%creating the search space for ga
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
%No of times ga has to be performed
numcases=50;
%calculation of stalgamite function value at each and every point in mesh grid
for i=1:length(xx)
    for j= 1:length(yy)
        inputvector(1)=xx(i,j);
        inputvector(2)=yy(i,j);
        %calling the stalgamite function
        f(i,j)=stalgamite(inputvector);
        
    end
end
% observing the program evaluation time by using tic and toc commands
tic
%Repeating the ga for different iterations
for i=1:numcases
    [inputs,fopt(i)]=ga(@stalgamite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study1time=toc
%plotting
figure(1)
subplot(2,1,1)
%generating the surface plot of stalgamite function
surfc(x,y,f);
hold on
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('x')
ylabel('y')
grid on
legend('stalgamite','ga generated optimum points')
title('stalgamite function with no boundation')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('function max value')

Explanation : 

1) First we have to create a search space for the ga for that take use of linspace and generate the arrays of x and y 

2)To generate a surface plot we must have the mesh grid so a mesh grid is developed.

3)The first for loop calculates stalagmite function value at each and every point in the mesh grid

4)Now the genetic algorithm is performed 50 times at each and every time different optimum values of x and y are generated and in the genetic algorithm no bound limits are mentioned.

5) For each and every value of xopt and y opt stalgamite function value(fopt) is calculated so we get 50 set of optimum values.

6)tic and toc commands are used for knowing the program execution time.

7) 2 subplots are generated in the first subplot stalgamite function surface and the optimum points are plotted and in the second subplot function maximum value with each iteration is plotted.

8) As it is a maximization case we have taken the -ve sign for the function so the plot gets inverted 

Output :

It can be clearly observed that the values generated are not accurate and they fluctuates so we have have to for an other study

Case 2 : Statistical study with bounded values

CODE :

clear all
close all 
clear all
%creating the search space for ga
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
%No of times ga has to be performed
numcases=50;
%calculation of stalgamite function value at each and every point in mesh grid
for i=1:length(xx)
    for j= 1:length(yy)
        inputvector(1)=xx(i,j);
        inputvector(2)=yy(i,j);
        %calling the stalgamite function
        f(i,j)=stalgamite(inputvector);
        
    end
end
% observing the program evaluation time by using tic and toc commands
tic
%Repeating the ga for different iterations
for i=1:numcases
    [inputs,fopt(i)]=ga(@stalgamite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study2time=toc
%plotting
figure(1)
subplot(2,1,1)
%observing the surface plot
surfc(x,y,f);
hold on
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('x')
ylabel('y')
grid on
legend('stalgamite','ga generated optimum points')
title('stalgamite function with boundation')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('function max value')

Explanation :

1) First we have to create a search space for the ga for that take use of linspace and generate the arrays of x and y 

2)To generate a surface plot we must have the mesh grid so a mesh grid is developed.

3)The first for loop calculates stalagmite function value at each and every point in the mesh grid

4)Now the genetic algorithm is performed 50 times at each and every time different optimum values of x and y are generated and in the genetic algorithm bound limits are mentioned. In the previous case the x and y values are taking -ve values to an optimum solution so we constrain the limits for x and y i.e x varies from 0 to 1 and y varies from 0 to 1

5) For each and every value of xopt and y opt stalgamite function value(fopt) is calculated so we get 50 set of optimum values.

6)tic and toc commands are used for knowing the program execution time.

7) 2 subplots are generated in the first subplot stalgamite function surface and the optimum points are plotted and in the second subplot function maximum value with each iteration is plotted.

8) As it is a maximization case we have taken the -ve sign for the function so the plot gets inverted so to get straight plots use -ve sign before f in surface plot and -fopt in point plot

Output :

We can clearly observe that the variations are greatly reduced and the values fall in between the 3 mountain peaks but still its not the accurate solution fot that we have do another case study. The maximum value falls between -1 and -0.7

Case 3 : Increasing the polution size with the help of optimoptions command :

CODE :

clear all
close all 
clear all
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
numcases=50;
options=optimoptions('ga','populationsize',300)
for i=1:length(x)
    for j= 1:length(y)
        inputvector(1)=xx(i,j);
        inputvector(2)=yy(i,j);
        f(i,j)=stalgamite(inputvector);
    end
end
tic
for i=1:numcases
    [inputs,fopt(i)]=ga(@stalgamite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study3time=toc
figure(1)
subplot(2,1,1)
surfc(x,y,f);
hold on
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('x')
ylabel('y')
grid on
title('stalgamite function with boundation and increase in population size')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('function max value')

Explanation :

1) First we have to create a search space for the ga for that take use of linspace and generate the arrays of x and y 

2)To generate a surface plot we must have the mesh grid so a mesh grid is developed.

3)The first for loop calculates stalagmite function value at each and every point in the mesh grid

4)Now the genetic algorithm is performed 50 times at each and every time different optimum values of x and y are generated and in the genetic algorithm bound limits are mentioned. In the previous case the x and y values are taking -ve values to an optimum solution so we constrain the limits for x and y i.e x varies from 0 to 1 and y varies from 0 to 1

5) For each and every value of xopt and y opt stalgamite function value(fopt) is calculated so we get 50 set of optimum values.

6)tic and toc commands are used for knowing the program execution time.

7) 2 subplots are generated in the first subplot stalgamite function surface and the optimum points are plotted and in the second subplot function maximum value with each iteration is plotted.

8) As it is a maximization case we have taken the -ve sign for the function so the plot gets inverted so to get straight plots use -ve sign before f in surface plot and -fopt in point plot

9) In this we have increased the population size to 300 and executed the program.

Output :

The value is constrained to a single mountain peak and the max value almost touches the value of -1. But it takes thrice the amount of time 

As it is time taking we have an alternative study case to improve the accuracy with low time 

Case 4 : Use of 'gaplotbestf' command

CODE :

clear all
close all 
clear all
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy]=meshgrid(x,y);
numcases=50;
options=optimoptions('ga','plotFcn',@gaplotbestf,'populationsize',150)
for i=1:length(x)
    for j= 1:length(y)
        inputvector(1)=xx(i,j);
        inputvector(2)=yy(i,j);
        f(i,j)=stalgamite(inputvector);
    end
end
tic
for i=1:numcases
    [inputs,fopt(i)]=ga(@stalgamite,2,[],[],[],[],[0;0],[0.3;0.3],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study4time=toc
figure(1)
subplot(2,1,1)
surfc(x,y,f);
hold on
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('x')
ylabel('y')
title('with use of gaplotbest and reduction of population size')
grid on
subplot(2,1,2)
plot(fopt)

Explanation : 

From second case study the xopt and y opt values lie in the range of 0 to 0.3 so reduce the search space and the population size with help of gaplotbest more accurate result with less time can be obtained.

Error :

No error 

Reference :

1) https://mech.iitm.ac.in/nspch52.pdf

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