Solving stalagmite function using Genetic Algorithm
Abstract :
A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. This theory is used as a search based optimisation technique to find the best solution.
In this project we aim at finding the global maxima of a "stalagmite Function" (defined below) with the help of Genetic Algorithm In Matlab.
What is Genetic Algorithm ?
In GA, 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”.
In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.
Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well.
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.
Genetic Algorithm Terminologies
1. Fitness Function : The fitness function is the function you want to optimize. For standard optimization algorithms, this is known as the objective function.
2. Individuals : An individual is any point to which you can apply the fitness function. The value of the fitness function for an individual is its score. An individual is sometimes referred to as a genome and the vector entries of an individual as genes.
3. Population : A population is an array of individuals. For example, if the size of the population is 100 and the number of variables in the fitness function is 3, you represent the population by a 100-by-3 matrix. The same individual can appear more than once in the population. For example, the individual (2, -3, 1) can appear in more than one row of the array.
4. Generation : At each iteration, the genetic algorithm performs a series of computations on the current population to produce a new population. Each successive population is called a new generation.
5. Diversity : Diversity refers to the average distance between individuals in a population. A population has high diversity if the average distance is large; otherwise it has low diversity.
6. Fitness Value and Best Fitness Value : The fitness value of an individual is the value of the fitness function for that individual. Because the toolbox software finds the minimum of the fitness function, the best fitness value for a population is the smallest fitness value for any individual in the population.
7. Parent and Children : To create the next generation, the genetic algorithm selects certain individuals in the current population, called parents, and uses them to create individuals in the next generation, called children. Typically, the algorithm is more likely to select parents that have better fitness values.
Stalagmite Function :
`f_1,_x = [sin(5pix + 0.5)]^6`
`f_1,y = [sin(5piy + 0.5)]^6`
`f_2,x = exp[-frac{4ln(2)(x-0.0667)^2}{0.64}]`
`f_2,y = exp[-frac{4ln(2)(y-0.0667)^2}{0.64}]`
f(x,y) = `f_1,_x xx f_1,y xx f_2,x xx f_2,y`
NOTE. Syntax for using GA
Case1 : [inputs, fval] = ga(fun,nvars)
Inputs represents the values of x and y for which function has minimumm value
fval - function minimum value
fun - function to be optimised
nvars - number of variables in our fitness function ie x and y
Case2 : [inputs, favl] = ga(fun,nvars, A, b, Aeq, beq, lb, ub)
Ex. If our function is defined by A*x <= b and Aeq*x = beq, then , A, b - Linear Inequality constraints. Since there is no constraint in our function, we write [] and Aeq,beq - Linear Equality contraints. Since there is no constraint in our function, we write []
lb - Lower bounds. Since no bounds given, we write []
ub - Upper bounds. Since no bounds given, we write []
Case3 : [inputs, favl] = ga(fun,nvars, A, b, Aeq, beq, lb, ub, nonlcon,IntCon,options)
nonlcon - Nonlinear Constraints. If there is none, write []
IntCon - Integer variables, specified as a vector of positive integers taking values from 1 to nvars. Each value in IntCon represents an x component that is integer-valued. if there is none, write []
options - Optimization options, specified as the output of optimoptions or a structure.
NOTE - ga in matlab is used only for minimisation of a function. Therefore for maximisation( like in this case) , the problem is converted into a minimisation and then solved.
1. Code for 3 different cases :
%defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%creating a 2D mesh
[xx, yy] = meshgrid(x,y);
%evaluating stalagmite_function
for i = 1:length(xx)
for j = 1:length(yy)
input_vector(1) = xx(i,j);
input_vector(2) = yy(i,j);
f(i,j) = stalagmite_function(input_vector);
end
end
%CASE 1 (Unbounded function with predefined population size)
num_case = 50;
tic
for p = 1:num_case
[input,fopt(p)] = ga(@stalagmite_function,2);
xopt(p) = input(1);
yopt(p) = input(2);
end
Running_Time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'Marker','o', 'MarkerFaceColor','r','LineWidth',2)
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Fun_Min')
------------------------------------------------------------------------------------
%CASE 2 (Statistical behaviour with upper and lower bounds)
num_case = 50;
tic
for p = 1:num_case
[input,fopt(p)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[1;1]);
xopt(p) = input(1);
yopt(p) = input(2);
end
Running_Time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'Marker','o', 'MarkerFaceColor','r','LineWidth',2)
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Fun_Min')
title('Statistical Behaviour with upper and lower bounds')
------------------------------------------------------------------------------------
%CASE 3 (Increasing Population size of GA)
options = optimoptions('ga');
options = optimoptions(options, 'populationsize',180);
num_case = 50;
tic
for p = 1:num_case
[input,fopt(p)] = ga(@stalagmite_function,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(p) = input(1);
yopt(p) = input(2);
end
Running_Time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'Marker','o', 'MarkerFaceColor','r','LineWidth',2)
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Fun_Min')
title('Incresing Population size')Explaination of above Code -
i) Under comment %defining search space
We divide the x and y between 0 to 0.6 in 150 equally spaced values.
ii) Under comment %creating a 2D mesh
We generate a 2D meshgrid.
iii) Under comment %evaluating stalagmite_function
We evaluate our stalagmite function for different values of x and y that we generated using meshgrid.
iv) Under comment %CASE 1 (Unbounded function with predefined population size)
In first case, we define the number of iterations as 50 for which our ga will run to optimise function. Then for loop is used to solve ga. The smallest value of function is outputted for each iteration and its x and y coordinated are stored in a seperate variable. The tic and toc command is used to determinne the time for which the loop ran and storing it in a variable named 'Running_Time'. Then 2 plots are printed, Upper plot shows the stalagmite function and the path that ga moves to find the global minima, lower plot depicts the function optimum value at each iteration. This is a case of unbounded function with predefined population size.
v) Under comment %CASE 2 (Statistical behaviour with upper and lower bounds)
In second case, we define our bounderies due to which the variables x and y will remain in defined search space in inputs. Rest program is same.
vi) Under comment %CASE 3 (Increasing Population size of GA)
In third case, we increase our population size as well as defining boundaries. This will generate more accuarate result. Rest progran is same.
2. Code for stalagmite function
function [func_value] = stalagmite_function(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x + 0.5))^6;
f2 = (sin(5.1*pi*y + 0.5))^6;
f3 = exp((-4)*log(2)*(x-0.0667)^2*(1/0.64));
f4 = exp((-4)*log(2)*(y-0.0667)^2*(1/0.64));
func_value = - f1*f2*f3*f4;
endResults :
Case 1 -
Case 2 -
Case 3 -
References :
https://in.mathworks.com/help/gads/ga.html#d120e41721
https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
https://in.mathworks.com/help/gads/some-genetic-algorithm-terminology.html
https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html - How Genetic Algorith Works?
https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm