(复杂系统的性能评价与优化课件资料）Lecture Notes PA.pdf

Copyright © by Yu-Chi Ho 1 LECTURE NOTES #9 VERSION: 3.2 DATE: 2007-5-18 FROM ES 205 LECTURE NOTES #12 INTRODUCTION TO PA REFERENCES OF THIS WEEK: 1. Introduction to Discrete Event Systems, Christos G. Cassandras, Sthane Lafortune, Boston : Kluwer Academic, 1999 2. Perturbation Analysis of Discrete Event Dynamic Systems, Yu-Chi Ho, Xi-Ren Cao, Boston : Kluwer Academic Publishers, c1991 x1 – system at rest x2 – node 1 transmitting x3 – node 2 transmitting x4 – waiting for acknowledgements x5 – all acknowledgments verified e1 – message 1 received by node 1 to transmit; e2 – message 2 received by node 2 to transmit; e3 – node 2 to repeat message 2; e4 – all transmissions complete; e5 – acknowledgements received; Figure 1. An Example of a DEDS Trajectory 1.To facilitate the discussion of Perturbation Analysis (PA), let us introduce some notations for DEDS. Let θ = system parameter(s) x(t) = a time history of the evolution of the DEDS, i.e., the (state, holding time) sequence as illustrated in Fig.1. In more physical terms, this may consist of the content of all the queues as a function of time, durations of all service intervals, etc. Since DEDS are often stochastic, x(t) will in general be Copyright © by Yu-Chi Ho 2 dependent on the actual realized values of various random variables in the system. ξ = a vector of random variables, defined on the underlying probability space, that represents all the random phenomena of the DEDS or a particular realization of all the random variables in the system. We may write x(t) = x(t;θ,ξ) to indicate the dependency on θ and ξ. x(t;θ,ξ) is called a trajectory, or a sample path, of the DEDS. Also we let τi = the ith transition of the state process x(t), i.e., the ith time when x(t) switches from one discrete state to another as a result of an occurrence of an event. When we perturb the parameter θ to θ+∆θ, we obtain a perturbed sample path denoted by x(t;θ+∆θ,ξ). In the parlance of discrete event simulations, if x(t;θ,ξ) is generated by a simulation, then x(t;θ+∆θ,ξ) is the simulation generated by the same model using the same initial seed for the random number generator with only the value of θ changed to θ+∆θ. To colloquially differentiate between x(t;θ,ξ) and x(t;θ+∆θ,ξ), we call the former the nominal path or trajectory, NP, the latter, the perturbed path or trajectory, PP. 2. Given a DEDS and its sample paths, a sample performance measure is a functional defined on that sample path, e.g., the time required to serve N customers. Two common examples for the sample performance measure are ()()()()() 01; ,; ,d,TL x tf x ttLTθ ξθ ξθ ξ≡≡∫(1) and ()()()()() 01; ,; ,d,NL x tf x ttLNτθ ξθ ξθ ξ≡≡∫. (2) Note that the sample performance defined above depends implicitly on the length of the sample path, T or τΝ. Since the sample paths of a DEDS are piecewise constant, we can equivalently write Eqs.(1) and (2) as ()( )()11 01,Niii iNLf xθ ξτττ−+ =≡−∑(3) ()( )()11 01,Niii iLf xNθ ξττ−+ =≡−∑, (4) where xi = x(τi+) is the ith state and (τi+1-τi) is the duration of the ith state, τ0=0. The expected value of L(θ,ξ) is J(θ) ≡ E[L(θ,ξ)], which is the central item of interest in the performance evaluation of DEDS. Note that the above performance measure is defined in terms of finite time intervals. Stated simply, Perturbation Analysis (PA), particularly Infinitesimal Perturbation Analysis (IPA), is a technique for the computation of the gradient of the expected or the Copyright © by Yu-Chi Ho 3 limiting performance measure of a discrete event dynamic system with respect to its parameters, i.e., ∂J(θ)/∂θ, using only one sample path or one Monte Carlo simulation of the system. A slightly more general definition of PA explains it as a technique to infer knowledge of L(θ+∆θ, ξ) from observing x(t;θ,ξ), the behavior of the system under θ alone. Thus, the basic goal of PA is to squeeze out as much information as possible from one sample path of a DEDS. Note that traditionally sensitivity information such as dJ(θ)/dθ are estimated by doing two experiments with the DEDS, one at θ and the other at θ+∆θ. Taking the difference between the two performance measures and dividing through by ∆θ yields an estimate for the derivative. In other words, ()()()0d,,,1lim limdnnNnE LLLNθθ ξθθ ξθ ξθθΔ →→∞⎡⎤+Δ−⎣⎦=Δ∑. One is trapped between the twin evils of noise and nonlinearity! 3. Introduction to PA history. The objections at the philosophical, intuitive, and mathematical level (Chapter 2). i. philosophical — how can x(θ,ξ) convey information about x(θ+∆θ,ξ). there is no free lunch ii. intuitive — does x(θ,ξ) deviate sooner or later from x(θ+∆θ,ξ) no matter how small is ∆θ. iii. mathematical — we use L(x(θ,ξ)) to estimate E[L(x(θ,ξ))], but it does not immediately follow that dL/dθ estimates correctly (unbiasedness and consistency) dE[L]/dθ. These are very good questions. We shall answer them in good time. The production line e。