节点运行模式状态自适应的自组织型排队网络研究

The networks techonlogy such as Internet of Things has been rapidly developed and extensively applied. The optimization problem of self-organized queueing networks is a new type of queueing networks problem. The academic and applying value has been gradually highlighted. This project studies a queueing networks control problem characterized with multi-operation-mode nodes or severs, transportation self-organized paths and self-organized networks architecture. We formulate the problem as the multi-objective Nested Semi-Markov Decision Process. Then we build the control model based on Reinforcement Learning architecture, and solve the problem by step size self-adaptive Reinforcement Learning algorithm combining a function approximator based on the support vector machine (SVM). We obtain a control policy integrating operation modes adjusting for the nodes, path selecting and customers sequencing. The main value of our study lies on proposing the concept of Nested Semi-Markov Decision Process and the step size self-adaptive Reinforcement Learning algorithm. We also provide the multi-objective global optimization solutions for a new type of self-organized queueing networks, e.g. shortening the weighted mean flow time and reducing the cost of operation simultaneously. We aim at enriching the theory and application study of self-organized queueing networks by conducting this research.

随着物联网等网络技术的快速发展和广泛应用，自组织型排队网络优化问题作为一类新型的排队网络问题，其学术和应用价值日益重要。本项目拟研究一类节点（服务台）具有多种运行模式、顾客传送路径和网络结构均具有自组织特性的排队网络控制问题。把该问题抽象为一类新型的多目标嵌套式半马尔可夫决策过程，再基于耦合式增强学习架构构建控制决策模型，并采用结合支持向量机函数泛化器的自适应步长增强学习算法来求解，获得集成网络节点运行模式自适应调整策略、路径选择策略和顾客发送排序策略于一体的控制策略。研究的主要价值在于提出嵌套式半马尔可夫决策过程的概念、增强学习算法的自适应学习步长调节机制，并为一类自组织型排队网络提供同时优化加权平均流程时间、网络运行成本等多个目标的整体优化方案。通过开展本项目以期丰富自组织型排队网络控制领域的理论方法和应用研究。

随着物联网等网络技术的快速发展和广泛应用，自组织型排队网络优化问题作为一类新型的排队网络问题，其学术和应用价值日益重要。本项目研究一类节点具有多种运行模式、顾客传送路径和网络结构均具有自组织特性的排队网络控制问题。把该问题抽象为一类新型的多目标嵌套式马尔可夫决策过程，再基于耦合式增强学习架构构建控制决策模型，并采用结合支持结合函数泛化器的增强学习算法来求解，获得集成网络节点运行模式自适应调整策略、路径选择策略和顾客发送排序策略于一体的控制策略。. 本研究的主要创新和科学意义在于：（1）提出一类新型的马尔可夫决策过程（嵌套式马尔可夫决策过程的概念），证明其收敛性等性质并提出分解值迭代算法（DVIA）、线性规划方法两种求解方法，获得比使用传统的马尔可夫决策过程求解方法更高的求解效率。（2）研究了转换时间和服务时间服从一般分布的多类顾客多服务台并联的排队控制问题，通过理论推导分析了其状态转移机制，获得状态转移概率和状态逗留时间的解析公式。（3）提出面向节点模式自适应控制的自组织型排队网络在线控制问题的平均报酬型瞬时差分算法，该算法可用于解决转移概率未知的嵌套式马尔可夫决策过程，为解决节点多模式的大规模自组织型排队网络控制问题提供精细化的解决方案。. DVIA算法每次迭代需要扫描比较的行为数量为所有维度的行为之和，而求解马尔可夫决策过程的经典值迭代算法（VIA）每次迭代需要扫描比较的行为数量为所有维度的行为之积。实验结果表明，DVIA算法的迭代次数和VIA算法差别不大，DVIA算法的状态值函数的收敛速度比VIA算法快，DVIA算法的效率明显高于VIA算法。实验结果表明，面向自组织型排队网络在线控制问题的平均报酬型瞬时差分算法随着学习进程其平均状态值是收敛的；当通过网络的顾客数量大于一定值时控制目标函数值处于较为稳定的状态，该算法通过学习将综合流程时间和成本的目标函数值减少了17.5%～32.6%；这表明增强学习系统通过学习获得优化的排队网络控制策略。