Week 5 - Genetic Algorithm
AIM
The aim is to study Genetic Algorithm and to calculate the global maxima of the stalagmite function using a Genetic Algorithm in Mathlab
OBJECTIVE
write a code in Mathlab to optimize the stalagmite function find the global maxima of the function and plot graphs based on its studies.
PROCEDURE
Concept Of Genetic Algorithm
The genetic algorithm works on the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. It is a method for solving both constrained and unconstrained optimization problems that is based on natural selection. The algorithm begins by creating a random initial population of individual selections and it keeps on modifying this population repeatedly creating a sequence of new populations. The algorithm uses the individuals in the current generation to create the next population. the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population evolves toward an optimal solution.
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 of 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.
The basic steps in creating a genetic algorithm are:
- The algorithm creates a random initial population at the beginning.
- Then it creates a new population, and the algorithm scores each member of the current population by computing its fitness value and converting them into a more usable range of values.
- Then based on these new values the algorithm selects members, called parents.
- Then the algorithm produces children from the parents. Children are produced either by making random changes to a single parent which is a mutation or by combining the vector entries of a pair of parents which is crossover.
- In this way, the algorithm replaces the current population with the children to form the next generation.
- The algorithm stops when it reaches any one of the specified factors such as time limit, generations, function tolerance, constraint tolerances, etc.
THE FLOW CHART FOR THE GENETIC ALGORITHM
STALAGMITE FUNCTION
The stalagmite function is a mathematical model which helps to generate local minima and maxima. It is a dimensional function and the way the function is designed is that it has a lot of local maxima or minima and one global maximum and minima. The same name stalagmite is actually a type of rock formation that arises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings.
The function is given as:
`f1,x=[sin(5.1pix+0.5)]^6`
`f1,y=[sin(5.1piy+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]`
∴`f(x,y) = f1,x`.f1,y.f2,x.f2,y`
The syntax for defining 'ga' (Genetic Algorithm) in Mathlab
The syntax is used to find the minimum of a function using a genetic algorithm. There are several ways to define the 'ga' function depending on the problem being solved. The syntax used for this study :
- x=ga(fun,nvars)
x= optimal solutions
fun=objective function
nvars=nuber of variable
Sometimes'[x,fval] is used instead of 'x' where 'fval' gives objective function value at the solution
- x=ga(fun,nvars,A,B,Aeq,Beq,lb,ub)
A,B=linear inequality constraints
Aeq,Beq=linear equality constraints
if there are no linear equalities and inequalities then A,B,Aeq,Beq are set to '[]'
- x=ga(fun,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,IntCon,options)
nonlcon=nonlinear constraints
IntCon=integer values
options=optimization options
If there are no nonlinear constraints and integer values, the nonlcon and IntCon are set to'[]'
The following stalagmite function is defined as:
function [stalagmite] = stalagmite_func(input_vector)
x = input_vector(1);
y = input_vector(2);
f1_x = (sin(5.1*pi*x+0.5)).^6;
f2_y = (sin(5.1*pi*y+0.5)).^6;
f3_x = exp((-4*0.6931).*(x-0.0667)^2/(0.64));
f4_y = exp((-4*0.6931).*(y-0.0667)^2/(0.64));
stalagmite = -(f1_x.*f2_y.*f3_x.*f4_y);
end
The negative sign in the function will invert the stalagmite plot which will eventually give the function maxima.
The following coding of the genetic algorithm for the stalagmite function
- The x and y arrays are defined using the linspace command to create values at 150 equal intervals.
- A 2D mesh of x and y array is created by using the mesh grid command and the number of iterations or cases that code should perform is defined. This is given by n=50.
- To evaluate the stalagmite function for loop is used where i is initialized and for every value of i another for loop is used to initialize j.
- The input vector values of ''xx ''and'' yy ''are defined and the stalagmite function for these input vectors is defined. This will form a basic stalagmite function and we can plot it separately if needed.
- After preparing the inputs needed for the function next step is to obtain the results for 3 cases of the genetic algorithm. In the first case or study the maximum value of the function is found with no restrictions no bounds and no limits.
- This is done using for loop where we use' ga' syntax to give values for inputs and optimum max value. The stalagmite function is called in' ga 'syntax and a number of variables'' nvars'' are 2.
- To know the time that is taken to solve the loop for 50 iterations'' tic'' and'' toc ''command is used before and after the loop respectively.
- Then the function created in the loop is plotted by using surfc command for ''xx'',''yy'', and function output. To neglect the fridlines on the surface and obtain a smooth and clean plot shading interp command is used . The subplot(2,1,1) is used to plot multiple plots on the same figure which also divides the figure in a grid of 2x1 and axes to be placed at 1.
- The plot 3 command plots the 3D points at ''xopt'',''yopt'', and the optimum value of function with o shaped and red colour. The labels and title are then provided. Now in the same figure, the values of optimum function fopt are plotted for 50 iterations.
- The results of the above case will be different for each time we run the program. To get the same value each time, we need to restrict the program within specific bounds namely upper bound and lower bound. The procedure for coding and plotting in this procedure is the same as study 1 The only difference is in the ga syntax. This time the algorithm is provided lower limits and upper limits as [0;0] and [1;1] respectively.
- After plotting the results for study 2 or the bounded case, it is observed that the results are not the same every time the program terminates. A solution to this problem is to increase the number of cases or iterations.
- So for the study 3 the number of iterations is increased to 300. So for this study, ''options = optimooptions('SolverName', 'Name', 'Value')'' is used which returns with named parameter 'Populations' with the altered values '300'.
- The syntax for 'ga' contains the 'option' term and the rest of the code is the same as for Study 1 and 2.
RESULTS
- STUDY 1 - Statistical Behaviour
It could be observed how the random sampling of the genetic algorithm generates a new optimum value for the function every time the decode is run. Although this falls in line with the definition of Genetic Algorithm. A large number of red dots shows values of co-ordinates of x, and y vary each time iteration runs.
STUDY 2 - Statistical Behaviour with upper and lower bounds
The graph shows the convergence of x and y values. The number of red dots is less compared to the previous plot. This is the result of providing upper and lower bounds to the function.
STUDY 3 - Statistical Behaviour with increasing iterations of GA
The number of iterations is increased to 300 to converge and find the global maxima of the function. Here we can see that there is only one red dot on the stalagmite function and that is the required global maxima point.
No major errors were found.
REFERENCES