常用降维动态规划.docx

常用降维动态规划.docx常用降维动态规划1逐次逼近动态规划(DPSA)逐次逼近动态规划是求解多维问题的冇效方法之一,它的基本思想是把带冇若干决策变量的问题分解成仅带有1个决策变量的若干个子问题,每个子问题比原来的总问题具有较少的状态变量,从而大大节省状态存储量及计算工作量,便丁计算机求解。对于多库联调优化问题,在确定初始可行调度线后采用DPSA求解的过程如(1) 先假定第2个到最后一个水库的调度过程全部固定,对第1个水库进行优化,这吋相当于单库优化调度,可以通过常规动态规划找到第1个水库的最优调度过程,此时其它水库仅进行简单的水务计算即可。计算完成后用最优结果替代初始解屮第1个水库的调度过程。(2) 假定第1个,第3个到最后一个水库的调度过程全部固定,求第2个水库的最优过程,这也相当于单库优化调度,同样通过常规动态规划找到第2个水库的最优调度过程。并将其最优结果替代初始解屮第2个水库的调度过程。(3) 依次类推,直至最后一个水库计算完成。此时初始可行解依次被各次的单库最优结果替代,一轮计算完成。(4) 以上一轮最优结果为基础,重新依次计算单个电站的最优过程,并替换总体最优结果,反复轮流优选,直至收敛。DPSA的思想是通过减少每次参与计算的电站数口,达到降维效果,其搜索结果精度与初始状态序列有关,因此它不能保证在所有情况下都收敛到真正的总体最优解,求解过程屮可以从多个不同的初始状态(库群初始调度过程)开始,求得多个最优值,然后选择最好的结果。2增量动态规划(DDDP)DDDP是用逐次逼近方法寻优,每次寻优只在某个状态序列附近的小范围内,用动态规划法进行搜索。其搜索流程是先根据一般经验或常规方法获得初始状态序列作为初始调度线,然后在该初始状态序列的上下各变动一个小范围,这个变动范围成为增量,形成一个带状“廊道”,接着在该廊道内用常规的动态规划寻优,可求得一条新的更接近于最优的状态序列。这样就完成了一轮寻优,然后在新的状态序列上卜•再变动一个增量,并进行寻优。依此逐次进行迭代,直到逼近最优状态序列为止。在迭代过程中,增量可曲大变小;也可根据情况只在初始决策序列的一侧选增量;在各个阶段和上下两侧的增量个数也可以不同,而且增量值的大小也可以不一样。DDDP的寻优过程如图3所示,各图中同一时段两个圈表示状态的间隔即为增量。(a)第一轮寻优过程Oo0•…o0(b)第一轮寻优结果(c)第二轮寻优过程QO©•…Q©©00•…©©(d)第二轮寻优结果DDDP的思想是通过减少每次计算时的离散状态,达到降维的效果,与DPSA一样不能保证所得的解是总体最优,有可能收敛到某一局部最优解。因此可以采用从几个不同的初始状态开始,求出几个“最优解”,然后从中选择一个最好的解。3状态逐密动态规划状态逐密动态规划是在状态空间内先以较低的精度要求,取较少的状态数口,在较稀的区间内寻找最优值。然后以当