Week 4 - Genetic Algorithm
Aim : To find the global maxima of the given stalagmite function using Genetic Algorithm.
Theory :
Stalagmite Function to be optimized using GA is given below:
`f(x,y)=f1,x*f2,x*f1,y*f2,y`
where,
`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)]`
Optimization of a Function:
Optimization helps to find the best results under a set of prioritized criteria or constraints. It is a procedure which is executed in iterations by comparing various solutions till an optimum or a satisfactory solution is found.
An optimization problem consists of maximizing or minimizing a real function by using various provided input values and then computing the valve of the function.
Genetic Algorithm(GA) :
Genetic Algorithm (GA) is an 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 which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems in various fields of engineering applications.
GA in MATLAB :
A genetic algorithm is a method for solving optimization problems based on a natural selection process that mimics biological evolution. 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.This process goes on untill an optimum solution is produced.
How GA works :
The following outline summarizes how the genetic algorithm works:
-
The algorithm begins by creating a random initial population.
-
The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population.
- The algorithm stops when one of the stopping criteria is met.
Stopping/Termination Criteria :
The genetic algorithm stops when generations, time,fitness,stall generation,stall time limits are reached.
Syntax of ga() function:
[x,fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
where
fun - fitness function (here stalagmite)
nvars - number of design variables
A,b - linear inequalities, if any
Aeq,beq - linear equalities, if any
lb - lower bound
ub - upper bound
nonlcon - non-linear constraints, if any
options - create options using optimoptions
fval - returns fval, the value of fitness function at x
MATLAB CODE:
Program to find the global maxima of the given stalagmite function.
Three studies are conducted -
(i) Unbounded optimization
(ii) Bounded optimization
(iii) Bounded optimization with increased population size,
respectively.
As a result, we will obtain 3 plots where Max Function value vs No of iterations graph is plotted to know the variation of optimum value in each iteration.
Main code:
clear all
close all
clc
%OPTIMIZING A STALAGMITE FUNCTION USING GENETIC ALGORITHM (GA)
%
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%now we specify the number of iterations
num_cases = 150 ;
[xx, yy] = meshgrid(x,y);
%evaluating the stalagmite function by creating a For loop
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: UNBOUNDED VARIABLES
for i = 1:num_cases
[inputs1, fopt1(i)] = ga(@stalagmite,2);
xopt1(i) = inputs1(1);
yopt1(i) = inputs1(2);
end
timer_1 = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Optm.')
subplot(2,1,2)
plot(-fopt1)
xlabel('iteration')
ylabel('function max')
colorbar
%STUDY 2 : BOUNDED VARIABLES
tic
for i = 1 : num_cases
[inputs2, fopt2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
xopt2(i) = inputs2(1);
yopt2(i) = inputs2(2);
end
timer2 = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded optimization')
subplot(2,1,2)
plot(-fopt2)
xlabel('iteration')
ylabel('function max')
colorbar
%STUDY 3 : BOUNDED VARIABLES Increased popuation size
options = optimoptions('ga');
options = optimoptions(options,'Populationsize',500);
tic
for i = 1 : num_cases
[inputs3, fopt3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.1;0.1],[],[],options);
xopt3(i) = inputs3(1);
yopt3(i) = inputs3(2);
end
timer3 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(-fopt3)
xlabel('iteration')
ylabel('function max')
disp(inputs3)
colorbar
Using tic toc command to calculte the time taken for each iteration.
Matlab code for the stalagmite function:
Stalagmite Function:
`f(x,y)=f1,x*f2,x*f1,y*f2,y`
where,
`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)]`
function [F] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
a = (sin(5.1*pi.*x + 0.5)).^6;
b = (sin(5.1*pi.*y + 0.5)).^6;
c = exp(4*-log10(2).*((x-0.0667).^2) /0.64);
d = exp(4*-log10(2).*((y-0.0667).^2) /0.64);
F = -a.*b.*c.*d; %for maxima
end
OUTPUTS:
STUDY `I`: UNBOUNDED
Here, the values are not converging and hence this cannot be used as a useful result.
STUDY `III`: BOUNDED
In study 2, we confined the domain of the stalagmite function by providing lower and upper bounds. So, the ga() function will take individuals from the bounded domain only. Hence, we narrowed down our results drastically.
STUDY `III`: BOUNDED WITH INCREASED POPULATION
Here, The global maxima has converged at a point
0.0668 0.0668
Also the function maxima(function max) has converged to a close set of values which can be used effectively.
References:
https://in.mathworks.com/help/gads/ga.html#mw_f69991d0-5b23-4023-8c8e-e2890f2474d5