Transcript global optimization algorithms

Global Optimization
• General issues in global optimization
• Classification of algorithms
• The DIRECT algorithm
– Relationship to EGO
– Lipschitzian optimization
– Exploration and Exploitation
– Application to High Speed Civil Transport
Global optimization issues
• Optimization problem is NP-hard
• No-free-lunch theorem (Wolpert and Macready)
– No single algorithm can do well on all problems
– If an algorithm is improved for one problem, it will
suffer for others.
• Great opportunity for engineers to use problem
knowledge to tailor algorithms.
• Big headache for journals because they get many
worthless new algorithms.
Global Optimization
Global
optimization
algorithms by
Thomas Weise
Global trend
• If there is global trend, the only issue is not to
be trapped in a local minimum
• If there are many important basins there is no
choice but to explore thoroughly.
global optimization algorithms
1.1 A Classification of Optimization Algorithms
Deterministic
State Space
Search
Algebraic
Geometry
Branch and
Bound
Probabilistic
Artificial
Intelligence (AI)
Monte Carlo
Algorithms
Soft Computing
Computational
Intelligence (CI)
(Stochastic)
Hill Climbing
Evolutionary
Computation (EC)
Memetic
Algorithms
Random
Optimization
Simulated
Annealing (SA)
Tabu Search
(TS)
Parallel
Tempering
Harmonic
Search (HS)
Evolutionary
Algorithms (EA)
Algorithms
(LCS)
System
Swarm
Intelligence (SI)
Ant Colony
Optimization (ACO)
Particle Swarm
Optimization (PSO)
Stochastic
Tunneling
Programming
Direct Monte
Carlo Sampling
Strategy (ES)
Differential
Evolution (DE)
(GP)
Programming
Standard Genetic
Programming
Linear Genetic
Prograaming
Grammar Guided
Genetic Prog.
Figure 1.1: The taxonomy of global optimization algorithms.
23
EGO and DIRECT
• EGO is an algorithm that relies on a surrogate to
connect all the data in design space.
• DIRECT is an algorithm that does not try to
exploit any correlation between the function
value at one point and its value at nearby points.
• EGO will do well for functions with global trend
and not too many deep local optima.
• DIRECT will do well for cheap functions with
many local optima.
• We combine them by using DIRECT to calculate
new sampling points for EGO.
DIRECT Algorithm
• Jones, D.R., Perttunen, C.D. and Stuckman, B.E. (1993),
Lipschitzan optimization without the Lipschitz constant,
Journal of Optimization Theory and Application 79, 157–181.
S. E. COX, R. T. HAFTKA, C. A. BAKER, B. GROSSMAN, W. H.
MASON and L. T. WATSON A Comparison of Global
Optimization Methods for the Design of a High-speed Civil
Transport, Journal of Global Optimization 21: 415–433, 2001.
Matlab: http://www4.ncsu.edu/~ctk/Finkel_Direct/
Lipschitzian Optimization
• Optimizer divides space
into boxes and samples
the vertices of each
• One box is further
divided based on a
predicted maximum rate
of change of the
function, K
DIRECT
• The function value at the
middle of each box and
it’s largest dimension are
used to determine
potentially optimal boxes
• Each potentially optimal
box is divided
• Lipschitzian optimization
for all possible Lipschitz
constants
DIRECT Box Division
.
Exploration vs. Exploitation
• DIRECT uses convex hull of box sizes to
balance exploitation vs. exploration.
• With enough function evaluations every
region in design space will be explored.
• This is clearly not feasible for high dimensional
spaces.
• Cox’s paper compares DIRECT to repeated
local optimization with random starts.
Optimization of a High Speed Civil
Transport
• 26 design variables defining the shape of the
wing and fuselage and tail and the flight
trajectory
• Long range (NY Tokyo type flight) with 250
passengers for minimum takeoff gross weight
• Constraints on takeoff and landing maneuvers,
engine out conditions.
• CFD analysis plus structural optimization
needed for each design.
Results
Minimum Weight
595000
590000
585000
DOT
LFOPCV3
DIRECT
580000
575000
570000
565000
5 DV
Case
10 DV
Case
26 DV
Case
Results
Function Calls
200000
150000
100000
50000
0
DOT
LFOPCV3
DIRECT
5 DV
Case
10 DV
Case
26 DV
Case
Results
DOT Optimum Values
579000
577000
573000
571000
569000
Optimization #
99
92
85
78
71
64
57
50
43
36
29
22
15
8
567000
1
Weight
575000
Results
DOT
DIRECT
26 DV case