Transcript Slide 1
ZEIT4700 – S1, 2015
Mathematical Modeling and Optimization
School of Engineering and Information Technology
Optimization - basics
Maximization or minimization of given objective function(s), possibly
subject to constraints, in a given search space
Minimize f1(x), . . . , fk(x)
Subject to
gj(x) < 0, i = 1, . . . ,m
hj(x) = 0, j = 1, . . . , p
Xmin1 ≤ x1 ≤ Xmax1
Xmin2 ≤ x2 ≤ Xmax2
.
.
(objectives)
(inequality constraints)
(equality constraints)
(variable / search space)
Classical optimization techniques
Bracketing (Exhaustive search) / Region elimination methods
Simplex based search
Gradient based search
Interval halving method
Nelder Mead simplex method
(Image source : K.Deb, Optimization for engineering design)
(Image source : http://upload.wikimedia.org/wikipedia/commons/9/96/Nelder_Mead2.gif)
Classical optimization techniques (cntd.)
Gradient based (Cauchy’s steepest descent method)
Image source : K. Deb, Multi-objective optimization using Evolutionary Algorithms, John Wiley and Sons, 2002.
Drawbacks of classical optimization methods
•
Gradient based methods : Assumptions on continuity / derivability
•
Region elimination methods : For single variable problem only
•
Search for local optimum only
•
Constraint handling is not inherently included
•
No provisions for handling multiple objectives
Optimization – Heuristics/meta-heuristics
A heuristic is a technique which seeks good (i.e., near optimal) solutions at a
reasonable computational cost without being able to guarantee either feasibility
or optimality, or even in many cases to state how close to optimality a particular
feasible solution is.
- Reeves, C.R.: Modern Heuristic Techniques for Combinatorial Problems. Orient Longman (1993)
Simple “Hill climb”
Start from random X
(while termination criterion not met)
{
Perturb X to get a new point X’
If F(X’) > F(X), move to X’, else not
}
Maximize f(x)
F(x)
X X’
X X’
•
•
“Greedy”
Local
Simulated Annealing
Start from random X
(while termination criterion not met)
{
Perturb X to get a new point X’
If F(X’) > F(X), move to X’,
else
Calculate P = exp(-(F(X) – F(X’))/T)
move to X’ with probability P
}
Maximize f(x)
F(x)
Attempts to escape local minima
by accepting occasional ‘worse’
moves
X X’
X X’
Genetic / Evolutionary algorithms
From point-to-point methods to population based methods..
•
EAs are nature inspired optimization methods which search for the optimum
solution(s) by evolving a population of solutions.
•
Require no assumptions on differentiability / continuity of functions, hence
can handle much more complex functions as compared to classical
optimization techniques.
•
Can deliver the whole Pareto Optimal Front in a single run as opposed to
conventional methods.
•
Its an Intelligent hit and trial !
Evolutionary Algorithms (EA)
Initialization
(population of
solutions)
Parent selection
Recombination /
Crossover
No
Output best
solution
obtained
Yes
Termination
criterion met ?
Mutation
Evaluate childpop
Reduction
Ranking (parent+child
pop)
“Evolve”
childpop
Evolutionary Algorithms (contd.)
Gen 1
Gen 50
Gen 25
Gen 100
Evolutionary Algorithm (cntd)
Minimize f(x) = (x-6)^2
0 ≤ x ≤ 31
Binary GA
Real Parameter GA
Representation
Binary
Real
Parent selection
Binary tournatment/
Roulett wheel
Binary tournatment/
Roulett wheel
Crossover
One point/multi-point
SBX,PCX …
Mutation
Binary flip
Polynomial
Resources
Course material and suggested reading can be
accessed at
http://seit.unsw.adfa.edu.au/research/sites/mdo/
Hemant/design-2.html