《常用降维动态规划》由会员分享，可在线阅读，更多相关《常用降维动态规划（4页珍藏版）》请在金锄头文库上搜索。
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、状态序列为止。在迭代过程中，增量可由大变小；也可根据情况只在初始决策序列的一侧选增量；在各个阶段和上下两侧的增量个数也可以不同，而且3所示，各图中同一时段增量值的大小也可以不一样。DDDP两个圈表示状态的间隔即为增量。（c）第二轮寻优it粗2）第二轮丫比詰采DDDP的思想是通过减少每次计算时的离散状态，达到降维的效果，与DPSA 一样不能保证所得的解是总体最优，有可能收敛到某一局部最优解。因此可以采用从几个不同的初始状态开始，求出几个“最优解”，然后从中选择一个最好的解。3状态逐密动态规划状态逐密动态规划是在状态空间内先以较低的精度要求，取较少的状态数目，在较稀的区间内寻找最优值。然后以当前最
5、优解为基础，在附近状态序列上 下一定范围内，加密搜索状态以提高精度，再一次优选。这样逐步加密状态，多 次选优，直至满足精度要求。4逐步优化算法（POA）加拿大学者Howson和Sancho N G R 根据贝尔曼最优化原理的思想提出 了逐步最优化原理：“最优路线具有这样的性质，每对决策集合相对于它的初始 值和终止值来说是最优的”。逐步优化算法便是根据这个原理设计的，主要用于 求解多维动态规划问题。该算法将多阶段决策问题分解成若干个子问题，子问题之间由系统状态联系，每个子问题仅考虑单个时段的状态及相邻两时段的子目标 值，逐个时段进行寻优，直到收敛。假设对 T个时段进行求解，其寻优过程如图3.2所示。水库调度优化，如果电站数目较多计算过程仍然存在“维数灾”问题。同时由于POA算法要逐时段求解大量非线性优化子问题，求解子问题算法的好坏、快慢 对整个计算过程的时间和结果优劣影响很大。
