动态规划培训.doc

什么是动态规划(DynamicProgramming)过程最优化:为了实现某项预定任务,需要对任务之前的过程施加控制,任务实现的好坏可以用某个数值指标衡量。在此情况下,需要选择一个措施去控制过程的发展,以期最好的完成任务,称这样的问题为过程最优化。多阶段决策问题:若过程可分为互相联系的若干阶段,每阶段都需做决策,且决策之间不是孤立的,,也同时影响过程的总收益,为了达到一定的目标,下一个决策要根据上一课决策的效果做适当的调整,(Multi-StageDecisionProblem)各阶段的决策结果构成一个决策序列,称为一个策略(Policy).每个阶段可选决策可能有很多,,:每次决策,不能仅仅从局部利益出发,,主要思想是根据最优化原理,将一个多变量最优化问题转变为一系列单变量最优问题。:{决策时刻集,系统状态集,系统行动集,状态转移,转移概率,收益}系统:所针对研究的对象,称之为系统。后面具体的举例子。1)决策时刻集即做出决策的时间点集合,以表示,其可以是连续的,也可以是离散的,可以有限、:当离散时,如,,且当有限时,称为有限周期决策问题(Finite-Period(Stage)DecisionProblem).如果无限,则称为一个无限周期(InfinitePeriod),离散情况。决策时刻是离散点,但是可能不是固定的,可能出现在任意的时刻点上(不是每个点必须做),如排队顾客的到来,(DiscreteEventDynamicSystem,DEDS).虽然也是在离散点上决策,、电子、交通灯领域用的很多,,)状态和行动集通过状态,来了解系统部分信息,为把握其运行规律奠定基础。状态实际上就是我们观测理解系统的一个中介。对于一个动态系统,由于其演化是动态变化的,每个决策时刻t,系统有可能表现为不同的状态值,从而构成一个状态集,表示为,,可以从所允许的行动集合选择一个行动,,,)收益与状态转移及转移概率时刻t选择一个行动at,后果有两个:得到一个当前的收益(或成本);,也可以用概率分布刻画,表示系统状态为,行动选择时,,即,则为确定动态规划,否则,如果不存在任何概率等于1的状态,则表示为随机动态规划。对于随机动态规划而言,必须描述,对于确定动态规划,则不需要写该项。最优系统还有一个终端收益4)决策目标和最优化问题决策目标:对确定问题,一般就是总费用最小或总收益最大等;对随机问题,:在所有的可能的策略集合中,找一个策略,使得5)动态规划方程(数学模型,也是算法步骤)基于动态规划原理,将上面的最优化问题用动态规划方程等价表示,实现多变量复杂问题联合最优后到单变量简单问题独立最优化的效果。具体表示为如下方程:令,或则有如果有限阶段问题,:从第k周期之后的最优等于对两部分和的最优,一部分为第k周期的收益,另外一部分为第k+1以后以为初始的最优收益。实现该过程依赖的思想——最优化原理:直观的,一个最优策略(各阶段决策顺序排列的决策集合)应该满足这样的性质,无论过去的状态和决策如何,对初始状态和前面决策所形成的当前状态而言,:,如果是最优的,不管以前的状态和决策如何,对于以前决策导致的当前状态而言,仍然是后面子系统的最优决策,即最优化原理直观解释例子----最短路问题(Djstra算法)最短路为:.任意截取最优策略,,能够想到的方法:穷举法(小规模可以)动态规划模型,DJStra算法(对于有限状态有限阶段问题,非常有效)线性规划模型,(也相对有效)启发算法:找一个规则,尽量向优的方向靠近,每次都找一个最好的。每次都找最短的,但是结果不是最短。确定型动态规划对确定性问题,由于一