Genetic algorithm for data optimization to find Global Maxima
Genetic Algorithm
Aim: To optimize a stalagmite function to find the global maximum using the genetic algorithm and plot over F maximum and iteration.
Concept of genetic algorithm:
Genetic algorithm is concept that was inspired from the theory of Evolution which aims to find the finest induvial are selected for reproduction to produce off spring which happens in a loop so that at the end of all the population one the fittest offspring is obtained.
The same concept could be used for handled data in which the most suitable data for the given function could be obtained, this is known as genetic algorithm in data science.
The process of genetic algorithm contains five steps:
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
The data obtained is subjected to these processes and the fittest data for the function is obtained at the end of these iteration.
Initial population: From total population all an individual is represented as string in terms of an alphabet and they are represented as gene, their binary values are represented as chromosomes.
By breaking each induvial from the population and providing a representation is done in induvial population.
Fitness Function: Then in fitness function all the induvial in the population is evaluated how good is the induvial data to perform the function and depending upon that they are provided a score to rank them for reproduction.
Selection: In this depending upon the scores given to the induvial data they are selected for the next phase of process, the more the fitness score is the more is the chance of them getting selected.
Crossover: Cross over is phase in the genetic algorithm in which the induvial populations are crossed in each other and new offspring is created. The new offspring data will have the character if of the parent data.
Mutation: In this process the produced offspring will be subjected to mutation in which the bits of them are flipped in order to maintain diversity within the produced offspring.
Termination: when the loop produces offspring data with no significance difference between each other then the program will be terminated by producing the final offspring as the result output.
Governing formula:
`F(x,y)=f1,x*f2,x*f1,y*f2,y`
`F1,x=[sin(5.1*pi*x+0.5)]^6`
`F1,y=[sin(5.1*pi*y+0.5)]^6`
`F2,x=exp[-4ln(2)((x-0.0667)^2)/0.64]`
`F2,y=exp[-4ln(2)((y-0.0667)^2)/0.64]`
ga function syntax:
x=ga(fun,nvars)
x=ga(fun,nvars,A,b)
x=ga(fun,nvars,A,b.Aeq,beq)
x=ga(fun,nvars,A,b.Aeq,beq,lb,ub)
x=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonicon)
x=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonicon,options)
x=ga(fun,nvars,A,b,[],[],lb,ub,nonicon,IntCon)
x=ga(fun,nvars,A,b,[],[],lb,ub,nonicon,IntCon,options)
where,
fun - name of the function
nvars - number of variables as input
A - linear inequality constraints as real matrix
B - linear inequality constrain as real vector
Aeq - linear equality constraints as real matrix
Beq - linear equality constrain as real vector
lb - lower Boundary
ub – upper Boundary
nonlcon – Non linear constraints
optons – creating optimization using ‘optimoptions’
Objective of the project:
- To code a program to optimize the stalagmite function and to find the global maximum of the function.
- To understand the concept of genetic algorithm and to implement the concept in the program.
- To understand the ga function in MATLAB.
- To plot the global maximum value to the graph in three different optimization technique.
Body of the content: -
Explanation of Codes
get_stalagmite code: -
- In this function the array of values of x and y from the main program is given to it by calling get_stalagmite
- The array of values of x and y are converted into a 150x150 matrix using meshgrid and are assigned to xx and yy
- For loop iterates i from 1 to 150 inside another for loop with variable j is iterated from 1 to 150.
- The xx(i,j) is assigned to first index of variable input_vector and yy(i,j) is assigned to second index of variable
- Thus, the obtained value of input_vector is provided as a input to the function stalagmite.
- From stalagmite function the value is stored in the (I,j) index path off.
%genetic algorithm
function [f]=get_stalagmite(x,y) %x and y value from main program is loaded
%initial parameters
[xx, yy]=meshgrid(x,y); %meshgrid is done for producing 150x150 matrix to xx and yy
for i = 1: length(xx) %i value iterates from 1 to 150(length of xx)
for j = 1: length(yy) %j value iterates from 1 to 150(length of yy)
input_vector(1)=xx(i,j); %value of xx(i,y) is assigned to first column of input_vector
input_vector(2)=yy(i,j); %value of yy(i,y) is assigned to secong column of input_vector
f(i,j)=stalagmite(input_vector); %stalagmite function is called with input_vector
end
end
endStalagmite code: -
- from the value obtained from the get_stalagmite the first index of input_vector is assigned to x and second to y.
- The value of f1x, f1y are calculated and f2x, f2y are calculated.
- All these values are multiplying and -ve sign to obtain the value of fa in negative so that when plotting its value in z axis it will be in negative of z axis, the is returned to the function.
% stalagmite function
function [fa] = stalagmite(input_vector)
x=input_vector(1); %x is assigned first column of input_vector
y=input_vector(2); %y is assigned second column of input _vector
f1x=(sin((5.1*pi.*x)+0.5))^6; %f1x is calculated from x
f1y=(sin((5.1*pi.*y)+0.5))^6; %f1y is calculated from y
term=-4*log(2); %common variable term is created
f2x=exp((((x-0.0667).^2)-0.064).*term); %f2x is created from x
f2y=exp((((y-0.0667).^2)-0.064).*term); %f2y is created from y
fa=-f1x*f1y*f2x*f2y; %-ve sign to make z co-ordinate of surfc downwards
endGenetic algorithm code: -
- The program starts with common commands clear all, close all, clc.
- The values of x and y are assigned as an array of values from 0 to 0.6 with 150 values.
- Then the function stalagmite is called with inputs x and y, and the value is stored to f.
- A new variable num_case is created with value of 50.
- A for loop i is iterated from 1 to 50.
- ga function is called with inputs of stalagmite function and no of inputs 2(x and y).
- This ga function returns the local minima of the inverted f value to fopt(i), (i.e.) the maximum of the original +ve value and also the x and y co-ordinate of the local minima to variable inputs.
- From the variable inputs the x and y co-ordinates of f is assigned to xopt(i) and yopt(i).
- tic and toc commands are used to find the execution time.
- figure(1) is created with subplot with 2 rows and 1 column and a surfc plot of normal value of x, y, +ve f is used by adding a -ve in it, and labels are provided
- shading interp is used to eliminate grids on the surfc.
- Another plot to represent the local minimum value with the optimized iteration of 50.
- The second row of subplot is created with +ve value of f.
- For the second method of optimization the same program is but the ga function is modified to provide the lower and upper bounce.
- The third method of optimization is also same but the total population of iteration is increased to 170 using the options type of ga
- Hence the more the population value the narrow will be the result.
%genetic algorithm
clear all
close all
clc
%initial parameters
x=linspace(0,0.6,150); %value assigned of 150 from 0 to 0.6 to x and y
y=linspace(0,0.6,150);
num_case=50; %num case is set to the value of 50
f=get_stalagmite(x,y); %stalagmite function is called with inputs x and y
tic
for i = 1:num_case %loop iterated from 1 to 50
%ga is called with stalagmite function and two inputs x and y
[inputs,fopt(i)]= ga(@stalagmite,2); %minimum value is fopt(i) and its co-ordinate to inputs
xopt(i)=inputs(1); %the x co-ordinate of fopt is assigned to xopt
yopt(i)=inputs(2); %the y co-ordinate of fopt is assigned to yopt
end
%time calculation of execution
studey_time= toc;
figure(1) %plot 1 is created
subplot(2,1,1) %subplot with 2 rows and 1 column is created
hold on %hold surf and plot3 together
surfc(x,y,(-f)) %creates surf plot in positive z co-cordinate
xlabel(\'x axis\') %label of x,y and z axis
ylabel(\'y axis\')
zlabel(\'z axis\')
shading interp %to eliminate grids over the surfc plot
%marks 50 values f in point and -fopt to plot on +ve z axis
plot3(xopt,yopt,(-fopt),\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Unbounded inputs\') %adding tittle to the plot
subplot(2,1,2) %plot on second row of subplot
%ploting 50 variation values of f
plot(-fopt)
xlabel(\'Iteration\') %x and y label to fopt plot
ylabel(\'F maximum\')
%second type optimization method
tic
for i = 1:num_case
%the function is provided with a limit in upper and lower bounce
[inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
%calculation of time execution of study 2
studey_time2= toc;
%creating plot 2
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,(-f))
xlabel(\'x axis\')
ylabel(\'y axis\')
zlabel(\'z axis\')
shading interp
plot3(xopt,yopt,(-fopt),\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Unbounded inputs\')
subplot(2,1,2)
plot(-fopt)
xlabel(\'Iteration\')
ylabel(\'F maximum\')
%third type optimization method
%the population is increased from 170
%rest are same
options=optimoptions(\'ga\')
options=optimoptions(options,\'populationSize\',170)
num_case=50;
tic
for i = 1:num_case
[inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
studey_time3= toc;
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
xlabel(\'x axis\')
ylabel(\'y axis\')
zlabel(\'z axis\')
shading interp
plot3(xopt,yopt,(-fopt),\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Unbounded inputs\')
subplot(2,1,2)
plot(-fopt)
xlabel(\'Iteration\')
ylabel(\'F maximum\')Graph:
first plot
Second plot
Third plot
Conclusion: - Hence the global maxima is found by optimizing the data by stalagmite function using the concept of genetic algorithm method.
Error:
The error was that f on the surfc plot was not converted which led to be negative because of the stalagmite formula(-ve on end).
This was resolved by surfc(x,y,(-f)).
Refference:
https://in.mathworks.com/help/gads/ga.html
https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/