基于梯度逼近方法的Markov系统及其在通信中的应用

发布时间：2020-11-02 01:30

　　 随着信息科学技术的迅猛发展和广泛应用,出现了大量的复杂随机动态系统,比如在通讯网络(Internet及无线网络),柔性制造,智能机器人,交通管理等领域。目前,该类系统的性能优化问题逐渐成为很多领域的研究热点。这些领域包括控制系统领域,运筹学领域,计算机科学领域以及人工智能领域等等。不同领域采用不同的方法来解决该问题,如控制系统领域的离散事件动态系统的摄动分析方法,运筹学领域的Markov决策过程理论,计算机科学和人工智能领域的强化学习(或神经元动态规划)方法。虽然这些方法对系统结构有着不同的描述,但这些方法都是围绕着同一个目的展开,即寻找一个“最好的策略”来优化系统的性能。 近几年来,一种基于灵敏度观点的优化方法将以上不同领域的不同方法有机的统一起来。该方法以性能势理论为基础,通过两种性能灵敏度公式:性能差公式和性能导数公式,将摄动分析方法,Markov决策过程理论以及强化学习方法统一在同一框架下。该方法不仅可以基于模型采用理论计算的方法来寻找系统的最优策略,而且可以在系统模型参数未知的情况下基于一条样本轨道在线地改进系统性能。因而在某种程度上它解决了该类系统的“维数灾”和“模型灾”问题。到目前为止,该方法在自适应Markov报酬过程上的应用还没有被研究,本文在该方法的基础上,研究了自适应Markov报酬过程的灵敏度分析,得到了性能差和性能导数公式,以及在单样本轨道上性能导数的估计式。 基于仿真的梯度逼近方法是基于一种可以基于单样本轨道在线的改进系统性能的梯度逼近方法。这个方法首先参数化策略。然后根据仿真出来的样本轨道估计出性能测度关于参数向量的梯度;最后再沿梯度的方向改进参数。利用参数化策略,减少了未知参数的个数,避开了“维数灾”的问题;通过仿真避开了“模型灾”的问题。参数的更新时刻的不同,这个方法分为两个传统的算法。再生环梯度逼近算法是每到更新点时,即更新一次参数,每步梯度逼近算法是每次状态转移都更新一次参数。这两个算法虽然很好的避开了“维数灾”和“模型灾”的问题,但它们也有其局限的地方:在再生环梯度逼近算法中,状态空间比较大时,再生环相应增大,更新缓慢,导致较低的计算效率,同时带来比较大的方差;在每步梯度逼近算法中,由于每做一次转移,算法进行一次更新,这洋计算量就会比较大,甚至有些实际系统是无法实现的。本文为了解决现有方法的这些不足,提出了Markov报酬过程、自适应Markov报酬过程以及随机策略的Markov决策过程的双时间尺度梯度逼近算法。算法主要思想是,在给定的更新周期上更新参数,而这个给定的更新周期序列是由两个时间尺度通过计算获得的,并且是个递增序列。算法的特点是开始更新较快,随后更新频率慢慢降低。这个特点带来的好处就是,在最初的更新中,算法结合了每步逼近算法的优点,更新较快,并且方差很小,有助于参数较快地收敛到最优值附近,同时将方差降低到一个很小的范围内;在随后的更新中,算法更新频率降低,经过很多次的状态转移参数才会更新一次,一次更新中获得的信息量比较多,有助于估值准确性的提高,提高了收敛精度,同时降低了计算量。并且在较弱的假设下,从理论上证明了算法的收敛性。 无线多媒体通信网络问题是近期的研究热点,目前仍存在大量瓶颈问题。本文在上述理论研究的基础上,研究OVSF-CDMA系统中动态编码分配的呼叫容许接入控制问题和有QoS指标约束下的CDMA系统的呼叫容许接入控制问题的建模和优化。通过将问题建模为Markov决策过程,提出一种在线学习估计策略梯度,随机逼近优化容许接入策略的在线算法,利用双时间尺度的技术降低计算复杂度,提高收敛速度。并且这个算法不依赖于系统的具体参数,具有较强的适应性,可以适用于复杂应用环境中的无线多媒体通信网的呼叫容许接入控制的在线优化,具有较高的应用价值。
【学位单位】：中国科学技术大学
【学位级别】：博士
【学位年份】：2009
【中图分类】：N941.4
【部分图文】：

{13!基于性能势和实现因子可以在线估计的特性，给出了性能势，实现因子，性能梯度的几种估计方法。对于基于灵敏度观点的优化，我们可以引用文献{ls]中的图1一1来概括。由图1一1可见，强化学习为性能势的在线估计提供了方法，性能势为两个灵敏度公式莫定了基础，基于性能差公式可以得到Markov决策过程的策略迭代算法以及在线的策略迭代算法，还可以得到随机控制中的最优性方程与在线优化算法。基于性能导数公式，可以得到策略梯度估计方法以及摄动分析的一些结果，进而设计在线的梯度优化算法。图1一1基于灵敏度观点的优化思路1.3神经元动态规划目前比较成熟的Markov系统的优化控制方法是传统的动态规划方法。这个方法首先利用Bellman方程建立最优性方程，再通过迭代计算求出最优性能{7}。寻优的过程依赖状态空间中每个状态的报酬函数和行动值函数，以及Markov系统的精确模型。而在某些实际问题中，系统的状态空间往往非常大，并且系统运行机制也往往很难精确描述

SuboPtimal tWOtime一sCals图5一1双时间尺度策略梯度CAC算法与传统的四个算法的出较可以看出这个算法得到的值最接近最优算法得到的值。图5一2演示了再生环梯度逼近算法、每步梯度逼近算法和双时间尺度梯度逼近算法的区别，可以看出我们的算法能够达到更快的收敛速度，更小的样本方差。为了比较三种梯度逼近算法的计算复杂度，我们计算每个算法的迭代次数，考虑到对于再生环梯度逼近算法，每条样本轨道上的再生环个数并不相同，所以我们仿真30个样本轨道，选择迭代次数的平均值，作为比较的依据。每步梯度逼近算法、再生环梯度逼近算法和双时间尺度梯度逼近算法的迭代次数分别是20，000，000、375
【参考文献】

相关期刊论文 前1条

1 ;Performance Potential-based Neuro-dynamic Programming for SMDPs[J];自动化学报;2005年04期

相关博士学位论文 前1条

1 李衍杰;扩展Markov决策过程的性能灵敏度分析与优化[D];中国科学技术大学;2006年

本文编号：2866380