動(dòng)態(tài)規(guī)劃類算法

1、動(dòng)態(tài)規(guī)劃類算法DDDP離散微分動(dòng)態(tài)規(guī)劃法(Discrete differential dynamic programming DDDP)選定初始可行的決策序列和相應(yīng)的狀態(tài)序列；1. 選增量形成廊道：取定增量，在初始狀態(tài)序列的上下各變動(dòng)，形成一個(gè)帶狀的“廊道”，每個(gè)階段一個(gè)狀態(tài)變量只可能取三個(gè)值， ；000,kkksss3. 在廊道內(nèi)用動(dòng)態(tài)規(guī)劃法選優(yōu)得到較好的新的狀態(tài)序列；4. 反復(fù)迭代：以新的狀態(tài)序列代替初始狀態(tài)序列，重復(fù)1.2.3.，直到收斂為止，得最優(yōu)狀態(tài)序列和最優(yōu)決策序列。初始狀態(tài)序列狀態(tài)增量廊道邊界例. 設(shè)用動(dòng)態(tài)規(guī)劃法求最優(yōu)解。0123411111125303736394458.3 ,

2、 7 , 4 , 6)(; 5)(1 , 5)(1;, 51 , 340tPtPtPVVVXThs且取整數(shù); 3,)(,10)(2tsshhIPPQPPB01234迭代一次的解1111142528333942475601234第二次迭代后的解最優(yōu)解DDDP法的特點(diǎn)能有效減輕動(dòng)態(tài)規(guī)劃的“維數(shù)災(zāi)”：與動(dòng)態(tài)規(guī)劃發(fā)比較，大大減少存儲(chǔ)量；計(jì)算量一般也會(huì)減少較多，但與初始狀態(tài)序列的選取有關(guān)。不能保證得到全局最優(yōu)解，可能收斂到局部最優(yōu)解；DDP微分動(dòng)態(tài)規(guī)劃法Differential Dynamic Programming (DDP)對(duì)DP的遞推方程設(shè)初始狀態(tài)為 ，相應(yīng)的決策為 ，記將f,r在 ， 處展開成二

3、次Taylor多項(xiàng)式，),()(),(min111kkkkkkkkkuusTssfusrk0ks0ku00,kkkkkkuuusss0ks0kuT線性展開：則令其對(duì) 的梯度為0，得：kkkkkkkkkkkkkkkkkkkkkkkkkkuFsEsudscuDusCusBsrsbsAssf1TTT21TT211T111T12111)(kkkkkkkkkkkkkkkkkkkkkkkkkkkkudFbscEbuDFAFusCEAFusBEAEsfr)()()()()(TT1TT11TT211TT1TT2110)()(1T1T1TkkkkkkkkkkkkkdbFuDFAFsCEAFkkkkkkkkkkk

4、kkkkkgsGdbFsCEAFDFAFu)()(1T1T11Tku代入目標(biāo)函數(shù)得其中，矩陣Ak,bk可由上述系數(shù)矩陣表示。順推根據(jù)狀態(tài)的增量求決策增量，在由狀態(tài)轉(zhuǎn)移方程的下一階段的狀態(tài)增量，從而得新的狀態(tài)序列和決策序列。特點(diǎn):克服了“維數(shù)災(zāi)”,具有二階收斂速度；必須計(jì)算二階導(dǎo)數(shù)，計(jì)算復(fù)雜，對(duì)性能指標(biāo)函數(shù)和系統(tǒng)方程要求高。kkkkkkksbsAssfTT21)(例 原例取初始解V=3,3,3,3,3, Q=3,3,3,3 ,Ph=3,1,4,1狀態(tài)轉(zhuǎn)移方程第一次迭代:階段k=4時(shí),由于末水位固定所以,階段k=3時(shí),04V,1kkkkQIVVkkkQVV134VQkhkkkQPQB2232344

5、244422VVQPQBfh3233323382QQQPQBh3222322332232323323323436222)(2)(828QVVQVQQVQVQQVVQQfB求偏導(dǎo),并令其等于0得:階段k=2時(shí),求偏導(dǎo),并令其等于0得:階段k=1時(shí),2/ )3(23VQ2/952/2223VVf22222 QQB122121222122122222222232532/2/3)(52/)(252/2VQVQVQQVQVQQVVQQfB13/12 VQ2/323/1212VVf12116 QQB求偏導(dǎo),并令其等于0得:得解V=3,3/2,3,3/2,3,Q=9/2,3/2,9/2,3/2,Ph=3/2

6、,5/2,5/2,3/2, k=4時(shí)012001211021012112112121243/3/23/4)(23/)(623/6VQVVQQQVQVQQVVQQfB2/34/01 VQ. 2/3, 2/3, 2/3, 0, 2/3, 2/3, 2/3, 043322110QVQVQVQV32343VVf2322232332232323323323433222)( 3)(535VQVVQQQVQVQQVVQQfB求偏導(dǎo),令偏導(dǎo)等于0得k=2時(shí),求偏導(dǎo),令偏導(dǎo)等于0得k=1時(shí),. 2/ ) 1(23VQ12211222212212222222223242/2/3)(42/)(542/5VQVVQQQVQVQQVVQQfB2/142/2223VVf. 3/ ) 1(12VQ6/13/ )13(1212VVf3/133/43/3/23/43/ )(133/)(33/133/3012001211021012112112132VQVVQQQVQVQQVVQQfB求偏導(dǎo),令偏導(dǎo)等于0得