Week 5 - Genetic Algorithm
Aim:
To write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
Objective:
1. Explaining the concept of genetic algorithm and also explain the syntax for ga in MATLAB.
2.Plot graphs for all 3 studies and for F maximum vs no. of iteration.
Introduction:
A genetic algorithm (GA) is a computational optimization technique inspired by the process of natural selection and genetics. It is used to find approximate solutions to optimization and search problems by mimicking the principles of biological evolution. MATLAB is a popular programming environment for implementing genetic algorithms due to its ease of use and extensive libraries for mathematical and optimization tasks.
Here's a high-level explanation of how to implement a basic genetic algorithm in MATLAB:
Initialization:
- Define the problem: Clearly define the problem you want to solve and determine the variables that need to be optimized.
- Create an initial population: Generate a population of potential solutions (individuals). Each individual represents a potential solution to the problem, and they are typically encoded as arrays or strings.
- Define the fitness function: Write a fitness function that evaluates how good each individual is with respect to the optimization problem. This function assigns a fitness score to each individual.
Selection:
- Select individuals for reproduction: Use a selection mechanism (e.g., roulette wheel selection, tournament selection) to choose individuals from the current population based on their fitness scores. Individuals with higher fitness scores are more likely to be selected.
Crossover (Recombination):
- Create new individuals: Perform crossover (recombination) operations on selected pairs of individuals. Crossover combines the genetic information of two parents to create one or more offspring.
Mutation:
- Introduce small random changes: Apply mutation operations to some of the newly created offspring. Mutation introduces small random changes to an individual's genetic information to maintain genetic diversity in the population.
Replacement:
- Create the next generation: Replace the old population with the new population of offspring. This may involve selecting the best individuals from both the parent and offspring populations.
Termination:
- Repeat steps 2-5 for a certain number of generations or until a termination condition is met (e.g., a sufficiently fit individual is found or a maximum number of iterations is reached).
Syntax:
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,fval,exitflag,output] = ga(___)
[x,fval,exitflag,output,population,scores] = ga(___)
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.
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.
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.
BODY OF THE CONTANT:
The above equations are used in the stalagmite function to plot the graph in the main functions.
function[f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1_x = (sin(5.1*pi*x + 0.5)).^6;
f1_y = (sin(5.1*pi*y + 0.5)).^6;
a1 = ((x - 0.0667).^2)/0.64;
f2_x = exp(-4*log(2)*a1);
a2 = ((y - 0.0667).^2)/0.64;
f2_y = exp(-4*log(2)*a2);
f = -(f1_x.*f1_y.*f2_x.*f2_y);
end
While using the function at the end as we are using the -ve sign so that the plot will be reversed as we have to find the maxima of the given function using ga.
Main body
- Firstly, creating the mesh from the two vectors which will be acting as a search space to find the maxima of the function.
- Creating the mesh of these two vectors using the ‘mesh’ command and defining the no. of iterations as num_cases to iterate the values of the optimum values of the function.
- Now calculating the values of fitness function at each point of the mesh grid formed.
- Now creating its surface through ‘surfc’ command which will also provide the contour of the generated surface.
- While using surfc applying the -ve sign to the function will generate the surface upside down which will be quite good to get the maxima of the function, as it will provide positive value for the maxima using the -ve sign.
clear all
close all
clc
%% PROVIDING THE SEARCH SPACE FOR THE FUNCTION
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[x,y]=meshgrid(x,y);
num_cases=50; %Number of itreation for which the function will evaluate the fitness
%% CREATING THE SURFACE PLOT OF STALAGEMITE 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); %values of function in given search space
end
end
surfc(x,y,-f); %generating the surface
shading interp %To remove the lines produced by the mesh grid
The plot generated is shown below:
Statistical behaviour without boundation:
In this evaluating the optimum value of fitness function at each iteration and calculating it using the above-mentioned syntax in the intro part (which gives the inputs ie. Values of x and y at which the stalagmite function is minimum)
Then plotting it into the surf command and also providing the optimum values of the function that how it is varying.
Also using the tic and tok command to evaluate the time used for optimizing the function.
%% STATISTICAL BEHAVIOUR (UNBOUNDED)
tic �lculating the study time through tic and toc command
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2); �lculating the optimized value of the function
xopt(i)=inputs(1); %at each iteration
yopt(i)=inputs(2);
end
study1_time=toc %displaying the time taken to evaluate
% PLOTING THE GRAPH
figure(1)
subplot(2,1,1)
surfc(x,y,-f);
hold on
shading interp
plot3(xopt,yopt,-fopt,’marker’,’o’,’markersize’,5,’markerfacecolor’,’r’);
xlabel(‘x’);
ylabel(‘y’);
grid on
subplot(2,1,2)
plot(-fopt);
xlabel(‘iterations’)
ylabel(‘function min value’)
Result:
From the figure as shown above it is clear that the results are not that much accurate and giving a lot of variation in optimizing the function.
Statistical study with the boundation:
The difference over here is in providing the upper and the lower limit in the ga so that the search space is reduced with the upper and lower boundary
And then plotting it as similar to the above study.
%% STATISTICAL BEHAVIOUR (BOUNDED)
tic �lculating the study time through tic and toc command
for j=1:num_cases
[inputs,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]); �lculating the optimized value of the function
xopt(j)=inputs(1); %at each iteration with boundation
yopt(j)=inputs(2);
end
study2_time=toc
%PLOTTING
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,’marker’,’o’,’markersize’,5,’markerfacecolor’,’r’);
xlabel(‘x’);
ylabel(‘y’);
grid on
subplot(2,1,2)
plot(-fopt);
xlabel(‘iterations’)
ylabel(‘function min value’)
Result:
It is clearly seen from the above that after providing the boundary limits the variation in the optimum value of the function has reduced.
Study with the increase in size of population:
In this study using the ‘optimoptions’ command to increase the size of population.
The benefit of that will be it will be working on the large set of numbers and which will be led to increase the possibilities of finding the better fitness of the function.
The drawback is that the time for evaluation will increase.
options=optimoptions(‘ga’,’populationsize’,300) %increaing the sixe of population by using
%optimoptions function
tic
for k=1:num_cases
[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
end
study3_time=toc
%PLOTTING
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel(‘x’);
ylabel(‘y’);
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
Results:
Main Code:
clear
close all
clc
%% PROVIDING THE SEARCH SPACE FOR THE FUNCTION
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[X,Y]=meshgrid(x,y);
num_cases=50; %Number of itreation for which the function will evaluate the fitness
%% CREATING THE SURFACE PLOT OF STALAGEMITE 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); %values of function in given search space
end
end
surfc(x,y,-f); %generating the surface
shading interp %To remove the lines produced by the mesh grid
%% Statistical Behaviour (UNBOUNDED)
tic �lculating the study time through tic and toc command
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2); �lculating the optimized value of the function
xopt(i)=inputs(1); %at each iteration
yopt(i)=inputs(2);
end
study1_time=toc %displaying the time taken to evaluate
% PLOTING THE GRAPH
figure(1)
subplot(2,1,1)
surfc(x,y,-f);
hold on
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
%% STATISTICAL BEHAVIOUR (BOUNDED)
tic �lculating the study time through tic and toc command
for j=1:num_cases
[inputs,fopt(j)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]); �lculating the optimized value of the function
xopt(j)=inputs(1); %at each iteration with boundation
yopt(j)=inputs(2);
end
study2_time=toc
%PLOTTING
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolo','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
%% MODIFYING THE NUMBER OF POPULATION
options=optimoptions(‘ga’,’populationsize’,300) %increaing the sixe of population by using
%optimoptions function
tic
for k=1:num_cases
[inputs,fopt(k)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(k)=inputs(1);
yopt(k)=inputs(2);
end
study3_time=toc
%PLOTTING
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x');
ylabel('y');
grid on
subplot(2,1,2)
plot(-fopt);
xlabel('iterations')
ylabel('function min value')
Results:
CONCLUSION:
When multiple number of iteration runs,ga becomes optimum or linear.The significance of num cases is to check over consistency of output values of ga whether it gives same output for all iterations,so that it can undergoes optimum value. i.e.,global maxima can be found.
If we provide less iteration and run the program,ga may or may not able to find global maxima.But as no. of iteration increases probability of finding global maxima can also increases.as when population size increases with iteration,probability of global maxima can be optimise.
RESULT:
Thus the global maxima of the stalagmite function is optimised using genetic algorithm in MATLAB.