Week 4.1 - Genetic Algorithm
Aim:
To understand the concept of genetic algorithm and optimize with the stalagmite function.
Objective:
- Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
- Clearly explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
- Make sure that your code gives the same output, even if it is made to run several times.
- Plot graphs for all 3 studies and for F maximum vs no. of iterations.
Genetic algorithm:
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions.Genetic algorithms employ the concept of genetics and natural selection to provide solutions to problems.
the genetic algorithm follows the following flow chart
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. To create the new population, the algorithm performs the following steps:
-
Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
-
Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
-
Selects members, called parents, based on their expectation.
-
Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
-
Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
-
Replaces the current population with the children to form the next generation.
-
-
The algorithm stops when one of the stopping criteria is met.
-
The algorithm takes modified steps for linear and integer constraints.
-
The algorithm is further modified for nonlinear constraints.
syntax for genetic algorithm:
x = ga(fun,nvars)x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
Stalagmite function:
A stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. Most stalagmites have rounded or flattened tips.
the mathematical function for stalagmite function is shown below
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);
endinput code:
clear all
close all
clc
% search space definition
x=linspace(0,0.5,150);
y=linspace(0,0.5,150);
N=50; %defining no of iteration
[X,Y]=meshgrid(x,y);% for 2D grid coordinates
%Evaluating the stalagmite function
for i=1: length(X)
for j=1: length(Y)
input_vector(1)=X(i,j);
input_vector(2)=Y(i,j);
f(i,j)=stalagmite(input_vector);
%stalagmite function takes in the data given inside parantheses and calculates f
end
end
surfc(X,Y,-f);
xlabel('X axis')
ylabel('Y axis')
shading interp
tic %measuring the time for study1
% study1 - without boundry condition
for i=1:N
[inputs,fopt(i)]=ga(@stalagmite,2);
%ga is an in-built function
%@defines what function is minimise
%2 denotes the no. of variables in the function, here it is x and y
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
Time_s1 =toc;
figure(1)
subplot(2,1,1)%for multiple plots inside the same figure window
hold on
surfc(x,y,-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 minimum');
tic
% study 2 - statistical behaviour - with upper and low boundary
for i=1:N
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
Time_s2 =toc;
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','s','markersize',5,'markerfacecolor','r')
title('bounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function minimum');
% study 3 - increasing ga iterations
options=optimoptions('ga')
options=optimoptions(options,'PopulationSize',320);
tic
for i=1:N
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
Time_s3 =toc;
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded Inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations');
ylabel('Function minimum');
code explanation:
- initially create x and y array and number of iterations you want.
- for 2D mesh: create xx and yy array by using meshgrid command.
- Using nested for loop, calculate the stalagmite function and store the value in f. Here we use –ve sign in stalagmite function, to calculate global maxima.
- Study-1, it calculate the global maxima by taking random samples from the function. Here we use tic-toc command for calculating the time taken for study-1
- syntax for ga in study -1 is [inputs,fopt(i)]=ga(@stalagmite,2);
- Study -2, it calculate the global maxima by giving boundry limits for the inputs.
- syntax for ga instudy 2 is [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);. In that you see the boundary limits 0 to 1.
- Study 3, it calculate the global maxima by given population size by which we can find the specific optimum point.
- syntax for ga in study 3 is [inouts,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);.
output:
study 1
study 2
here all local maxima are found
study 3
here the global maxima is found