动态规划问题的数学原理——如何按部就班就能推导出状态转移方程?

动态规划问题的数学原理——如何按部就班就能推导出状态转移方程?动态规划动态规划是解决多阶段决策过程最优化的一种方法,其基本思想是从终点逐段向始点方向寻找最短路线。生活中平常的事例,即可深刻揭示最短路线的重要特性:如果最短路线在第$K$站通过点$P_k$,则由点$P_k$出发到达终点的这条路线,对于从点$P_k$出发到达终点的所有可能选择

大家好,欢迎来到IT知识分享网。

动态规划

动态规划是解决多阶段决策过程最优化的一种方法,其基本思想是从终点逐段向始点方向寻找最短路线。

生活中平常的事例,即可深刻揭示最短路线的重要特性:

如果最短路线在第 \(K\) 站通过点 \(P_k\) , 则由点 \(P_k\) 出发到达终点的这条路线,对于从点 \(P_k\) 出发到达终点的所有可能选择的不同路线来说,必定也是最短路线。

动态规划的分类

  • 按照决策过程的时间参量是离散/连续区分:离散(多段)决策过程 vs 连续决策过程
  • 按照决策过程的演变是确定/随机区分:确定性决策过程 vs 随机性决策过程
  • 按照上述分类可以得到四种组合:
    • 离散确定性决策过程
    • 离散随机性决策过程
    • 连续确定性决策过程
    • 连续随机性决策过程

多阶段决策问题

  • 由于它的特殊性,可将过程划分为若干互相联系阶段
  • 在它的每一个阶段都需要作出决策,并且一个阶段的决策确定以后,常影响下一个阶段的决策,从而影响整个过程的活动路线;
  • 各个阶段所确定的决策就构成一个决策序列,通常称为一个策略
  • 每一个阶段可供选择的决策往往不止一个,对应于一个策略就有确定的活动效果
  • 多阶段决策问题,就是要在允许选择的那些策略中间,选择一个最优策略,使在预定的标准下达到最好的效果

动态规划的基本概念

阶段(Stage)

把所给问题的过程,恰当地划分成若干个相互联系的阶段,以便于求解。通常用 \(k\) 表示阶段变量。

状态(State)

状态表示某段的出发位置。它既是该段某支路的始点,同时也是前一段某支路的终点。通常一个阶段包含若干个状态。

描述过程状态的变量,称为状态变量。常用 \(x_k\) 表示在第 \(k\) 段的某一状态。第 \(k\) 段状态集合可表示为:

\[X_k = \{x_k^{(1)}, x_k^{(2)}, \dots,x_k^{(i)}, \dots, x_k^{(r)}\} \]

决策(Decision)

决策就是某阶段状态给定以后,从该状态演变到下一阶段某状态的选择。

描述决策的变量,称为决策变量。

常用 \(u_k(x_k)\) 表示第 \(k\) 段当状态处于 \(x_k\) 时的决策变量。决策变量的取值往往限制在某一范围之内,此范围称为允许决策集合。通常以 \(D_k(x_k)\) 表示第 \(k\) 段当状态处于 \(x_k\) 时的允许决策集合。

\[u_k(x_k) \in D_k(x_k) \]

策略(Policy)

由过程的第1阶段开始到终点为止的过程,称为问题的全过程。

由每段的决策 \(u_i(x_i)(i=1,2, \dots,n)\) 组成的决策函数序列就称为全过程策略,简称策略,记为 \(p_{1,n}\)。即:

\[p_{1,n}(x_k)=\{ u_1(x_1), u_2(x_2), \dots, u_n(x_n) \} \]

由第 \(k\) 段开始到终点的过程称为原过程的后部子过程(或称为 \(k\) 子过程)。

其决策函数序列 \(\{ u_1(x_1), u_2(x_2), \dots, u_n(x_n) \}\) 称为 \(k\) 子过程策略,简称子策略。即

\[p_{k,n}(x_k)=\{ u_k(x_k), u_{k+1}(x_{k+1}), \dots, u_n(x_n) \} \]

在实际问题中,可供选择的策略有一定的范围,此范围称为允许策略集合,用 \(P\) 表示。从允许策略中找出的达到最优效果的策略称为最优策略。

指标函数

在多阶段决策过程最优化问题中,指标函数是用来衡量所实现过程的优劣的一种数量指标,它是一个定义在全过程和所有后部子过程上的确定数量函数,常用 \(V_{k,n}\) 表示。即

\[V_{k,n}=V_{k,n}(x_k ,u_k ,x_{k+1} ,\dots, x_{n+1}) \quad 其中\ k=1,2,…,n \]

不同的问题中,指标的含义也不同:距离、利润、成本、产量、资源消耗等。

\(k\) 阶段由状态 \(x_k\) 作出决策 \(u_k(x_k)\) 的所对应的指标称为阶段指标(阶段效益),可记为 \(d_k(x_k, u_k)\)

比如由 点\(x_k\) 到 点\(u_k(x_k)\) 的距离,就是一个阶段指标。

最优指标函数

指标函数 \(V_{k,n}\) 的最优值,称为相应的最优指标函数。记为 \(f_k(x_k)\)

举例: \(f_k(x_k)\) 可以代表从第 \(k\) 段 点\(x_k\) 到 终点\(G\) 的最短距离。


动态规划的基本思想和基本方程

动态规划最优化原理

作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。

可逆过程

顺序解法:假设求点A到点G的最短路线,那么以G为始端,以A为终端的左行解法程序称为顺序解法。

逆序解法:同理。

可逆过程:可以把段次颠倒过来求最优解的多阶段决策过程称为可逆过程。

构成动态规划模型的条件 (通用解法)

建立动态规划模型时,除了要将实际问题恰当地划分若干个阶段(一般是根据时间和空间而划分的)外,主要明确以下四个方面:

1、正确选择状态变量

正确选择状态变量 \(x_k\),使它既能描述过程的状态,又要满足无后效性。

动态规划中的状态与一般所说的状态概念是不同的,它必须具有三个特性:

  • 要能够用来描述受控过程的演变特征。
  • 要满足无后效性。所谓无后效性是指:如果某段状态给定,则在这段以后过程的发展不受前面各阶段状态的影响。
  • 可知性。即是规定的各段状态变量的值,由直接或间接都是可以知道的。

2、确定决策变量及每阶段的允许决策集合

确定决策变量 \(u_k\) 及每阶段的允许决策集合 \(D_k(x_k)={u_k}\)

3、写出状态转移方程

如果给定第 \(k\) 段状态变量 \(x_k\) 的值,则该段的决策变量 \(u_k\) 一经确定,第 \(k+1\) 段状态变量 \(x_{k+1}\) 的值也就完全确定。

\(x_{k+1}\) 的值随 \(x_k\)\(u_k\) 的值的变化而变化的这种对应关系,表示为:

\[x_{k+1} = T_k(x_k, u_k) \]

它表示由 \(k\) 段到 \(k+1\) 段的整体转移规律,称为状态转移方程。

4、根据题意,列出指标函数关系,并要满足递推性。

正确列出指标函数 \(V_{k,n}\) 关系,必须使它具有三个性质:

  • 它是定义在全过程和所有后部子过程上的数量函数;
  • 要满足递推关系。 即:
\[V_{k,n}(x_k, u_k, x_{k+1}, \dots, x_{n+1})= \Psi[x_k, u_k, V_{k+1, n}(x_{k+1, \dots, x_{n+1}})] \]

  • $ \Psi[x_k, u_k, V_{k+1, n}]$ 对其变元 \(V_{k+1,n}\) 来说要严格单调。

常见的指标函数是取各段指标和的形式。即

\[V_{k,n} = \sum_{j=k}^{n}v_j(x_j, u_j) \]

其中 \(v_j(x_j, u_j)\) 表示第 \(j\) 段的指标。它显然是满足上述三个性质的。所以上式可写成:

\[V_{k,n} = v_k(x_k,u_k) + V_{k+1, n}\left[x_{k+1}, \dots, x_{n+1}\right] \]

当初始状态给定,过程的策略也确定了时,指标函数也就确定了。

因此,指标函数是初始状态和策略的函数,记为 \(V_{k,n}[x_k, p_{k,n}(x_k)]\)。故上面递推关系又可写成:

\[V_{k,n} = v_k(x_k,u_k) + V_{k+1, n}[x_{k+1}, p_{k+1, n}] \]

因其子策略 \(p_{k,n}(x_k)\) 可看成是由决策 \(u_k(x_k)\)\(p_{k+1,n}(x_{k+1})\) 组合而成。即

\[p_{k,n}(x_k) = \{u_k(x_k), p_{k+1,n}(x_{k+1}) \} \]

对于最优策略的指标函数值,有

\[f_k(x_k) = V_{k,n}[x_k, p^*_{k,n}(x_k)] = \underset{p_{k,n}}{opt}\ V_{k,n}[x_k, p_{k,n}(x_k)] \]

其中 \(P^*_{k,n}(x_k)\) 表示初始状态为 \(x_k\) 的后部子过程所有子策略中的最优子策略

由上述四个条件(组成部分)得出动态规划的基本方程:

动态规划的基本方程

若从 \(x_k\) 出发,有:

\[\begin{align} \underset{p_{k,n}}{opt}\ V_{k,n}(x_k, p_{k,n}) &= \underset{\{u_k, p_{k+1,n}\}}{opt}\ \{v_k(x_k, u_k) + V_{k+1, n}(x_{k+1}, p_{k+1, n})\} \\ &= \underset{u_k}{opt}\ \{v_k(x_k, u_k) + \underset{p_{k+1,n}}{opt}\ V_{k+1, n}\} &(k=n,\ n-1,\ \dots,\ 1) \end{align} \]

于是可得:

\[\begin{align} f_k(x_k) &= \underset{p_{k,n}}{opt}\ V_{k,n}(x_k, p_{k,n}) \\ &= \underset{u_k}{opt}\ V_{k,n}(x_k, u_k, p^*_{k+1,n}) \\ &= \underset{u_k\in D_k(x_k)}{opt}\ \{v_k(x_k, u_k) + f_{k+1}(x_{k+1})\} &(k = n,\ n-1,\ \dots,\ 1) \end{align} \]

以及:

\[f_{n+1}(x_{n+1}) = 0 \]

以上是逆序解法的基本方程。

其递推过程从 \(k = n\) 开始,逐段向前推移,一直到求出 \(f_1(x_1)\) 时,就得到了整个过程的最优解,包括最优策略和相应的最优指标函数值。

问题举例

上面的公式太抽象了,我们来看看在实际问题中是怎么操作的:

机器负荷分配问题

某种机器,可以在高低两种不同的负荷下进行生产。

在高负荷下进行生产时,产品的年产量 \(s_1\) 和投入生产的机器数量 \(u_1\) 的关系为:

\[s_1 = g (u_1) \]

这时,机器的年折损率为 \(a\),即如果年初完好机器的数量为 \(u\),到年终时完好的机器就为 \(au\)\(0<a<1\)

在低负荷下生产时,产品的年产量 \(s_2\) 和投入生产的机器数量 \(u_2\) 的关系为:

\[s_2 = h(u_2) \]

相应的机器的年折损率为 \(b\) , \(0<b<1\)

假定开始生产时完好的机器数量为 \(x_1\)。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。

设机器在高负荷下生产的产量函数为 \(S_1=8u_1\),折损率为 \(a=0.7\);

在低负荷下生产的产量函数为 \(S_2=5u_2\) ,年折损率为 \(b=0.9\)

开始生产时完好机器的数量 \(x_1=1000\) 台。按题意要安排好五年的生产计划,使产品的总产量最高。

问题的动态规划模型:

  • 阶段序数 \(K\) 表示年度。
  • 状态变量 \(x_k\) 为第 \(K\) 年度初拥有的完好机器数量,亦为第 \(K-1\) 年度末时的完好机器数量。
  • 决策变量 \(u_k\) 为第 \(K\) 年度中分配高负荷下生产的机器数量。则 \(x_k-u_k\) 为该年度中分配在低负荷下生产的机器数量。
    • 这里 \(x_k\)\(u_k\) 均取连续变量。如 \(u_k=0.3\),表示一台机器在该年度只有 \(3/10\) 的时间在高负荷下工作。
  • 状态转移方程为:
\[\begin{align} x_{k+1} &= au_k+b(x_k-u_k) \\ &= 0.7u_k + 0.9(x_k – u_k) &(k=1,2,…,5) \end{align} \]

  • \(k\) 阶段的允许决策集合\(D_k(x_k) = \{u_k| 0 \le u_k \le x_k \}\)
  • 所以,指标函数\(V_{1,5} = \sum\limits_{k=1}^5v_k(x_k, u_k)\)
  • \(f_k(x_k)\) 表示由 \(x_k\) 出发采用最优分配方案到第5年度结束这段期间的产品产量,根据最优化原理,则有递推关系式
\[\begin{cases} f_6(x_6) = 0 \\ f_k(x_k) = \underset{u_k \in D_k(x_k)}{\max}{8u_k+5(x_k-u_k) +f_{k+1}[0.7u_k+0.9(x_k-u_k)]} &k=1,2,3,4,5 \end{cases} \]

  • 逆序计算,得 \(u_k = \{0, 0, x_3, x_4, x_5\}\),故最高产量为 23700。

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
  • 阶段序数:第 \(k\) 步移动棋子,假设移动后处于 \((i,j)\)格,则用 \(g_k(i,j)\) 表示在 \((i,j)\) 格获得的礼物数,\(k = 1, 2, …, m+n-1\)
  • 状态变量\(x_k\) 表示为 \((i,j)\)格 移动到 \((m,n)\)格 的总礼物数量
  • 决策变量\(u_k\) 表示下一步(\(k+1\)步,选择移动到 \((i+1,j)\)格 或者 \((i,j+1)\)格)获得的礼物数量
  • 状态转移方程\(x_{k+1} = x_k – u_k\)\(x_{k+1}\) 表示从第 \(k+1\) 步所处的格子 到 \((m,n)\)格 的总礼物数(因为是逆序解法,也可以表示为 \(x_{k} = u_k + x_{k+1}\)
  • 允许决策集合\(D_k(x_k) = \{g_k(i+1,j), g_k(i, j+1) | 0 < i \le m, 0 < j \le n\}\)
  • 最优递推式\(f_k(x_k)\) 表示 \((i,j)\)格 移动到 \((m,n)\)格 的最优总礼物数量
\[\begin{cases} f_k(x_k) &= \underset{u_k \in \{(i+1, j), (i, j+1)\}}{\max} \{g_k(u_k) + f_{k+1}(x_{k+1})\} &, k=m+n-2, \dots, 1 \\ f_{m+n-1}(x_{m+n-1}) &= g_{m+n-1}(m,n) \end{cases} \]

  • 代码实现:

    class Solution:
        def maxValue(self, grid: List[List[int]]) -> int:
            m = len(grid)
            n = len(grid[0])
            dp = [[0] * n] * m	# dp[i][j]: (i, j) 到 (n, n) 的最优礼物数
            
            for i in range(m-1, -1, -1):
                for j in range(n-1, -1, -1):
                    if i == m-1 and j == n-1:
                        dp[m-1][n-1] = grid[m-1][n-1] 
                    down  = dp[i+1][j] + grid[i][j] if i != m-1 else 0 	# 状态转移方程 x_k = x_{k+1} +u_k 
                    right = dp[i][j+1] + grid[i][j] if j != n-1 else 0 		# 注意i,j的边界条件
                    decision_set = {down, right}						# 允许决策集合
                    dp[i][j] = max(decision_set)						# 最优递推式
            return dp[0][0]
    

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/27790.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信