计算机系统与计算机网络中的动态优化：模型、求解与应用

孙丹丹

摘要：针对计算机系统在网络应用中存在主要问题，该文给出了基于动态优化的设计方案，通过对动态优化数学模型的建立与求解，实现了动态优化在计算机系统及其网络中的应用。对比静态优化理论，对动态优化中应用马尔可夫决策过程进行了详细的讨论与分析。依据马尔可夫决策过程深入的研究讨论了计算机系统与计算机网络中的建模、求解方法和应用实例。

关键词：计算机系统；动态优化；模型解析

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）35-0038-02

近年来，计算机系统和计算机网络对居民生活所产生的影响越来越大，在各个领域的应用也越来越多，不仅在高端科研实验中大量应用，而且深入到了人们的日常生活中。在这样的复杂背景下，想要提高计算机网络和计算机系统的运行效率，就不得不面对系统资源如何分配、系统数据如何调动等问题，而且为了公众效益，降低成本也是十分关键的问题。

优化理论是研究计算机网络以及计算机系统的一种常见的方法之一，主要用于处理资源分配还有任务调度等问题。优化理论可以根据时间维度分为静态优化和动态优化两种方式。两种优化方式中的静态优化系统是不随时间的变化而改变，也就是说计算机系统中资源的需求量和保有量是不随时间变化而变化的常量。然而，在实际应用的过程中，计算机系统并不是一成不变的，它不仅可能受到时间变化的影响，而且往往会被外界环境所干扰，这就导致在未来可能发生的变化被静态优化系统所忽略，从而不能反映出因为决策者的行為，然后对未来可能产生的影响，体现不出系统受时间影响的特性。综上，本文将以动态优化的处理方法去处理计算机网络和计算机系统的应用问题。进行动态优化时，关于时间累积量的系统收益是系统的目标函数，对比与静态优化，动态优化可以更好地体现出系统的时变性，亦能反映出随时间累积，决策者的决策对目标函数的影响。

马尔可夫决策过程（MDP）是动态优化的基本理论模型。具体定义为：根据决策者的行为，并依赖时间t的系统状态，可以推断出系统在t+1时刻时的状态转移情况，且在[0，t+1]的时间段中，决策者的行为对系统状态不产生影响。对于当前计算机系统和计算机网络中，动态优化模型一直是解决资源分配、资源整理和任务调度等问题的一个热点。本文利用马尔可夫决策过程，从建立模型、找出解答方法及提出应用等角度，论述了动态优化理论的实际应用。

1 动态优化理论模型构建

1.1 马尔可夫决策过程

马尔可夫决策过程包含的要素有：

1） 用来描述系统状态的状态集合S；

2） 在状态空间中决策者可能发生的行为，也就是依赖于当前状态下决策者的行为集合，用A（s）来表示；

3） 收益函数是指决策者发出行为，并且该行为对系统产生了影响，因此而产生效益；

4） 当下一时刻计算机系统的状态仅受决策者行为和当前状态影响，即与系统的历史状态无关时，将这一特性称为马尔可夫决策过程的后效性，它是马尔可夫决策过程的一个显著特性。

1.2 马尔可夫决策流程

马尔可夫决策过程中决策者当前所需的决策行为一般根据策略π来得到，策略π是一个从状态集合S到行为集合A的映射。马尔可夫决策过程一般都具有四个执行流程，分别是：

1） 首先由决策者观察所处状态s（当前状态）；

2） 获得已知状态信息后，根据该信息发出决策行为π（s）；

3） 系统状态可能会因为行决策行为π（s）的发出而发生转换；

4） 重复流程1中的操作。

系统在执行时，会由MDP生成一个收益序列，引入目标函数J，目的是用来比较MDP中决策者发出的策略的优劣程度，且收益序列将会被映射成一个实数值。

1.3 值函数

值函数是MDP中的非常重要概念之一，用表示。是一个映射，范围是从π×S到R（实数集）。的含义为：已知策略π，状态，求得目标函数J的期望，且在无限时间内，MDP满足递推方程，即：

（1）

式中，α—折扣因子，根据式（1）不难看出，策略是收益的和。式（1）也可写为向量形式，即：

（2）

2 马尔可夫过程数学解

1） 运行目标

首先，对于随机MDP，目标函数常带有期望形式（E），一般带有期望的目标函数分为有限马尔可夫决策流程和无限马尔可夫决策流程，具体形式如下：

有限：

（3）

无限：

（4）

（5）

式中，—系统所处状态，—决策者采取的行为。式（4）位无穷时间折扣情况下的目标函数，式（5）为无穷时间平均情形下的目标函数，通常情况下，最大（小）化上述目标函数J，从而得到运行目标。

2） 状态空间分析

系统的状态空间和决策者的行为空间，满足特定条件时，可能是有联系的，在无线电系统中，如果用户设为发射数据的概率为P，则用户的行为空间就是连续的，行为空间的取值范围是固定的，为[0，1]

3） 建立Bellman递推方程

在（3）中，对于一个随机的MDP，其转移方程为，转移频率为。当状态转移频率，没有办法准确得知时，实际操作中经常使用“强化学习”法，去对问题进行求解。用这种方法求最优策略是非常高效且准确的。

4） 以上步骤求解出最优策略。

3 马尔可夫求解

3.1 值迭代算法

值迭代算法是一个近似算法。为求解最优解，常采用值迭代算法，随着迭代过程进行，值迭代算法求得的值，将逐渐逼近最优解。算法如下：

算法1：值迭代算法

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

2） 依据迭代式，求出值迭代算法过程中第n次时，值函数V和策略π；

3） 重复2。

不难证明，算法1在时，收敛于最优值函数，另外还能估计出每一次迭代时的最优解的区间：

当此条件成立时，不再运行算法算法。

3.2 策略迭代计算

使用策略迭代算法，为的是获得最优解，即，为集合内所有元素的个数。策略迭代算法如算法2所示。

算法2：策略迭代算法

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

2） 求解；

3） 确定，且满足

4） if，算法终止，设最优策略为，else，转步骤2。

算法2中，先确定一个初始策略，然后根据求解出值函数，且根据所求得的值函数，改变策略，对比策略，如果结果相等，那么这个就是最优策略，不再进行算法计算。

3.3 近似求解计算

前文中提到，在实际计算机系统中资源种类和数量都非常庞大，使得建立的MDP模型不能利用精确算法去求解，原因包含兩点：①在算法处理中，每个状态下的值函数都需要存储，根据现有的技术，当状态数较多时，无法提供足够的空间去存储这些子函数；②进行迭代过程时，所有的状态都要带人计算值函数，这就导致迭代的时间过长，从而使算法收敛速度变慢。为解决上述问题，研究者只能使用出MDP的近似求解算法，解出次优解。

4 随机博弈网的应用

MDP、MDPN以及MDWN模型通常是，用来描述系统内只存在一个决策者的系统，即具有集中式控制设施系统。实际应用时，系统当中，一般会有多个决策者，此时一般的模型没有办法去处理相关问题，如果以某一个决策者，针对他的角度去分别建立模型，虽然可以建立模型求出最优解，但是不能体现出决策者们之间的联系。动态随机博弈可处理含有多个决策者的系统，并能够体现出决策者们之间的关系，可以将它看做是马尔可夫决策过程的一个扩展。决策者们之间的关系有很多，包括：①合作关系，即将所有决策者看作为一个整体，所关心的是总收益，对系统的细粒度，建立模型起到一定的帮助，还能简化求解。②竞争关系，简单地说就是每个决策者只希望自己的收益可以最大化。

5 总结

本文计算机系统与计算机网络中的动态优化及其应用进行了概述。对比与静态优化理论，动态优化能够对系统的时变性进行精确地刻画。文中依据马尔可夫决策过程深入的研究讨论了计算机系统与计算机网络中的建模、求解方法和应用实例。

参考文献：

[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].徐州工程学院学报：自然科学版，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].徐州工程学院学报：自然科学版，2016（03）：55-57，81.endprint