Week 4 - Genetic Algorithm
GENETIC ALGORITHM
AIM :
To write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
EQUATIONS USED :
Stalagmite function `f(x,y)=f_(1x)*f_(2x)*f_(1y)*f_(2y)`
where, `f_(1x)=[sin(5.1pix+0.5)]^6`
`f_(1y)=[sin(5.1piy+0.5)]^6`
`f_(2x)=exp[-4ln(2)(x-0.0667)^2/0.64]`
`f_(2y)=exp[-4ln(2)(y-0.0667)^2/0.64]`
OBJECTIVES :
- To define stalagmite function and make necessary modification to make it suitable for maximizing problem
- To understand concept of Genetic Algorithm and syntax of Genetic algorithm in MATLAB
- To optimize the Genetic Algorithm to give same result on each iteration for stalagmite function
- To find Maximum value of function
CONTENT :
Genetic Algorithm (GA) solves optimization problems based on natural selection, the process that drives biological evolution. It can solve both constrained and unconstrained optimization problems. GA can be used to solve variety of optimization problems that are not suited with standard optimization algorithms such as discontinuous, non differentiable, etc. GA generally used to minimize a function f(x), so if we want to maximize a function, this can be done by minimizing -f(x).
The algorithm begin by creating a random initial population. At each step GA select some random individual from the current population and fix it as parent. This parent individual used to produce the children for next generation. Over successive generation, the population evolves towards an optimal solution. GA uses three main types of Rules to produce children for next generation which are,
- Selection Rule: Select parent that contribute to population at next generation
- Cross over rule: Combine two parents and create children for next generation
- Mutation Rule: Apply random change to parent to create children
GA uses random number generators, so that the function return slightly different result each time we run it but it will be close to optimal solution. But if we have and idea about optimized result, it is possible to give same result for GA using some constrains.
So GA producing generations continuously, but this is to be stopped once we get an optimized result. For this, there are some stopping criteria. So algorithm stops when one of the stopping criteria met. Following are those Stopping criteria,
- Generations: The algorithm stops when the number of generations reaches the input value of Generations.
- Time limit: The algorithm stops after running for an amount of time in seconds equal to Time limit.
- Fitness limit: The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to Fitness limit.
- Stall time limit: The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to Stall time limit.
- Stall generations: The algorithm stops when the weighted average change in the fitness function value over Stall generations is less than Function tolerance.
- Function Tolerance: The algorithm runs until the weighted average change in the fitness function value over Stall generations is less than Function tolerance
- Nonlinear constraint tolerance: The Nonlinear constraint tolerance is not used as stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints.
The basic syntax of GA is as follows,
[x fval]=ga(@fitnessfunction,nvars),
where, 'x' is point at which minimum value obtained and 'Fval' is minimum of function.
This is actually used to solve non constrained optimization problems. However we can use constraints to get same optimized result for GA. That is,
Minimum of f(x), such that, `C_i(x)le0, i=1....m`, `C_i(x)=0, i=m+1....mt`, `Axleb`, `A_(eq)x=b_(eq)`, and LB≤x≤UB. For this type of problems
[x fval]=ga(@fitnessfunction,nvars,A,b,Aeq,beq,LB,UB,nonlcon,Intcon,options),
where Intcon represent integer constraint and nonlcon represent Non linear constraint function which are `C_i(x)le0, i=1....m` and `C_i(x)=0, i=m+1....mt`. Also we can setup lot of options for GA. Setting Population size, Generations, Time limit, Fitness limit are some of those which are commonly used. There is a default value for Population size which is 20, so by setting a specific value we can adjust that. Similarly Generation is fixed as 100 by default, this can also be changed. So by making all these type of options we can have an optimized result within the constraints. To use an option following syntax is to be used,
options=optimoptions('ga');
options=optimoptions(options,'OptionNAme',argument);
However, in earlier versions of MATLAB, this is used in following manner,
options=gaoptimset('OptionName',argument);
this still works, but not recommended by MATLAB now.
Based on above studies, the program is wriiten as follows. In program 3 studies are performed with different constraints. So in final study, we get optimsed result on every trial of program. So inorder to confirm that same result is giving by genetic algorith on each execution of program, the program is iterated multiple times.
The Actual stalagmite function is defined as follows,
function f=stalagmite(input_vec)
%Inputting a 1x2 matix to the function
x=input_vec(1);
y=input_vec(2);
f1x=(sin((5.1*pi*x)+0.5))^6;
f1y=(sin((5.1*pi*y)+0.5))^6;
f2x=exp(-(4/0.64)*log(2)*((x-0.0667)^2));
f2y=exp(-(4/0.64)*log(2)*((y-0.0667)^2));
f=f1x*f1y*f2x*f2y;
endIn order to get maximum, negetive values of the function is taken. That function is defined as follows,
function f=stalagmite_max(input_vec)
%Inputting a 1x2 matrix to function
x=input_vec(1);
y=input_vec(2);
f1x=(sin((5.1*pi*x)+0.5))^6;
f1y=(sin((5.1*pi*y)+0.5))^6;
f2x=exp(-(4/0.64)*log(2)*((x-0.0667)^2));
f2y=exp(-(4/0.64)*log(2)*((y-0.0667)^2));
%Taking negetive of the function inorder to get maximum
f=-1*f1x*f1y*f2x*f2y;
endWith above two functions, the main program is written as follows,
clear all
close all
clc
%Defining A search space for x and y
x=linspace(0,0.6,100);
y=linspace(0,0.6,100);
%Creating a 2D mesh array
[xx,yy]=meshgrid(x,y);
%Evaluatiing Stalagmite function
for i=1:length(xx)
for j=1:length(yy)
input_vec(1)=xx(i,j);
input_vec(2)=yy(i,j);
f(i,j)=stalagmite(input_vec);
end
end
%Study 1 With unbounded inputs
numcase=50;
%Starting time counter
tic
for k=1:numcase
%Calculating Optimal results with GA
[opt_input,fval(k)]=ga(@stalagmite_max,2);
%Assigning OPtimal values of x and y into a matrix
x_opt(k)=opt_input(1);
y_opt(k)=opt_input(2);
end
%Stopping time counter
study_time1=toc
%Plotting the obtained result
figure(1)
%Breaking the figure Window by 2X1 matrix
%First subplot
subplot(2,1,1)
hold on
%Plotting Calculataed stalagmite function
surfc(x,y,f);
xlabel('X Values');
ylabel('Y Values');
zlabel('F Value');
title('Unbounded Inputs')
%To make plot more smooth
shading interp
%To plot obtained maximum and corresponding x and y values in 3D space
%Since negetive values of function is minimized, Negetive of function
%minimum will be maximum value of actual function
plot3(x_opt,y_opt,-fval,'marker','o','markerfacecolor','r')
%second Sub plot
subplot(2,1,2)
plot(-fval)
xlabel('Iteration');
ylabel('Fmaximum');
%Study 2 With Lower and Upeer bounds
numcase=50;
%Starting time counter
tic
for k=1:numcase
%Calculating Optimal results with GA
[opt_input,fval(k)]=ga(@stalagmite_max,2,[],[],[],[],[0;0],[0.6;0.6]);
%Assigning OPtimal values of x and y into a matrix
x_opt(k)=opt_input(1);
y_opt(k)=opt_input(2);
end
%Stopping time counter
study_time2=toc
%Plotting the obtained result
figure(1)
%Breaking the figure Window by 2X1 matrix
%First subplot
subplot(2,1,1)
hold on
%Plotting Calculataed stalagmite function
surfc(x,y,f);
xlabel('X Values');
ylabel('Y Values');
zlabel('F Value');
title('Bounded Inputs')
%To make plot more smooth
shading interp
%To plot obtained maximum and corresponding x and y values in 3D space
%Since negetive values of function is minimized, Negetive of function
%minimum will be maximum value of actual function
plot3(x_opt,y_opt,-fval,'marker','o','markerfacecolor','r')
%second Sub plot
subplot(2,1,2)
plot(-fval)
xlabel('Iteration');
ylabel('Fmaximum');
%Study 3 Increased Population size
numcase=50;
%Setting Populations size as 300 for genetic algorithm
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',300);
%Starting time counter
tic
for k=1:numcase
%Calculating Optimal results with GA
[opt_input,fval(k)]=ga(@stalagmite_max,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
%Assigning OPtimal values of x and y into a matrix
x_opt(k)=opt_input(1);
y_opt(k)=opt_input(2);
end
%Stopping time counter
study_time3=toc
%Plotting the obtained result
figure(1)
%Breaking the figure Window by 2X1 matrix
%First subplot
subplot(2,1,1)
hold on
%Plotting Calculataed stalagmite function
surfc(x,y,f);
xlabel('X Values');
ylabel('Y Values');
zlabel('F Value');
title('Bounded Inputs with Modified Populatiuon size')
%To make plot more smooth
shading interp
%To plot obtained maximum and corresponding x and y values in 3D space
%Since negetive values of function is minimized, Negetive of function
%minimum will be maximum value of actual function
plot3(x_opt,y_opt,-fval,'marker','o','markerfacecolor','r')
%second Sub plot
subplot(2,1,2)
plot(-fval)
xlabel('Iteration');
ylabel('Fmaximum');
ylim([0 1.5]);RESULT :
The maximum value of Stalagmite function is obtained, which is 1. This is actually predictable. Because, stalagmite function is a product of 4 terms. So in order to get maximum, these 4 terms should attain their maximum. f1x and f1y are functions of sine, so these two will have a maximum value of 1. And f2x and f2y are reciprocals of function of e. So maximum happens as denominator reduces. So that also have maxima of 1. Thus product will have a maximum of 1.
Coming to programming part, we are performing 3 studies. In first study no restrictions are given. So that, every time GA gave different values. But all are close to the maximum. This is plotted using MATLAB. Those red dots are the maximum values obtained from GA on each execution. Also maximum of function given by GA is plotted gainst number of iteration. So that it can give better idea of diversity of result than first complicated plot.
In the second study, a lower and upper bounds are fixed for x and y values, which are 0 and 0.6 respectively. Then the same method is used to plot the result. But this time, the results obtained have comparatively less diversity. Most of them where very close to function maximum.
In third study, in addition to upper and lower bounds, a change is made on population size. By default population size is 20, so population size is increased to 300. So when result plotted, GA gave same value on each iteration. Thus GA is constrained to give same result for the optimization of Stalagmite function. The second plot is a straight line, which means everytime GA could give same result for the maximum of Stalagmite function
Even though third study could give optimized result. It took lot more time to complete the execution of program. The time taken by each study is given as follows,
So comparing other two studies, third study took lot more time, but it could give better result. The performance rating of computer may also affect study time. However, third study needs to manage a larger population than other two. So definitely it will affect speed of execution.
CONCLUSION :
Genetic algorithm is a powerful tool to optimize most of the optimization problems which can’t be optimized with normal methods. Also there are lots of options are available for GA to get best result. In this study, Population size is used as the option. But there are other options such as Generations, Time, etc. in order to constrain the GA to get best result. But these options may slow down the algorithm. So selection of proper options should consider time of execution also along with the result.
REFERENCES :