Week 4 - Genetic Algorithm
Aim :
To write a program in MATLAB to optimize the stalagmite function and find the global maxima of the function.
Objectives :
- Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
- Clearly explain the concept of genetic algorithm and also explain the syntax for ga in MATLAB in the report.
- Make sure that the code gives the same output, even if it is made to run several times.
- Plot graphs for all 3 studies and for F maximum vs no. of iterations along with the titles and the axes.
Use of GA in our program :
GA is the abbrev. for Genetic Algorithm that is mimicking the biological concept of producing the next generation of the fittest value, by mating of the fittest values of the previous generation. This process happens by initially defining the fitness function which is why this function is used in MATLAB, where this fitness function varies as per the point of application/theory behind the concept where it is used. By using these fitness values, a series of processes such as selection, crossover and mutation take place upto the point where the termination happens which is where, further optimization cannot be achieved as the fittest individual by using the GA, through the previous generation of variables is achieved.
Theory of GA in brief :
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.
Notion of Natural Selection :
The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.
This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.
Five phases are considered in a genetic algorithm.
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
Initial Population :
The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.
An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).
In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.
Fitness Function :
The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.
Selection :
The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.
Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.
Crossover :
Crossover 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.
For example, consider the crossover point to be 3 as shown below.
Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.
The new offspring are 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.
Mutation 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.
Applying the GA function in our problem for optimization :
We see that firstly in the GA, we have a certain predetermined number of population, which in our case is the number of variables we have created by simply randomly assigning variations to every variable by giving random genetic values on the basis of our fitness function.
We describe our fitness function as :
where, x and y are our set of variables which serve as our inputs and could be unbounded or bounded during our study of this algorithm for our optimization.
In this, we derive a fitness value for our every x and y input, thus providing us the binary 0 and 1 value analogous to the genetic characteristic.
The, so called chromosome turns to be the product of these four terms we see above and thus every such product is called from the function and saved into an array to the corresponding input (x,y) values.
Here, we will be initially inputting a meshgrid command to create a 2D matrix of x and y, into [xx yy] so that for 2D plot we will be having a product of the terms for every point in the xy plane. The z value of the x(i) and y(i) plotted point will be determined by their respective combination or product value 'f(x(i),y(i))'.
This will be our first function, wherein our main program will be inputting the predetermined x and y values into this function using meshgrid and thus create a 2D matrix of points of x's and y's, to a combination of each x and y shall be assigned a corresponding product of fitness value 'f'.
As, we will be needing the global maxima, we shall find the positive product of these terms else we would just add a negative sign before the product symboling the global minima.
Beginning with our study :
Study 1 :
Our first study shall be done by passing our fitness function as our input argument for the ga function, on the basis of which ga function shall process the optimal solution.
Also, we will be defining our input values x and y using the linspace command.
Later we will pass the ga function and input the no of iterations we want the program to perform to give a clearer idea of our optimal solution being the only logical set of values to give us the desired optimization.
[, for any previous input arguments, also returns x,fval] = ga(___)fval, the value of the fitness function at x.
function f = get_stalagmite_best(x,y)
[xx yy] = meshgrid(x,y)
for m = 1:length(xx)
for n = 1:length(yy)
input_vector(1)=xx(m,n);
input_vector(2)=yy(m,n);
f(m,n) = stalagmite_best(input_vector);
end
endfunction [term] = stalagmite_best(input_vector)
term1 = (sin(5.1*pi*input_vector(1)+ 0.5))^6;
term2 = (sin(5.1*pi*input_vector(2)+ 0.5))^6;
term3 = exp(-4*log(2)*((input_vector(1)-0.0667)^2)/0.64);
term4 = exp(-4*log(2)*((input_vector(2)-0.0667)^2)/0.64);
term = -(term1*term2*term3*term4);
endclear all
close all
clc
% Passing the search space values and the necessary inputs
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 100
f = get_stalagmite_best(x,y);
% Study 1 - Statistical behaviour by inputting ga function and passsing no
% of variables (2), and the fitness function (stalagmite_best)
tic
for i = 1 : num_cases
[input1, fopt1(i)] = ga(@stalagmite_best,2);
xopt1(i) = input1(1);
yopt1(i) = input1(2);
end
study1_time = toc %for measuring the time taken to process the function
figure(1)
% for getting a 2x1 matrix style figure and assigning first plot by
% indicating (1) on the extreme right
subplot(2,1,1)
hold on
surfc(x,y,-f)
xlabel('X value')
ylabel('Y value')
zlabel('Function value')
% for giving a smoother looking stalagmite surface
shading interp
% Plots the optimal point of each iteration in 3D
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt1)
xlabel('Iterations')
ylabel('function Maximum')In the first code, we have taken the x and y values to create a meshgrid and then we have passed it onto another function which is our stalagmite function, which is our fitness function, and return these values back to variable 'f'.
In the function , we have created a for loop such that we can assign a fitness value to every combination of x and y respectively.
We also return the values of our ga function to input1 and fopt(i), where input1 takes the corresponding x and y values for the respective optimal function value and further we also return the input1 x and y value to an array xopt1(i) and yopt1(i) respectively.
We also assign '-f' into our plot commands and change our output values to turn the problem into a maximization problem as our values for 'f' are negative.
Thus we assign fopt(i) as '-fopt(i) too.
Output :
The function has used random variables as inputs and processed the program. Thus this has not helped us achieve our optimal solution as the program has not taken or might have taken a selected number of inputs from our desired search space.
Study 2 :
Here, the difference will be that we shall use the ga function and change the syntax by inputting the search space as upper bound and lower bound for x and y respectively, which will give us a much relevant solution if not the exact or the optimal solution.
The syntax hence used will take the form :
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist, and also A and B, in this case)
Looking at the way the function is defined, only the bounds have to be introduced.
We can use this information and change the required parameters or arguments.
clear all
close all
clc
% Passing the search space values and the necessary inputs
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 100
f = get_stalagmite_best(x,y);
tic
%Study 2 - Statistical behaviour - with upper and lower bounds
for i= 1:num_cases
[input2, fopt2(i)] = ga(@stalagmite_best,2,[],[],[],[],[0;0],[1;1]);
xopt2(i) = input2(1);
yopt2(i) = input2(2);
end
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
xlabel('X value')
ylabel('Y value')
zlabel('Function value')
% for giving a smoother looking stalagmite surface
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt2)
xlabel('Iterations')
ylabel('function Maximum')Output :
Now, from the second study we can infer that, we have defined the search space thus getting our stalagmite surface and the function maximum output as well, which is relevant to our desired output.
Here, the values for the solution change as we see in the function maximum plot. Thus to get an optimum solution we need to make a few more changes.
That brings us to our next study.
Study 3 :
In this study, we will be using a command whih helps us change the default parameters of the ga function which is the population size, and by changing this value we can obtain a certain optimal solution for our ga function.
options = optimoptions('ga')
options = optimoptions(options,'populationsize',170);
This will be our program base in the study 3. Our ga function thus takes the form :
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)IntCon take integer values.
Also, here we define our nonlcon - non linear constraints and Intcon - integer constraints as [],[] and the options in the ga function remain as it is in the program thus defining the change in the population size which the program has to work with.
clear all
close all
clc
% Passing the search space values and the necessary inputs
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 20
f = get_stalagmite_best(x,y);
% Study3 - increasing the populationsize to give more randomness and more
% accuracy of the final solution.
options = optimoptions('ga')
options = optimoptions(options,'populationsize',250);
tic
for i= 1:num_cases
%defining 'options' in the ga function and the nonlcon and IntCon
[input3, fopt3(i)] = ga(@stalagmite_best,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt3(i) = input3(1);
yopt3(i) = input3(2);
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
xlabel('X value')
ylabel('Y value')
zlabel('Function value')
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with increased population size')
subplot(2,1,2)
plot(-fopt3)
xlabel('Iterations')
ylabel('function Maximum')Conclusion :
In this manner, by seeing the 3 studies we can see how by using the optimization options in GA , we can actually narrow down on the optimal solution for our problem. By using and altering some parameters, we can actually optimize any problem given that the basis of the problem is defined by such a function(stalagmite function) as this.
References :
https://in.mathworks.com/help/gads/ga.html#d120e39323
https://in.mathworks.com/help/gads/genetic-algorithm.html
https://in.mathworks.com/help/optim/ug/passing-extra-parameters.html