Transcript box - 知的システムデザイン研究室

A Hybrid Optimization Approach
for Global Exploration
2005年度 713番
日和 悟
Satoru HIWA
知的システムデザイン研究室
Intelligent Systems Design Laboratory
Optimization
Mathematical discipline that concerns the finding of
minima or maxima of functions, subject to constraints
 Optimization problem consists of:
- Objective function: we want to minimize or maximize.
- Design variables: affect the objective function value.
- Constraints: allow the design variables to take on certain
values but exclude others.
Real-world applications
 Optimization techniques have been applied to various realworld problems.
e.g.) Structural design
Electric device design
Problem Solving by Optimization
 There are many good optimization algorithms.
 Each method has its own characteristics.
- It is difficult to choose the best method for the optimization
problem.
 It is important to select and apply the appropriate
algorithms according to the complexities of the problems.
 It is hard to solve the problem with only one algorithm
when the problem is complicated.
Hybrid optimization approach, which combines
plural optimization algorithms, should be necessary.
Purpose of the research:
To develop an efficient hybrid optimization algorithm
Hybrid Optimization Approach
Hybrid optimization algorithm
 It provides the high performance which cannot be
accomplished with only one algorithm.
To develop an efficient hybrid optimization algorithm
 We have to determine what kinds of solutions are required.
 Desired solutions may vary depending on the user:
- One may require the better result within a reasonable time.
- The other may want not only the optimum, but also the
information of the landscape.
 Optimization strategy
- First, how the optimization process is performed should be
determined.
Optimization Strategy
To explore the search space uniformly and equally
 By this, we can obtain not only the optimum point, but also
the information of the landscape.
 Many optimization algorithms are designed only to derive
an optimum.
Why is the strategy needed?
Why is the Strategy Needed?
 When we solve real-world optimization problems;
- Usually, the landscape and the optimum are unknown.
- In this case, the obtained results should be reliable.
 Genetic Algorithms (GAs) are powerful techniques to obtain
the global optimum.
- Probabilistic algorithm inspired by evolutionary biology
 Example of optimization by GAs:
Problem
GAs
Why is the Strategy Needed?
 When we solve real-world optimization problems;
- Usually, the landscape and the optimum are unknown.
- In this case, the obtained results should be reliable.
 Genetic Algorithms (GAs) are powerful techniques to obtain
the global optimum.
- Probabilistic algorithm inspired by evolutionary biology
 Example of optimization by GAs:
Problem
GAs
Why is the Strategy Needed?
 When we solve real-world optimization problems;
- Usually, the landscape and the optimum are unknown.
- In this case, the obtained results should be reliable.
 Genetic Algorithms (GAs) are powerful techniques to obtain
the global optimum.
- Probabilistic algorithm inspired by evolutionary biology
 Example of optimization by GAs:
Unexplored area exists.
Is real optimum in the area?
Unknown
The result is not reliable.
Problem
GAs
Why is the Strategy Needed?
 When we solve real-world optimization problems;
- Usually, the landscape and the optimum are unknown.
- In this case, the obtained results should be reliable.
 Genetic Algorithms (GAs) are powerful techniques to obtain
the global optimum.
- Probabilistic algorithm inspired by evolutionary biology
 Example of optimization by GAs:
Unexplored area exists.
Unknown
Is real optimum in the area?
The result is not reliable.
Problem
The
strategy isGAs
not achieved only by GAs.
Why is the Strategy Needed?
 When we solve real-world optimization problems;
- Usually, the landscape and the optimum are unknown.
- In this case, the obtained results should be reliable.
 Genetic Algorithms (GAs) are powerful techniques to obtain
the global optimum.
- Probabilistic algorithm inspired by evolutionary biology
 Example of optimization by GAs:
The strategy is achieved.
The landscape is grasped.
Unknown
Reliability can be evaluated.
Problem
GAs
Optimization Algorithms
 The strategy is not achieved only by GAs.
 Other algorithm, which provides more global search, is
needed.
 However, the globally-intensified search converges slowly
compared to GAs or local search algorithms.
- the much time is consumed in exploring the entire search space.
 There are tradeoff between the search broadness and the
convergence rate.
It is necessary to balance the global and local search.
Both global and local search algorithms are hybridized.
 GAs
 DIRECT: explores search space globally.
 SQP: is high-convergence local search method.
DIRECT
 Deterministic, global optimization algorithm
 Its name comes from ‘DIviding RECTangles’.
- Search space is considered to be a hyper-rectangle (box).
- Each box is trisected in each dimension.
- Center point of each box is sampled as solution.
 Boxes to be divided
- are mathematically guaranteed to be promising.
- are called ‘potentially optimal boxes.’
Characteristics of the DIRECT search
 Potentially optimal boxes potentially contain a better value
than any other box.
 DIRECT divides the potentially optimal boxes at each
iteration.
Characteristics of the DIRECT search
 Example: 2-dimensional Schwefel Function
- Some Local optima exist far from the global optimum.
- DIRECT explores the search space uniformly and equally.
- DIRECT also detects the promising area.
Global Optimum
Local Optima
Characteristics of the DIRECT search
 Example: 2-dimensional Schwefel Function
- Some Local optima exist far from the global optimum.
- DIRECT explores the search space uniformly and equally.
- DIRECT also detects the promising area.
Global Optimum
Local Optima
Characteristics of the DIRECT search
 Example: 2-dimensional Schwefel Function
- Some Local optima exist far from the global optimum.
- DIRECT explores the search space uniformly and equally.
- DIRECT also detects the promising area.
Global Optimum
Local Optima
Genetic Algorithms (GAs)
 Heuristic algorithms inspired by evolutionary biology.
- Solutions are called ‘individuals’, and genetic operators
(Crossover, Selection, Mutation) are applied.
 Real-coded GAs
- Individuals are represented by real number vector.
 Although GAs are global optimization algorithm, the search
broadness is inferior to DIRECT.
 GAs are used as more locally-intensified search than
DIRECT.
Parents
Individuals
Children
Sequential Quadratic Programming
(SQP)
 Gradient-based local search algorithm
- The most efficient method in nonlinear programming
- By using gradient information, SQP rapidly converges to
the optimum.
 Advantage
- High convergence
 Disadvantage
- SQP is often trapped to the local optima, for the problem which
has many local optima.
Hybrid Optimization Algorithm
Idea of the proposed hybrid optimization approach
Global exploration Locally-intensified
by DIRECT
search by GAs
Fine tuning
by SQP
Procedure of the proposed algorithm
1. Perform the DIRECT search.
2. Execute GAs.
3. Improve the best solution obtained in GAs search by SQP.
Hybrid Optimization Algorithm
Idea of the proposed hybrid optimization approach
Optimum
Global exploration Locally-intensified
by DIRECT
search by GAs
Fine tuning
by SQP
Procedure of the proposed algorithm
1. Perform the DIRECT search.
2. Execute GAs.
3. Improve the best solution obtained in GAs search by SQP.
How to Combine DIRECT and GAs
 GAs utilize the center points of the potentially optimal boxes
in DIRECT as their individuals.
DIRECT stopped.
GAs start.
 Number of potentially optimal = number of individuals
- Number of potentially optimal differs at each iteration.
- Number of individuals are determined according to the
complexities of the problems.
(e.g. In N-dim. space, N×10 individuals are recommended.)
How to Combine DIRECT and GAs
 GAs utilize the center points of the potentially optimal boxes
in DIRECT as their individuals.
DIRECT stopped.
GAs start.
 Number of potentially optimal = number of individuals
- Number of potentially optimal differs at each iteration.
- Number of individuals are determined according to the
complexities of the problems.
Number
of potentially
optimal
boxesare
should
be
(e.g.
In N-dim.
Space, N×10
individuals
recommended.)
adjusted according to the number of individuals.
How to Combine DIRECT and GAs
Ni: Number of individuals in GAs
 If the number of potentially optimal is smaller than Ni,
randomly generated individuals are added.
 If the number of potentially optimal is larger than Ni,
a certain number of potentially optimal boxes are selected.
Box selection rules are proposed and applied.
Box Selection Rules for DIRECT
Idea of selecting the boxes to be divided
 DIRECT sometimes performs an local improvement.
 In the hybrid optimization, it is not necessary for DIRECT
to perform locally-intensified search.
 Proposed rules reduce the crowded boxes.
- Distance from the box with best function value is calculated.
- A certain number of boxes far from the best point are selected.
- The rules are applied at each iteration in DIRECT search.
Box Selection Rules for DIRECT
Idea of selecting the boxes to be divided
 DIRECT sometimes performs an local improvement.
 In the hybrid optimization, it is not necessary for DIRECT
to perform locally-intensified search.
 Proposed rules reduce the crowded boxes.
- Distance from the box with best function value is calculated.
- A certain number of boxes far from the best point are selected.
- The rules are applied at each iteration in DIRECT search.
Potentially optimal boxes near the best point are discarded,
and locally-biased search is prevented.
The number of potentially optimal boxes is reduced
without breaking the global search characteristics of DIRECT.
Experiments
Verification of effectiveness of the hybrid approach
 Numerical example is shown
- to verify whether the proposed method achieve the proposed
strategy − to explore the search space uniformly and equally.
 The proposed hybrid optimization algorithm
- is applied to the benchmark problem.
- is compared to the search only by GAs.
Target problem
 10-dimensional Schwefel function
- A lot of local optimum exist.
- The function value of the global optimum is zero.
Results and Discussions
Searching ability
 Average values of function value and the number of function
evaluations are shown.
Average of 30 runs
Function value
Function evaluations
Hybrid
GAs
9.07×10-8
5.58×102
129,373
279,703
 Proposed hybrid algorithm obtains better function value
than that of GAs, with less function evaluations.
Results and Discussions
To see whether the proposed strategy is achieved…
 Search histories of DIRECT and GAs in the hybrid
algorithm are checked.
 History in 10-dimensional space is projected into
2-dimensional plane.
 Although 45 plots exist, 4 typical examples are picked.
(x1, x2, …, x10) → (x1, x2), (x1, x3), …
Search History of DIRECT
(x1, x2)
(x2, x5)
(x3, x6)
(x7, x9)
Search History of DIRECT
Search Histories of DIRECT and GAs
Search Histories of DIRECT and GAs
The proposed strategy is achieved.
Conclusions
Hybrid optimization approach is proposed.
 ‘optimization strategy’ is proposed:
- To explore the search space uniformly and equally
 Optimization algorithms used for the strategy:
- DIRECT, GAs, and SQP
Modification to DIRECT
 Box selection rules are proposed and applied.
Hybrid optimization algorithm
 It achieved the proposed strategy.
 It provided the efficient performance than the search only
by GAs.
Paper List
Proceeding of International Conference
 Mitsunori Miki, Satoru Hiwa, Tomoyuki Hiroyasu
“Simulated Annealing using an Adaptive Search Vector”
Proceedings of IEEE International Conference on Cybernetics and Intelligent Systems 2006
(Bangkok, Thailand)
The Science and Engineering Review of Doshisha University
 三木光範，日和 悟，廣安知之
「LEDを用いた調色用照明システムの基礎的検討」
同志社大学理工学研究報告 Vol.46 No.3 pp 9-18，2005
Oral Presentation (in Japan)
 日和 悟，廣安知之，三木光範
「大域的最適化のための複数最適化手法の動的制御法」
日本機械学会 第7回最適化シンポジウム，2006
 日和 悟，廣安知之，三木光範
「大域的最適化のための複数最適化手法の動的制御法」
日本機械学会 第6回設計工学・システム部門講演会，2006
 三木光範，日和 悟，廣安知之
「適応的探索ベクトルをもつシミュレーテッドアニーリング」
日本機械学会 第8回計算力学講演会，2005
Lipschitzian Optimization
[Shubert 1972]
It requires the user to specify the Lipschitz constant K
 K is used as a prediction of the maximum possible slope of
the objective function over the global domain.
–K
+K
.
Slope = −K
a
Slope = +K
x1
b
a
x1 x2 b
a
x3 x1 x2 b
DIRECT (one-dimensional)
a
Box 1
b
Box 2 Box 1 Box 3
Box 4 Box 5
Box 2 Box 1 Box 3
DIRECT (one-dimensional)
Slope = K
a
Box 1
b
Box 2 Box 1 Box 3
Slope = K1
Slope = K2
Box 2 Box 1 Box 3
Box 4 Box 5
Box 2
Box 1
Box 4
Box 5
DIRECT (one-dimensional)
 If box i is potentially optimal, then f(ci) <= f(cj) for all
boxes that are of the same size as i. Slope = K
 In the largest boxes, the box with the best function
value is potentially optimal.
a
Box 1
b
Box 2 Box 1 Box 3
Slope = K1
Slope = K2
Box 2 Box 1 Box 3
Box 4 Box 5
Box 2
Box 1
Box 4
Box 5
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
 Potentially optimal boxes are defined by:
A hyper box j is potentially optimal if there exists
some
such that
cj: center point of the box j
dj: distance from the center point to vertices
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
Search space
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
cj
dj
Box j
Search space
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
cj
dj
f (cj)
Box j
Center - vertex distance (dj)
Search space
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
cj
dj
f (cj)
Box j
fmin
( 0, fmin -ε| fmin | )
Center - vertex distance (dj)
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
Make the convex hull which contains all points.
cj
dj
f (cj)
Box j
fmin
( 0, fmin -ε| fmin | )
Center - vertex distance (dj)
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
Boxes on the lower part of convex hull
is selected as potentially optimal.
cj
dj
f (cj)
Box j
fmin
: Potentially optimal
( 0, fmin -ε| fmin | )
Center - vertex distance (dj)
DIRECT ー Potentially Optimal Boxes
Identification of potentially optimal boxes
 DIRECT divides all potentially optimal boxes.
Boxes on the lower part of convex hull
is selected as potentially optimal.
cj
dj
f (cj)
Box j
: Potentially optimal
Center - vertex distance (dj)
Search space
Genetic Algorithms (GAs)
 Global search algorithm inspired by evolutionary biology.
- Solutions are called ‘individuals’, and genetic operators
(Crossover, Selection, Mutation) are applied.
 Real-Coded GAs (RCGAs)
- Individuals are represented by real number vector.
- Crossover operator significantly affects the searching ability.
 Simplex Crossover (SPX)
- One of the efficient crossover operator for RCGAs.
- Generates offspring in a simplex, which is formed by n+1
individuals in n-dimensional space
 RCGAs using the SPX operator
- has both global and local search
characteristics.
RCGAs using the SPX operator are used.
GAs and SQP
GAs (Genetic Algorithms)
 Heuristic algorithm inspired by evolutionary biology.
- Solutions are called ‘individuals’, and genetic operators
(Crossover, Selection, Mutation) are applied.
Parents
Individuals
Children
SQP (Sequential Quadratic Programming)
 Gradient-based local search algorithm
- By using gradient information, SQP rapidly converges to the
optimum.
Stopping Criterion
DIRECT
 is terminated when the size of the best potentially optimal
box is less than certain value prescribed.
 A certain depth of search space exploration is
obtained.
GAs
 are terminated when their individuals converged.
 Spread of the individuals in design variable space:
xmax – xmin < threshold
SQP
 continues its search until the improvement of solution
becomes a minute value.
Stopping Criterion (DIRECT)
DIRECT
 is terminated when the longest side length of the best
potentially optimal box is less than 10-3.
 A certain depth of search space exploration is
obtained.
Stopping Criterion (GAs)
GAs
 are terminated when their individuals converged.
 Spread of the individuals in design variable space:
Spreadi = xmax – xmin
xmax : the maximum value of i-th design variables in all individuals.
xmin : the minimum value of i-th design variables in all individuals.
 If Spreadi is smaller than 10-3 × feasible range for all
dimensions, GAs are terminated.
Spread1
Population converged
Spread2
Results (of each algorithm)
Function
value
DIRECT
(po 52)
GAs
(Ind 100)
SQP
Hybrid
GAs only
(Ind 100)
Average
3.52x10-2 1.23x10-4 9.07x10-8 9.07x10-8
5.58x102
St. Dev.
0.00 1.29x10-4 9.16x10-8 9.16x10-8
1.82x102
Num. of
eval.
DIRECT
GAs
SQP
Hybrid
GAs only
Average
13529
115793
50
129373
279703
St. Dev.
0
9300
18
9307
22402
How to Combine DIRECT and GAs
 GAs utilize the center points of the potentially optimal boxes
in DIRECT as their individuals.
DIRECT stopped.
GAs start.
 If Npo > Nind
- Box selection rules are applied.
 If Npo < Nind
- Randomly generated individuals are added to GAs.
Modification to DIRECT
Box selection rules
1. Select two boxes, with the smallest size and with the
largest from the set of potentially optimal boxes.
2. For each boxes, calculate the distance from two box.
3. Sort the boxes by the distance in descending order,
and select N boxes from them.
Potentially optimal boxes near two boxes are discarded,
and locally-biased search is prevented.
The number of potentially optimal boxes is reduced
without breaking the global search characteristics of DIRECT.
Modification to DIRECT
Box selection rules
1. Select two boxes, with the smallest size and with the
largest from the set of potentially optimal boxes.
2. For each boxes, calculate the distance from two box.
3. Sort the boxes by the distance in descending order,
and select N boxes from them.
Potentially optimal boxes near two boxes are discarded,
and locally-biased search is prevented.
The number of potentially optimal boxes is reduced
without breaking the global search characteristics of DIRECT.
Potentially optimal boxes
(when DIRECT was terminated)
(x1, x2)
(x2, x5)
(x3, x6)
(x7, x9)
History of the search only by GAs
(x1, x2)
(x2, x5)
(x3, x6)
(x7, x9)
History of the search only by GAs
(x1, x2)
(x2, x5)
GAs were trapped to the local optima.
(x3, x6)
(x7, x9)