To optimize Stalagmite function & finding the global maxima with Genetic Algorithm
Aim – To optimize Stalagmite function & to find the global maxima using MATLAB.
Objective –
1. To study briefly about Genetic Algorithm.
2. To write a code for the optimization of stalagmite function.
3.To find the global maxima of stalagmite function using Genetic Algorithm.
4. To plot the graph for global maxima of stalagmite function.
Theory –
Genetic Algorithm (GA) - A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems. The in-built ‘ga’ function in MATLAB returns a point close to the local minimum.
The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.
This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.
Five phases are considered in a genetic algorithm.
- Initial population - The process begins with a set of individuals which is called a Population. An individual is characterized by a set of variables known as Genes.
- Fitness function - The fitness function determines how fit an individual is to compete with other individuals. It gives a fitness score to each individual.
- Selection - The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.
- Crossover - For each pair of parents to be mated, a crossover point is chosen at random from within the genes.
- Mutation - In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability.
Stopping Criteria - This generational process is repeated until a termination condition has been reached. The genetic algorithm uses the following conditions to determine when to stop:
- Generations — The algorithm stops when the number of generations reaches the 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 generations — The algorithm stops when the average relative change in the fitness function value over Stall generations is less than Function tolerance.
- 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 test — The stall condition is either average change or geometric weighted. For geometric weighted, the weighting function is 1/2n, where n is the number of generations prior to the current. Both stall conditions apply to the relative change in the fitness function over Stall generations.
- Function tolerance — The algorithm runs until the average relative change in the fitness function value over Stall generations is less than Function tolerance.
Syntax for GA –
• 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. 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.
• 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.
• 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, where problem is a structure.
• [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.
Significance of running multiple iterations and cases – Iteration refers to a process wherein a computer program is instructed to perform a process over and over again repeatedly for a specific number of times or until a specific condition has been met. It is important in optimization process to run multiple iterations as in each step we get closer to the desired point but it may or may not be the exact solution. But if we repeat the whole process for a definite no. of times, eventually we will find the solution.
Stalagmite Function – Stalagmite function is a 3-D mathematical model which helps us generate local maxima and minima.
CODE –
Stalagmite function –
% Stalagmite function
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;
f2_x = exp(-4*log(2).*((x-0.0667).^2/0.64));
f2_y = exp(-4*log(2).*((y-0.0667).^2/0.64));
f = -[f1_x.*f1_y.*f2_x.*f2_y];
end
Optimization Code –
clear all
close all
clc
% Case Study 1
% Defining our search area
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50
% Creating a 2D mesh
[xx yy] = meshgrid(x,y);
% Evaluating the stalagmite function
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
[inputs, fval] = ga(@stalagmite,2)
tic
% Study 1 - Statistical behaviour
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
stude1_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
colorbar
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Inputs')
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations')
ylabel('Function Values')
% Case Study 2
tic
% Study 2 - Statistical behaviour with upper and lower bounds
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
colorbar
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations')
ylabel('Function Maxima')
% Case Study 3
options = optimoptions('ga')
options = optimoptions(options,'PopulationSize',200);
tic
% Study 3 - Increasing GA iteration
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
colorbar
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
title('Final Iteration')
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations')
ylabel('Function Maxima')
Explanation –
- First of all, we have to write a program for the Stalagmite function. As the genetic algorithm function, which is in-built in MATLAB, gives us a minimum value of the function. So to find the maximum value of the function, we need to change the sign of function, so that it will give value for the reverse case of minima, i.e. maxima.
- Then we define the search space which the value of ‘x’ and ‘y’ using the ‘linspace’ command and no of iterations are set using ‘num_cases’ command.
- 'meshgrid' command is used to create a 2-D mesh. Then we use 'for' loop to define our output function ‘f’ and then use the genetic algorithm function to derive the value of ‘f’.
- After that, we optimize the solution in three cases. In first case, maximum value of the function is found out with no restrictions, no bounds, and no limits. Genetic algorithm is free to choose the population then reproduce and mutate.
- As the program is in three parts, so we have to run the program of all sections one by one at a time.
- In second case, to get the more precise value for optimization, we need to restrict the program within specific bounds namely upper bound and lower bound in ‘ga’ function.
- Then in third case, we increase the no. of GA iterations. We can raise it to any value, we have chosen it as 200. In this case, syntax for GA is different than the previous case. GA has to give this population size via an option.
- Results for this case will be just one value of function which does not deviate with no of iterations.
Result –
- Workspace Output –
- First case – Study time = 4.2353s
- Second case – Study time = 7.1772s
- Third case – Study time = 20.0901s
- Final value and iteration points –
x = 0.06443;
y = 0.06846;
optimized value (f) = 0.9935
Errors - No plot was shown during the first iteration set.
Forgot to use the negative sign in stalagmite function.
Used the negative sign in stalagmite function and then saved the function. After that, we got our desired plot.
Conclusion – The optimization of stalagmite function is performed and global maxima is obtained using genetic algorithm. This kind of optimization can be performed on many various processes. Ex. drag force on a turbine blade.
Reference – 1. https://en.wikipedia.org/wiki/Genetic_algorithm