动态规划基本理论推广函数迭代与策略迭代法市公开课获奖课件

1、动态规划基本理论推广函数迭代法与策略迭代法管理科学与系统工程第1页第1页本章内容举例简朴阐明不定期与无期决议过程形式和概念；以不定期和无期决议过程为例，简介函数迭代法和策略迭代法。管理科学与系统工程第2页第2页不定期与无期决议过程定义：多阶段决议过程阶段数N拟定，称为定期决议过程，当N不拟定期，称这类决议过程为不定期决议过程，当N趋向无穷时称为无期决议过程。管理科学与系统工程第3页第3页不定期与无期决议过程例1：段数不定最短路线问题（不定期决议过程）n个点互相连接构成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间距离(费用)记作dij 。求任意一点i到点n(靶点)最短路

2、线(距离)。51432322575560.51管理科学与系统工程第4页第4页不定期与无期决议过程例1：段数不定最短路线问题（不定期决议过程）n个点互相连接构成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间距离(费用)记作dij 。求任意一点i到点n(靶点)最短路线(距离)。51432322575560.51管理科学与系统工程第5页第5页不定期与无期决议过程例2：无限期决议过程模型 ，状态变换函数为。( 存在明显级变量，但级数是无限 )管理科学与系统工程第6页第6页不定期与无期决议过程求解这类问题假如仍使用以前逐层递推办法，将碰到极大计算量，为此必需寻找新办法。函数方程能

3、够用迭代法求解，通常有函数迭代法和策略迭代法两种迭代办法。管理科学与系统工程第7页第7页函数迭代法与策略迭代法1.函数迭代法环节是：(1)选初始函数 (普通取 )；(2)用迭代公式及 计算其中为当前阶段状态和决议， 为已知终止函数， 为迭代步数, v为指标函数(3)当或管理科学与系统工程第8页第8页函数迭代法与策略迭代法(4)当或时迭代停止，最优值函数，最优策略 ；不然以k+1代替k重复(2),(3).管理科学与系统工程第9页第9页函数迭代法与策略迭代法说明：函数迭代法和策略迭代法中，序列 和 收敛性在相称广泛条件下是能够确保，普通来说它与 等详细形式相关。函数迭代法基本思想是以步数(段数)作

4、为参数，先求在各个不同时数下最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。管理科学与系统工程第10页第10页函数迭代法与策略迭代法策略迭代法基本思想是：先选定一初始策略 然后按某种方式求得新策略 直至最后求出最优策略。若对某一k，对所有i有： ，则称 收敛，此时，策略就是最优策略。普通来说，选定初始策略要比选定初始目的最优值函数容易得多，且策略迭代收敛速度稍快，但其计算量要大些。管理科学与系统工程第11页第11页函数迭代法与策略迭代法 ( 是事先给定数)时迭代停止，最优值函数,最优策略 。2.策略迭代法环节是：(1)选初始策略 ，令k=1；(2)用 求解 ，(3)用 求改进

5、策略 ，管理科学与系统工程第12页第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页第13页函数迭代法与策略迭代法距离，它是阶段指标之和， 并满足可分离性要求，有最优值函数(i)为由i出发到达n最短距离，即式中u*(x)是最

6、优策略，满足基本方程 管理科学与系统工程第14页第14页函数迭代法与策略迭代法该式记为()式，它不是一个递推方程，而是一个关于(i)函数方程,对固定i使()右端 dij+(j) 达到极小j即为最优决议u*(i)，对所有i求解()式得到最优策略u*(x)。管理科学与系统工程第15页第15页不定期与无期决议过程例1：段数不定最短路线问题（不定期决议过程）n个点互相连接构成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间距离(费用)记作dij 。求任意一点i到点n(靶点)最短路线(距离)。管理科学与系统工程第16页第16页函数迭代法与策略迭代法用函数迭代法求解例1只求1,2,3

7、,4各点到点5最优路线，其余类似。解：(1)假设从i点走一步到靶点5最优距离为 , 则显然有： 最优决议为:管理科学与系统工程51432322575560.51第17页第17页函数迭代法与策略迭代法 (2)假设从i点走两步到靶点5最优距离为 , 依据最优化原理得：详细计算下列：管理科学与系统工程第18页第18页函数迭代法与策略迭代法 注：不取含 地方作为最优决议管理科学与系统工程第19页第19页函数迭代法与策略迭代法 (3)假设从i点走三步到靶点5最优距离为 , 则得：计算结果下列：管理科学与系统工程第20页第20页函数迭代法与策略迭代法 (4)假设从i点走四步到靶点5最优距离为 , 则得：计

8、算结果下列：管理科学与系统工程第21页第21页函数迭代法与策略迭代法 管理科学与系统工程第22页第22页函数迭代法与策略迭代法 由于只有5个点,因而从任一点出发到达靶点,其间最多有4步(不然，有回路)，这样就不需继续下去了。将计算结果列成表：管理科学与系统工程i1252525252755.534.534.53355444444435353535第23页第23页函数迭代法与策略迭代法 分析上面结果可得：从点1到点5走一步为最优，最优距离为2，最优路线 ；从点2到点5走三步为最优，最优距离为4.5,最优路线 ；从点3到点5走两步为最优，最优距离为4,最优路线 ；从点4到点5走一步为最优，最优距离为

9、3，最优路线 。管理科学与系统工程第24页第24页函数迭代法与策略迭代法 最优决议最多走4步，多于此步数，会出现走回头路或回路，显然这些不是最优路线。 从任一点出发到靶点，走m(m=1,2,)步与走m+1步最优距离同样，决议函数也同样，假如继续计算走m+2步、m+3步、，其结果仍同样, 即 也就阐明 一致收敛于 ， 一致收敛于 。故当这种一出现，计算便可停止。管理科学与系统工程第25页第25页函数迭代法与策略迭代法例1求解：(策略迭代法） 解：第一步，先选取初始策略 。如取：即 ,但必需没有回路，每点可达靶点。第二步，由 求 ，由策略迭代法方程组可得：因策略 直达靶点，应先计算：管理科学与系统

10、工程第26页第26页函数迭代法与策略迭代法第三步，由 求 ,由求出它解 ：时，管理科学与系统工程第27页第27页函数迭代法与策略迭代法因此， （不在含 项取 ） 时，管理科学与系统工程第28页第28页函数迭代法与策略迭代法因此，同理，可求得 ,于是得到第一次策略迭代结果为以 为初始策略继续重复使用第二、三步进行迭代。第二步：由 求管理科学与系统工程第29页第29页函数迭代法与策略迭代法第三步：由 求,即由求解 。 时，因此同理，求出故第二次策略迭代结果为管理科学与系统工程第30页第30页函数迭代法与策略迭代法第二步：由 求第三步：由 求，类似前面办法求得第三次策略迭代结果为管理科学与系统工程第

11、31页第31页i1234545321156535525.553534524.5435345函数迭代法与策略迭代法将以上结果统计下来：管理科学与系统工程第32页第32页函数迭代法与策略迭代法由以上结果得到 ，对所有i都成立，阐明迭代环节能够停止。故找到最优策略为列表表示为从而能够得到各点到靶点(点5)最优路线和最优距离：管理科学与系统工程i12345345第33页第33页函数迭代法与策略迭代法最优路线 最短距离值 2 4.5 4 3能够看到策略迭代法得到结果与函数迭代法结果一致。管理科学与系统工程第34页第34页不定期与无期决议过程例2：无限期决议过程模型 ，状态变换函数为。( 存在明显级变量，

12、但级数是无限 )管理科学与系统工程第35页第35页函数迭代法与策略迭代法例2求解（函数迭代法）解：(1)任取初值，如状态变换函数为迭代公式为(2)i=1时，进行第一次迭代管理科学与系统工程第36页第36页函数迭代法与策略迭代法 对 求导，并令其等于零，有 可得管理科学与系统工程第37页第37页函数迭代法与策略迭代法 ，取i=2时，进行第二次迭代对 求导，并令其等于零，得管理科学与系统工程第38页第38页函数迭代法与策略迭代法故由于 ，应继续进行迭代。当i=3时，进行第三次迭代，类似以上才办法，可得管理科学与系统工程第39页第39页函数迭代法与策略迭代法由于 ,取i=4继续进行第四次迭代。其结果

13、下列:管理科学与系统工程第40页第40页函数迭代法与策略迭代法由于 ,能够拟定该问题最优收益函数为最优决议为管理科学与系统工程第41页第41页函数迭代法与策略迭代法例2求解（策略迭代法）解：(1)任取初始策略值，如及(2)进行第一次迭代，取i=1,2,得管理科学与系统工程第42页第42页函数迭代法与策略迭代法 由于取 再来拟定第二次迭代决议 ： 管理科学与系统工程第43页第43页函数迭代法与策略迭代法上式解为 由于，需要进行第二次迭代： 管理科学与系统工程第44页第44页函数迭代法与策略迭代法由于 ，需要继续进行迭代，直到 时为止，节约时间，直接给出结果 ，但由于 ，因此需要继续进行迭代。现在

14、来拟定第三次迭代决议，有管理科学与系统工程第45页第45页函数迭代法与策略迭代法则由于，还必须进行下次迭代。第三次迭代：管理科学与系统工程第46页第46页函数迭代法与策略迭代法由于 ，需要继续进行迭代，直到 时为止，最后得到 由于 ，因此需要继续进行迭代。现在来拟定第四次迭代决议，有管理科学与系统工程第47页第47页函数迭代法与策略迭代法则第四次迭代：管理科学与系统工程第48页第48页函数迭代法与策略迭代法继续进行迭代，直到 时为止，最后得到 由于 ，因此可停止迭代。最优收益函数为 相应最优策略为管理科学与系统工程第49页第49页函数迭代法与策略迭代法注：对于定义一个无期决议过程最优化问题，须

15、满足三个条件，即对所有有：状态转移方程故意义；允许决议集合 故意义，并且非空，则存在允许策略使得对所有 非空；目的函数 对所有 故意义，且对所有允许策略，极限 存在。管理科学与系统工程第50页第50页函数迭代法与策略迭代法注：对于定义一个无期决议过程最优化问题，须满足三个条件，即对所有有：状态转移方程故意义；允许决议集合 故意义，并且非空，则存在允许策略使得对所有 非空；目的函数 对所有 故意义，且对所有允许策略，极限 存在。管理科学与系统工程第51页第51页函数迭代法与策略迭代法当上述三个条件成立时，就能够说，无期决议过程最优化意义在于求最优策略 使得其中P是定义在无期过程上非空允许策略集。 是 P元素， 是定义在P上目的函数。管理科学与系统工程第52页第52页函数迭代法与策略迭代法例1、例2共同点是在多阶段决议过程中允许决议集合、状态转移规律、阶段指标等于阶段变量k无关，从而基本方程成为函数方程，称这样过程是平稳。定义：满足下列条件多阶段决议过程成为平稳过程，相应策略称为平稳策略:(1) 允许决议集合Uk(x)与k无关，可记为U(x)， 为状态变量;(2) 状态转移Tk与k无关，于是可写作x，u为当前阶段和决议， 为下一阶段状态