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

《动态规划基本理论推广函数迭代与策略迭代法课件》由会员分享，可在线阅读，更多相关《动态规划基本理论推广函数迭代与策略迭代法课件（57页珍藏版）》请在装配图网上搜索。

1、函数迭代法与策略迭代法动态规划基本理论推广函数迭代与策略迭代法课件举例简单说明不定期与无期决策过程的形式和概念；以不定期和无期决策过程为例，介绍函数迭代法和策略迭代法。动态规划基本理论推广函数迭代与策略迭代法课件定义：多阶段的决策过程的阶段数N确定，称为定期决策过程，当N不确定时，称此类决策过程为不定期决策过程，当N趋向无穷时称为无期决策过程。动态规划基本理论推广函数迭代与策略迭代法课件例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。51

2、43232257 5560.51动态规划基本理论推广函数迭代与策略迭代法课件例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。5143232257 5560.51动态规划基本理论推广函数迭代与策略迭代法课件例2：无限期决策过程模型，状态变换函数为。(存在明显的级变量，但级数是无限的)动态规划基本理论推广函数迭代与策略迭代法课件1jjjx2200minlimjjkkjzxV求解这类问题如果仍使用以前的逐级递推方法，将遇到极大的计算量，为此必需

3、寻找新方法。函数方程可以用迭代法求解，通常有函数迭代法和策略迭代法两种迭代方法。动态规划基本理论推广函数迭代与策略迭代法课件1.函数迭代法的步骤是：(1)选初始函数 (一般取 )；(2)用迭代公式及 计算其中为当前阶段的状态和决策，为已知终止函数，为迭代步数,v为指标函数(3)当或动态规划基本理论推广函数迭代与策略迭代法课件0()fx0()0fx 1()()(,)(,),kku U xfxopt v x ufT x uxX()(),knfxx xX(),1,2,kfx k,x u()xk1()(),kkfxfx xX1()()()kkkfxfxfx(4)当或时迭代停止，最优值函数，最优策略 ；

4、否则以k+1代替k重复(2),(3).动态规划基本理论推广函数迭代与策略迭代法课件1()(),kkuxux xX1()(),()kkkfxfxxXfx()()kf xfx()()kuxux说明：函数迭代法和策略迭代法中，序列 和 的收敛性在相当广泛的条件下是可以保证的，一般来说它与 等的具体形式有关。函数迭代法的基本思想是以步数(段数)作为参数，先求在各个不同步数下的最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。动态规划基本理论推广函数迭代与策略迭代法课件()kfx()kux(),(),(,),nU x T x v x uX策略迭代法的基本思想是：先选定一初始策略 然后按某

5、种方式求得新策略 直至最终求出最优策略。若对某一k，对所有i有：，则称 收敛，此时，策略就是最优策略。一般来说，选定初始策略要比选定初始目标最优值函数容易得多，且策略迭代的收敛速度稍快，但其计算量要大些。动态规划基本理论推广函数迭代与策略迭代法课件()1,2,1ku i in12(),(),u i u i 1()()kkuiu i12(),(),u i u i()1,2,1ku i in (是事先给定的数)时迭代停止，最优值函数,最优策略 。2.策略迭代法的步骤是：(1)选初始策略 ，令k=1；(2)用 求解 ，(3)用 求改进策略 ，动态规划基本理论推广函数迭代与策略迭代法课件xX()()k

6、f xfx()()kuxux1()u x()kux()kfx()(,()(,(),.kkkkfxv x uxf T x uxxX()(),.knfxx xX()kfx1()kux1()()(,)(,).kku U xuxu opt v x uf T x u例1的求解：分析：可以不考虑回路，因为含有回路的路线一定不是最短的.本问题路线的段数事先不固定，而是随着最优策略确定的，然而状态、决策、状态转移、指标函数与以前的最短路线问题的相同.状态记作x=i，i=1,2,n，决策记作u(i).策略是对任意状态x的决策函数，记作u(x)。阶段指标是任意两状态i,j间的距离dij，指标函数V(i,u(x)是

7、由状态i出发，在策略u(x)下到达状态n的路线的动态规划基本理论推广函数迭代与策略迭代法课件距离，它是阶段指标之和，并满足可分离性要求，有最优值函数(i)为由i出发到达n的最短距离，即式中u*(x)是最优策略，满足基本方程 动态规划基本理论推广函数迭代与策略迭代法课件(,()(,()ijVi u xdVj u x*()()min(,()(,()u xf iV i u xV i ux1()min(),1,2,1.ijj nf idf jin 该式记为()式，它不是一个递推方程，而是一个关于(i)的函数方程,对固定的i使()右端 dij+(j)达到极小的j即为最优决策u*(i)，对所有的i求解()

8、式得到最优策略u*(x)。动态规划基本理论推广函数迭代与策略迭代法课件例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。动态规划基本理论推广函数迭代与策略迭代法课件用函数迭代法求解例1只求1,2,3,4各点到点5的最优路线，其余类似。解：(1)假设从i点走一步到靶点5的最优距离为 ,则显然有：最优决策为:动态规划基本理论推广函数迭代与策略迭代法课件1()f i115(1)2fd(1)5u125(2)7fd135(3)5fd145(4)3fd

9、155(5)0fd(2)5u(3)5u(4)5u(5)5u5122257 5560.5(2)假设从i点走两步到靶点5的最优距离为 ,根据最优化原理得：具体计算如下：动态规划基本理论推广函数迭代与策略迭代法课件2()f i21152()min(),1,2,3,4(5)0ijif idfjif 21115(1)min()jifdfj 111min(1),df121131141151(2),(3),(4),(5)dfdfdfdf 注：不取含 的地方作为最优决策动态规划基本理论推广函数迭代与策略迭代法课件2(1)5umin02,67,55,23,2020ijd()u i22115(2)min()jif

10、dfj 211min(1),df221231241251(2),(3),(4),(5)dfdfdfdfmin62,07,0.55,53,705.52(2)3u(3)假设从i点走三步到靶点5的最优距离为 ,则得：计算结果如下：动态规划基本理论推广函数迭代与策略迭代法课件3()f i32153()min(),1,2,3,4(5)0ijif idfjif 33(1)2,(1)5fu33(2)4.5,(2)3fu33(3)4,(3)4fu33(4)3,(4)5fu(4)假设从i点走四步到靶点5的最优距离为 ,则得：计算结果如下：动态规划基本理论推广函数迭代与策略迭代法课件4()f i43154()mi

11、n(),1,2,3,4(5)0ijif idfjif 44(1)2,(1)5fu44(2)4.5,(2)3fu44(3)4,(3)4fu44(4)3,(4)5fu 动态规划基本理论推广函数迭代与策略迭代法课件23115(3)min()jifdfj 311min(1),df321331341351(2),(3),(4),(5)dfdfdfdfmin52,0.57,05,13,5042(3)4u24115(4)min()jifdfj 411min(1),df421431441451(2),(3),(4),(5)dfdfdfdfmin22,57,15,03,3032(4)5u 由于只有5个点,因而从

12、任一点出发到达靶点,其间最多有4步(否则，有回路)，这样就不需继续下去了。将计算结果列成表：动态规划基本理论推广函数迭代与策略迭代法课件i1252525252755.534.534.533554444444353535351()f i1()u i2()f i3()f i4()f i2()u i3()u i4()u i 分析上面的结果可得：从点1到点5走一步为最优，最优距离为2，最优路线 ；从点2到点5走三步为最优，最优距离为4.5,最优路线 ；从点3到点5走两步为最优，最优距离为4,最优路线 ；从点4到点5走一步为最优，最优距离为3，最优路线 。动态规划基本理论推广函数迭代与策略迭代法课件11

13、(1)5u3212(2)3(3)4(4)5uuu213(3)4(4)5uu14(4)5u 最优决策最多走4步，多于此步数，会出现走回头路或回路，显然这些不是最优路线。从任一点出发到靶点，走m(m=1,2,)步与走m+1步的最优距离一样，决策函数也一样，如果继续计算走m+2步、m+3步、，其结果仍一样,即 也就说明 一致收敛于 ，一致收敛于 。故当这种一出现，计算便可停止。动态规划基本理论推广函数迭代与策略迭代法课件1()(),mmfifi1()(),mmuiui()mfi()f i()mui()u i例1的求解：(策略迭代法）解：第一步，先选取初始策略 。如取：即 ,但必需没有回路，每点可达靶

14、点。第二步，由 求 ，由策略迭代法的方程组可得：因策略 直达靶点，应先计算：动态规划基本理论推广函数迭代与策略迭代法课件1()u i1111(1)5,(2)4,(3)5,(4)3.uuuu1()u i1()f i11,()111()()(5)0i uif idf u if11(1),(3)uu1()5,4,5,3u i第三步，由 求 ,由求出它的解 ：时，动态规划基本理论推广函数迭代与策略迭代法课件1151135114311241(1)(5)202(3)(5)505(4)(3)156(2)(4)5611fdffdffdffdf 1()f i2()u i,()1()min()i u iu idf

15、 u i2()u i()1u i 所以，（不在含 的项取 ）时，动态规划基本理论推广函数迭代与策略迭代法课件2(1)5uiid1,()1()111121131141151min()min(1),(2),(3),(4),(5)min02,611,55,26,202u iu idf u idfdfdfdfdf2(1)u()2u i 2,()1()min()min62,011,0.55,56,705.5u iu idf u i所以，同理，可求得 ,于是得到第一次策略迭代的结果为以 为初始策略继续反复使用第二、三步进行迭代。第二步：由 求动态规划基本理论推广函数迭代与策略迭代法课件2(2)3u2()u

16、 i2()u i22(3)5(4)5uu，2()5,3,5,5u i2()f i215235(1)2(3)5fdfd第三步：由 求,即由求解 。时，所以同理，求出故第二次策略迭代的结果为动态规划基本理论推广函数迭代与策略迭代法课件3()u i2452232(4)3(2)(3)0.555.5fdfdf2()f i,()2()min()i u iu idf u i3()u i()1u i 1,()2()min()u iu idf u imin02,65.5,55,23,2023(1)5u333(2)3,(3)4,(4)5uuu3()5,3,4,5u i第二步：由 求第三步：由 求，类似前面的方法求

17、得第三次策略迭代的结果为动态规划基本理论推广函数迭代与策略迭代法课件3()u i4()5,3,4,5u i3()f i31534533433233(1)2(4)3(3)(4)134(2)(3)0.544.5fdfdfdffdf 3()f i4()u ii1234545321156535525.553534524.5435345将以上结果记录下来：动态规划基本理论推广函数迭代与策略迭代法课件1()u i2()f i1()f i4()u i2()u i3()u i3()f i由以上结果得到 ，对所有的i都成立，说明迭代步骤可以停止。故找到最优策略为列表表示为从而可以得到各点到靶点(点5)的最优路线

18、和最优距离：动态规划基本理论推广函数迭代与策略迭代法课件34()()u iu i()5,3,4,5u ii12345345()u i最优路线 最短距离值 2 4.5 4 3可以看到策略迭代法得到的结果与函数迭代法的结果一致。动态规划基本理论推广函数迭代与策略迭代法课件例2：无限期决策过程模型，状态变换函数为。(存在明显的级变量，但级数是无限的)动态规划基本理论推广函数迭代与策略迭代法课件1jjjx2200minlimjjkkjzxV例2的求解（函数迭代法）解：(1)任取初值，如状态变换函数为迭代公式为(2)i=1时，进行第一次迭代动态规划基本理论推广函数迭代与策略迭代法课件20()2g(,)T

19、xx221()min()iixgxg2210()min()xgxg2221min2()min(,)xxxxGx 对 求导，并令其等于零，有 可得动态规划基本理论推广函数迭代与策略迭代法课件222122()()2()33g 2251.66731G124()0Gxxx12()0.6663x ，取i=2时，进行第二次迭代对 求导，并令其等于零，得动态规划基本理论推广函数迭代与策略迭代法课件10()()gg2221()min()xgxg22225min()3min(,)xxxxGx2G2102()03Gxxx故由于 ，应继续进行迭代。当i=3时，进行第三次迭代，类似以上才方法，可得动态规划基本理论推广

20、函数迭代与策略迭代法课件25()0.6258x 2222555()()()838g 22131.625821()()gg由于 ,取i=4继续进行第四次迭代。其结果如下:动态规划基本理论推广函数迭代与策略迭代法课件313()0.61921x 2223131313()()()21821g 22341.6192132()()gg由于 ,可以确定该问题的最优收益函数为最优决策为动态规划基本理论推广函数迭代与策略迭代法课件434()0.61855x 2224343434()()()552155g 22891.6185543()()gg2()1.618jg()0.618jjx 例2的求解（策略迭代法）解：

21、(1)任取初始策略值，如及(2)进行第一次迭代，取i=1,2,得动态规划基本理论推广函数迭代与策略迭代法课件0()x,0()0(1,2,3,)jgj()()min(,()(,()xgfxg Tx0,100,00()(,()(,()gfxgTx222()02 由于取 再来确定第二次迭代的决策 ：动态规划基本理论推广函数迭代与策略迭代法课件20()2g0,20,1()()gg0,200,10()(,()(,()gfxgTx2222()2()2 1()x02222211111(,)()2()()2()4()0 xg Txxxxxxx上式的解为 由于，需要进行第二次迭代：动态规划基本理论推广函数迭代与

22、策略迭代法课件10()()xx12()0.6663x 1,111,01()(,()(,()gfxgTx2222213()01.44439 1,211,11()(,()(,()gfxgTx222222132130()()1.60539381 由于，需要继续进行迭代，直到 时为止，节省时间，直接给出结果 ，但由于，因此需要继续进行迭代。现在来确定第三次迭代的决策，有动态规划基本理论推广函数迭代与策略迭代法课件1,21,1()()gg1,11,()()iigg211,()()1.625igg210()()2gg2()x12222222222(,)()1.625()()2()3.25()0 xg Tx

23、xxxxxx则由于，还必须进行下次迭代。第三次迭代：动态规划基本理论推广函数迭代与策略迭代法课件213()0.61921x 21()()xx2,122,02()(,()(,()gfxgTx222213610()01.38321441 2,222,12()(,()(,()gfxgTx22221361013()()1.5832144121 由于，需要继续进行迭代，直到 时为止，最后得到 由于，因此需要继续进行迭代。现在来确定第四次迭代的决策，有动态规划基本理论推广函数迭代与策略迭代法课件2,22,1()()gg2,12,()()iigg222,()()1.618igg21()()gg3()x222

24、22233333(,)()1.618()()2()3.236()0 xg Txxxxxxx则第四次迭代：动态规划基本理论推广函数迭代与策略迭代法课件3()0.618x 3,133,03()(,()(,()gfxgTx222(0.618)01.382 3,233,13()(,()(,()gfxgTx2222(0.618)1.382(0.618)1.583 继续进行迭代，直到 时为止，最后得到 由于，因此可停止迭代。最优收益函数为 相应的最优策略为动态规划基本理论推广函数迭代与策略迭代法课件3,13,()()iigg23()1.618g32()()gg2()1.618jjg()0.618jjjx

25、注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对所有的有：状态转移方程有意义；允许决策集合 有意义，而且非空，则存在允许策略使得对所有 非空；目标函数 对所有 有意义，且对所有允许策略，极限 存在。动态规划基本理论推广函数迭代与策略迭代法课件1(,)kkkkxT x u()kkDx00()D x0011(),(),uxu x1,()kkkDx0kV0k 0k 0limkkV注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对所有的有：状态转移方程有意义；允许决策集合 有意义，而且非空，则存在允许策略使得对所有 非空；目标函数 对所有 有意义，且对所有允许策略，极限 存在

26、。动态规划基本理论推广函数迭代与策略迭代法课件1(,)kkkkxT x u()kkDx00()D x0011(),(),uxu x1,()kkkDx0kV0k 0k 0limkkV当上述三个条件成立时，就可以说，无期决策过程的最优化的意义在于求最优策略 使得其中P是定义在无期过程上的非空允许策略集。是 P的元素，是定义在P上的目标函数。动态规划基本理论推广函数迭代与策略迭代法课件pP()()p PV poptV p()V pp00001(,)(,)(,)NNNkkkkkkkkVvx uv x uvx u()()(,()(,)(,()u D xp xV x pxopt v x uopt x p

27、x例1、例2的共同点是在多阶段决策过程中允许决策集合、状态转移规律、阶段指标等于阶段变量k无关，从而基本方程成为函数方程，称这样的过程是平稳的。定义：满足以下条件的多阶段决策过程成为平稳过程，相应的策略称为平稳策略:(1)允许决策集合Uk(x)与k无关，可记为U(x)，为状态变量;(2)状态转移Tk与k无关，于是可写作x，u为当前的阶段和决策，为下一阶段状态;动态规划基本理论推广函数迭代与策略迭代法课件xX(,)xT x u x(3)阶段指标Vk与k无关，可记作 。如果决策序列 中 与k无关，称为平稳的，可用一个函数u(x)表示。平稳过程的最优策略一定是平稳策略，记作 .动态规划基本理论推广函

28、数迭代与策略迭代法课件(,)V x u111(),()nnnpu xuxku1()npux 收敛性证明对所有的k、i、j,根据极限存在准则，必收敛于 当收敛性于 时，证明 即为 的解动态规划基本理论推广函数迭代与策略迭代法课件1111()min()()()Kijkiikkj nfidfjdfjfj()Kfi0,()0ijKdfi()Kfi()f i()Kfi()f i()f i()min()()xf ig if imin()()2()min()()2 xxg if if ig if i 收敛于 ，有动态规划基本理论推广函数迭代与策略迭代法课件()()()kf ifif i1()()()kf ifif i()f i()kfi1()()min()()min()()min()()2 kkxxxf ifig ifig if ig if i合并上面两式，即得动态规划基本理论推广函数迭代与策略迭代法课件1()()min()()min()()min()()2 kkxxxf ifig ifig if ig if imin()()2()min()()2 xxg if if ig if i