下载掌阅APP，畅读海量书库
立即打开
动态规划是美国数学家Bellman等人所提出的一种寻优算法，通过将问题划分成多个阶段进行逐一求解，并通过保存各个阶段的计算结果来避免重复计算，最终实现在全局寻优中节省计算时间的目的。在数学本质上，动态规划与庞特里亚金极小值原理具有等效性，通过Hamilton-Jacobi-Bellman（HJB）方程可以将两者联系起来，DP求解的最优轨迹与相应的协变量轨迹与极小值原理近似。多阶段决策过程是指该问题可以分为若干个互相联系的子阶段，在每一个阶段都需要做出决策，一个阶段的决策确定以后，常常会影响到下一个阶段的决策，从而就完全确定了该问题的决策序列。将解决这种多阶段决策问题最优化的过程称为动态规划，其原理如图 3.1 所示。Bellman提出的多阶段决策的动态规划问题具有无后效性，当前与未来的收益仅决定于当前的状态，不依赖于过去的状态和决策。基于无后效性的动态规划问题存在最优性原理，即在最优轨迹上，不管之前的阶段状态和决策如何，就当前阶段的决策所形成的状态而言，余下的所有决策必然构成最优策略，最优化策略的子策略总是最优的。
图3.1 多阶段决策过程示意图
动态规划算法是解决多阶段决策最优化问题的一种思想或途径，而不是某一种特殊算法。不像搜索或数值优化算法那样，如模拟退火算法、粒子群算法等，都有一个明确的数学表达式。针对不同的问题，建立状态转移的递推关系表达式，将整个问题分解成若子问题，通过逆向求解的方式获得最优的代价函数，根据初始状态正向求解出整个过程的最优决策序列。其求解过程和基本模型如下。
对于一个 N 阶段的离散控制系统，其系统状态方程为：
式中， x k 为系统的状态变量 x k ∈ Ω k ， x 0 为系统的初始状态， u k 为 x k 对应的系统控制变量， u k ∈ U k ， k ＝ 0，1，2，…， N －1。
系统初始状态 x 0 在 0 到 N －1 控制序列 u ＝｛ u 0 ， u 1 ， u 2 ，…， u N －1 ｝的作用下，系统的目标函数 J 如式（3.2）所示。
式中， L k （ x k ， u k ）为 k 阶段的阶段指标函数。
该多阶段决策的过程就是寻找一个控制序列
，使得整个过程的目标函数
J
最优，该控制序列即为动态规划的最优解，在
u
*
的作用下，目标函数如式（3.3）所示。
动态规划的最优性原则指，对于状态
，从
i
＋ 1 到
N
控制序列
为余下子问题的最优决策序列，那么在逆向求解第
i
阶段的最优目标函数和决策时，可转化为式（3.4）。
式中， J * （ x i ＋1 ）为 i ＋1 阶段 x i ＋1 状态下到 N 阶段的最优目标函数。由式（3.4）可知，动态规划逆向计算过程，从 N －1 阶段开始，在已知任一状态下 J * （ x N －1 ）条件下，可计算 J * （ x N －2 ），以此类推到初始阶段 J * （ x 0 ），通过逆向求解单步最优子问题来获得全局最优的控制序列，如图 3.2 所示。
图3.2 逆向求解过程示意图
由图 3.2 可知，当动态规划的逆向求解过程从阶段
N
一直计算到阶段 0，此时逆向求解结束。如果初始状态
x
0
确定，根据逆向过程保存的每一阶段离散状态所对应的最优控制解，正向依次求得最优控制序列
。