（管理科學(xué)與工程專業(yè)論文）半markov型排隊網(wǎng)絡(luò)的優(yōu)化及其并行仿真算法研究與應(yīng)用.pdf

摘要 本文的工作重點是研究半m a r k o v 控制過程中的并行優(yōu)化算法。首先給出一種半 m a r k o v 控制過程性能勢的估計算法，相對于基于實現(xiàn)矩陣的估計方法具有速度快，對計算 機硬件要求不高等特點。其后研究了半m a r k o v 控制過程基于單樣本軌道的仿真優(yōu)化算法， 并從實際應(yīng)用的角度出發(fā)發(fā)展了相應(yīng)的并行算法，并提供了計算實例并分析比較其結(jié)果。 最后，我們給出了通訊中兩個實際網(wǎng)絡(luò)的優(yōu)化與導(dǎo)數(shù)估計的應(yīng)用實例一是半m a r k o v 決 策過程方法在航空軍械綜合系統(tǒng)維護問題中的應(yīng)用；二是m p h 1 排隊系統(tǒng)的性能靈敏度估 計與仿真及其在a t m 交換機性能分析中的應(yīng)用。 本文的創(chuàng)新之處在于： ( 1 ) ：根據(jù)m a r k o v 性能勢理論，將它推廣到半m a r k o v 模型，得出了半m a r k o v 模型 的性能優(yōu)化公式，并給出了相應(yīng)的優(yōu)化算法。 ( 2 ) ：利用并行估計，給出了一套并行算法，大大提高了處理速度。 、，上 天 建- 7 ：半m a r k o v 過程，性能勢，實現(xiàn)矩陣，優(yōu)化算法，并行仿真 a b s t r a c t p a r a l l e ls i m u l a t i o na l g o r i t h mo fs e m i m a r k o vc o n t r o lp r o c e s s e si ss t u d i e di nt h i st h e s i s a s i m u l a t i o na l g o r i t h mo ft h ep e r f o r m a n c ep o t e n t i a l si sp r e s e n t e d ，w i t ht h ea d v a n t a g eo ff a s t e r s p e e d ，l o w e rd e m a n d so fc o m p u t e rh a r d w a r et h a nt h ea l g o r i t h mb a s e do nr e a l i z a t i o nm a t r i x t h e nw ep r o v i d eas i m u l a t i o no p t i m i z a t i o na l g o r i t h mo fs e m i m a r k o vc o n t r o lp r o c e s s e sb a s e d o ns i n g l es a m p l ep a t h ，a n dac o r r e s p o n d i n gp a r a ll e l a l g o r i t h mw a sd e v e l o p e d s o m en u m e r i c a l e x a m p l e sa r eg i v e nt oi l l u s t r a t et h ea p p l i c a t i o no ft h ea l g o r i t h m s f i n a l l y , t w or e a le x a m p l e si nc o m m u n i c a t i o nw e r eg i v e n o n ee x a m p l ei st h a ts e m i m a r k o v d e c i s i o np r o c e s sm e t h o di nt h em a i n t e n a n c eo ft h ea v i a t i o no r d n a n c es y n t h e t i cs y s t e m t h eo t h e r i s s e n s i t i v i t ye s t i m a t e & s i m u l a t i o n so fp e r f o r m a n c ei nm p h 1 q u e u e i n gs y s t e m sa n dt h e a p p l i c a t i o n si na t m s w i t h t h ei n n o v a t i o no ft h i sp a p e ri s ： ( 1 ) ：a c d o r d i n gt ot h em a r k o vp e r f o r m a n c ep o t e n t i a l st h e o r y , e x t e n di tt ot h es e m i m a r k o v m o d l e ，g e tt h ep e r f o r m a n c eo p t i m i z a t i o ne q u m i o n ，a n dt h eo p t i m i z a t i o na l g o r i t h m si sg i v e n ( 2 ) ：b a s e do nt h ep a r a l l e ls i m u l m i o n ，ap a r a l l e la l g o r i t h m si s g i v e n ，a n dt h es p e e di sm u c h h i g h e r 一， - k e y w o r d s ：s e m i m a r k o vc o n t r o lp r o c e s s e s ，p e r f o r m a n c ep o t e n t i a l ，r e a l i z a t i o nm a t r i x o p t i m i z m i o na l g o r i t h m ，p a r a l l e ls i m u l m i o n 中國科學(xué)技術(shù)大學(xué)碩士論文 第一章緒論 在這一章中簡單介紹了離散事件動態(tài)系統(tǒng)，其后說明了本文的工作所涉及到的相關(guān)概 念：半m a r k o v 控制過程和性能勢、仿真及并行計算，并簡單介紹了本文的結(jié)構(gòu)，作為后續(xù) 文章的基礎(chǔ)。 1 1 離散事件動態(tài)系統(tǒng) 離散事件動態(tài)系統(tǒng)是系統(tǒng)和控制領(lǐng)域的一門新的分支，它在許多實際應(yīng)用中有著廣泛 的應(yīng)用前景，因此自提出以來得到飛速的發(fā)展。 1 1 1 基本概念 隨著信息通訊、計算機和機器人等高新技術(shù)的發(fā)展和應(yīng)用，在通信網(wǎng)絡(luò)、柔性制造、 交通管理、軍事指揮等領(lǐng)域相繼出現(xiàn)了大量反映現(xiàn)代科學(xué)技術(shù)發(fā)展方向的人造系統(tǒng)，這類 系統(tǒng)通常能被描述為離散事件動態(tài)系統(tǒng)( d e d s ) 。經(jīng)過近幾十年的快速發(fā)展，離散事件動態(tài) 系統(tǒng)己經(jīng)成為控制和系統(tǒng)領(lǐng)域的一個前沿方向，并在當(dāng)今一大批高科技領(lǐng)域獲得了廣泛應(yīng) 用，是系統(tǒng)和控制領(lǐng)域的一門新的分支，它是由哈佛大學(xué)何毓琦( yc h o ) 教授等人于八十 年代前后創(chuàng)立的 1 】，名稱也是由何毓琦教授等人提出的，以區(qū)別于此前已得到廣泛研究的 連續(xù)變量動態(tài)系統(tǒng)( c v d s ) 。在d e d s 中，對系統(tǒng)行為進程起決定作用的是一批離散事件， 而不是連續(xù)變量，所遵循的是一些復(fù)雜的人為規(guī)則，而不是物理學(xué)定律或廣義物理學(xué)定律。 正是基于對這類人造系統(tǒng)行為和性能研究的需要，推動著d e d s 理論的形成和發(fā)展【2 1 2 】 構(gòu)成d e d s 的基本要素是離散事件，d e d s 行為隨時間的演化過程就是離散事件復(fù)雜 交互影響的結(jié)果。粗略地說，離散事件是指d e d s 中發(fā)生在離散時刻的事件，所謂事件則 是使d e d s 狀態(tài)發(fā)生變動的一個行動或事情。 和離散時間連續(xù)變量動態(tài)系統(tǒng)不同，d e d s 中離散事件的發(fā)生時刻通常是異步的。離 散事件的發(fā)生時刻，取決于這一時刻前系統(tǒng)行為的演化過程。柔性生產(chǎn)線中的“工件到達 機床”和“工件加工完成”，通信網(wǎng)絡(luò)中的“信號到達網(wǎng)絡(luò)”和“信息傳遞結(jié)束”，就是離 散事件的一些典型例子。在d e d s 中，一個離散事件的發(fā)生，在驅(qū)動系統(tǒng)狀態(tài)產(chǎn)生躍變的 同時，還會按照系統(tǒng)的運行規(guī)則在系統(tǒng)其他部分觸發(fā)新的離散事件，從而形成在離散事件 驅(qū)動下系統(tǒng)狀態(tài)的演化過程。柔性生產(chǎn)線中工件沿著加工機床的持續(xù)加工過程，通信網(wǎng)絡(luò) 中信息沿傳輸設(shè)施的持續(xù)傳遞和變換過程，就是離散事件復(fù)雜交互影響下所形成的d e d s 行為演化過程的一些例子。 從上面可以看出，d e d s 中的離散事件具有三個基本特征：其一，離散事件是導(dǎo)致d e d s 狀態(tài)發(fā)生躍變和觸發(fā)新離散事件的唯一因素，也即離散事件是驅(qū)動系統(tǒng)狀態(tài)演化的基本因 素。其二，離散事件的發(fā)生時刻是異步的和非約定的，即發(fā)生時刻由且只由系統(tǒng)的演化過 程所決定。其三，離散事件是研究d e d s 的主體，對d e d s 的分析歸結(jié)為確定離散事件交 互影響所導(dǎo)致的系統(tǒng)狀態(tài)的演化過程，對d e d s 的控制歸結(jié)為禁止不期望事件的發(fā)生或使 事件按期望的時序發(fā)生。 在實際系統(tǒng)中有許多可以用d e d s 來描述。例如一間只有一個理發(fā)師的理發(fā)店，在正 常工作的時間內(nèi)，如果沒有顧客到達理發(fā)店，則理發(fā)師空閑：如果有顧客到達理發(fā)店，則理 4 中國科學(xué)技術(shù)大學(xué)碩士論文 發(fā)師為顧客進行理發(fā)服務(wù)。如果顧客到達理發(fā)店時，理發(fā)師正在為其他顧客服務(wù)，則新來 的顧客在一旁排隊等待。顯然，每個顧客到達理發(fā)店的時間是隨機的，而理發(fā)師為每個顧 客進行理發(fā)服務(wù)的時間也是隨機的，從而每個隊列中的顧客等待的時間也是隨機的，這是 一個典型的離散事件系統(tǒng)的例子。 在現(xiàn)代高技術(shù)領(lǐng)域中出現(xiàn)的大量人造系統(tǒng)大多數(shù)也可以用d e d s 來描述。例如通訊 網(wǎng)絡(luò)中的呼叫接入系統(tǒng)，其中一個用戶呼叫的到來和結(jié)束就是兩個離散的事件，而某一時 刻所有不同的服務(wù)節(jié)點中接入的不同形式的用戶數(shù)目就構(gòu)成了一個狀態(tài)。如果考慮緩沖器， 則還需要計入不同緩沖器中的不同的用戶數(shù)目。 如圖1 1 所示的柔性生產(chǎn)線或稱柔性制造系統(tǒng)，簡稱為f m s ( f l e x i b l e m a n u f a c t u r i n g s y s t e m s ) ，也是最具典型性和重要性的一個例子。在計算機控制單元的控制下，不同的待加 工工件通過自動物料傳送系統(tǒng)輸送到相應(yīng)加工中心的緩沖區(qū)，由加工中心對工件進行多類 型的加工，從刀具的控制到加工工藝的確定都由計算機控制程序決定和控制，且程序的調(diào) 用和更改非常方便靈活，因此具有很好的柔性。加工完畢的工件通過自動物料傳送系統(tǒng)輸 送到自動倉庫。 圖1 1 柔性制造系統(tǒng)示意圖 這樣的柔性制造系統(tǒng)是一個典型的離散事件動態(tài)系統(tǒng)。在f m s 中，各個加工中心對 各類工件的加工活動構(gòu)成為系統(tǒng)的狀態(tài)，由工件和加工中心組成系統(tǒng)的資源，資源的投入 或釋放構(gòu)成為系統(tǒng)的離散事件。表征系統(tǒng)加工活動的狀態(tài)的躍變，由待加工工件的到達( 投 入) 和機床的完成加工( 釋放) 等事件所驅(qū)動。顯然，狀態(tài)演化過程中，狀態(tài)躍變時刻將呈現(xiàn) 出異步性，而系統(tǒng)演化則由離散事件錯綜復(fù)雜的相互作用所決定。當(dāng)f m s 的基本參數(shù)( 如 加工中心對各種工件的作業(yè)時間、自動物料傳送系統(tǒng)的運行速度、工件的加工特性等) 為固 定不變時，f m s 中出現(xiàn)的事件可認(rèn)為是確定性的，整個f m s 可表征為一個確定性d e d s 。 如果f m s 的基本參數(shù)( p n 機床作業(yè)時間、自動物料傳送系統(tǒng)的運行速度等) 受內(nèi)部和外部因 素影響而具有不確定性時，f m s 中的事件在本質(zhì)上是隨機性的，f m s 相應(yīng)地需要采用隨機 d e d s 來描述。 基于f m s 的d e d s 模型，可用來確定對待加工工件的排序，分析加工過程的加工節(jié) 奏，避免f m s 出現(xiàn)阻塞現(xiàn)象，優(yōu)化配置各個緩沖區(qū)的容量，以及優(yōu)化系統(tǒng)的生產(chǎn)率等。 5 中國科學(xué)技術(shù)大學(xué)碩士論文 1 1 2d e d s 的研究方法 d e d s 的研究，根據(jù)所用模型和采用工具的不同，基本上可以分為三個不同的方向， 即邏輯層次，時間層次，及隨機統(tǒng)計層次。采用不同的方式來描述d e d s 中的事件和狀態(tài) 這兩個基本要素，并通過它們運用不同的手段來研究同一個過程，從而決定了這三種模型 及其研究方法。在對d e d s 的研究中各有其側(cè)重點，因而它們也各有其優(yōu)缺點。 在邏輯層次模型下，采用的系統(tǒng)模型主要有形式語言，有限自動機，m a r k o v 鏈，p e t r i 網(wǎng)j 1 3 一i 8 1 等。在該層次模型下，一般用一些離散的符號來表征系統(tǒng)的狀態(tài)，并且不要求狀 態(tài)空間( 事件的集合) 有任何的拓?fù)浣Y(jié)構(gòu)。運用人們規(guī)定的某種機制來驅(qū)動事件的產(chǎn)生和滅 亡，從而導(dǎo)致系統(tǒng)狀態(tài)的轉(zhuǎn)移。因此，從邏輯層次研究d e d s ，就是研究事件和狀態(tài)按照 邏輯時間序列運行，而不涉及系統(tǒng)的真實物理時間。故其采用的研究手段，大多是一些邏 輯性較強的工具，例如有限自動機，p e t r i 網(wǎng)等，在邏輯層次下，對系統(tǒng)的控制及控制作用 下的系統(tǒng)行為有較深刻的研究，但由于其未考慮系統(tǒng)的物理時間，故難以用于連續(xù)時間 d e d s 的動態(tài)分析。 在時問層次模型下，采用的主要建模方法包括，極大極小代數(shù)，有限遞歸過程等，而 基于極大極小代數(shù)或更一般的雙子代數(shù)的研究，由于其特殊的運算規(guī)則，導(dǎo)致系統(tǒng)的動態(tài) 方程非常類似于通常連續(xù)變量線性系統(tǒng)。在這一層次下，不僅考慮事件和狀態(tài)的邏輯順序 關(guān)系，而且也涉及系統(tǒng)真實的物理時間，從而可以用于系統(tǒng)的動態(tài)分析。特別是，基于線 性化的動態(tài)方程，可以定量的研究系統(tǒng)的穩(wěn)定性及結(jié)構(gòu)特征等系統(tǒng)行為。但其主要缺陷是 適用的范圍較窄 1 9 】，并且通常連續(xù)變量線性系統(tǒng)中一系列行之有效的分析，控制和優(yōu)化 技術(shù)難以應(yīng)用到這樣的線性系統(tǒng)模型中。 在隨機統(tǒng)計層次模型下，采用的系統(tǒng)模型主要是排隊網(wǎng)絡(luò)和隨機過程。一般來說， d e d s 中某個參變量的微小變化，都會導(dǎo)致系統(tǒng)以十分不同的方式運行，因此需要考慮系 統(tǒng)中許多參變量的隨機變化，從而在性能分析中需要采用統(tǒng)計平均的方法。從統(tǒng)計性能層 次研究d e d s ，也是d e d s 研究的最初形式，何毓琦( yc h o ) 教授等人提出d e d s 這個概 念時就是從該層次出發(fā)的。在這一層次下，采用的系統(tǒng)模型主要為m a r k o v 過程、半m a r k o v 過程、廣義半m a r k o v 過程和各種類型的排隊網(wǎng)絡(luò)等，其中有代表性的研究方法是攝動分 析( p a ) ，無窮小攝動分析( i p a ) ，m a r k o v 決策( 控制) 過程等。 總體而言，現(xiàn)在對離散事件動態(tài)系統(tǒng)建模的研究，還遠不是成熟的和完善的。不管是 從形式的統(tǒng)一性，還是從數(shù)學(xué)表達的簡明性和計算分析的可行性，都遠不如連續(xù)變量動態(tài) 系統(tǒng)的建模那樣完美。更廣義地說，由于d e d s 屬于人造系統(tǒng)的范疇，系統(tǒng)機制中可能會 同時并存多種交互作用，如事件之間的交互作用、人與系統(tǒng)的交互作用、系統(tǒng)與環(huán)境的交 互作用等，系統(tǒng)各種關(guān)系中也可能會同時含有多種表達形式，如定t 、定性和知識的形式 等。因此，一個復(fù)雜的離散事件動態(tài)系統(tǒng)助建模，最終可能需要同時借助于運籌學(xué)、系統(tǒng) 與控制理論、人工智能與自然語言理解等多學(xué)科的方法的結(jié)合。一般認(rèn)為，如圖1 2 所示 那樣，d e d s 的模型定位于這三個學(xué)科之間的交叉部分。 1 2 半m a r k o v 控制過程和性能勢 m a r k o v 控制過程，又稱為m a r k o v 決策過程、m a r k o v 決策規(guī)劃、m a r k o v 動態(tài)規(guī)劃和 受控m a r k o v 過程等，是研究類隨機序貫決策問題的理淪，即在系列相繼的或連續(xù)的時刻( 稱 6 中國科學(xué)技術(shù)大學(xué)碩士論文 之為決策時刻) 點做出決策，在各個決策時刻點，決策者根據(jù)觀察到的狀態(tài)從可用的若干個 決策中選擇一個；將決策付諸實施后，系統(tǒng)將獲得與所處狀態(tài)和所采取決策有關(guān)的一項報酬 ( 或費用等) 并影響系統(tǒng)在下一決策時刻點所處的狀態(tài)。系統(tǒng)在下一決策時刻點處的狀態(tài)是 隨機的。在這一新的決策時刻點上，決策者要觀察系統(tǒng)所處的新的狀態(tài)( 即收集新的信息) 并采取新的決策，如此一步一步進行卜去。在每一決策時刻采取的決策不僅影響當(dāng)前決策 周期的運行和性能( 狀態(tài)的逗留時間，獲得的報酬或代價等) ，而且會直接或問接影響下決策 時刻系統(tǒng)的運行和性能，并以此影響將來。決策的目的是選擇一種控制決策方案，使系統(tǒng) 的運行在某種意義下( 稱為性能準(zhǔn)則) 達到最優(yōu)，例如在期望平均報酬( 或期望平均代價) 準(zhǔn)則 下，使系統(tǒng)的期望平均總報酬( 或期望平均代價) 最大( 或最小) 。這樣，在每一個決策時刻所 選擇的控制決策，不但要使當(dāng)前決策周期獲得的報酬( 代價) 盡可能大( 小) ，而且要使系統(tǒng) 在將來的后續(xù)周期所獲得的報酬( 代價) 盡可能大( 小) 。這需要決策者從全局的觀點做出權(quán) 衡，因而這也是m c p 優(yōu)化控制問題的難點所在m c p 實際上是隨機型離散事件動態(tài)系統(tǒng)的 唯一的動態(tài)控制方法，與離散事件動態(tài)系統(tǒng)的邏輯控制方法也有著密切的關(guān)系。其基本模 型有離散時間m a r k o v 控制過程( d t m c p ) 和連續(xù)時間m a r k o v 控制過程( c t m c p ) 。從性能 上來說，m c p 又可分為折扣準(zhǔn)則m c p 和平均代價m c p 等。 圖1 2d e d s 與其它學(xué)科的關(guān)系 m c p 的優(yōu)化方法通常有數(shù)值計算求解、直接搜索法、線性規(guī)劃方法( l p ) ，梯度方法、以 及策略迭代( p i ) 和數(shù)值迭代( v i ) 方法等。目前后三種方法是主要的優(yōu)化手段。對于m c p 的 優(yōu)化目前國際上已經(jīng)有諸多理論和應(yīng)用成果問世 3 1 3 5 】，國內(nèi)在其優(yōu)化理論和應(yīng)用方面的 研究，也有了諸多成果 3 6 4 0 1 。對有限行動集或可數(shù)行動集、緊致行動集，折扣準(zhǔn)則下以 及平均性能準(zhǔn)則下的優(yōu)化問題都有了很多研究成果。本文在m c p 基于性能勢的最優(yōu)性原 理和最優(yōu)性方程的基礎(chǔ)上考慮一些優(yōu)化算法，如策略迭代算法以及數(shù)值迭代算法。 在實際的優(yōu)化問題中，系統(tǒng)模型可以是已知的，也可以是未知或者不完全知道的。在 系統(tǒng)模型已知時，可以根據(jù)模型參數(shù)直接進行優(yōu)化計算。然而在狀態(tài)空間很大的優(yōu)化計算 問題中，存在兩個問題。一是直接的優(yōu)化計算量常常相當(dāng)大，尤其是矩陣求逆運算等，需 要耗費大量的運算時間；二是在一定的策略下一部分狀態(tài)出現(xiàn)的概率很小或者幾乎不出現(xiàn)， 7 中國科學(xué)技術(shù)大學(xué)碩士論文 對優(yōu)化問題的貢獻很小，從而耗費了不必要的計算時間。為了降低優(yōu)化問題的成本，我們 可以考慮基于仿真的算法，通過仿真隨機產(chǎn)生出具有代表性的狀態(tài)，然后對這些狀態(tài)進行 計算，這樣避免了每次都要對那些很少出現(xiàn)的狀態(tài)進行計算，因而節(jié)省了計算時間。另外 由于性能勢的一個特點就是可以在一條單樣本軌道上得到其無偏估計值，并用于進一步的 優(yōu)化，因此在基于性能勢的優(yōu)化問題中也要考慮基于仿真的優(yōu)化方法。 在系統(tǒng)模型未知或者不完全知道時，也必須求助于仿真的方法。首先需要對系統(tǒng)的模 型參數(shù)進行估計和改進以期得到和符合實際系統(tǒng)的優(yōu)化結(jié)果，而在基性能勢的優(yōu)化算法中， 不僅要對系統(tǒng)的模型參數(shù)進行估計，還要對性能勢進行估計。 二十世紀(jì)九十年代，曹希仁( x r c a o ) 教授和陳翰馥教授提出了一個新的理論：m a r k o v 性能勢理論 2 7 1 ，并揭示了m a r k o v 性能勢、無窮小攝動分析( i p a ) 與m a r k o v 決策過程三者 之間的聯(lián)系【4 l l 】。這一成果被廣泛應(yīng)用到一般m a r k o v 系統(tǒng)和排隊網(wǎng)絡(luò)的靈敏度分析中， 并取得了顯著成果 2 7 2 8 4 1 4 8 ；另一方面，曹希仁( x r c a o ) 運用m a r k o v 性能勢理論，給 出了m c p 在有限行動集下基于性能勢的優(yōu)化理論和算法 4 l ，4 2 】。在此基礎(chǔ)上，我們進一 步建立了m a r k o v 控制過程和受控排隊網(wǎng)絡(luò)在緊致行動集上基于性能勢的優(yōu)化理論和算法 4 9 5 3 】 事實上，性能勢理論為m c p 的優(yōu)化提供了一個統(tǒng)一的基本的理論框架。運用性能勢 理論，從p o i s s o n 方程著手，在較少的假設(shè)條件下，很容易建立起m c p 基于性能勢的最優(yōu) 性原理和最優(yōu)性方程，并且容易證明其最優(yōu)解的存在性定理。在此基礎(chǔ)上可給出一些收斂 的優(yōu)化算法，如基于計算的梯度類算法和策略迭代以及數(shù)值迭代算法 4 0 ，4 9 5 4 l 。但是這 種基于理論計算的優(yōu)化方法，依賴于系統(tǒng)的精確模型，往往需要系統(tǒng)的轉(zhuǎn)移矩陣或無窮小 矩陣的完全信息及有關(guān)矩陣的求逆運算( 如由p o i s s o n 方程求解性能勢) 。對于一個實際系 統(tǒng)，其模型可能未知或不全知，那種需要轉(zhuǎn)移矩陣或無窮小矩陣的理論算法己經(jīng)不再適用； 另一方面，對那些存在“維數(shù)災(zāi)難”問題的大規(guī)模實際系統(tǒng)，即使模型己知，由于其狀態(tài) 空間很大，在進行優(yōu)化計算時，有關(guān)矩陣求逆運算也需要大量計算機內(nèi)存，占用相當(dāng)長的 計算時間，往往導(dǎo)致計算機負(fù)擔(dān)過重而不可行。而性能勢的一個重要特點是可以通過仿真 或觀測一個實際系統(tǒng)的運行，得到單個樣本軌道來進行無偏估計 2 8 】，在此基礎(chǔ)上可以發(fā) 展基于單條樣本軌道的仿真優(yōu)化算法和有關(guān)在線優(yōu)化算法。這種算法將適用于大規(guī)模實際 系統(tǒng)在模型已知或未知情況下的優(yōu)化求解。 從實際應(yīng)用的角度出發(fā)，需要對基于單樣本軌道的優(yōu)化算法效率做進一步的優(yōu)化?？?察性能勢的仿真算法，可以發(fā)現(xiàn)其具有很好的并行性，而且基于性能勢的策略迭代算法和 數(shù)值迭代算法都易于進行并行處理。這樣在理論計算優(yōu)化方法和仿真優(yōu)化方法的基礎(chǔ)上可 以進一步發(fā)展一種新的高效并行理論算法和并行仿真算法 5 5 5 7 】，因而能大大節(jié)省計算時 間，從而為大規(guī)模實際系統(tǒng)的優(yōu)化提供一條途徑這也是本文的主要內(nèi)容之一。 性能勢的這些性質(zhì)為實際m a r k o v 系統(tǒng)的性能分析和優(yōu)化提供了一個強有力的工具， 它在實際系統(tǒng)中的應(yīng)用突出體現(xiàn)在排隊網(wǎng)絡(luò)中。實際系統(tǒng)中的許多排隊網(wǎng)絡(luò)都可以用 m a r k o v 控制過程來描述，我們稱這樣的排隊網(wǎng)絡(luò)為m a r k o v 型排隊網(wǎng)絡(luò)。本文也把有關(guān)排 隊網(wǎng)絡(luò)的研究作為重要內(nèi)容。 目前，離散事件動態(tài)系統(tǒng)在隨機統(tǒng)計層次下是主要以m a r k o v 過程為研究模型的，該 類模型的性能靈敏度分析以及性能優(yōu)化問題已經(jīng)有了很多成果。但是由于半m a r k o v 過程 的逗留時間服從一般分布，因而半m a r k o v 過程是比m a r k o v 過程更為廣泛的一類系統(tǒng)，更 接近實際系統(tǒng)。所以半m a r k o v 控制過程的相關(guān)問題逐漸成為近年來d e d s 領(lǐng)域的一個研 究熱點問題。半m a r k o v 控制過程( s m c p ) 是一類受到一系列控制決策驅(qū)動的半m a r k o v 系 統(tǒng)，其狀態(tài)轉(zhuǎn)移規(guī)律和控制決策所采用的行動方案相互作用決定了系統(tǒng)的演化，過程在每 個狀態(tài)的逗留時間服從一般分布。并且該分布不僅與當(dāng)前狀態(tài)有關(guān)，而且與將要轉(zhuǎn)移到的 8 中國科學(xué)技術(shù)大學(xué)碩士論文 下一個狀態(tài)有關(guān)。很明顯，如果該分布是指數(shù)分布，則就是m a r k o v 控制過程，那么，我 們可以看出，半m a r k o v 控制過程是一類比m a r k o v 控制過程更廣泛的一類系統(tǒng)。 本文將重點研究半m a r k o v 控制過程的相關(guān)理論，并給出一些實際例子 1 3 仿真及并行計算 計算機仿真方法己經(jīng)成為分析復(fù)雜系統(tǒng)的重要手段，這一方法能夠為各種類型的實際 問題提供數(shù)值解。利用仿真手段可以代替某些費用昂貴的試驗，并且能夠更快地積累數(shù)據(jù)， 以便選擇合適的假設(shè)及檢驗預(yù)測的結(jié)論，并檢驗有關(guān)理論中假設(shè)的合理性。在實際仿真中 運算速度常常是考慮的重點之一，因此除了理論本身的改進之外需要采取并行計算的方法 減少運算時間滿足實際仿真的需求。 1 3 1 仿真 上面已經(jīng)說明基于性能勢來解決m a r k o v 控制系統(tǒng)優(yōu)化問題可以通過理論方法，計算 出性能勢的理論值進行優(yōu)化，但這種方法涉及到矩陣求逆等運算，對于大規(guī)模系統(tǒng)則力不 從心。而基于性能勢的優(yōu)化方法的一個重要優(yōu)點就是可以通過觀測或仿真系統(tǒng)的一條單樣 本軌道得到性能勢的無偏估計，因而適用于大規(guī)模實際系統(tǒng)。不同于傳統(tǒng)的基于直接計算 的優(yōu)化方法，在這種基于仿真的優(yōu)化方法中，穩(wěn)態(tài)概率和性能勢都是根據(jù)系統(tǒng)的一條樣本 軌道信息來估計計算的 2 8 ，5 8 】。 所謂系統(tǒng)仿真是以系統(tǒng)理論、形式化理論、隨機過程與統(tǒng)計學(xué)理論和優(yōu)化理論為基礎(chǔ)， 以計算機和仿真系統(tǒng)軟件為工具，對現(xiàn)實系統(tǒng)或未來系統(tǒng)進行動態(tài)實驗研究的理論和方法 5 9 - 6 l 】 從系統(tǒng)仿真的實施過程來看，系統(tǒng)仿真是通過對所研究系統(tǒng)的認(rèn)識和了解，抽取其中 的基本要素的關(guān)鍵參數(shù)，建立與現(xiàn)實系統(tǒng)相對應(yīng)的仿真模型，經(jīng)過模型的確認(rèn)和仿真程序 的驗證，在仿真實驗設(shè)計的基礎(chǔ)上，對該模型進行仿真實驗，以模仿系統(tǒng)的運行過程，觀 察系統(tǒng)狀態(tài)變量隨時問變化的動態(tài)規(guī)律性，并通過數(shù)據(jù)采集和統(tǒng)計分析，得到被仿真系統(tǒng) 參數(shù)的統(tǒng)計特性，據(jù)此推斷和估計系統(tǒng)的真實參數(shù)和性能測度，為輔助決策提供依據(jù) 系統(tǒng)仿真的一般步驟如圖1 3 所示【6 l 】 1 3 2 并行計算及其在仿真中的應(yīng)用 由于并行計算在本文中有重要應(yīng)用，因此我們介紹有關(guān)概念并根據(jù)相關(guān)研究的特點選 擇合適的硬件和軟件。 9 中國科學(xué)技術(shù)大學(xué)碩士論文 1 3 2 1 并行計算的背景 簡單的講，并行計算( p a r a l l e lc o m p u t i n g ) 就是在并行計算機上所做的計算 6 2 6 4 】，它和 常說的高性能計算( h i g hp e r f o r m a n c ec o m p u t i n g ) 、超級計算( s u p e r c o m p u t i n g ) 是同義詞，因 為任何高性能計算和超級計算總是離不開使用并行技術(shù)。隨著計算機和計算方法的飛速發(fā) 展，幾乎所有的學(xué)科都走向定量化和精確化，從而產(chǎn)生了一系列諸如計算物理、計算化學(xué)、 計算生物學(xué)、計算地質(zhì)學(xué)、訓(xùn)算氣象學(xué)冪n i - t 4 算材料科學(xué)等的計算科學(xué)，在世界上逐漸形成 了一門計算性的學(xué)科分支，即計算科學(xué)與工程，簡稱為c s e ( c o m p u t a t i o n a ls c i e n c e & e n g i n e e r i n g ) 。在許多情況下，或者是理論模型復(fù)雜甚至理論尚未建立，或者試驗費用昂 貴甚至試驗無法進行，此時計算就成為求解問題的唯一或主要手段計算極大地增強了人們 從事科學(xué)研究的能力，大大地加速了把科技轉(zhuǎn)化為生產(chǎn)力地過程，深刻地改變著人類認(rèn)識 世界和改造世界的方法和途徑。計算科學(xué)的理論和方法，作為新的研究手段和新的設(shè)計與 制造技術(shù)的理論基礎(chǔ)，正在推動著當(dāng)代科學(xué)與技術(shù)向縱深發(fā)展。 l o 中國科學(xué)技術(shù)大學(xué)碩士論文 圖1 3 系統(tǒng)仿真的步驟 科學(xué)和工程計算中的重大挑戰(zhàn)性課題，要求能提供lt f l o p s 計算能力、i t b 主存容量 和1t b s 的i o 帶寬，這就是所謂的3 t 性能目標(biāo)。而在h p c c 計劃提出的當(dāng)時，性能最 好的計算機與3 t 指標(biāo)相比，速度太慢，而存儲容量太小，帶寬太窄。面對這些要求，只 有采用并行計算的技術(shù)，才能夠在要求的時間內(nèi)解決相同的問題，或在相同的時間內(nèi)解決 更多更復(fù)雜的問題，以較低的投入完成串行計算的任務(wù)。另外對于今后越來越高的計算速 度要求，不能依賴物理設(shè)備的進化，光速是不可逾越的速度極限，設(shè)備和材料也不可能做 得無限小，處理器本身的速度不能夠無限提高，只有通過并行才能夠不斷提高速度，滿足 越來越高的性能要求。 由于并行計算是本文工作的重點，因此下面詳細(xì)介紹一下有關(guān)的概念。 中國科學(xué)技術(shù)大學(xué)碩士論文 1 3 2 2 并行計算機的分類 為了利用計算機實現(xiàn)相關(guān)算法，使所用的高級語言能夠被有效的編譯并且能夠用硬件 來實現(xiàn)，必須有一種計算模型作為硬件和軟件之間的橋梁以充分設(shè)計分析算法。在串行計 算時，馮諾依曼機就是一個理想的串行計算模型，在此模型上硬件設(shè)計者可以設(shè)計多種 多樣的馮諾依曼機而無需慮及將要在其上執(zhí)行的軟件：而軟件工程師能夠編寫各種可在此 模型上有效執(zhí)行的程序而不需考慮所使用的硬件。但在并行計算時尚未有一個類似于馮， 諾依曼機地真正通用的并行計算模型因此對于不同的并行結(jié)算機硬件結(jié)構(gòu)，在其上的軟件 編制工作都有相當(dāng)大的不同。在我們的并行訓(xùn)。算工作中也必須根據(jù)所采用的并行計算機硬 件結(jié)構(gòu)特點，分析如何發(fā)展盡量通用和高效的算法，這也是本文工作的重點之一。 在考慮并行算法之前首先需要熟悉并行計算機的各種分類及其特點 6 2 ， 6 4 。根據(jù)一個并 行計算機能夠同時執(zhí)行的指令與處理的數(shù)據(jù)的多少，可以把并行計算機分為s i m i ) ( s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ，單指令多數(shù)據(jù)并行計算機) 和m i m d ( m u l t i p l e i n s t r u c t i o n m u l t i p l e d a t a ，多指令多數(shù)據(jù)并行計算機) 兩種 按同時執(zhí)行的程序和數(shù)據(jù)的不同，人們又提出了s p m d ( s i n g l e p r o g r a m m u l t i p l e d a t a ， 單程序多數(shù)據(jù)并行計算機) 和m p m d ( m u l t i p l e p r o g r a m m u l t i p l e d a t a ，多程序多數(shù)據(jù)并行計 算機) 的概念。這種劃分方式所依據(jù)的執(zhí)行單位不是指令而是程序，顯然其劃分粒度( 劃分 對象的大小程度) 要大得多。 根據(jù)并行計算機結(jié)構(gòu)模型的不同，一般可以分為六類：單指令多數(shù)據(jù)流機s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ) 并行向量處理機p v p ( p a r a l l e lv e c t o r p r o c e s s o r ) 、對稱多 處理機s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 、大規(guī)模并行處理機m p p ( m a s s i v e l yp a r a l l e l p r o c e s s o r ) ，i 作站機群c o w ( c l u s t e ro fw o r k s t a t i o n ) 和分布式共享存儲d s m ( d i s t r i b u t e d s h a r e dm e m o r y ) 多處理機。 從物理劃分上，共享內(nèi)存和分布式內(nèi)存是兩種基本的并行計算機存儲方式。除此之外， 分布式共享內(nèi)存也成為一種越來越重要的并行汁算機存儲方式。具體可分為下面幾類：均勻 存儲訪問u m a ( u n i f o r mm e m o r ya c c e s s ) ，非均勻存儲訪問n u m a ( n o n u n i f o r mm e m o r y a c c e s s ) 、全高速緩存存儲訪問c o m a ( c a c h e o n l ym e m o r ya c c e s s ) 、高速緩存一致性非均 勻存儲訪問c c n u m a ( c o h e r e n t c a c h en o n u n i f c l l 1 1 1m e m o r ya c c e s s ) 和非遠程存儲訪問 n o r m a ( n o r e m o t em e m o r ya c c e s s ) 對于共享內(nèi)存的并行計算機，各個處理單元通過對共享內(nèi)存的訪問來交換信息，協(xié)調(diào) 各處理器對并行任務(wù)的處理。這種共享內(nèi)存的編程實現(xiàn)起來相對簡單，但共享內(nèi)存往往成 為性能特別是擴展性的重要瓶頸 對于分布式內(nèi)存的并行計算機，各個處理單元都擁有自己獨立的局部存儲器。由于不 存在公共可用的存儲單元，因此各個處理器之間通過消息傳遞來交換信息，以協(xié)調(diào)和控制 各個處理器的執(zhí)行。這也是本文采用的消息傳遞并行編程模型所面對的并行計算機的存儲 方式不難看出，通信對分布式內(nèi)存并行計算機的性能有重要的影響，復(fù)雜的消息傳遞語句 的編寫成為在這種并行計算機上進行并行程序設(shè)計的難點所在，但是，對于這種類型的并 行計算機，出于它有很好的擴展性和很高的性能，因此它的應(yīng)用非常廣泛。 本文的并行工作的硬件基礎(chǔ)是國家高性能中心( 合肥) 曙光2 0 0 0 并行計算機 6 5 6 6 曙光 2 0 0 0 基于分布式存儲機群系統(tǒng)和消息傳遞體系結(jié)構(gòu)，是通用的可擴展超級服務(wù)器系統(tǒng)。系 統(tǒng)的節(jié)點數(shù)目可以從4 個擴展到1 2 8 個，節(jié)點c p u 采用m o t o r o l a 公司的p o w e rp c 6 0 4 e 微 處理器，節(jié)點之間通過1 0 1 0 0 m b p s 高速以太網(wǎng)和1 0 0 m b s 的“蛀洞”( w o r m h o l e ) 路由芯片 組成的二維網(wǎng)絡(luò)互連。在3 2 個計算節(jié)點( 單c p u ) 缺省配置下，整機峰值速度達到 1 2 中國科學(xué)技術(shù)大學(xué)碩士論文 2 0 0 g f l o p s ( 耳p 每秒2 0 0 億次浮點運算) ，內(nèi)存總?cè)萘窟_到8 g b ，磁盤總?cè)萘窟_到1 4 4 g b 曙光2 0 0 0 的節(jié)點運行完整的i b ma i x 操作系統(tǒng)，可以運行上千種a i x 應(yīng)用程序和數(shù)據(jù)庫、 網(wǎng)絡(luò)服務(wù)器等商用軟件，支持c ，f o r t r a n j a v a 等程序設(shè)計語言，支持e s s l ，b l a s ，s c a l a p a c k 等高效數(shù)學(xué)和工程庫。系統(tǒng)軟件提供b c l ( b a s i cc o m m u n i c a t i o n l i b r a r y ) 底層通訊機制、定 制的p v m 和m p i 并行程序設(shè)計環(huán)境、集成化并行程序設(shè)計環(huán)境、并行調(diào)試器、基于w e b 的友好界面、自動并行化工具、c o s m o s 可擴展文件系統(tǒng)、對高可用性的支持、作業(yè)管理、 資源管理、系統(tǒng)管理、a u t o p a r 自動并行化工具、服務(wù)器聚集軟件，以及d s m ，h p f , p a r a v t 等其它工具。廣泛采用j m ，a 和面向?qū)ο蠓椒?，在設(shè)計上注重可用性要求。 1 3 2 3 并行算法模型及并行語言的選擇 一個物理問題并行求解的最終目的是將該問題映射到并行機上通過不同層次上的抽象 映射來實現(xiàn)的。如圖1 4 所示。 圖1 4 問題的并行求解過程 忽略并行機的非本質(zhì)的細(xì)節(jié)特征，可以得到該并行機的并行計算模型。在這一模型上， 可以設(shè)計各種適合該模型的并行算法，這些算法精確描述了該并行模型能夠?qū)崿F(xiàn)的功能， 而這些算法是通過用特定的并行語言設(shè)計并行程序后得以實現(xiàn)。對于現(xiàn)實世界的物理問題， 為了能夠高效地并行求解，必須建立它的并行求解模型，一個串行的求解模型是很難在并 行機上取得滿意的并行效果的。有了并行求解模型，就可以針對該模型設(shè)計高效的并行算 法，對該問題的求解進行精確描述和定量分析，對各種算法進行性能上的比較，最后通過 并行程序設(shè)計，實現(xiàn)問題和并行機的結(jié)合。 并行程序設(shè)計需要將問題的并行求解算法轉(zhuǎn)化為特定的適合并行計算模型的并行算 法。為了達到這一目的，首先是問題的并行求解算法必須能夠?qū)栴}內(nèi)在的并行特征充分 體現(xiàn)出來，否則并行求解算法將無法利用這些并行特征，從而使問題的高效并行求解成為 1 3 中國科學(xué)技術(shù)大學(xué)碩士論文 不可能：其次是并行求解模型要和并行計算模型盡量吻合，這樣，就為問題在并行機上的高 效解決提供了前提。 目前兩種最重要的并行編程模型是數(shù)據(jù)并行和消息傳遞【6 4 】。數(shù)據(jù)并行編程模型的編 程級別比較高、編程相對簡單，但它僅適用于數(shù)據(jù)并行問題；消息傳遞編程模型的編程級別 相對較低，但消息傳遞編程模型可以有更廣泛的應(yīng)用范圍。數(shù)據(jù)并行即將相同的操作同時 作用于不同的數(shù)據(jù)，因此適合在s i m d 及s p m d 并行計算機上運行。在向量機上通過數(shù)據(jù) 并行求解問題的實踐也說明，數(shù)據(jù)并行可以高效地解決一大類科學(xué)與工程計算問題。 消息傳遞即各個并行執(zhí)行的部分之間通過傳遞消息來交換信息、協(xié)調(diào)步伐、控制執(zhí)行， 消息傳遞一般是面向分布式內(nèi)存的，但是它也可適用于共享內(nèi)存的并行饑c 消息傳遞為編 程者提供靈活的控制手段和表達并行的方法，一些用數(shù)據(jù)并行方法很難表達的并行算法， 都可以使用消息傳遞模型來實現(xiàn)。靈活性和控制手段的多樣化，是消息傳遞并行程序能提 供高的執(zhí)行效率的重要原因。 消息傳遞模型一方面為編程者提供了靈活性，另一方面，它也將各個并行執(zhí)行部分之 間復(fù)雜的信息變換和協(xié)調(diào)、控制的任務(wù)交給了編程者，在一定程度上增加了編程者的負(fù)擔(dān)， 這也是消息傳遞編程模型編程級別低的主要原因：雖然如此，消息傳遞的基本通信模式是簡 略和清楚的，學(xué)習(xí)和掌握這些部分并不困難，因此目前大量的并行程序設(shè)計仍然是消息傳 遞并行編程模式。本文的并行工作考慮到為了盡可能擴大程序的適用面，因此采用消息傳 遞模型。 本文考慮到并行語言的使用廣泛性和并行程序設(shè)計的通用性，另外由于c 語言在工程 和科學(xué)計算中的廣泛應(yīng)用，因此選擇m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 并行標(biāo)準(zhǔn)的c 語言版 本實現(xiàn)并行算法6 4 】 m p i 是一個庫，而不是一門語言?？梢园裞 + m p i 看作是一種在原來串行語言( c 語言) 基礎(chǔ)之上擴展后得到的并行語言。m p i 庫可以被c c + + 調(diào)用，從語法上說，它遵守所有對 庫函數(shù)過程的調(diào)用規(guī)則，與一般的函數(shù)過程沒有什么區(qū)別。m p i 是種標(biāo)準(zhǔn)或規(guī)范的代表， 而不特指某一個對它的具體實現(xiàn)。迄今為止，所有的并行計算機制造商都提供對m p i 的支 持，可以在網(wǎng)上免費得到m p i 在不同并行計算機上的實現(xiàn)，一個正確的m p i 程序，可以 不加修改地在所有的并行機上運行。m p i 是一種消息傳遞編程模型，并成為這種編程模型 的代表和事實上的標(biāo)準(zhǔn)m p i 雖然很龐大，但是它的最終日的是服務(wù)于進程問通信這一目標(biāo) 的。在m p i 上很容易移植其他的并行代碼，而且編程者不需要去努力掌握許多其他的全新 概念，就可以學(xué)習(xí)編寫m p i 程序。正是由于m p i 的這些特點，促使本文的并行算法都采 用m p i 來實現(xiàn)。 1 4 文章結(jié)構(gòu)安排 本文主要研究具有數(shù)狀態(tài)空間的半m a r k o v 控制過程在無窮水平平均代價準(zhǔn)則下的性 能靈敏度分析和優(yōu)化問題。給出了以等價m a r k o v 過程和嵌入m a r k o v 鏈的性能勢表示的靈 敏度公式，建立了優(yōu)化理論，給出了最優(yōu)性方程并證明了解的存在性定理：研究了優(yōu)化算法， 給出了基于單個樣本軌道的仿真優(yōu)化算法及其并行算法。并給出了大量的數(shù)值例子，來說 明相應(yīng)算法的應(yīng)用。文章的結(jié)構(gòu)安排如下： 第二章中建立了半m a r k o v 過程的性能勢理論，并在性能勢的基礎(chǔ)上討論了穩(wěn)態(tài)性能 勢靈敏度分析問題。首先利用等價無窮小矩陣，定義了半m a r k o v 過程的p o i s s o n 方程，將 該p o i s s o n 方程的解定義為半m a r k o v 過程的性能勢：然后利用等價m a r k o v 過程和嵌入 m a r k o v 鏈的方法，討論了半m a r k o v 過程的性能靈敏度分析問題，導(dǎo)出了基于等價m a r k o v 1 4 中國科學(xué)技術(shù)大學(xué)碩士論文 過程和嵌入m a r k o v 鏈的性能勢的靈敏度公式。并對其進行了串行和并行的仿真。 第三章討論了一類可數(shù)狀態(tài)空間的半m a r k o v 控制過程的性能優(yōu)化問題，研究半 m a r k o v 控制過程基于直接計算的理論優(yōu)化方法，討論了半m a r k o v 控制過程基于樣本軌道 仿真的優(yōu)化方法。 第四章，我們給出了通訊中兩個實際網(wǎng)絡(luò)的優(yōu)化與導(dǎo)數(shù)估計的應(yīng)用實例一是m a r k o v 決 策過程方法在呼叫接入控制中的應(yīng)用；二是m p h 1 排隊系統(tǒng)的性能靈敏度估計與仿真及其 在a t m 交換機性能分析中的應(yīng)用。 最后對本文工作做了一個總結(jié)，指出了進一步的研究方向。 事實上，許多實際人造系統(tǒng)，例如柔性制造系統(tǒng)中自動車的移動策略，物流系統(tǒng)中的 最小代價路徑問題，大規(guī)模計算機和通信網(wǎng)絡(luò)中的多媒體信流的接收和發(fā)送，系統(tǒng)的最優(yōu) 維護代價和安全可靠性等問題，最終均可歸結(jié)為一個半m a r k o v 控制過程問題。本論文的 研究能夠為大量實際復(fù)雜人造系統(tǒng)的性能優(yōu)化提供一個直接的、行之有效的方法，這對進 一步改進系統(tǒng)的設(shè)計，提高系統(tǒng)的運行效率和管理水平具有極其重要的意義。 中國科學(xué)技術(shù)大學(xué)碩士論文 第二章半m a r k o v 性能勢及其仿真 2 1 半m a r k o v 性能勢理論 在實際系統(tǒng)中，我們還常常會遇到非m a r k o v 型排隊網(wǎng)絡(luò)的情況，與m a r k o v 過程相比， 半m a r k o v 過程或廣義半m a r k o v 過程具有更廣泛的應(yīng)用范圍。 2 1 1 半m a r k o v 過程 定義1 若狀態(tài)空間= 1 , 2 ，k ) 上的隨機過程n = n ，；f 0 ) 滿足下列條件： ( 1 ) 對任意的f ，j ，若已知過程處于狀態(tài)f ，則它下一次轉(zhuǎn)移到狀態(tài)的概率是p 口， 并設(shè)p 。= 0 ( 2 ) 若已知過程處于狀態(tài)f 和下一次將轉(zhuǎn)移到狀態(tài)j ，則它在狀態(tài)f 的逗留時間的分布為 弓。 則稱n = n ，；f 0 ) 為一個半m a r k o v 過程( s m p ) 。 定義2 設(shè)n = n ，；f 0 ) 為狀態(tài)空間= 1 , 2 ，k ) 上的隨機過程， 0 = r l f 2 是該過程發(fā)生狀態(tài)轉(zhuǎn)移的時刻，則x 。= m 。+ o 是過程在時刻f 。發(fā)生的第刀 次轉(zhuǎn)移后所處的狀態(tài)。若對任意的整數(shù)，2 0 ，任意的i o ，i ，f ，j 和任意的實數(shù)f 0 ， 均有 = 工一乙4 五= 攻，后= a 1 1 ；門一1 ，k = 蠢，；乙) = p ( x 州= j , t 川一f 。刮以= f ) = 鱗( f ) ( 2 1 ) 則稱隨機過