Week 4 - Genetic Algorithm
Aim:
Write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
Genetic algorithm:
Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems that otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.
In GAs, 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”.
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.
'ga' syntax:(I found these syntaxes in the Matlab help)
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.
x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').
x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').
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.)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
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.
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values
formulas used:
Matlab code:
code for stalagmite function:
function fx_y=stalagmite(inputvector)
x=inputvector(1);
y=inputvector(2);
f1_x=(sin(5.1*pi*x+0.5)).^6;
f1_y=(sin(5.1*pi*y+0.5)).^6;
f2_x=exp(-4*log(2).*(x-0.0667).^2/0.64);
f2_y=exp(-4*log(2).*(y-0.0667).^2/0.64);
fx_y=-(f1_x.*f1_y.*f2_x.*f2_y);
end
study1:
%To calculate the maxima of a function with unbounded inputs
clear all
close all
clc
% inputs for search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
% number of iterations
num_cases=50;
% creating a 2_dimensional mesh
[xx,yy] = meshgrid(x,y);
% 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
% Study1-Statistical behaviour with unbounded input values
for a=1:num_cases
[inputs,fopt_1(a)]= ga(@stalagmite,2);
xopt(a)=inputs(1);
yopt(a)=inputs(2);
end
study1_time=toc;
% plotting our data
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
colorbar
plot3(xopt,yopt,-fopt_1,'marker','o','markerfacecolor','r','markersize',5)
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt_1)
xlabel('Iterations')
ylabel('Function maximum')study2:
% To calculate the maxima of a function with bounded inputs
clear all
close all
clc
% inputs for search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
% creating a 2_dimensional mesh
[xx,yy] = meshgrid(x,y);
% 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
% Study2-Statistical behavior with upper and lower bounded input values
for b=1:num_cases
[inputs,fopt_2(b)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(b)=inputs(1);
yopt(b)=inputs(2);
end
study2_time = toc
% plotting our data
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
colorbar
plot3(xopt,yopt,-fopt_2,'marker','o','markerfacecolor','r','markersize',5)
title('Bounded inputs')
subplot(2,1,2)
plot(-fopt_2)
xlabel('Iterations')
ylabel('Function maximum')study3:
% To calculate the maxima of a function with bounded inputs and
% increasing iterations
clear all
close all
clc
% inputs for search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
% creating a 2_dimensional mesh
[xx,yy] = meshgrid(x,y);
% 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
% Study3-Statistical behavior with upper and lower bounded input values
% and increasing genetic algorithm iterations
option_1 = optimoptions('ga');
option_1 = optimoptions(option_1,'Populationsize',300);
tic
for c=1:num_cases
[inputs,fopt_3(c)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],option_1);
xopt(c)=inputs(1);
yopt(c)=inputs(2);
end
study3_time = toc
% plotting our data
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
colorbar
plot3(xopt,yopt,-fopt_3,'marker','o','markerfacecolor','r','markersize',5)
title('Bounded inputs with increasing population size')
subplot(2,1,2)
plot(-fopt_3)
xlabel('Iterations')
ylabel('Function maximum')Results:
study1:
study2:
study3:
If not implemented properly, the GA may not converge to the optimal solution.