动态规划

Posted on In

拿着以前的笔记复习一下~

概念

决策可以分为静态决策与动态决策。

其中静态决策又被称为“一次性决策”，即根据输入进行决策判断，得到相应的输出结果。如图所示：

1
2
3
4
5
6
7
8
9
10
         u决策
           +
           |
        +--v--+
x1输入+-->     +-->x2输出
        +--+--+
           |
           v
        z决策效应

动态决策也叫“多阶段决策”

1
2
3
4
5
6
7
8
9
       u1         u2                 uk                     un
       |          |                  |                      |
    +--v--+    +--v--+            +--v--+                +--v--+
x1-->  T1 +-x2-> T2  +-x3->...xk-->  Tk +-x(k+1)->...xn-->  Tn  +-->x(n+1)
    +--+--+    +--v--+            +--v--+                +--v--+
       |          |                  |                      |
       v          v                  v                      v
       r1         r2                 rk                     rn

也可以记为\(X_{k+1} = T_k(x_k,u_k)\)，若系统在 k 阶段之后的决策只与\(x_k\)有关，而与之前做过的决策无关，则这样的决策过程称为具有无后效性的多段决策过程。

多段决策过程从第 k 步到最后一步的过程称为 k-后部子过程，简称 k-子过程

动态规划模型

\[ \text{opt}_{u_1 \cdots u_n} R = \bigoplus_{k=1}^n r_k (x_k,u_k) \]

\[\left\{ \begin{aligned} &x_{k+1} = T_k(x_k,u_k) \\ &x_k \in X_k \\ &u_k \in U_k \\ &k = 1 \sim n \end{aligned} \right. \]

opt 表示求优过程

Xk 为一个集合，表示在 k 阶段时状态所有可能取值的范围，因此称为状态可能集合

Uk 为一个集合，表示在 k 阶段时决策所有可能取值的范围，称为决策允许集合

一般对于不同的状态，可以选择的决策范围也不同，因此决策允许集合也记为\(U_k(x_k)\)

解决动态规划问题需要确定以下几个步骤：

1、确定阶段与阶段变量

2、明确状态变量与状态可能集合

3、确定决策变量与决策允许集合

4、确定状态转移方程

5、明确阶段效应和目标

其中重要的是确定状态转移方程与明确阶段相应和目标。

状态转移方程即在状态\(x_k\)时做出了决策\(u_k(x_k)\)之后系统状态的变化，这个变化会影响之后的决策过程。因此必须明确状态的转移过程，即根据问题的内在关系，明确\(x_{k+1}=T_k(x_k,u_k)\)中的函数Tk()。

阶段效应\(r_k(x_k,u_k)\)是在阶段k以\(x_k\)为起点发出决策\(u_k\)所产生的后果。明确\(r_k,x_k,u_k\)才能构成目标函数，目标函数由具体问题决定，例如根据具体问题确定求最大还是最小。

多段决策的特点

1、每个阶段都要进行决策

2、相继进行的阶段决策构成决策序列

3、前一阶段的终止状态是后一阶段的起始状态

阶段 k 的最优决策不应该只是当前阶段的最优决策，而应该是 k-后部子过程的最优决策。

最优性原理

无论初始状态和初始决策如何，对于之前所有决策造成的某一状态而言，剩余的决策序列必须构成最优策略。

最优性原理的含义：

1、最优策略的任何一部分子策略，也是相应最初状态的最优策略。

2、每个最优策略只能由最优子策略构成。

因此对于无后效多段决策过程而言，按照 k-后部子过程最优的原则来求各阶段的最优决策，这样构成的决策序列一定具有最优性原理的性质。

贝尔曼函数

阶段 k，从状态\(x_k\)出发，执行最优决策序列，最终到达终点时，整个 k-后部子过程中的目标函数取值被称为条件最优目标函数，即贝尔曼函数。

\[f_k(k_k)=opt_{u_k~u_n} \sum^{n}_{i=n} r_i(x_i,u_i) | k\in {1,2,3,...,n}\]

动态规划基本方程、贝尔曼方程

在阶段 k时，执行任意决策\(u_k\)后的状态是\(x_{k+1} = T_k(x_k,u_k)\)。这时 k-后部子过程就缩小为了 k+1 后部子过程。根据最优性原理，k+1 后部子过程应该采取最优策略，由于无后效性，k-后部子过程的目标函数值为 \(r_k(x_k,u_k)+f_{k+1}(T_k(x_k,u_k))\)。根据条件最优目标函数的定义，有：

\[f_k(x_k) = opt_{u_k}{ r_k(x_k,u_k) + f_{k+1}(T_k(x_k,u_k)) }\]

此方程即为动态规划基本方程。

动态规划求解

1、逆序求出条件最优目标函数值集合与条件最优决策集合

2、顺序求最优目标值、最优策略和最佳路线

逆序求集合：

\[ \begin{aligned} k=n, &f_n(x_n) = \text{opt}_{u_n}\{r_n(x_n,u_n) + f_{n+1}(x_{n+1})\} \\ & \because f_{n+1}(x_{n+1}) = 0 \\ & \therefore 原式 = \text{opt}_{u_n}\{r_n(x_n,u_n)\} \\ & \Rightarrow f_n(x_n) = r_n(x_n,u_n^\prime(x_n)) \\\\ k=n-1, &f_{n-1}(x_{n-1}) = \text{opt}_{u_{n-1}}\{r_{n-1}(x_{n-1},u_{n-1}) + f_{n}(x_{n})\} \\ & \because f_n(x_n) 已求出，因此根据 x_n = T_{n-1}(x_{n-1},u_{n-1})\\ & 可得 n-1 时的 x_{n-1} \in X_{n-1} 对应的条件最有目标函数值\\ & f_{n-1}(x_{n-1}) \\ & \Rightarrow \{f_{n-1}(x_{n-1}),u_{n-1}^\prime(x_{n-1})|x_{n-1} \in X_{n-1}\} \\\\ k=1, &f_1(x_1) = \text{opt}_{u_1}\{r_1(x_1,u_1) + f_2(x_2)\} \\ & \{f_1(x_1),u_1^\prime(x_1)|x_1 \in X_1\} \\ \end{aligned} \]

顺序求目标值：

\[ \begin{aligned} x_1 确定, &R^* = f_1(x_1) \qquad u^*_1(x_1) = u_1^\prime(x_1) \\ x_1 不确定, &R^* = \text{opt}_{x_1 \in X_1}\{f_1(x_1)\} = f_1(x_1^*) \\ & 得 x_1^*,带入求 x_2^,以此类推得 x_n^*,x_{n+1}^* \end{aligned} \]