Limitations of the traditional optimization
approaches
Limitations:
Computationally expensive.
For a discontinuous objective function, methods may fail.
Method may not be suitable for parallel computing.
Discrete (integer) variables are difficult to handle.
Methods may not necessarily adaptive.
Evolutionary algorithms have been evolved to address the above
mentioned limitations of solving optimization problems with traditional
approaches.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 2 / 26
Evolutionary Algorithms
The algorithms, which follow some biological and physical behaviors:
Biologic behaviors:
Genetics and Evolution –> Genetic Algorithms (GA)
Behavior of ant colony –> Ant Colony Optimization (ACO)
Human nervous system –> Artificial Neural Network (ANN)
In addition to that there are some algorithms inspired by some physical
behaviors:
Physical behaviors:
Annealing process –> Simulated Annealing (SA)
Swarming of particle –> Particle Swarming Optimization (PSO)
Learning –> Fuzzy Logic (FL)
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 3 / 26
Genetic Algorithm
It is a subset of evolutionary algorithm:
Ant Colony optimization
Swarm Particle Optimization
Models biological processes:
Genetics
Evolution
To optimize highly complex objective functions:
Very difficult to model mathematically
NP-Hard (also called combinatorial optimization) problems (which
are computationally very expensive)
Involves large number of parameters (discrete and/or continuous)
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 4 / 26
Background of Genetic Algorithm
Firs time itriduced by Ptrof. John Holland (of Michigan University, USA,
1965).
But, the first article on GA was published in 1975.
Principles of GA based on two fundamental biological processes:
Genetics: Gregor Johan Mendel (1865)
Evolution: Charles Darwin (1875)
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 5 / 26
A brief account on genetics
The basic building blocks in living bodies are cells. Each cell carries
the basic unit of heredity, called gene
Nucleus
Chromosome
Other cell bodies
For a particular specie, number of chromosomes is fixed.
Examples
Mosquito: 6
Frogs: 26
Human: 46
Goldfish: 94
etc.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 6 / 26
Working of Genetic Algorithm
Definition of GA:
Genetic algorithm is a population-based probabilistic search and
optimization techniques, which works based on the mechanisms of
natural genetics and natural evaluation.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 13 / 26
Framework of GA
Start
Note:
An individual in the
population is
corresponding to a
Initial Population possible solution
No
Converge ? Selection
Yes
Reproduction
Stop
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 14 / 26
Working of Genetic Algorithm
Note:
1 GA is an iterative process.
2 It is a searching technique.
3 Working cycle with / without convergence.
4 Solution is not necessarily guranteed. Usually, terminated with a
local optima.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 15 / 26
Framework of GA: A detail view
Start
Define parameters
Parameter representation
Create population
Initialize population
Apply cost
function to each of
the population
No
Converge ? Evaluate the fitness
Selection
Yes
Select Mate
Stop
Crossover
Reproduction
Mutation
Inversion
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 26.02.2016 16 / 26
