Transcript Derivative Free Optimization

Derivative Free Optimization
G.Anuradha
Contents
•
•
•
•
Genetic Algorithm
Simulated Annealing
Random search method
Downhill simplex method
Characteristics of Derivative free
optimization techniques
•
Derivative freeness
– Does not require derivatives
– Rely on repeated evaluations of objective function
•
Intuitive guidelines
– Guidelines based on simple intuition
– Some concepts are based on nature’s wisdom and
thermodynamics
•
Slowness
– Comparatively slower to derivative based
optimization techniques.
Characteristics of Derivative free
optimization techniques Contd…
• Flexibility:– Works well with a complex objective function also.
• Randomness
– Derivative free methods are stochastic in nature
– They are global optimizers given enough
computational time
• Analytic Opacity
– Difficult to do analytic studies of these methods
– Most of the knowledge about these methods are
empirical in nature.
Characteristics of Derivative free
optimization techniques Contd…
• Iterative Nature:– Unlike LSE these methods are iterative in nature
and requires certain stopping criteria to determine
when to terminate the optimization process
– For eg. The stopping criteria for a maximization
problem includes
•
•
•
•
Computational time
Optimization goal
Minimal improvement
Minimal relative improvement
Genetic Algorithm
• Genetic Algorithms are search and
optimization techniques based on Darwin’s
Principle of Natural Selection.
• Proposed by John Holland at University of
Michigan in 1975
Darwin’s Principle Of Natural Selection
IF there are organisms that reproduce,
and
IF offsprings inherit traits from their parents,
and
IF there is variability of traits,
and
IF the environment cannot support all members of a growing population,
THEN
those members of the population with less-adaptive traits (determined
by the environment) will die out, and
THEN
those members with more-adaptive traits (determined by the environment) will thrive
The result is the evolution of species.
7
Basic Idea Of Principle Of Natural
Selection
“Select The Best, Discard The Rest”
8
Principles behind GA
• Encodes each point in solution space into binary bit
string called a chromosome
• Each point is associated with a fitness value
• GA keeps a set of points called population or gene
pool.
• In each generation GA constructs a new population
using crossover and mutation
• Members of higher fitness values are most likely to
survive and to participate in mating or crossover
operations.
• This is analogous to the Darwin’s model of evolution
How is it different from other optimization
and search procedures?
1. Works with a coding of the parameter set, not the
parameters themselves
2. Search for a population of point and not a single
point
3. Use objective function information and not
derivatives or other auxiliary knowledge
4. Uses probabilistic transition rules and not
deterministic rules
Characteristics of GA
Major components of GA
•
•
•
•
•
Encoding schemes
Fitness evaluation
Parent selection
Crossover operators
Mutation operators
Crossover operators
Elitism
A policy of always keeping a certain number of
best members when each new population is
generated is called ELITISM