計算機(jī)系統(tǒng)與計算機(jī)網(wǎng)絡(luò)中的動態(tài)優(yōu)化：模型、求解與應(yīng)用

孫丹丹

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

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

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

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

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

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

1 動態(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ā)出行為，并且該行為對系統(tǒng)產(chǎn)生了影響，因此而產(chǎn)生效益；

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

1.2 馬爾可夫決策流程

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

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

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

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

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

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

1.3 值函數(shù)

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

（1）

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

（2）

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

1） 運行目標(biāo)

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

有限：

（3）

無限：

（4）

（5）

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

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

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

3） 建立Bellman遞推方程

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

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

3 馬爾可夫求解

3.1 值迭代算法

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

算法1：值迭代算法

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

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

3） 重復(fù)2。

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

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

3.2 策略迭代計算

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

算法2：策略迭代算法

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

2） 求解；

3） 確定，且滿足

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

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

3.3 近似求解計算

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

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

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

5 總結(jié)

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

參考文獻(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ī)網(wǎng)絡(luò)課程教學(xué)平臺的構(gòu)建與應(yīng)用[J].徐州工程學(xué)院學(xué)報：自然科學(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)中.對模糊推理算法的一點思考[J].徐州工程學(xué)院學(xué)報：自然科學(xué)版，2016（03）：55-57，81.endprint