Week 4.1 - Genetic Algorithm
AIM :- TO WRITE A PROGRAM IN MATLAB TO OPTIMISE THE STALAGMITE FUNCTION & FIND THE GLOBAL MAXIMA FOR THE FUNCTION.
DEFINITION OF GENETIC ALGORITHM :-
- A Genetic Algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.
- A Genetic Algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution.
- A Genetic Algorithm (GA) is a search based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near optimal solution difficult problems which otherwise would take a lifetime solve. It is frequently used to solve optimization problems, in research and in machine learning.
DEFINITION OF OPTIMIZATION :-
- An act, process, or methodology of making something (such as a design, system, or decision) as fully perfect, functional, or effective as possible specifically : the mathematical procedures (such as finding the maximum of a function) involved in this.
- The action of making the best or most effective use of a situation or resource.
- Optimization is defined as the mathematical procedures involved in effecting optimality. Mathematical model attempts to optimize (maximize or minimize) an objective function without violating resource constraints.
STALAGMITE & STALACTITE :-
A Stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. Most stalagmites have rounded or flattened tips.
A Stalactite an icicle-shaped formation that hangs from the ceiling of a cave and is produced by precipitation of minerals from water dripping through the cave ceiling.
Genetic Algorithm :-
A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. Genetic Algorithms (GA) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. 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.
Process of Natural Selection :-
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.
Following Five steps are considered in a genetic algorithm
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
(A) Intial Population :-
- The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.
- An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).
- In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.
(B) Fitness Function :-
- Fitness function is used in Genetic Algorithm in each iteration of the algorithm to evaluate the quality of all the proposed solutions to your problem in the current population.
- The fitness function evaluates how good a single solution in a population is, e.g. if you are trying to find for what x-value a function has it's y-minimum with a Genetic algorithm, the fitness function for a unit might simply be the negative y-value (the smaller the value higher the fitness function).
(C) Selection :-
- The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.
- Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.
(D) Crossover :-
- Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.
-
Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.
(E) Mutuation :-
- In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.Mutation occurs to maintain diversity within the population and prevent premature convergence.
-
The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.
-
The population has a fixed size. As new generations are formed, individuals with least fitness die, providing space for new offspring.The sequence of phases is repeated to produce individuals in each new generation which are better than the previous generation.
Advantages of Genetic Algorithm (GA) :-
- Large and wide solution space search ability.
- Parallelism, easily modified and adaptable to different problems.
- Non-knowledge based optimisation process used of a fitness function for evaluation.
- Easily distributed.
- Good choice for large scale/wide variety of optimisation problem.
- Capable of multi-objective optimisation can return suite of potential solutions.
- Easy to discover global optimum and avoid trapping in local optima.
Disadvantages of Genetic Algorithm (GA) :-
- GA requires less information about the problem, but designing an objective function and getting representation and operates right can be difficult.
- GA is computationally expensive i.e. time consuming.
- GA implementation is still an art.
Application of Genetic Algorithm (GA) :-
-
Optimization − Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints. The approach to solve Optimization problems has been highlighted throughout the tutorial.
-
Economics − GAs are also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.
-
Neural Networks − GAs are also used to train neural networks, particularly recurrent neural networks.
-
Parallelization − GAs also have very good parallel capabilities, and prove to be very effective means in solving certain problems, and also provide a good area for research.
-
Image Processing − GAs are used for various digital image processing (DIP) tasks as well like dense pixel matching.
-
Vehicle routing problems − With multiple soft time windows, multiple depots and a heterogeneous fleet.
-
Scheduling applications − GAs are used to solve various scheduling problems as well, particularly the time tabling problem.
-
Machine Learning − as already discussed, genetics based machine learning (GBML) is a niche area in machine learning.
-
Robot Trajectory Generation − GAs have been used to plan the path which a robot arm takes by moving from one point to another.
-
Parametric Design of Aircraft − GAs have been used to design aircrafts by varying the parameters and evolving better solutions.
-
DNA Analysis − GAs have been used to determine the structure of DNA using spectrometric data about the sample.
-
Multimodal Optimization − GAs are obviously very good approaches for multimodal optimization in which we have to find multiple optimum solutions.
-
Traveling salesman problem and its applications − GAs have been used to solve the TSP, which is a well-known combinatorial problem using novel crossover and packing strategies.
SYNTAX :-
DESCRIPTION :-Description
x = ga(fun,nvars)x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
Note
Passing Extra Parameters (OPTIMIZATION TOOLBOX) explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)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,intcon)x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options)intcon take integer values.
Note
When there are integer constraints, ga does not accept nonlinear equality constraints, only nonlinear inequality constraints.
x = ga(problem)problem, a structure described in problem.
Main Program :-
clear all
close all
clc
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 stalamite 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_456(input_vector);
end
end
tic
% study 1 - statistical behaviour
for i = 1:num_cases
[input,fopt(i)] = ga(@Stalagmite_456, 2);
xopt(i) = input(1);
yopt(i) = input(2);
end
study1_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x, y, f)
shading interp
plot3(xopt,yopt,fopt,'o','MarkerSize',8,'MarkerFaceColor','r')
title ('Unbounded Input')
subplot(2,1,2)
plot(fopt)
xlabel ('iterations')
ylabel ('Function minimum')
tic
% Study 2 - Statisstical behaviour - wth upper and lower bounds
for i = 1:num_cases
[input, fopt(i)] = ga(@Stalagmite_456,2,[],[],[],[],[0,0],[1,1]);
xopt(i) = input(1);
yopt(i) = input(2);
end
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x, y, f)
shading interp
plot3(xopt,yopt,fopt,'o','MarkerSize',8,'MarkerFaceColor','r')
title ('Bounded Input')
subplot(2,1,2)
plot(fopt)
xlabel ('iterations')
ylabel ('Function minimum')
% Study 3 = increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',300);
tic
for i = 1:num_cases
[input, fopt(i)] = ga(@Stalagmite_456,2,[],[],[],[],[0,0],[1,1],[],[],options);
xopt(i) = input(1);
yopt(i) = input(2);
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(x, y, f)
shading interp
plot3(xopt,yopt,fopt,'o','MarkerSize',8,'MarkerFaceColor','r')
title ('Bounded Input')
subplot(2,1,2)
plot(fopt)
xlabel ('iterations')
ylabel ('Function minimum')
Function Program :-
function [f] = Stalagmite_456(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x+0.5))^6;
f2 = (sin(5.1*pi*y+0.5))^6;
f3 = exp(-4*log(2)*((x-0.0667)^2)/(0.64));
f4 = exp(-4*log(2)*((y-0.0667)^2)/(0.64));
f = -1*f1*f2*f3*f4;
end
PROCEDURE :-
- The stagalmite function is defined separately. This function is later called into the main GA program.
- Now we define the x & y inputs using linspace command.
- Then the input vectors are transformed into array [xx,yy]. So, tha it can be used to evaluate function of two variables and three dimensional mesh/surface plots.
- Now the values in the different matrixs ceated can be put as an input into the function that we have created, by calling it.
- By this we can get the value of the stalagmite function at various values of x & y.
- Since we have got the value of the function at various values, we now need to calculate the maxima value, which can be calculated using the GA command, which is an in-built function in MATLAB.
- Then, the total number of time the ga needs to run is defined using num_cases and with help of for loop is made to run for each iteration and value is stored in an array.
- GA generally gives the minima value , but we neeed the maxima hence we can just inverse the stagalmite function by introducing a 'Negative sign' (This inversethe stagalmite curve and the fglobal maximas can be found, instead minima).
- The total study time is calculated using the 'tic' & 'toc' command at the start and end of the ga for loop respectively.
- The results plotted using the surfc command and plot command.
- GA is made to run for 3 iterations, with each iteration having bounded inputs, unbounded inputs & increasing population size.
Results & Outputs :-
(1) STUDY 1 - Unbounded
- There is numbers of points coming inside & outside region.
- It takes very less time to compute & plot the graph.
(2) STUDY 2 - Bounded
- Few points coming after the fix region. It showing our optimization function in the right directions.
- study 2 takes slightly more time than study 1, simuntaneously creating accurate plot.
(3) STUDY 3 - Bounded with increased Population Size
- More Accurate and optimise value of global maxima achieved.
- Study 3 consumed more time compared to study 1 and study 2 for accurate results.
References :-
- https://www.nps.gov/ozar/learn/education/speleothems.htm
- https://skill-lync.com/student-projects/week-4-genetic-algorithm-228
- https://en.wikipedia.org/wiki/Stalagmite
- https://www.youtube.com/watch?v=mSqZqvm7YUA
- https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_application_areas.htm
Errors :-
- The graph direction is downward (Statactile) showing instead of stalagmite because of not put - (Negative sign) before function , fot & plot.
Thank You ...