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