动态规划基本理论推广函数迭代与策略迭代法省公共课一等奖全国赛课获奖课件.pptx

动态规划基本理论推广函数迭代法与策略迭代法管理科学与系统工程第1页本章内容举例简单说明不定时与无期决议过程形式和概念；以不定时和无期决议过程为例，介绍函数迭代法和策略迭代法。管理科学与系统工程第2页不定时与无期决议过程定义：多阶段决议过程阶段数N确定，称为定时决议过程，当N不确定时，称这类决议过程为不定时决议过程，当N趋向无穷时称为无期决议过程。管理科学与系统工程第3页不定时与无期决议过程例1：段数不定最短路线问题（不定时决议过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间距离(费用)记作dij。求任意一点i到点n(靶点)最短路线(距离)。5143232257 5560.51管理科学与系统工程第4页不定时与无期决议过程例1：段数不定最短路线问题（不定时决议过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间距离(费用)记作dij。求任意一点i到点n(靶点)最短路线(距离)。5143232257 5560.51管理科学与系统工程第5页不定时与无期决议过程例2：无限期决议过程模型，状态变换函数为。(存在显著级变量，但级数是无限)管理科学与系统工程第6页不定时与无期决议过程求解这类问题假如仍使用以前逐层递推方法，将碰到极大计算量，为此必需寻找新方法。函数方程能够用迭代法求解，通常有函数迭代法和策略迭代法两种迭代方法。管理科学与系统工程第7页函数迭代法与策略迭代法1.函数迭代法步骤是：(1)选初始函数 (普通取 )；(2)用迭代公式及 计算其中为当前阶段状态和决议，为已知终止函数，为迭代步数,v为指标函数(3)当或管理科学与系统工程第8页函数迭代法与策略迭代法(4)当或时迭代停顿，最优值函数，最优策略 ；不然以k+1代替k重复(2),(3).管理科学与系统工程第9页函数迭代法与策略迭代法说明：函数迭代法和策略迭代法中，序列 和 收敛性在相当广泛条件下是能够确保，普通来说它与 等详细形式相关。函数迭代法基本思想是以步数(段数)作为参数，先求在各个不一样时数下最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。管理科学与系统工程第10页函数迭代法与策略迭代法策略迭代法基本思想是：先选定一初始策略 然后按某种方式求得新策略 直至最终求出最优策略。若对某一k，对全部i有：，则称 收敛，此时，策略就是最优策略。普通来说，选定初始策略要比选定初始目标最优值函数轻易得多，且策略迭代收敛速度稍快，但其计算量要大些。管理科学与系统工程第11页函数迭代法与策略迭代法 (是事先给定数)时迭代停顿，最优值函数,最优策略 。2.策略迭代法步骤是：(1)选初始策略 ，令k=1；(2)用 求解，(3)用 求改进策略 ，管理科学与系统工程第12页函数迭代法与策略迭代法例1求解：分析：能够不考虑回路，因为含有回路路线一定不是最短.本问题路线段数事先不固定，而是伴随最优策略确定，然而状态、决议、状态转移、指标函数与以前最短路线问题相同.状态记作x=i，i=1,2,n，决议记作u(i).策略是对任意状态x决议函数，记作u(x)。阶段指标是任意两状态i,j间距离dij，指标函数V(i,u(x)是由状态i出发，在策略u(x)下抵达状态n路线管理科学与系统工程第13页函数迭代法与策略迭代法距离，它是阶段指标之和，并满足可分离性要求，有最优值函数(i)为由i出发抵达n最短距离，即式中u*(x)是最优策略，满足基本方程 管理科学与系统工程第14页函数迭代法与策略迭代法该式记为()式，它不是一个递推方程，而是一个关于(i)函数方程,对固定i使()右端 dij+(j)到达极小j即为最优决议u*(i)，对全部i求解()式得到最优策略u*(x)。管理科学与系统工程第15页不定时与无期决议过程例1：段数不定最短路线问题（不定时决议过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间距离(费用)记作dij。求任意一点i到点n(靶点)最短路线(距离)。管理科学与系统工程第16页函数迭代法与策略迭代法用函数迭代法求解例1只求1,2,3,4各点到点5最优路线，其余类似。解：(1)假设从i点走一步到靶点5最优距离为 ,则显然有：最优决议为:管理科学与系统工程5143232257 5560.51第17页函数迭代法与策略迭代法(2)假设从i点走两步到靶点5最优距离为 ,依据最优化原理得：详细计算以下：管理科学与系统工程第18页函数迭代法与策略迭代法 注：不取含 地方作为最优决议管理科学与系统工程第19页函数迭代法与策略迭代法(3)假设从i点走三步到靶点5最优距离为 ,则得：计算结果以下：管理科学与系统工程第20页函数迭代法与策略迭代法(4)假设从i点走四步到靶点5最优距离为 ,则得：计算结果以下：管理科学与系统工程第21页函数迭代法与策略迭代法 管理科学与系统工程第22页函数迭代法与策略迭代法 因为只有5个点,因而从任一点出发抵达靶点,其间最多有4步(不然，有回路)，这么就不需继续下去了。将计算结果列成表：管理科学与系统工程i1252525252755.534.534.53355444444435353535第23页函数迭代法与策略迭代法 分析上面结果可得：从点1到点5走一步为最优，最优距离为2，最优路线 ；从点2到点5走三步为最优，最优距离为4.5,最优路线 ；从点3到点5走两步为最优，最优距离为4,最优路线 ；从点4到点5走一步为最优，最优距离为3，最优路线 。管理科学与系统工程第24页函数迭代法与策略迭代法 最优决议最多走4步，多于此步数，会出现走回头路或回路，显然这些不是最优路线。从任一点出发到靶点，走m(m=1,2,)步与走m+1步最优距离一样，决议函数也一样，假如继续计算走m+2步、m+3步、，其结果仍一样,即 也就说明 一致收敛于 ，一致收敛于 。故当这种一出现，计算便可停顿。管理科学与系统工程第25页函数迭代法与策略迭代法例1求解：(策略迭代法）解：第一步，先选取初始策略 。如取：即 ,但必需没有回路，每点可达靶点。第二步，由 求 ，由策略迭代法方程组可得：因策略 直达靶点，应先计算：管理科学与系统工程第26页函数迭代法与策略迭代法第三步，由 求 ,由求出它解 ：时，管理科学与系统工程第27页函数迭代法与策略迭代法所以，（不在含 项取 ）时，管理科学与系统工程第28页函数迭代法与策略迭代法所以，同理，可求得 ,于是得到第一次策略迭代结果为以 为初始策略继续重复使用第二、三步进行迭代。第二步：由 求管理科学与系统工程第29页函数迭代法与策略迭代法第三步：由 求,即由求解 。时，所以同理，求出故第二次策略迭代结果为管理科学与系统工程第30页函数迭代法与策略迭代法第二步：由 求第三步：由 求，类似前面方法求得第三次策略迭代结果为管理科学与系统工程第31页i1234545321156535525.553534524.5435345函数迭代法与策略迭代法将以上结果统计下来：管理科学与系统工程第32页函数迭代法与策略迭代法由以上结果得到 ，对全部i都成立，说明迭代步骤能够停顿。故找到最优策略为列表表示为从而能够得到各点到靶点(点5)最优路线和最优距离：管理科学与系统工程i12345345第33页函数迭代法与策略迭代法最优路线 最短距离值 2 4.5 4 3能够看到策略迭代法得到结果与函数迭代法结果一致。管理科学与系统工程第34页不定时与无期决议过程例2：无限期决议过程模型，状态变换函数为。(存在显著级变量，但级数是无限)管理科学与系统工程第35页函数迭代法与策略迭代法例2求解（函数迭代法）解：(1)任取初值，如状态变换函数为迭代公式为(2)i=1时，进行第一次迭代管理科学与系统工程第36页函数迭代法与策略迭代法 对 求导，并令其等于零，有 可得管理科学与系统工程第37页函数迭代法与策略迭代法，取i=2时，进行第二次迭代对 求导，并令其等于零，得管理科学与系统工程第38页函数迭代法与策略迭代法故因为 ，应继续进行迭代。当i=3时，进行第三次迭代，类似以上才方法，可得管理科学与系统工程第39页函数迭代法与策略迭代法因为 ,取i=4继续进行第四次迭代。其结果以下:管理科学与系统工程第40页函数迭代法与策略迭代法因为 ,能够确定该问题最优收益函数为最优决议为管理科学与系统工程第41页函数迭代法与策略迭代法例2求解（策略迭代法）解：(1)任取初始策略值，如及(2)进行第一次迭代，取i=1,2,得管理科学与系统工程第42页函数迭代法与策略迭代法 因为取 再来确定第二次迭代决议 ：管理科学与系统工程第43页函数迭代法与策略迭代法上式解为 因为，需要进行第二次迭代：管理科学与系统工程第44页函数迭代法与策略迭代法因为，需要继续进行迭代，直到 时为止，节约时间，直接给出结果 ，但因为，所以需要继续进行迭代。现在来确定第三次迭代决议，有管理科学与系统工程第45页函数迭代法与策略迭代法则因为，还必须进行下次迭代。第三次迭代：管理科学与系统工程第46页函数迭代法与策略迭代法因为，需要继续进行迭代，直到 时为止，最终得到 因为，所以需要继续进行迭代。现在来确定第四次迭代决议，有管理科学与系统工程第47页函数迭代法与策略迭代法则第四次迭代：管理科学与系统工程第48页函数迭代法与策略迭代法继续进行迭代，直到 时为止，最终得到 因为，所以可停顿迭代。最优收益函数为 对应最优策略为管理科学与系统工程第49页函数迭代法与策略迭代法注：对于定义一个无期决议过程最优化问题，须满足三个条件，即对全部有：状态转移方程有意义；允许决议集合 有意义，而且非空，则存在允许策略使得对全部 非空；目标函数 对全部 有意义，且对全部允许策略，极限 存在。管理科学与系统工程第50页函数迭代法与策略迭代法注：对于定义一个无期决议过程最优化问题，须满足三个条件，即对全部有：状态转移方程有意义；允许决议集合 有意义，而且非空，则存在允许策略使得对全部 非空；目标函数 对全部 有意义，且对全部允许策略，极限 存在。管理科学与系统工程第51页函数迭代法与策略迭代法当上述三个条件成立时，就能够说，无期决议过程最优化意义在于求最优策略 使得其中P是定义在无期过程上非空允许策略集。是 P元素，是定义在P上目标函数。管理科学与系统工程第52页函数迭代法与策略迭代法例1、例2共同点是在多阶段决议过程中允许决议集合、状态转移规律、阶段指标等于阶段变量k无关，从而基本方程成为函数方程，称这么过程是平稳。定义：满足以下条件多阶段决议过程成为平稳过程，对应策略称为平稳策略:(1)允许决议集合Uk(x)与k无关，可记为U(x)，为状态变量;(2)状态转移Tk与k无关，于是可写作x，u为当前阶段和决议，为下一阶段状态;管理科学与系统工程第53页函数迭代法与策略迭代法(3)阶段指标Vk与k无关，可记作 。假如决议序列 中 与k无关，称为平稳，可用一个函数u(x)表示。平稳过程最优策略一定是平稳策略，记作 .管理科学与系统工程第54页附：理论证实 收敛性证实 对全部k、i、j,依据极限存在准则，必收敛于 当收敛性于 时，证实 即为 解管理科学与系统工程第55页附：理论证实 收敛于 ，有管理科学与系统工程第56页附：理论证实合并上面两式，即得管理科学与系统工程第57页