常用降维动态规划

《常用降维动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案常用降维动态规划1逐次逼近动态规划（DPSA）逐次逼近动态规划是求解多维问题的有效方法之一，它的基本思想是把带有若干决策变量的问题分解成仅带有1个决策变量的若干个子问题，每个子问题比原来的总问题具有较少的状态变量，从而大大节省状态存储量及计算工作量，便于计算机求解。对于多库联调优化问题，在确定初始可行调度线后采用DPSA求解的过程如下：（1）先假定第2个到最后一个水库的调度过程全部固定，对第1个水库进行优化，这时相当于单库优化调度，可以通过常规动态规划找到第1个水库的最优调度过程，此时其它水库仅进行简单的水务计算

2、即可。计算完成后用最优结果替代初始解中第1个水库的调度过程。（2）假定第1个，第3个到最后一个水库的调度过程全部固定，求第2个水库的最优过程，这也相当于单库优化调度，同样通过常规动态规划找到第2个水库的最优调度过程。并将其最优结果替代初始解中第2个水库的调度过程。（3）依次类推，直至最后一个水库计算完成。此时初始可行解依次被各次的单库最优结果替代，一轮计算完成。（4）以上一轮最优结果为基础，重新依次计算单个电站的最优过程，并替换总体最优结果，反复轮流优选，直至收敛。DPSA的思想是通过减少每次参与计算的电站数目，达到降维效果

3、，其搜索结果精度与初始状态序列有关，因此它不能保证在所有情况下都收敛到真正的总体最优解，求解过程中可以从多个不同的初始状态(库群初始调度过程)开始，求得多个最优值，然后选择最好的结果。2增量动态规划（DDDP）DDDP是用逐次逼近方法寻优，每次寻优只在某个状态序列附近的小范围内，用动态规划法进行搜索。其搜索流程是先根据一般经验或常规方法获得初始状态序列作为初始调度线，然后在该初始状态序列的上下各变动一个小范围，这个变动范围成为增量，形成一个带状“廊道”精彩文档实用标准文案，接着在该廊道内用常规的动态规划寻优，可求得一条新的更

4、接近于最优的状态序列。这样就完成了一轮寻优，然后在新的状态序列上下再变动一个增量，并进行寻优。依此逐次进行迭代，直到逼近最优状态序列为止。在迭代过程中，增量可由大变小;也可根据情况只在初始决策序列的一侧选增量;在各个阶段和上下两侧的增量个数也可以不同，而且增量值的大小也可以不一样。DDDP的寻优过程如图3所示，各图中同一时段两个圈表示状态的间隔即为增量。DDDP的思想是通过减少每次计算时的离散状态，达到降维的效果，与DPSA一样不能保证所得的解是总体最优，有可能收敛到某一局部最优解。因此可以采用从几个不同的初始状态开始，求出

5、几个“最优解”，然后从中选择一个最好的解。3状态逐密动态规划状态逐密动态规划是在状态空间内先以较低的精度要求，取较少的状态数目，在较稀的区间内寻找最优值。然后以当前最优解为基础，在附近状态序列上下一定范围内，加密搜索状态以提高精度，再一次优选。这样逐步加密状态，多次选优，直至满足精度要求。4逐步优化算法（POA）加拿大学者Howson和SanchoNGR根据贝尔曼最优化原理的思想提出了逐步最优化原理：“最优路线具有这样的性质，每对决策集合相对于它的初始值和终止值来说是最优的”精彩文档实用标准文案。逐步优化算法便是根据这个原理

6、设计的，主要用于求解多维动态规划问题。该算法将多阶段决策问题分解成若干个子问题，子问题之间由系统状态联系，每个子问题仅考虑单个时段的状态及相邻两时段的子目标值，逐个时段进行寻优，直到收敛。假设对T个时段进行求解，其寻优过程如图3.2所示。POA算法的每个子问题实际上是一个带约束的多维非线性规划问题，对于水库调度优化，如果电站数目较多计算过程仍然存在“维数灾”问题。同时由于POA算法要逐时段求解大量非线性优化子问题，求解子问题算法的好坏、快慢对整个计算过程的时间和结果优劣影响很大。精彩文档