Week 4 - Genetic Algorithm
AIM: To write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
OBJECTIVE: 1) Explanation about the concept of a genetic algorithm.
2) Explanation of syntax for ga in MATLAB.
EQUATIONS :
THEORY :
Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space.
“They are commonly used to generate high-quality solutions for optimization problems and search problems.”
A Fitness Score is given to each individual which shows the ability of an individual to “compete”. The individual having optimal fitness score (or near optimal) are sought.
The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores. The individuals having better fitness scores are given more chance to reproduce than others.
Operators of Genetic Algorithms
Once the initial generation is created, the algorithm evolve the generation using following operators –
1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass there genes to the successive generations.
2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example –
3) Mutation Operator: Mutation is a random process where once the genes are replaced by another to produce a new generic structure. The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence. For example –
This generational process is repeated until a termination condition has been reached. Common terminating conditions are:
- A solution is found that satisfies minimum criteria
- Fixed number of generations reached
Why use Genetic Algorithm
Fastest search technique.
Provide optimisation over large space state.
Does not require any derivative information
Always gets an answer to the problem, which gets better over the time.
Useful when the search space is very large and there are a large number of parameters involved.
Make no assumption about the problem space.
SYNTAX of GA :
x = ga(fun,nvars)
x = ga(fun,nvars,A,b)
x = ga(fun,nvars,A,b,Aeq,beq)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
x = ga(problem)
[x,fval] = ga(___)
Here,
Input Arguments
fun — Objective function
nvars - number of variables
A - Linear inequality constaints
b - Linear inquality constraints
Aeq - Linear equality constraints
beq - linear equlity constarints
lb - lower bound
up - upper bound
nonlcon - Nonlinear constraints
options - integer variables
problem - problem descriptions
Output Arguments
x - solution
fval - Objective function value at the solution
PROGRAM :
MATLAB CODE 1:
clear all
close all
clc
% Defining search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
% Creating 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
surfc(xx,yy,-f)
xlabel('x values')
ylabel('y values')
shading interp
[x,fval] = ga(@stalagmite,2)
Function code:
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 = -(f1*f2*f3*f4);
endOUTPUT :
MATLAB CODE 2 :
clear all
close all
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50
% Creating 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_func(input_vector);
end
end
% Study 1 - Statictical behavior
tic
for i = 1:num_cases
[inputs,fopt(i)] = ga(@stalagmite_func,2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study1_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
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 Maximum')
tic
% Study 2 - Statistical behavier - with upper & lower bounds
for i = 1:num_cases
[inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0,0],[1:1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
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 Maximum')
% Study 3 - Increasing GA interations
options = optimoptions('ga')
options = optimoptions(options,'PopulationSize',150);
tic
for i = 1:num_cases
[inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0,0],[1:1],[],[],options);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with increasing ga interations')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
Function code:
function [f] = stalagmite_func(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 = -(f1*f2*f3*f4);
endCode Explanation :
1) Start with clear all ,close all, clc to clear all content previously stored.
2) linspace command is used to define 150 x & y values between 0 to 0.6 with 50 num_cases to run 50 time.
3) meshgrid command is used to form two dimentional array.
4) for loop is executed to evaluate the stalagmite function.
5) For case study 1 - statictical behavier for loop is executed.During execution stalagmite function is called with 'ga'.Respective plotting is done. Also, tic and toc command is used to measure time taken for execution.
6) For case study 2 - statictical behavier with upper & lower bounds ,for loop is executed.During execution stalagmite function is called with 'ga'.Also tic and toc command is used to measure time taken for execution.
7) Again , For case study 3 - with increasing interations ,for loop is executed.During execution stalagmite function is called with 'ga'.Here optimoptions function is used to return ga solver and to define population size. Also tic and toc command is used to measure time taken for execution.
Function Creation
Here function is created called 'stalagmite_func(input_vector)' using standard formulae .It is get called in main program.
OUTPUT :
case 1:
case2:
case 3:
REFERENCE:
https://skill-lync.com/knowledgebase/genetic-algorithm-explained