精确求解一类动态规划问题的神经网络

根据一类动态规划问题的特点，提出一种能够精确求解此问题的神经网络。ＬＤＰＮＮ具有结构简单、易于硬件实现、求解速度快并且能够求得精确最优解等优点，特点适合于大规模动态规划问题的求解。在复杂系统的实时优化与控制等方面具有广阔的应用前景。     

动态模糊逻辑（DFL）在问题求解中的应用研究

问题求解是人工智能中的一大类问题。本文基于动态模糊逻辑（ＤＦＬ）,以动态模糊（ＤＦ）冰生式作为问题的表示方法,用动态模糊（ＤＦ）与／或语义图来分析问题的特征。     

基于Hopfield神经网络的双线性离散系统最优控制

将基于二次型性能指标的离散双线性系统最优控制问题转化为动态规划问题，并用Hopfield神经网络（HNN）求解．该方法具有结构简单、易于硬件实现、求解速度快且能求得精确最优解等特点．在复杂系统的实时优化与控制等方面具有广阔的应用前景．     

基于NARA模型和筛选方法的并行神经网络体系结构

本文将介绍一种并行的神经网络体系结构（ＰＮＮ），它是以ＮＡＲＡ模型和筛选方法为基础的，ＰＮＮ由一个控制网络ＣＮ和一组识别网络ＲＮｉ（ｉ＝１，２，３，…，ｐ）组成。它能够自动地将复杂问题分解为简单问题，容易实现追加学习，并且可以分析其内部状态，其结构也是模块化结构，易于硬件电路实现，可以作为一种计算机运算部件，而且ＰＮＮ具有较高的运行效率。     

面向agent的程序设计语言:DL-1

为适应协作分布式问题求解（ＣＤＰＳ）研究和应用的需要，我们研制了面向ａｇｅｎｔ的程序设计语言：ＤＬ－１语言。ＤＬ－１语言由二部分组成：ＤＬ－１／ｓｙｓｔｅｍ和ＤＬ－１／ａｇｅｎｔ。ＤＬ－１／ｓｙｓｔｅｍ主要用于显式地描述ＣＤＰＳ系统的行政管理结构。ＤＬ－１／ａｇｅｎｔ主要用于描述ＣＤＰＳ系统的ａｇｅｎｔ，并允许用户在描述ａｇｅｎｔ的同时，描述ＣＤＰＳ系统的问题求解结构。     

一种新的非线性离散动态大系统递阶控制的神经网络方法发*

本文给出了一种新具有全集成化特征的，求解非线性动态大规模系统递阶控制问题（ＬＯＣＰ）的神经网络模型（ＬＨＣＮＮ）该神经网络具有结构简洁，紧凑，高效的特点，适合于动态大规模系统的实时优化控制。     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP），并给出一个用非线性精确罚函数法来求解该等价NIP的方法，从而达到求解IP或MIP的目的，数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解，特别是为非线性IP和MIP问题提供了一条通用 的求解途径，对解决许多实际优化问题具有重要意义。     

国际大学生程序设计竞赛试题与算法分析(三)──动态规划及其应用──最短路问题

动态规划实际上是研究一类最优化问题的方法，在经济、工程技术、企业管理、工农业生产及军事等领域中都有广泛的应用。近年来，在ＡＣＭ／ＩＣＰＣ中，使用动态规划（或部分应用动态规划思维）求解的题不仅常见，而且形式也多种多样。而在与此相近的各类信息学竞赛中，应用动态规划解题已经成为一种趋势，这和动态规划的优势不无关系。 与其说动态规划是一种算法，不如说是一种思维方法来得贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的 Ｄｉｊｋｓ…     

贪心核加速动态规划算法求解折扣{0-1}背包问题

针对现有动态规划算法求解折扣{0-1}背包问题（D{0-1}KP）缓慢的问题，基于动态规划思想并结合新型贪心修复优化算法（NGROA）与核算法，通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划（GCADP）算法。首先利用NGROA对问题进行贪心求解，得到非完整项；然后通过计算得到模糊核区间的半径和模糊核区间范围；最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划（BDP）算法求解。实验结果表明：GCADP算法适用于求解D{0-1}KP，且在求解速度上相比BDP算法平均提升了76.24%，相比FirEGA算法平均提升了75.07%。     

动态大型计算机网络的路由通信协议

本文了一种基于离散动态规划原理的分层动态路由协议（ＨＤＲＰ）它适应于分族拓扑的动态大型计算机网络（ＤＬＣＮ）文中给出了该协议路由信息更新的路由决策的实现过程，以及它的正确性证明和复杂性分析，通过仿真实验，研究了该协议的吞吐量和平均报文延迟等特性。文中 一种基于学习自动机的网络故障概率估计了方法及其路由策略，本文的研究表明，分层动态路由协议为动态大型计算机网络的路由决策提供了一种新的有效途径。     

一种基于动态规划策略的离散动态大系统递阶优化神经网络

给出了一种具有集成化特征的、快速求解大规模系统动态规划问题的神经网络模型 (LDPNN),该神经网络将大系统的各子系统的动态方程约束嵌入局部优化子网络,使得整个 网络的结构简洁、紧凑,便于硬件实现,该神经网络计算模型克服了数值方法迭代计算的缺 陷,求解效率高,适宜于大规模动态系统实时优化应用.     

Approximate Dynamic Programming for Self-Learning Control

This paper introduces a self-learning control approach based on approximate dynamic programming. Dynamic programming was introduced by Bellman in the 1950’s for solving optimal control problems of nonlinear dynamical systems. Due to its high computational complexity, the applications of dynamic programming have been limited to simple and small problems. The key step in finding approximate solutions to dynamic programming is to estimate the performance index in dynamic programming. The optimal control signal can then be determined by minimizing (or maximizing) the performance index. Artificial neural networks are very efficient tools in representing the performance index in dynamic programming. This paper assumes the use of neural networks for estimating the performance index in dynamic programming and for generating optimal control signals, thus to achieve optimal control through self-learning.     

Dynamic programming equations for discounted constrained stochastic control

In this paper, the application of the dynamic programming approach to constrained stochastic control problems with expected value constraints is demonstrated. Specifically, two such problems are analyzed using this approach. The problems analyzed are the problem of minimizing a discounted cost infinite horizon expectation objective subject to an identically structured constraint, and the problem of minimizing a discounted cost infinite horizon minimax objective subject to a discounted expectation constraint. Using the dynamic programming approach, optimality equations, which are the chief contribution of this paper, are obtained for these problems. In particular, the dynamic programming operators for problems with expectation constraints differ significantly from those of standard dynamic programming and problems with worst-case constraints. For the discounted cost infinite horizon cases, existence and uniqueness of solutions to the dynamic programming equations are explicitly shown by using the Banach fixed point theorem to show that the corresponding dynamic programming operators are contractions. The theory developed is illustrated by numerically solving the constrained stochastic control dynamic programming equations derived for simple example problems. The example problems are based on a two-state Markov model that represents an error prone system that is to be maintained.     

动态模糊逻辑程序设计语言探讨

动态模糊问题是普遍存在的,但是现存的程序设计语言中适合解决动态模糊问题的极少,本文试图作这方面的研究,设计一种适合解决动态模糊性问题的程序设计语言.本文仿照监督命令的程序结构,给出动态模糊逻辑程序设计语言的一个抽象模型,其内容包括:动态模糊逻辑程序设计语言的抽象语法、动态模糊语义.     

Dynamic programming on a functional memory computer

In a previous paper [1], we described the solution of dynamic programming problems on a new class of parallel processing systems, the Hawaii Parallel Computer (HPC). The HPC has a novel architecture distinguished by its incorporation of field programmable gate arrays to evaluate expressions and by its use of a decision-table data structure to represent computer programs. As specific examples, we showed how the HPC can be used to implement dynamic programming solutions of shortest-path and traveling-salesman problems. In that earlier implementation, we simply adapted algorithms intended for execution on conventional deterministic von Neumann computers. More recently, we designed a successor to the HPC, a “functional memory” computer, which includes constructs for nondeterministic computation. In this paper, we discuss how dynamic programming algorithms can be adapted to take advantage of this nondeterminism.     

Performance Evaluation of Direct Heuristic Dynamic Programming using Control-Theoretic Measures

Approximate dynamic programming (ADP) has been widely studied from several important perspectives: algorithm development, learning efficiency measured by success or failure statistics, convergence rate, and learning error bounds. Given that many learning benchmarks used in ADP or reinforcement learning studies are control problems, it is important and necessary to examine the learning controllers from a control-theoretic perspective. This paper makes use of direct heuristic dynamic programming (direct HDP) and three typical benchmark examples to introduce a unique analytical framework that can be applied to other learning control paradigms and other complex control problems. The sensitivity analysis and the linear quadratic regulator (LQR) design are used in the paper for two purposes: to quantify direct HDP performances and to provide guidance toward designing better learning controllers. The use of LQR however does not limit the direct HDP to be a learning controller that addresses nonlinear dynamic system control issues. Toward this end, applications of the direct HDP for nonlinear control problems beyond sensitivity analysis and the confines of LQR have been developed and compared whenever appropriate to an LQR design.     

动态规划算法在基于子区间消除的随机点定位问题中的应用

针对原有基于判决方程的子区间消除算法中所存在的判决结果与决策表不相符,以及当子区间划分规模增大时,运行时间呈平方次增长的问题,本文提出了一种全新的基于动态规划的子区间消除算法。新算法充分利用动态规划在多阶段决策问题中的卓越性能,将子区间的消除问题划分为合理性判断和新区间生成两部分,这两个部分均可以利用动态规划中子问题分割的思想来解决。文中证明了通过解决这些子问题可以构造得到原问题的最优解,分析了算法的时间复杂度和空间复杂度。为了检验新算法的性能,本文从理论和实验两种维度,进行了新旧两种算法的对比。实验结果表明,该方法大大降低了算法的时间复杂度,有效克服了子区间规模增大所导致的问题,提高了算法的灵活性和运行速度。     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.     

构造移动通信中降低能耗的前缀码的动态规划加速

动态规划是一种常用的寻找问题最优解的算法设计方案。当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图。一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划。本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划。移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗。本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗。对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n2)的时间复杂度。     

Dynamic programming in Datalog with aggregates

Dynamic programming is a general technique for solving optimization problems. It is based on the division of problems into simpler subproblems that can be computed separately. In this paper, we show that Datalog with aggregates and other nonmonotonic constructs can express classical dynamic programming optimization problems in a natural fashion, and then we discuss the important classes of queries and applications that benefit from these techniques