Genetic Algorithm
AIM: To write a program to generate a genetic algorithm in MATLAB.
THEORY: A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.
One can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, non-differentiable, stochastic, or highly nonlinear.
PROGRAM:
1) Main Program
clear all;
close all;
clc;
% Defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
% Creating a 2D mesh
[xx,yy] = meshgrid(x,y);
% Defining the no of iteration
num_case = 50;
% Evaluating the 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(input_vector);
end
end
tic
% Study 1 Statistical behaviour
for i = 1:num_case
[inputs, fopt(i)] = ga(@stalagmite,2);
xout(i) = inputs(1);
yout(i) = inputs(2);
end
study1_time = toc;
figure(1)
subplot(2,1,1);
hold on;
surfc(xx,yy,-f);
shading interp;
plot3(xout,yout,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('Unbound Inputs');
xlabel('X');
ylabel('Y');
zlabel('f');
subplot(2,1,2);
plot(fopt);
xlabel('Iteration');
ylabel('Function Maximum');
tic
% Study 2 Statstical behaviour - with upper and lower bounds
for i = 1:num_case
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xout(i) = inputs(1);
yout(i) = inputs(2);
end
study2_time = toc;
figure(2)
subplot(2,1,1);
hold on;
surfc(xx,yy,-f);
shading interp;
plot3(xout,yout,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('Bounded Inputs');
xlabel('X');
ylabel('Y');
zlabel('f');
subplot(2,1,2);
plot(fopt);
xlabel('Iteration');
ylabel('Function Maximum');
% Study 3 Increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options, 'PopulationSize',150);
tic
for i = 1:num_case
[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xout(i) = inputs(1);
yout(i) = inputs(2);
end
study3_time = toc;
figure(3)
subplot(2,1,1);
hold on;
surfc(xx,yy,-f);
shading interp;
plot3(xout,yout,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
title('Bounded Inputs with more sample size');
xlabel('X');
ylabel('Y');
zlabel('f');
subplot(2,1,2);
plot(fopt);
xlabel('Iteration');
ylabel('Function Maximum');
2) User-defined function
%Stalagmite function
function input = stalagmite(input_vector)
a=input_vector(1);
b=input_vector(2);
x1=[sin(5.1*pi*a+0.5)]^6;
y1=[sin(5.1*pi*b+0.5)]^6;
x2=exp(-4*log(2)*((a-0.0667)^2)/0.64);
y2=exp(-4*log(2)*((b-0.0667)^2)/0.64);
input=-x1*y1*x2*y2;
end
EXPLANATION:
1) Main Program
The linspace() command divides the 0-0.6 values into 150 times and stored into the arrays x and y.
xx and yy 2 dimensional matrices are created using meshgrid function from 1D array of x, and y.
The total number of cases to be evaluated is decided to be 50 and stored into variable num_cases.
To find out the z value in the 3D graph we are using the stalagmite function. Each value from xx and yy graph are used as the constants a and b in the given equation. Using these values the value in the z axis corresponding to each value in the xx and yy axis is found out. This axis value is stored in the f vector.
Study 1- Statistical Study with no Bounds
Here the ga algorithm syntax is [coordinates, optimum value of function]=ga(@function, no of input).
We have to find out the optimum value for x and y axis from the z axis value already discovered.
For loop is used for various iteration
We run the genetic algorithm function to optimize the stalagmite function as input. This results in us receiving a vector 'coordinates' with the optimized values for both x, y and z axis. We save the values in the coordinates in variables as xoptc, yopt and fopt respectively.
We find out and save the time required to find out the optimized values using tic and toc.
We plot a surface graph using the values from x, y and f.
We plot a 3d graph using the optimized values xopt ,yopt and fopt.
we plot a graph between fopt and number of iterations.
Study 2- Statistical Study with Upper and Lower Bounds
Here the ga algorithms syntax is [coordinates,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
Here [0;0] and [1;1] represents the lower and upper bounds for the optimal values.
The rest of the steps are similar to study 1.
Study 3- Statistical Study with increased iterations
In this study we are going to increase the number of iterations from 150 to 500. This can be done using the option and optimoption functions.
Here the ga algorithm syntax is
[cordinates, optimumvalue]=ga(@function, 2,[],[],[],[],[0;0],[1;1],[],[],options);
The rest of the study code is similar to case 1 and 2.
2) User-defined program
Here the function stalagmite receives the vector 'input_vector' as its input value.
It outputs the value 'input'
The '-' is added to give us the maxima of the function.
OUTPUT
1) Plots
i) Study 1
ii) Study 2
iii) Study 3
2) Workspace
ERRORS:
No major error were encountered in while programming the project.
Additional Question
Clearly expalin the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
The genetic algorithm is an optimization tool. It mimics natural selection and genetics. Consider that we have a set of candidate solutions to any given problem. We can find the best or optimal solution by changing different factors in the candidate solutions. To manually change the factors and find out the optimal solution is a time and resource intensive process. Hence it is better to automate it. Using genetic algorithm we can evolve the candidate solution to the optimal solution in an automated manner. We just have to provide a limiting condition to the software to tell it when to stop the evolution of the solution or what parameters must be met for the solution to be optimal. This evolution can be doen in 3 ways
(i)Mutation-Any factor in the parent solutions randomly changed and checked whether the second generation solution is better than the parent solution. If so it is used as one of the parent for the next step of evolution
(ii)Crossover-Two candidate solution factors are combined and checked whether it is more optimal compared to the parent. If so it is passed on to the next generation solution.
(iii)Selection- The bets candidates of the parent solution pool are automatically passed on to the 2nd generation.
Ga Syntax.
x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun. fun is the funtion to be minimized. nvars is the number of variables.
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[]and beq=[] if no linear equalities exist.) lb and ub represents the upper and lower boundaries repectively.
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
REFERANCES