Genetic algorithm for Stalagmite function optimization using MATLAB
AIM: To optimize the stalagmite function and find its global maxima using MATLAB.
EQUATION: The given function is as follows:
`f(x,y) = f_(1,x) . f_(2,x) . f_(1,y) . f_(2,y)`
`f_(1,x) = [sin(5.1pix + 0.5)]^0.6`
`f_(1,y) = [sin(5.1piy + 0.5)]^0.6`
`f_(1,x) = exp[-4ln(2) . frac((x-0.0667)^2)(0.64)]`
`f_(1,y) = exp[-4ln(2) . frac((y-0.0667)^2)(0.64)]`
|
OBJECTIVE: 1. To optimize and find the global maxima of the stalagmite function. 2. To study the results (Function Maximum vs Iterations) for the following conditions: - Unbounded Inputs - Bounded Inputs - Bounded Inputs with a defined Population Size |
THEORY:
Optimization: Mathematical optimization is the selection of the best element (with regard to some criterion) from some set of available alternatives. In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains.
Genetic Algorithm: Genetic Algorithms (GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms proposed by Charles Darwin. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems.
1. Selection: Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding (using the crossover operator).
2. Crossover: Crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring.
3. Mutation: Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. It is analogous to biological mutation. Mutation alters one or more gene values in a chromosome from its initial state. In mutation, the solution may change entirely from the previous solution.
Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to the next generation. In simple words, they simulate “survival of the fittest” among individuals of consecutive generations for solving a problem. Each generation consist of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.
Foundation of Genetic Algorithms
Genetic algorithms are based on an analogy with genetic structure and behavior of chromosome of the population. Following is the foundation of GAs based on this analogy:
- Individual in population compete for resources and mate
- Those individuals who are successful (fittest) then mate to create more offspring than others
- Genes from “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent
- Thus each successive generation is more suited for their environment.
SOLUTION:
Programming Language: MATLAB
Procedure/Steps:
1. Define the search space using linspace command and assign suitable variables to store the given input values.
2. meshgrid returns 2-D grid coordinates based on the coordinates contained in vectors x and y. xx is a matrix where each row is a copy of x, and yy is a matrix where each column is a copy of y. The grid represented by the coordinates xx and yy has length(y) rows and length(x) columns.
3. Create for loops i and j for data generation of the inputs.
4. vector is a row vector and is an array which takes xx and yy values and generates the data.
5. stalagmite takes the vector and is used to create the function f.
6. In this way, the data is generated for the plots by using the for loops.
7. tic and toc calculates the total time to perform the operation.
8. A for loop for total 50 iterations (num_cases) is initialized.
9. [inputs,f_opt(i)] = ga(@stalagmite,2)
where;
inputs mean the values of x and y for which f_opt would be a minimum value
stalagmite is the fitness function which is to be optimized
2 is the number of design variables that need to be plotted
10. ga by default calculates the minima. To calculate maxima, either we need to use the Global Optimization Toolbox or reverse the function f by inserting a negative sign.
11. subplot(m,n,p) divides the current figure into an mxn grid and creates axes in the position specified by p.
12. surfc(X,Y,Z) creates a three-dimensional surface plot with a contour plot underneath. A surface plot is a three-dimensional surface that has solid edge colors and solid face colors. The function plots the values in matrix Z as heights above a grid in the x-y plane defined by X and Y. The color of the surface varies according to the heights specified by Z.
13. shading interp is used to smoothen and remove the grid pattern on the plot.
14. plot3 is used to plot coordinates in 3-D space.
Function: The MATLAB program to compute the given function is shown below.
function [f] = stalagmite(vector)
% Inputs:
x = vector(1);
y = vector(2);
% Solution:
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);
endPart #1: Unbounded Inputs
Code #1: The MATLAB program to optimize the function with unbounded inputs is shown below.
The syntax used here is:
x = ga(fun,nvars)
where;
fun = Objective Function (function handle)
nvars = Number of Variables (positive integer)
% Program to optimize the stalagmite function using genetic algorithm.
% Study 1 : Unbounded Inputs
% Inputs:
% Search Space:
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
% 2_D Mesh Generation:
[xx, yy] = meshgrid(x,y);
% Solution:
for i = 1:length(xx)
for j = 1:length(yy)
vector(1) = xx(i,j);
vector(2) = yy(i,j);
f(i,j) = stalagmite(vector);
end
end
tic
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
end
time1 = toc
% Plot:
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('X-axis')
ylabel('Y-axis')
zlabel('Function Maximum')
title('Unbounded Inputs')
grid on
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations')
ylabel('Function Maximum')
grid onOutput #1: Total Time taken for performing the optimization is 2.7424 secs. The default population size used by ga is 50.
Plot #1: The maxima is created in an unconfined space as the search space region is unbounded and the values are dispersed.
Part #2: Bounded Inputs
Code #2: The MATLAB program to optimize the function with bounded inputs is shown below.
The syntax used here is:
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
where;
A = Linear Inequality constraints (real matrix), [] for null
b = Linear Inequality constraints (real vector), [] for null
Aeq = Linear Equality constraints (real matrix), [] for null
beq = Linear Equality constraints (real vector), [] for null
lb = Lower Bounds (real vector or array)
ub = Upper Bounds (real vector or array)
% Program to optimize the stalagmite function using genetic algorithm.
% Study 2 : Bounded Inputs
% Inputs:
% Search Space:
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
% 2_D Mesh Generation:
[xx, yy] = meshgrid(x,y);
% Solution:
for i = 1:length(xx)
for j = 1:length(yy)
vector(1) = xx(i,j);
vector(2) = yy(i,j);
f(i,j) = stalagmite(vector);
end
end
tic
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
time2 = toc
% Plot:
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('X-axis')
ylabel('Y-axis')
zlabel('Function Maximum')
title('Bounded Inputs')
grid on
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations')
ylabel('Function Maximum')
grid onOutput #2: Total Time taken for performing the optimization is 3.5778 secs. The default population size used by ga is 50.
Plot #2: Global Maxima is generated in a bounded region unlike in Study 1.
Part #3: Bounded Inputs with a defined Population Size
Code #3: The MATLAB program to optimize the function with bounded inputs and increased population size is shown below.
The syntax used here is:
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)
where;
nonlcon = Nonlinear Constraints (positive integer), [] for null
IntCon = Integer Variables (vector of positive integers), [] for null
options = Options object
[options = optimoptions(SolverName) ; options = optimoptions(SolverName,Name,Value)]
% Program to optimize the stalagmite function using genetic algorithm.
% Study 3 : Bounded Inputs with defined Population Size
% Inputs:
% Search Space:
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
% 2_D Mesh Generation:
[xx, yy] = meshgrid(x,y);
% Solution:
for i = 1:length(xx)
for j = 1:length(yy)
vector(1) = xx(i,j);
vector(2) = yy(i,j);
f(i,j) = stalagmite(vector);
end
end
% Altering the Population Size:
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',200);
tic
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
time3 = toc
% Plot:
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(x_opt,y_opt,-f_opt,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('X-axis')
ylabel('Y-axis')
zlabel('Function Maximum')
title('Bounded Inputs with defined Population Size')
grid on
subplot(2,1,2)
plot(-f_opt)
xlabel('Iterations')
ylabel('Function Maximum')
grid onOutput #3: Total Time taken for performing the optimization is 17.765 secs. This is more than the earlier study due to the increased population size of 200.
Plot #3: Global Maxima converges at a single point and most of the iterations fall around the value of 0.9999997 to 0.99999985 with a high level of precision.
⁸
CONCLUSION: From the above results, we can infer that:
- Improvement in the output can be achieved by increasing the population size of the study.
- More simulation time is encountered for the function to get considerably optimized.
REFERENCES:
2. ga Syntax