Week 4.1 - Genetic Algorithm
Aim:To write a code to optimize the stalagamite function and find the global maxima of the function.
Objectives:
- To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
- To clearly expalin the concept of genetic algorithm in own words and also explain the syntax for ga in MATLAB in your report.
- To make sure that your code gives the same output, even if it is made to run several times.
- To Plot graphs for all 3 studies and for F maximum vs no. of iterations. Title and axes labels are a must, legends could be shown if necessary.
Theory: - A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function. 3. For this in Matlab we are using a method called 'Optimization'.
- In matlab to optimize we use Genetic Algorithm method which is inbuild function in matlab to find the global maxima of given stalagmite function.
Genetic Algoritrhm: - 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. ... The sequence of points approaches an optimal solution.
-
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:
*Selection rules select the individuals, called parents, that contribute to the population at the next generation.
*Crossover rules combine two parents to form children for the next generation.
*Mutation rules apply random changes to individual parents to form children.
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.
5. The algorithm is further modified for nonlinear constraints.
Syntax for ga
Explanation of the syntax
Description
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.
Passing Extra Parameters explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.
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,Aeq,beq,lb,ub,nonlcon,intcon) or x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) requires that the variables listed in intcon take integer values.
When there are integer constraints, ga does not accept nonlinear equality constraints, only nonlinear inequality constraints.
x = ga(problem) finds the minimum for problem, a structure described in problem.
[x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
[x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
[x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.
clc
close all
clear all
%stalagmite function
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
%creating 2d mesh
[xx, yy]=meshgrid(x,y);
% % for evaluating stalagmite function
%nested loop for array value input
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_fn(input_vector);
end
end
surfc(xx,yy,f)
shading interp
xlabel('xaxis')
ylabel('yaxis')
[results,fval]= ga(@stalagmite_fn,2);
maximum=-fval;
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
%we have initialize 150 values of x & y within the range 0 to 0.6
%for study 1
%%for study_statistical behaviour
iterations=50; %we have considered 50 values of itterations
tic
% f=stalagmite_fn(@stalagmite_fn,x,y);%it was error here i had called fvariable twice..by removing this it can be solved
for i=1:iterations
[inputs,fopt(i)]=ga(@stalagmite_fn,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study_time1=toc;
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',6,'MarkerFaceColor','r');
title('unbounded input');
subplot(2,1,2);
plot(-fopt)
xlabel('iterations');
ylabel('function maximum');
%for study 2
%for study_statistical behaviour inserting bounding inputs
iterations=50;
tic
for i=1:iterations
[input,fopt(i)]=ga(@stalagmite_fn,2,[],[],[],[],[0;0],[1;1]);
xopt(i)=input(1);
yopt(i)=input(2);
end
study_time2=toc;
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3( xopt,yopt,-fopt,'marker','o','MarkerSize',6,'MarkerEdgeColor','r');
title('bounded input');
subplot(2,1,2);
plot(-fopt);
xlabel('iterations')
ylabel('function maximum')
%for study 3
%for study_statistical behaviour inserting bounding inputs with modified
%population size
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',250);
tic
for i=1:iterations
[input, fopt(i)]=ga(@stalagmite_fn,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i)=input(1);
yopt(i)=input(2);
end
study_time3=toc;
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',4,'MarkerEdgeColor','b');
title('bounded input after modifying population size');
subplot(2,1,2);
plot(-fopt);
xlabel('iterations')
ylabel('function maximum')
%for study 3
%for study_statistical behaviour inserting bounding inputs with modified
%population size
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',250);
tic
for i=1:iterations
[input, fopt(i)]=ga(@stalagmite_fn,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i)=input(1);
yopt(i)=input(2);
end
%for study 4
%for study_statistical behaviour inserting bounding inputs with modified
%population size
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',350);
tic
for i=1:iterations
[input, fopt(i)]=ga(@stalagmite_fn,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i)=input(1);
yopt(i)=input(2);
end
study_time4=toc;
figure(4)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',6,'MarkerEdgeColor','r');
title('bounded input after modifying population size');
subplot(2,1,2);
plot(-fopt);
xlabel('iterations')
ylabel('function maximum')
Stalagmite function
%function
% we have called a function s with a input vectors a stalagmite function
function s= stalagmite_fn(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);
s=-f;
%here we get the global minima value so to get global maxima we have used
%-f
end
Two random array x&y values were created and the corresponding 2d array was obtained using meshgrid function.A nested loop was used to asign values from the array as input vector.input vector is the input to the stalagmite function.The stalagmite function is written as seperate.Minus sign is given to the output of stalagmite fn so that after ga process we get the global maxima.Tic-Toc commands are used to get running time of each case,In the first study the bounds are not defined .Negative sign is given for f value inside sufc fn to get the stalagmite fn upwards.Bounding is given in next case so that the number of soln approaches more accuracy.The population is increased in the the subsequent study with bounded inputs .The global maxima is found in last case.The x&y values for which the functn has maximum value display.
