Resampling methods-ER Equal resampling(ER) B f(=2x)6() x1 b=1 f(x2) X1 x3 x4 x2 o Resample fitness 4>e e Average fitness 10 Particle
Resampling Methods-ER ◼ Equal resampling (ER) 𝑓ሚ 𝑥 = 1 𝐵 × 𝑏=1 𝐵 𝑓 መ 𝑏(𝑥) 0 𝒙𝟏 𝒙𝟐 𝑓ሚ 𝑥1 𝑓ሚ 𝑥2 fitness 𝒙𝟑 𝒙 𝑓ሚ 𝑥3 𝒙𝟒 𝑓ሚ 𝑥4 Resample fitness Average fitness 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 1 2 3 4 5 6 7 8 9 10 re -evaluations Particle
Resampling methods-ERN ERN fitmess 1. Evaluate all solutions for b times f(x1) 2. Allocate extra budget to top n f(x2) solutions f(x 765432 o Resample in the first round o Resample in the second round O Average fitness 12 Particle
Resampling Methods-ERN ◼ ERN 1. Evaluate all solutions for 𝐵 times 2. Allocate extra budget to top 𝑁 solutions 0 𝒙𝟏 𝒙𝟐 𝑓ሚ 𝑥1 𝑓ሚ 𝑥2 fitness 𝒙𝟑 𝒙 𝑓ሚ 𝑥3 𝒙𝟒 𝑓ሚ 𝑥4 Resample in the second round Average fitness Resample in the first round re -evaluations Particle
Resampling Methods-OCBA [1-2]: Idea Optimal Computing- Budget Allocation Maximize the probability of identifying the true optimal design Maximize the simulation accuracy with a given simulation budget Minimize the total number of simulation runs in order to achieve a desired simulation accuracy U H.C. Chen, C.-H. Chen, and E. Yucesan, " Computing efforts allocation for ordinal optimization and discrete event simulation EEE Trans. on Autom. Cont. vol. 45 no.5,pp.960-964,2000 2 C.H. Chen, J. Lin, E. Yucesan, and S. E Chick, "Sim- ulation budget allocation for further enhancing the effi- ciency of ordinal optimization Discrete Event dynamic Systems: Theory and Applications, vol. 10, pp. 251-270 2000
Resampling Methods-OCBA [1-2]: Idea ◼ Optimal Computing-Budget Allocation ◼ Maximize the probability of identifying the true optimal design ◼ Maximize the simulation accuracy with a given simulation budget ◼ Minimize the total number of simulation runs in order to achieve a desired simulation accuracy [1] [2]
Ordinal Optimization (by ho et al/ [1-2 Idea "Order"is much more robust and easier against noise than " value" 80/20 rule: easier to identify the tallest guy then their heights in a classroom Don' t insist on getting the best but be willing to settle for the good enough U Y.C. Ho, R.S. Sreenivas and P. Vakili. "Ordinal optimization of DEDS, Discrete event dynamic systems, 2(1): 61-88, 1992 2 Y. C. Ho. "An ordinal optimization approach to optimal control problems. " Automatica, 35(2): 331-338, 1999 Recent pioneering algorithm Optimal Computing-Budget Allocation(OCBA, by Chen et al. in 2000)
Ordinal Optimization (by Ho et al. [1-2]) ◼ Idea ◼ “Order” is much more robust and easier against noise than “Value” ◼ 80/20 rule: easier to identify the tallest guy then their heights in a classroom ◼ Goal softening ◼ Don’t insist on getting the “Best” but be willing to settle for the “Good Enough” ◼ Recent pioneering algorithm ◼ Optimal Computing-Budget Allocation (OCBA, by Chen et al. in 2000) [1] [2]
OCBA: Solution max PICS S.M1+N2+…+Nk=T Approach: Chen et al.(2000) N∈N,i=1,,,k Common approximation to P Correct Selection denoted as( css) Derive the allocation ratio based on Karush-Kuhn-Tucker(KKt)conditions P=rn(-o02-2-p1-=4 i=li≠b 1-∑>= APCS XI X2X3 X4 Xs Asymptotically Optimal Solution N(1)_(0(1)(0m N(t)-(a()/(6n(t) 1=1,≠m
OCBA: Solution ◼ Approach: Chen et al. (2000) ◼ Common approximation to P{Correct Selection} denoted as (P{CS}) ◼ Derive the allocation ratio based on Karush–Kuhn–Tucker (KKT) conditions ◼ Asymptotically Optimal Solution