torsj03-18.dvi

Size: px

Start display at page:

Download "torsj03-18.dvi"

こうざぶろうふじた
7 years ago
Views:

1 Transactions of the Operations Research Society of Japan ( ; ) :,,,, 1. 1 Tantawi and Towsley[19] Kameda et al.[9] Li and Kameda[10] Shivaratri et al.[17] Eager et al.[5] M/M Zhou[20] Eager et al.[5] [5] 46

2 47 Mirchandaney et al.[11, 12] Mitzenmacher[13] Dahlin[3] (Undiscounted Markov Decision Processes, UMDP) (Neuro-Dynamic Programming, NDP) [2] NDP (Reinforcement Learning, RL)[18] 2 UMDP 3 2 UMDP 1 Modified Policy Iteration Method, MPIM [14, 16] 4 NDP Semi-Markov Average Reward Technique (SMART)[4] Simulation-Based Policy Iteration Algorithm (SBPI)[7] Simulation-Based Modified Policy Iteration Method (SBMPIM)[15] 5 NDP [20] 3 NDP 6 2. xxxxxx xxxxxx xxxxxx xxxxxx xxxxxx xxxxxx external stream (source) xxx xxx x0 xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx B0 switch node 0 load balancing x1 xxxxxxxx xxxxxxxx xxxxxxxx B1 xxx x2 xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx B2 xxx xxx xxx xxx xxx xxx xxx Bn server node xxx xxx xn xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx 1 2 n 1: 1 1 n 0 1,...,n M s = {1,...,n} M = {0,...,n} B i (i M)

Iteration Method, MPIM [14, 16] 4 NDP Semi-Markov Average Reward Technique (SMART)[4] Simulation-Based Policy Iteration Algorithm (SBPI)[7] Simulation-Based Modified Policy Iteration Method

3 48 t (t =0, 1,...) [t, t +1) i A(t) S i (t) A(t) S i (t) t Pr{A(t) =l} = α(l), Pr{S i (t) =l} = σ i (l), i M s, (l =0, 1,...) t i X i (t) X(t) =(X i (t); i M) π (f(x); x X ) f(x) (f i (x); i M s ) x X B i (i M) X = { (x i ; i M); 0 x i B i,i M } (2.1) x { } K(x) = (f i ; i M s ); f j x 0,f i + x i B i,i M s, x X (2.2) j M s (2.2) Π = {π; f(x) K(x), x X} X(t) X(t +1) t f K(X(t)) A(t) i S i (t) (i M s ) X 0 (t +1) = min{x 0 (t) f i + A(t),B 0 } (2.3) i M s X i (t +1) = max{x i (t)+f i S i (t), 0}, i M s (2.4) t x f t +1 x p(x, x, f) = Pr(X(t +1)=x X(t) =x, f) q i (x i,x i, f) (i M) p(x, x, f) = q i (x i,x i, f) (2.5) i M q 0 (x 0,x 0, f) (2.3) (x 0 i M s f i ) (x 0 x 0 + i M s f i ) B 0 x 0 x 0 + i M s f i 0 α(x 0 (x 0 i M s f i )), for 0 x 0 <B 0 q 0 (x 0,x 0, f) = l=b 0 (x 0 P i Ms f i) α(l), for x 0 = B 0 (2.6) 0, otherwise

2) j M s (2.2) Π = {π; f(x) K(x), x X} X(t) X(t +1) t f K(X(t)) A(t) i S i (t) (i M s ) X 0 (t +1) = min{x 0 (t) f i + A(t),B 0 } (2.3) i M s X i (t +1) = max{x i (t)+f i S i (t), 0}, i M s (2.

4 49 i (i M s ) q i (x i,x i, f) (2.4) (x i + f i ) (x i + f i x i) x i + f i x i 0 σ i ((x i + f i ) x i), for 0 <x i B q i (x i,x i i, f) = l=x i +f i σ i (l), for x i =0 i M s (2.7) 0, otherwise, : Ci H : 1 i (i M) C R : 1 Ci P : i (i M s ) 1 x f x r(x, x, f) r(x, x, f) = C0 H (x 0 f i )+ Ci H (x i + f i ) i M s i M s + I {x 0 =B 0 }C R l α(b 0 x 0 + l=0 i M s C P i (x i + f i x i) i M s f i + l) (2.8) I X X 1 0 x f r(x, f) r(x, f) = x X p(x, x, f)r(x, x, f) (2.9) UMDP [1,8,16] g + h(x) = min {r(x, f)+ p(x, x, f)h(x 0 )}, x X (2.10) f K(x) x X g h(x) x x (2.10) π =(f (x); x X) g (2.10) NDP x 0 (2.10)

7) 0, otherwise, : Ci H : 1 i (i M) C R : 1 Ci P : i (i M s ) 1 x f x r(x, x, f) r(x, x, f) = C0 H (x 0 f i )+ Ci H (x i + f i ) i M s i M s + I {x 0

5 50 3. (2.10) (Modified Policy Iteration Method : MPIM) MPIM Howard[8] (Policy Iteration Method :PIM) MPIM (Value Iteration Method: VIM) 0 VIM MPIM (MPIM) Step 1( ): x r X h 0 (x r )=0 h 0 (h 0 (x); x X ) π 0 Π, L ε>0, m =0 Step 2( ): x X g m+1 (x) = min {r(x, f)+ p(x, x 0, f)h m (x 0 ) h m (x)} f K(x) x X f m (x) g m+1 (x) f m+1 (x) =f m (x) f m+1 (x) g m+1 (x) f Step 3( ): w 0 (x) =h m (x) +g m+1 (x), x X l =0, 1,...,L 1 w l+1 (x) =r(x, f m+1 (x)) + p(x, x 0, f m+1 (x))w l (x 0 ) x 0 X h m+1 (x) =w L (x) w L (x r ), x X max x X hm+1 (x) h m (x) <ε m = m +1 step 2 Puterman[16] MPIM 4. NDP MDP NDP NDP SMART[4] SBPI[7] SBMPIM[15] 4.1. SMART[4] SMART (Semi-Markov decision process, SMDP) NDP Q- (Q-Learning) Semi-Markov Average Reward Technique(SMART) Step 1: m =0 R old (x, f) =R new (x, f) =0 π =(f(x); x X ) Π x 0 X TC =0 T =0 g =0 γ =(γ 0,γ τ ) η =(η 0,η τ ) Step 2: m<maxsteps Step 3

Π, L ε>0, m =0 Step 2( ): x X g m+1 (x) = min {r(x, f)+ p(x, x 0, f)h m (x 0 ) h m (x)} f K(x) x X f m (x) g m+1 (x) f m+1 (x) =f m (x) f m+1 (x) g m+1 (x) f Step 3( ): w 0 (x) =h m (x) +g m+1 (x), x

6 51 Step 3: η m,γ m η m = η 0 1+ m2 η τ + m,γ m = γ 0 1+ m2 γ τ + m Step 4: [0, 1] U U <1 η m f = arg min f K(x m) R old(x m, f) f = f K(x m ) f f Step 5: x m+1 Step 6: R new r imm = r(x m, x m+1, f) R new (x m, f) =(1 γ m )R old (x m, f)+γ m {r imm g + Step 7: : f = f Step8 Step 9 Step 8: TC T g TC = TC + r(x m, x m+1, f), T= T +1,g= TC T Step 9: R old (x m, f) =R new (x m, f),m= m +1 Step 2 min R old (x m+1, f)} f K(x m+1 ) 4.2. SBPI[7] SBPI PIM Simulation-Based Policy Iteration Algorithm(SBPI) Step 1( ): π 0 Π x r X M m =0 Step 2( ): g m h m (a) g m (i) x 0 X x 1,...,x M (ii) g m =0 t =0,...,M 1 (x t, x t+1 ) g m g m =(1 1 t +1 )gm + 1 t +1 r(x t, x t+1, f m (x t )) (b) h m (i) Step 2 (a)-(i) x (ii) x 0 x L

m, f) =R new (x m, f),m= m +1 Step 2 min R old (x m+1, f)} f K(x m+1 ) 4.2. SBPI[7] SBPI PIM Simulation-Based Policy Iteration Algorithm(SBPI) Step 1( ): π 0 Π x r X M m =0 Step 2( ): g m h m (a) g m (i) x 0 X x 1,.

7 52 (iii) (x 0, x 1,...,x ) (x t, x t+1 ) w(x i ) (i =1, 2,...,t) w(x i )=w(x i )+γ i η t i d t γ i x i 0 η 1 d t = r(x t, x t+1, f(x t )) g m + w(x t+1 ) w(x t ) (iv) h m Step 3( ): x X h m (x) =w(x) w(x r ), x X f m+1 (x) =argmin {r(x, f)+ p(x, x, f)h m+1 (x 0 )} f K(x) x X f m+1 (x) f m+1 (x) π m = π m+1 m = m +1 Step 2 [7] Step 2 (a) L A L A =1 (b) Fox-Landi algorithm [16] (a) 4.3. SBMPIM[15] SBMPIM MPIM [15] Simulation-Based Modified Policy Iteration Method(SBMPIM) Step 1( ): x 0 X x k η, (0 η 1) S v = φ S T = φ TC =0 x = x 0 m = l =1 Step 2( ): x S v S v = S v {x} S T = S T {x} x v(x) =1 f(x) x u(x) =r(x, f(x)) x S v x S T S T = S T {x} v(x) =1 u(x) =r(x, f(x)) x S T v(x) =v(x)+1, u(x) =u(x)+r(x, f(x)) x f(x) x TC = TC + r(x,f(x)), x = x l = k Step 3 l = l +1 Step 2

m+1 (x 0 )} f K(x) x X f m+1 (x) f m+1 (x) π m = π m+1 m = m +1 Step 2 [7] Step 2 (a) L A L A =1 (b) Fox-Landi algorithm [16] (a) 4.3.

8 53 Step 3(g ) : g Step 4(h ) :S v x r h(x r )=(1 ηv(x r) k x( x r ) S v h(x) =(1 ηv(x) k g = TC k )(w(x r ) g)+ ηv(x r) ( u(x r) k v(x r ) g) )(w(x) g)+ ηv(x) ( u(x) k v(x) g) h(x r) h(x r )=0 m =1 h(x r )= u(x r) g, h(x) =u(x) v(x r ) v(x) g h(x r) Step 5( ): x S v 5. w(x) = min {r(x,f)+ p(x, x,f)h(x 0 )} f K N (x,f(x)) x X f(x) =f v(x) =1 K N (x, f(x)) ( K(x)) f(x) p(x, x,f) > 0 x S v S v = S v {x } v(x 0 )=1 f(x ) x w(x )=r(x, f(x )) h(x )=h(x) w(x) f(x) w(x) w(x) f(x) m S T = φ TC =0 l =1 m = m +1 Step NDP NDP MPIM NDP i α(l) =λ(1 λ) l,l=0, 1,... (5.1) σ i (l) =μ i (1 μ i ) l,l=0, 1,..., i M s (5.2) n =2 λ =0.4 μ 1 =0.2 μ 2 =0.3 C i H =2(i M) C R =15 Ci P =0(i M s ) 3 :

w(x) = min {r(x,f)+ p(x, x,f)h(x 0 )} f K N (x,f(x)) x X f(x) =f v(x) =1 K N (x, f(x)) ( K(x)) f(x) p(x, x,f) > 0 x S v S v = S v {x } v(x 0 )=1 f(x ) x w(x )=r(x, f(x ))

9 54 1) B i =5(i M) 2) B i =8(i M) 3) B i =10(i M) 216, 729, 1331 DOS/V (CPU: AMD Athlon XP 2200+, Memory: 512MB OS: Windows 2000) 1 MPIM ε =10 5 m =20 SMART (η 0,η τ )=(0.4, ) (γ 0,γ τ )=(0.6, ) MAX STEPS = (2),3) ) SBPI η =0.9 m = L = 1000 SBMPIM η =0.8 k = 5000 =40 SBMPIM K N (x, f ) f =(f 1,f 2,...,f n) K 2 { } K A (f )= (f i ; i M s ); f j 1 f j f j +1, x X j M s j M s j M s } K B (f )= {(f i ; i M s ); f i 1 f i f i +1,i M s, x X K N (x, f )=K(x) K A (f ) K B (f ) 1 SBPI SBMPIM MPIM SBMPIM 95% SMART [15] SMART SMART SBMPIM 2 2 SBMPIM 2 1) MPIM SBMPIM SBPI SBMPIM MPIM SBMPIM 1: 1) 2) 3) MPIM SMART SBPI SBMPIM 5.894± ± ± SBMPIM NDP [5, 17, 20]

..,f n) K 2 { } K A (f )= (f i ; i M s ); f j 1 f j f j +1, x X j M s j M s j M s } K B (f )= {(f i ; i M s ); f i 1 f i f i +1,i M s, x X K N (x, f )=K(x) K A (f ) K B (f ) 1 SBPI SBMPIM MPIM

10 MPIM SBMPIM SMART SBPI 25 CPU Time The Total Number of States 2: NDP 3 SBMPIM t X 0 (t) K i (t) (i M s ) E[S i (t)] i P i P i = E[S i (t)] i M s E[S i (t)] (5.3) Step 1: H = X 0 (t) K i (t) =0(i M s ) Step 2: H =0 X i (t)+k i (t) =B i (i M s ) Step 4 Step 3: P j j X j (t) +K j (t) < B j K j (t) = K j (t)+1 H = H 1 Step 2 Step 4: K(t) =(K i (t); i M s ) t

11 56 2: 1) x MPIM SMART SBPI SBMPIM (2,0,0) (1,1) (1,1) (1,1) (1,1) (2,0,1) (2,0) (1,1) (2,0) (2,0) (2,0,2) (2,0) (2,0) (2,0) (2,0) (2,0,3) (2,0) (0,2) (2,0) (2,0) (2,0,4) (2,0) (2,0) (2,0) (2,0) (2,0,5) (2,0) (2,0) (2,0) (2,0) (2,1,0) (1,1) (0,2) (1,1) (1,1) (2,1,1) (2,0) (0,2) (2,0) (2,0) (2,1,2) (2,0) (0,0) (2,0) (2,0) (2,1,3) (2,0) (0,2) (2,0) (2,0) (2,1,4) (2,0) (2,0) (2,0) (2,0) (2,1,5) (2,0) (2,0) (2,0) (2,0) (2,2,0) (1,1) (0,2) (1,1) (1,1) (2,2,1) (1,1) (0,0) (1,1) (1,1) (2,2,2) (2,0) (0,2) (2,0) (2,0) (2,2,3) (2,0) (2,0) (2,0) (2,0) (2,2,4) (2,0) (2,0) (2,0) (2,0) (2,2,5) (2,0) (0,0) (2,0) (2,0) (2,3,0) (0,2) (2,0) (0,2) (0,2) (2,3,1) (1,1) (1,1) (1,1) (1,1) (2,3,2) (1,1) (2,0) (2,0) (1,1) (2,3,3) (2,0) (1,1) (2,0) (2,0) (2,3,4) (2,0) (1,1) (2,0) (2,0) (2,3,5) (2,0) (2,0) (2,0) (2,0) , 3,... 1 n 1 t i t +1 i +1 i = n 1 Step 1: H = X 0 (t) K i (t) =0(i M s ) t =0 j =1 j t 1 Step 2: H =0 Step 4 Step 3: K j (t) =K j (t)+1 H = H 1 j = j +1 j = n +1 j =1 Step 2

(2,0) (2,0) (2,0) (2,0) (2,2,0) (1,1) (0,2) (1,1) (1,1) (2,2,1) (1,1) (0,0) (1,1) (1,1) (2,2,2) (2,0) (0,2) (2,0) (2,0) (2,2,3) (2,0) (2,0) (2,0) (2,0) (2,2,4) (2,0) (2,0) (2,0) (2,0) (2,2,5) (2,0)

12 57 Step 4: K(t) =(K i (t); i M s ) t t i L i L i = X i(t) E[S i (t)],i M s (5.4) (5.4) X i (t) K i (t) L i L i = X i(t)+k i (t),i M s (5.5) E[S i (t)] (5.5) 1 Step 1( ): H = X 0 (t) K i (t) =0(i M s ) Step 2( ) : H =0 X i (t)+k i (t) =B i (i M s ) Step 4 Step 3( ) : j j = arg min j M s {L j; X j (t)+k j (t) <B j } K j (t) =K j (t)+1 H = H 1 Step 2 Step 4( ) : K(t) =(K i (t); i M s ) t SBMPIM (2.9) (5.1) Z 0 =(1 λ)/λ (5.2) SBMPIM η = m = NM+MCB[6] 95% ρ ρ = E[A] i M s E[S i ] (5.6) n =4 B 0 =10 B i =2, (i M s ) μ i =0.5 (i M s ) Ci H =3(i M) C R =5 Ci P =1(i M s ) ρ i Y i Y i min j i Y j 3 Random RoundRobin

K j (t) =K j (t)+1 H = H 1 Step 2 Step 4( ) : K(t) =(K i (t); i M s ) t 5.2.4. SBMPIM (2.9) (5.1) Z 0 =(1 λ)/λ (5.2) SBMPIM η =0.

13 58 Shortest ρ λ SBMPIM SBMPIM 1.5 SBMPIM Random RoundRobin Shortest 1 cost difference traffic rate 3: 6. (UMDP) (NDP) (MPIM) Semi-Markov Average Reward Technique (SMART) Simulation-Based Policy Iteration Algorithm (SBPI) Simulation-Based modified Policy Iteration Method (SBMPIM) 4 NDP NDP NDP Simulation-Based Modified Policy Iteration Method(SBMPIM) SBMPIM SBMPIM NDP

14 59 [1] R.E. Bellman: Dynamic Programming (Princeton University Press, Princeton, 1957). [2] D.P. Bertsekas, and J.N. Tsitsiklis: Neuro-Dynamic Programming (Athena Scientific, Belmont, 1996). [3] M. Dahlin: Interpreting stale load information. IEEE Transactions on Parallel and Distributed Systems, (2000), [4] T.K. Das, A. Gosavi, S. Mahadevan, and N. Marchalleck: Solving semi-markov decision problem using average reward reinforcement learning. Management Science, 45 (1999), [5] D. Eager, E. Lazowska, and J. Zahorjan: Adaptive load sharing in homogeneous distributed systems. IEEE Transactions on Software Engineering, 12-5 (1986), [6] D. Goldsman, and B.L. Nelson: Computing systems via Simulation. In J. Banks (ed.): Handbook of Simulation: Principles, Methodology, Advances, Applications, and Practice (John Wiley & Sons, New York, 1998), [7] Y. He, M.C. Fu, and S.I. Marcus: A simulation-based policy iteration algorithm for average cost unichain Markov decision processes. In M. Laguna and J. L. G. Velarge (eds.): Computer Tools for Modeling, Optimization and Simulation (Kluwer Academic, Boston, 2000), [8] R. Howard: Dynamic Programming and Markov Processes (MIT Press, Cambridge, 1960). [9] H. Kameda, J. Li, C. Kim, and Y. Zhang: Optimal Load Balancing in Distributed Computer Systems (Springer, London, 1997). [10] J. Li, H. Kameda: Optimal load balancing problems for multiclass jobs in distributed/parallel computer systems. IEEE Transactions on Computers, 47-3 (1998), [11] R. Mirchandaney, D. Towsley, and J. Stankovic: Analysis of the effects of delays on load sharing. IEEE Transactions on Computers, (1989), [12] R. Mirchandaney, D. Towsley, and J. Stankovic: Adaptive load sharing in heterogeneous distributed systems. Journal of Parallel and Distributed Computing, 9 (1990), [13] M. Mitzenmacher: How useful is old information. IEEE Transactions on Parallel and Distributed Systems, 11-1 (2000), [14] K. Ohno: Modified policy iteration algorithm with nonoptimality tests for undiscounted Markov decision process. Working Paper, Dept. of Information System and Management Science, Konan University (1985). [15],, :,, 54-5 (2003), [16] M.L. Puterman: Markov Decision Processes (John Wiley & Sons, New York, 1994). [17] N.G. Shivaratri, P. Krueger, and M. Shinghal: Load distributing for locally distributed systems. Computer, (1992), [18] R.S. Sutton and A.G. Barto: Reinforcement Learning (MIT Press, Cambridge, 1998)

Marchalleck: Solving semi-markov decision problem using average reward reinforcement learning. Management Science, 45 (1999), 560-574. [5] D. Eager, E. Lazowska, and J.

15 60 [19] A.N. Tantawi and D. Towsley: Optimal static load balancing in distributed computer systems. Journal of the ACM, 32-2 (1985), [20] S. Zhou: A trace-driven simulation study of dynamic load balancing. IEEE Transactions on Software Engineering, 14-9 (1988), inoie@nw.kanagawa-it.ac.jp

Journal of the ACM, 32-2 (1985), 445-465. [20] S.

16 61 ABSTRACT A DISCRETE-TIME LOAD BALANCING PROBLEM BY NEURO-DYNAMIC PROGRAMMING ALGORITHMS Atsushi Inoie Kanagawa Institute of Technology Katsuhisa Ohno Aichi Institute of Technology The meaning of load balancing is to dispatch jobs among resources of a system for maximizing the system performance. This paper deals with a discrete-time optimal load balancing problem that minimizes an expected total cost. This problem is formulated as an undiscounted Markov decision process, and is solved by the modified policy iteration method. Since the modified policy iteration method can not solve practical sized problems due to the curse of dimensionality, a near-optimal load balancing policy is computed by neuro-dynamic programming algorithms. We further compare this policy with heuristic policies such as the random policy, round-robin policy and shortest policy.

This paper deals with a discrete-time optimal load balancing problem that minimizes an expected total cost.

$\mathrm{d}\mathrm{p}$ (Katsuhisa $\mathrm{o}\mathrm{m}\mathrm{o}$) Aichi Institute of Technology (Takahiro Ito) Nagoya Institute of Te

$$\mathrm{d}\mathrm{p}$ (Katsuhisa $\mathrm{o}\mathrm{m}\mathrm{o}$) Aichi Institute of Technology (Takahiro Ito) Nagoya Institute of Te$ Title ニューロ DP による多品目在庫管理の最適化 ( 不確実で動的なシステムへの最適化理論とその展開 ) Author(s) 大野勝久 ; 伊藤崇博 ; 石垣智徳 ; 渡辺誠 Citation 数理解析研究所講究録 (24) 383: 64-7 Issue Date 24-7 URL http://hdlhandlenet/2433/2575 Right Type Departmental