孫丹丹

摘要：針對(duì)計(jì)算機(jī)系統(tǒng)在網(wǎng)絡(luò)應(yīng)用中存在主要問題，該文給出了基于動(dòng)態(tài)優(yōu)化的設(shè)計(jì)方案，通過對(duì)動(dòng)態(tài)優(yōu)化數(shù)學(xué)模型的建立與求解，實(shí)現(xiàn)了動(dòng)態(tài)優(yōu)化在計(jì)算機(jī)系統(tǒng)及其網(wǎng)絡(luò)中的應(yīng)用。對(duì)比靜態(tài)優(yōu)化理論，對(duì)動(dòng)態(tài)優(yōu)化中應(yīng)用馬爾可夫決策過程進(jìn)行了詳細(xì)的討論與分析。依據(jù)馬爾可夫決策過程深入的研究討論了計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)中的建模、求解方法和應(yīng)用實(shí)例。

關(guān)鍵詞：計(jì)算機(jī)系統(tǒng)；動(dòng)態(tài)優(yōu)化；模型解析

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）35-0038-02

近年來，計(jì)算機(jī)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)對(duì)居民生活所產(chǎn)生的影響越來越大，在各個(gè)領(lǐng)域的應(yīng)用也越來越多，不僅在高端科研實(shí)驗(yàn)中大量應(yīng)用，而且深入到了人們的日常生活中。在這樣的復(fù)雜背景下，想要提高計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)的運(yùn)行效率，就不得不面對(duì)系統(tǒng)資源如何分配、系統(tǒng)數(shù)據(jù)如何調(diào)動(dòng)等問題，而且為了公眾效益，降低成本也是十分關(guān)鍵的問題。

優(yōu)化理論是研究計(jì)算機(jī)網(wǎng)絡(luò)以及計(jì)算機(jī)系統(tǒng)的一種常見的方法之一，主要用于處理資源分配還有任務(wù)調(diào)度等問題。優(yōu)化理論可以根據(jù)時(shí)間維度分為靜態(tài)優(yōu)化和動(dòng)態(tài)優(yōu)化兩種方式。兩種優(yōu)化方式中的靜態(tài)優(yōu)化系統(tǒng)是不隨時(shí)間的變化而改變，也就是說計(jì)算機(jī)系統(tǒng)中資源的需求量和保有量是不隨時(shí)間變化而變化的常量。然而，在實(shí)際應(yīng)用的過程中，計(jì)算機(jī)系統(tǒng)并不是一成不變的，它不僅可能受到時(shí)間變化的影響，而且往往會(huì)被外界環(huán)境所干擾，這就導(dǎo)致在未來可能發(fā)生的變化被靜態(tài)優(yōu)化系統(tǒng)所忽略，從而不能反映出因?yàn)闆Q策者的行為，然后對(duì)未來可能產(chǎn)生的影響，體現(xiàn)不出系統(tǒng)受時(shí)間影響的特性。綜上，本文將以動(dòng)態(tài)優(yōu)化的處理方法去處理計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)的應(yīng)用問題。進(jìn)行動(dòng)態(tài)優(yōu)化時(shí)，關(guān)于時(shí)間累積量的系統(tǒng)收益是系統(tǒng)的目標(biāo)函數(shù)，對(duì)比與靜態(tài)優(yōu)化，動(dòng)態(tài)優(yōu)化可以更好地體現(xiàn)出系統(tǒng)的時(shí)變性，亦能反映出隨時(shí)間累積，決策者的決策對(duì)目標(biāo)函數(shù)的影響。

馬爾可夫決策過程（MDP）是動(dòng)態(tài)優(yōu)化的基本理論模型。具體定義為：根據(jù)決策者的行為，并依賴時(shí)間t的系統(tǒng)狀態(tài)，可以推斷出系統(tǒng)在t+1時(shí)刻時(shí)的狀態(tài)轉(zhuǎn)移情況，且在[0，t+1]的時(shí)間段中，決策者的行為對(duì)系統(tǒng)狀態(tài)不產(chǎn)生影響。對(duì)于當(dāng)前計(jì)算機(jī)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)中，動(dòng)態(tài)優(yōu)化模型一直是解決資源分配、資源整理和任務(wù)調(diào)度等問題的一個(gè)熱點(diǎn)。本文利用馬爾可夫決策過程，從建立模型、找出解答方法及提出應(yīng)用等角度，論述了動(dòng)態(tài)優(yōu)化理論的實(shí)際應(yīng)用。

1 動(dòng)態(tài)優(yōu)化理論模型構(gòu)建

1.1 馬爾可夫決策過程

馬爾可夫決策過程包含的要素有：

1） 用來描述系統(tǒng)狀態(tài)的狀態(tài)集合S；

2） 在狀態(tài)空間中決策者可能發(fā)生的行為，也就是依賴于當(dāng)前狀態(tài)下決策者的行為集合，用A（s）來表示；

3） 收益函數(shù)是指決策者發(fā)出行為，并且該行為對(duì)系統(tǒng)產(chǎn)生了影響，因此而產(chǎn)生效益；

4） 當(dāng)下一時(shí)刻計(jì)算機(jī)系統(tǒng)的狀態(tài)僅受決策者行為和當(dāng)前狀態(tài)影響，即與系統(tǒng)的歷史狀態(tài)無關(guān)時(shí)，將這一特性稱為馬爾可夫決策過程的后效性，它是馬爾可夫決策過程的一個(gè)顯著特性。

1.2 馬爾可夫決策流程

馬爾可夫決策過程中決策者當(dāng)前所需的決策行為一般根據(jù)策略π來得到，策略π是一個(gè)從狀態(tài)集合S到行為集合A的映射。馬爾可夫決策過程一般都具有四個(gè)執(zhí)行流程，分別是：

1） 首先由決策者觀察所處狀態(tài)s（當(dāng)前狀態(tài)）；

2） 獲得已知狀態(tài)信息后，根據(jù)該信息發(fā)出決策行為π（s）；

3） 系統(tǒng)狀態(tài)可能會(huì)因?yàn)樾袥Q策行為π（s）的發(fā)出而發(fā)生轉(zhuǎn)換；

4） 重復(fù)流程1中的操作。

系統(tǒng)在執(zhí)行時(shí)，會(huì)由MDP生成一個(gè)收益序列，引入目標(biāo)函數(shù)J，目的是用來比較MDP中決策者發(fā)出的策略的優(yōu)劣程度，且收益序列將會(huì)被映射成一個(gè)實(shí)數(shù)值。

1.3 值函數(shù)

值函數(shù)是MDP中的非常重要概念之一，用表示。是一個(gè)映射，范圍是從π×S到R（實(shí)數(shù)集）。的含義為：已知策略π，狀態(tài)，求得目標(biāo)函數(shù)J的期望，且在無限時(shí)間內(nèi)，MDP滿足遞推方程，即：

（1）

式中，α—折扣因子，根據(jù)式（1）不難看出，策略是收益的和。式（1）也可寫為向量形式，即：

（2）

2 馬爾可夫過程數(shù)學(xué)解

1） 運(yùn)行目標(biāo)

首先，對(duì)于隨機(jī)MDP，目標(biāo)函數(shù)常帶有期望形式（E），一般帶有期望的目標(biāo)函數(shù)分為有限馬爾可夫決策流程和無限馬爾可夫決策流程，具體形式如下：

有限：

（3）

無限：

（4）

（5）

式中，—系統(tǒng)所處狀態(tài)，—決策者采取的行為。式（4）位無窮時(shí)間折扣情況下的目標(biāo)函數(shù)，式（5）為無窮時(shí)間平均情形下的目標(biāo)函數(shù)，通常情況下，最大（小）化上述目標(biāo)函數(shù)J，從而得到運(yùn)行目標(biāo)。

2） 狀態(tài)空間分析

系統(tǒng)的狀態(tài)空間和決策者的行為空間，滿足特定條件時(shí)，可能是有聯(lián)系的，在無線電系統(tǒng)中，如果用戶設(shè)為發(fā)射數(shù)據(jù)的概率為P，則用戶的行為空間就是連續(xù)的，行為空間的取值范圍是固定的，為[0，1]

3） 建立Bellman遞推方程

在（3）中，對(duì)于一個(gè)隨機(jī)的MDP，其轉(zhuǎn)移方程為，轉(zhuǎn)移頻率為。當(dāng)狀態(tài)轉(zhuǎn)移頻率，沒有辦法準(zhǔn)確得知時(shí)，實(shí)際操作中經(jīng)常使用“強(qiáng)化學(xué)習(xí)”法，去對(duì)問題進(jìn)行求解。用這種方法求最優(yōu)策略是非常高效且準(zhǔn)確的。

4） 以上步驟求解出最優(yōu)策略。

3 馬爾可夫求解

3.1 值迭代算法

值迭代算法是一個(gè)近似算法。為求解最優(yōu)解，常采用值迭代算法，隨著迭代過程進(jìn)行，值迭代算法求得的值，將逐漸逼近最優(yōu)解。算法如下：

算法1：值迭代算法

1） n=0，是初始值；endprint

2） 依據(jù)迭代式，求出值迭代算法過程中第n次時(shí)，值函數(shù)V和策略π；

3） 重復(fù)2。

不難證明，算法1在時(shí)，收斂于最優(yōu)值函數(shù)，另外還能估計(jì)出每一次迭代時(shí)的最優(yōu)解的區(qū)間：

當(dāng)此條件成立時(shí)，不再運(yùn)行算法算法。

3.2 策略迭代計(jì)算

使用策略迭代算法，為的是獲得最優(yōu)解，即，為集合內(nèi)所有元素的個(gè)數(shù)。策略迭代算法如算法2所示。

算法2：策略迭代算法

1） n=0，給定初始策略；

2） 求解；

3） 確定，且滿足

4） if，算法終止，設(shè)最優(yōu)策略為，else，轉(zhuǎn)步驟2。

算法2中，先確定一個(gè)初始策略，然后根據(jù)求解出值函數(shù)，且根據(jù)所求得的值函數(shù)，改變策略，對(duì)比策略，如果結(jié)果相等，那么這個(gè)就是最優(yōu)策略，不再進(jìn)行算法計(jì)算。

3.3 近似求解計(jì)算

前文中提到，在實(shí)際計(jì)算機(jī)系統(tǒng)中資源種類和數(shù)量都非常龐大，使得建立的MDP模型不能利用精確算法去求解，原因包含兩點(diǎn)：①在算法處理中，每個(gè)狀態(tài)下的值函數(shù)都需要存儲(chǔ)，根據(jù)現(xiàn)有的技術(shù)，當(dāng)狀態(tài)數(shù)較多時(shí)，無法提供足夠的空間去存儲(chǔ)這些子函數(shù)；②進(jìn)行迭代過程時(shí)，所有的狀態(tài)都要帶人計(jì)算值函數(shù)，這就導(dǎo)致迭代的時(shí)間過長，從而使算法收斂速度變慢。為解決上述問題，研究者只能使用出MDP的近似求解算法，解出次優(yōu)解。

4 隨機(jī)博弈網(wǎng)的應(yīng)用

MDP、MDPN以及MDWN模型通常是，用來描述系統(tǒng)內(nèi)只存在一個(gè)決策者的系統(tǒng)，即具有集中式控制設(shè)施系統(tǒng)。實(shí)際應(yīng)用時(shí)，系統(tǒng)當(dāng)中，一般會(huì)有多個(gè)決策者，此時(shí)一般的模型沒有辦法去處理相關(guān)問題，如果以某一個(gè)決策者，針對(duì)他的角度去分別建立模型，雖然可以建立模型求出最優(yōu)解，但是不能體現(xiàn)出決策者們之間的聯(lián)系。動(dòng)態(tài)隨機(jī)博弈可處理含有多個(gè)決策者的系統(tǒng)，并能夠體現(xiàn)出決策者們之間的關(guān)系，可以將它看做是馬爾可夫決策過程的一個(gè)擴(kuò)展。決策者們之間的關(guān)系有很多，包括：①合作關(guān)系，即將所有決策者看作為一個(gè)整體，所關(guān)心的是總收益，對(duì)系統(tǒng)的細(xì)粒度，建立模型起到一定的幫助，還能簡化求解。②競爭關(guān)系，簡單地說就是每個(gè)決策者只希望自己的收益可以最大化。

5 總結(jié)

本文計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)中的動(dòng)態(tài)優(yōu)化及其應(yīng)用進(jìn)行了概述。對(duì)比與靜態(tài)優(yōu)化理論，動(dòng)態(tài)優(yōu)化能夠?qū)ο到y(tǒng)的時(shí)變性進(jìn)行精確地刻畫。文中依據(jù)馬爾可夫決策過程深入的研究討論了計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)中的建模、求解方法和應(yīng)用實(shí)例。

參考文獻(xiàn)：

[1] Murugesan S，Sch niter P，Shroff N B.Multiuser scheduling in a Markov-modeled downlink using randomly delayed ARQ feedback.IEEE Transactions on Information Theory，2012，58（2）：1025-1042.

[2] ZHAO Q ET Al.Decentralized cognitive MAC for opportunistic spectrum access in Ad HOC networks ：A POMDP frame-work.IEEE Journal on Selected Areas in Communications，2007，25（3）：589-600.

[3] 浦江，焦炳連.基于Moodle的計(jì)算機(jī)網(wǎng)絡(luò)課程教學(xué)平臺(tái)的構(gòu)建與應(yīng)用[J].徐州工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2011（4）：39-42.

[4] Choi Kae Won.Adaptive sensing technique to maximize spectrum utilization in cognitive radio.IEEE Transactions on Vehicular Technology，2010，59（2）：992-998.

[5] 沈進(jìn)中.對(duì)模糊推理算法的一點(diǎn)思考[J].徐州工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2016（03）：55-57，81.endprint