Genetic Algorithm in MATLAB
Title : Genetic Algorithm program for calculating local maxima for a given function.
Genetic Algorithm:
Genetic algorithm is based upon random sampling. It is the method of solving constrained and unconstrained problems which are based upon selection. This process is derived from the biological evolution.The genetic algorithm includes three main steps,
Selection :Select the individuals according to the fitness, called parents, that contribute to the population at the next generation.
Crossover : Combine two parents to form children for the next generation.
Mutation : Here random changes occurs in individual parents to form children.
While carrying out genetic algorithm,random sample points are chosen in the workspace and the function is evaluated at these random points.Then the limiting point(maxima/minima) is approached on these points where the function gives the relatable output.Then the sampling workspace is made more constrained and iterations occur to evaluate the function at new sample points.This is continued till the new iterations return the same value for the fuction ie. the solution converges.
This final converging point is the maxima/minina of the function.
Genetic algorithm is carried out in MATLAB as a predefined function - ga.
The MATLAB code for carrying out ga is given below.
clear all
close all
clc
% Defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
n = 100;
% Creating a 2-D mesh
[a b] = meshgrid(x,y)
% Evaluating the Stalagmite function
for k = 1:length(a)
for j = 1:length(b)
input_vector(1) = a(k,j);
input_vector(2) = b(k,j);
f(k,j) = stalagmite(input_vector);
end
end
surfc(a,b,f)
xlabel(\'x value\')
ylabel(\'y value\')
shading interp
hold on
[inputs,fval]= ga(@stalagmite,2)
tic
% Study1 - Behaviour without boundary conditions
for i = 1:n
[inputs,fopt(i)] = ga(@stalagmite,2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
xlabel(\'x value\')
ylabel(\'y value\')
shading interp
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\');
title(\'Unbounded inputs\')
subplot(2,1,2)
plot(fopt)
xlabel(\'iterations\')
ylabel(\'Function minimum\')
% Study 2 - Under upper and lower boundaries
tic
for m = 1:n
[inputs,fopt(m)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(m) = inputs(1);
yopt(m) = inputs(2);
end
study2_time = toc;
figure(2)
subplot(2,1,1)
hold on
surf(x,y,f)
xlabel(\'x value\')
ylabel(\'y value\')
shading interp
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
title(\'bounded inputs\')
subplot(2,1,2)
plot(fopt)
xlabel(\'iterations\')
ylabel(\'function minimum\')
% Study 3- Increaing the iterations
options = gaoptimset(\'ga\')
options = gaoptimset(options,\'populationsize\',400)
tic
for o = 1:n
[inputs,fopt(o)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(o)
yopt(o)
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surf(x,y,f)
xlabel(\'x value\')
ylabel(\'y value\')
shading interp
plot3(xopt,yopt,fopt,\'marker\',\'o\',\'markersize\',5,\'markerfacecolor\',\'r\')
title(\'bounded inputs\')
subplot(2,1,2)
plot(fopt)
xlabel(\'iterations\')
ylabel(\'function minimum\')
figure(4)
surfc(a,b,f)
xlabel(\'x value\')
ylabel(\'y value\')
shading interp
[inputs,fopt(o)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
study_time,study2_time,study3_time
The code for the define stalagmite fuction is written below.
function[f] = stalagmite(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))./(0.64));
f4 = exp(-4*(log(2))*(((y-0.0667).^2))./(0.64));
f = 1/(1+(f1*f2*f3*f4))
endExplaination of the code :
The code starts with defining our search space, x and y defines our search space.n is the number of iterations we want.
Further for loops are used for getting the coordinates of the 2 dimensional grid. By calling the function in loop we make sure that the value of f is calculated at each and every element of 150*150 co-ordinate matrix.The input for the stalagmite function is input_vector.
In this program we did 3 studies. In study 1, we ran the genetic algorithm without making any boundary conditions. Then plots are ploted function value vs iterations.
In study 2, the genetic algorithm is used to find the values of f. Here, we have the lower and upper boundaries i.e 0 and 1 respectively.
In study 3, the genetic algorithm is used to find the values of f. Here too we have lower and upper boundaries 0 and 1 respectively. But we have increased the population from 50 to 400 and then a plot is plotted.
tic and toc command is used to calculate the time required for running each study.Shading interp is used for removing the grids.
Syntax of Genetic algorithm:
For Study 1
[inputs,fopt(i)] = ga(@stalagmite,2);
inputs - inputs or coordinates
fopt(i) - It is the optimum value of the function that ga has found while solvin the function in the search boundaries during iterations i.
ga - function call
stalagmite - function to be optimized
2 - number of variables.
For Study 2
[inputs,fopt(m)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
fopt(m) - It is the optimum value that ga has found in iteration m
[],[] - first 2 square brackets state that non linear ineqalities exists between x and y
[],[] - 3rd and 4th square bracket state that non linear ineqalities exists between xeq and yeq
[0;0] - it is lower boundary condition of x and y
[1;1] - it is upper boundary condition of x and y
For Study 3
[inputs,fopt(o)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
[],[] - first 2 square brackets state that non linear ineqalities exists between x and y
[],[] - 3rd and 4th square bracket state that non linear ineqalities exists between xeq and yeq
[0;0] - it is lower boundary condition of x and y
[1;1] - it is upper boundary condition of x and y
[],[] - 5th and 6th square bracket indicats that there are no non linear constraints
Output generated:
The following plots are generated:
For Study 1:
As in study 1, the there are no boundary limits the minimization values of function f lies between 0.5 and 1.
For study 2:
In study 2, the boundaries are updated. Hence the values of the function lies between 0.5 to 0.7
For study 3:
In study 3, as there is increase in population as well as boundaries are applied, the values lie between 0.5 to 0.5001.
The study times for all the 3 cases were obtained in the workspace as
75seconds for 1st case
36seconds for 2nd case
268seconds for 3rd case.
These results were exactly as expected.Time was reduced for the second case as the workspace was within defined boundaries.Reduced workspace reduced the nuber of trial points and thus time.
Maximum time was obtained for the 3rd case ,as the lookup resolution/The population size was drastically increased from 50 to 400 in 3rd case.
Inputs wer the values of x and y for which the optimum value of function was obtained.
Inputting the term\"input \"in the command window gives the following output for x and y.
This can also be verified manually by rotating the plot and hovering the mouse upon the optimum function value.
The system will automatically show the corresponding x and y coordinates.
However this will be roughly estimated value.
Figure showing rough values of x,y at F(optimum).