Week 4.1 - Genetic Algorithm
Aim
To code in MATLAB to optimise the stalagmite function and find the global maxima.
Global optimization
Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global
minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem
because the maximization of the real-valued function is obviously equivalent to the minimization of the function.
f(x) == (-1) • g(2).
where f(x) = Global optimization
g(x) = real value function
Brute-Force Method
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general
problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible
candidates for the solution and checking whether each candidate satisfies the problem's statement.
A brute-force algorithm to find the divisors of a natural number n would enumerate all integers from 1 to n, and check
whether each of them satisfies your statement.
Genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of
natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly
used to generate high-quality solutions to optimization and search problems by relying on biologically inspired
operators such as mutation, crossover and selection.
Differentiation Between Brute-Force Method and Genetic algorithm.
Firstly in Brute-Force Method it will start from 1 to n, but in Genetic algorithm it will generate a random value and start
to solve problem.
Secondly Brute-Force Method will check all the value until satisfies your statement. But in GA it will pick random
values until it satisfies your statement.Brute Force Method is also used when the simplicity of implementation is more important than speed.
GA is more effective and Brute force requires checking every possible strategy to find the most optimal,there are cases where brute force approach is impossible where genetic algorithms can be useful.
For OWR problem the best method is to work with GA
Steps In GA
Create a random initial Population
scale the fitness value to convert them into more usable range of value and they are expactation value
Select member called parents based on expectation value
Some individual lower fitness value called Elite. The elite passedto the next population.
Produce children from parents by any one of this methods
(A) Selection
(B)Mutuation
(C)Cross Over
Selection
The selection function chooses parents for the next generation based on their scaled values from the fitness scaling
function.
Mutuation
Mutation functions make small random changes in the individuals in the population, which provide genetic diversity
and enable the genetic algorithm to search a broader space.
Cross Over
Crossover combines two individuals, or parents, to form a new individual, or child, for the next generation
Combining the vector entriesof pair of parents to form Cross Over.
Finally replace the current populationwith the children to form next generation. And it will repeat the next generation
till Stopping criteria.
As the generation increases the individuals in the population get closer together and approach the minimum.
Generation
A complete cycle in a GA is known as generation.
Population
Population size specifies how many individuals there are in each generation.
Stopping Condition-:
Stopping Condition
1. Generation - the algorithm stops when it reaches the value of generation.
2. Time Limits - the algorithm stops when it reaches the time in second.
3. Fitness Limits - the algorithm stops when the fitness function for the best point is less or equal to fitness limits.
4. Stall Generation - the algorithm stops when average relative change in fitness Function over stall generation is less
than Function tolerance.
5. Stall Time Limits - the algorithm stops when no improvement in the objective function during an interval of time to
stall time limits.
6. Stall Test - the algorithm stops when both stall condition apply to relative change in the fitness.
7. Function Tolerance - the algorithm stops when stall generation is less than Function Tolerance.
8. Constraint Tolerance - the algorithm not for stopping condition feasibility with respect to non-linear Constrain.
Here we are using Function Tolerance to stop the the function and default is le^-6. And here also the assigning the value of lower tolerance than default le^-8 so the accuracy need with 8th digit.
Genetic Algorithm in MatLab
Genetic algorithm solver for mixed-integer or continuous-variable optimization, constrained or unconstrained
Genetic algorithm solves smooth or nonsmooth optimization problems with any types of constraints, including
integer constraints. It is a stochastic, population-based algorithm that searches randomly by mutation and
crossover among population members.
Syntax used for solving GA
x = ga (fun,nvars,A,b,Aeq,beq,lb, ub,nonlcon, IntCon,options) where x is the value of optimization,
ga=the syntax for Genetic Algorithm is ga followed by open bracket to give your inputs,
fun= your function value or @function to run function program in side the ga itself,
nvars=number of variable that you have been used
Ab=linear inequalities of value of A and b,
Aeq,beq=linear equalities of A and b,
lb,ub=lower bounce or boundry and upper bounce or boundry,
IntCon=Nonlinear constraints, specified as a function handle or function name. nonlcon is a function that accepts a vector or array x and returns two arrays c(x) and ceq(x).
Options=Optimisation options,specefied as the output of optimisations or a structure.
Stalagmite function:-
A stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from cieling drippings.
In the same way The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation.
Equation of Stalagmite Function-:
Function Program
%Function Program for the stalagmite equation
function[f] = stalagmite_equation(input)
f1x = (sin(5.1*pi*input(1)+0.5))^6;
f1y = (sin(5.1*pi*input(2)+0.5))^6;
f2x = exp(-4*log (2)*((input (1)-0.0667)^2/0.64)) ;
f2y = exp(-4*log (2)*((input (2)-0.0667) ^2/0.64));
f =-(f1x*f2x*f1y*f2y);
endMain Program
% MAin Program
clear all
close all
clc
%defining value
x = linspace(0,0.6,150);
y= linspace(0,0.6,150);
num_case = 50;
%2 dimensional mesh
[xx, yy] = meshgrid(x, y) ;
%evaluating
for i= 1:length(xx)
for j= 1:length(yy)
input(1) = xx(i,i);
input(2) = yy(i,j);
f(i,j) = stalagmite_equation(input);
end
end
tic
%study of satistical behaviour
for i =1:num_case
[input, fopt(i)] = ga(@stalagmite_equation, 2);
xopt(i)=input (1) ;
yopt(i)=input (2) ;
end
study1_time = toc;
%Plotting
figure(1)
subplot (2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',4,'markerfaceColor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iteration')
ylabel('Function Minimum')
tic
%study of bounded inputs
for i =1:num_case
[input,fopt(i)] = ga(@stalagmite_equation,2,[],[],[],[],[0;0],[1;1]);
xopt (i)=input(1) ;
yopt (i)=input (2) ;
end
study2_time = toc;
%Plotting
figure(2)
subplot (2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt, yopt, -fopt, 'marker', 'o', 'markersize' ,4, 'markerfacecolor','r')
title ('bounded inputs')
subplot (2,1,2)
plot (fopt)
xlabel('Iteration')
ylabel('Function Minimum')
tic
%study of increase in Population
options = optimoptions('ga');
options= optimoptions (options, 'PopulationSize', 700, 'FunctionTolerance',1e-8);
for i =1:num_case
[input, fopt(i)] = ga(@stalagmite_equation,2, [],[],[],[],[0;0],[0.1;0.1],[],[],options);
xopt (i) =input (1);
yopt(i)=input(2);
end
study3_time = toc;
%Plotting
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',4,'markerfacecolor','r')
title('Increase in population size')
subplot(2,1,2)
plot(fopt)
xlabel('Iteration')
ylabel('Function Minimum')
Explanation Of the Program
step 1- starting the program with program with defining the value and then giving num_case = 50 i.e ill be going with 50 iterations of GA values with respect to the function function program(to Check the consistency of the values).Then running the meshgrid program to matrix form from my given value of row and column.
Then for loop has been used to find the stalamite function outputs,
Without Boundry Values
First comparison is done with without boundry Values to that check how the result has been
produced my GA. So it has taken random values to generated the output, Here we are not
required of some values which have been generated shown in Figurell
For without boundry condition just we are plotting the value with respect to the iteration, so we
are used for loop to get inputs from Stalagmite function.
Figure 1.1
FIgure 1.1 shows that there are many values along with the global maxima.
With Boundry Values
Then comparsion with boundry values to optimize result that i need the result form the selected reagion only, So it has generated the values which are accurate that without boundry as shown in Figure1.2
For second case we are defining the boundry value in ga syntex itself.Here for loop has been used to get input with respect to boundy conditions. And plotting the values of x,y,f Here we are used upper limits and lower limits as per GA when we reduce in area with boundry condition so that it will produce acceptable values.
Figure 1.2
in figure 1.2 both local and global maxima are present
With Increase in Population
This comparsion shows that the increase in population show that the value will be more accurate that the other two condition shown in Figure 1.3.Here we are increasing the population size and defining the boundaries and i have been used the Function tolerance so that it will have a default values of le1-6 so that i need more accurate than that so i have used le1-8.
Figure 1.3
figure 1.3 shows only global maxia value which comparatively more accurate
In Genetic Algorithm the population size is directly propotional to the tolerance value.
In program i have used
Subplot(2,1,1)
where this denotes that 2 is the no of rows,1 is column, creating axes position.
Shading interp-This commant will remove the grid from the graph.
tic-This command is used for calculating the time tic will implement the start time.
toc-This command is used for calculating time toc will implement the stop time.
Conclusion
Coding has been done using MATLAB to optimise the stalagmite function and find the global
maxima with three condition.
Here i got Global maxima value of -0.99999986 to -0.9999998. changes is lies in power of 7 so
it will not be considered.
From here i have learned that Genetic Algorithm's population size is directly propotional to
Reference:-
https://in.mathworks.com/help/gads/ga.html?s_tid=srchtitle
https://in.mathworks.com/help/gads/options-in-genetic-algorithm.html
https://www.youtube.com/watch?v=Z_8MpZeMdD4
https://in.mathworks.com/help/gads/genetic-algorithm.html
https://in.mathworks.com/help/gads/examples.html?s_cid=doc_ftr