布尔控制网络最小能耗问题的半张量方法

Semi-Tensor Method for Minimum Energy Consumption Problem in Boolean Control Networks

摘要: 布尔网络是研究生物系统和基因调控网络的一种重要模型。本文利用矩阵半张量积的方法，给出逻辑动态系统的代数状态空间表示和最小能耗问题目标泛函的一个新的表达形式，并应用动态规划法求解其最优控制问题，最后举例说明算法的有效性。

Abstract: Boolean network is an important model to study biological systems and gene regulatory networks. In this paper, a new expression of the object functional of the algebraic state space representation and the minimum energy consumption problem of the logical dynamical system is given by using the matrix half tensor product method. Then the dynamic programming method is used to discuss the optimization problem. Finally, an example is given to illustrate the effectiveness of the proposed algorithm.

1. 引言

布尔网络是描述人工智能系统、神经网络系统、基因调控网络等的有效工具之一。早在上世纪60年代，Jacob和Monod发现任何细胞的调控基因像开关一样，能打开或关闭其他基因。1969年，Kauffman首次提出用布尔网络描述细胞和基因的调控网络，将基因的表达和不表达分别用逻辑值“1”和“0”表示，基因之间复杂的关系和作用通过简单的逻辑关系表达，这种理想化的模型不仅具有高度抽象性，而且反映了系统丰富的动力学行为。虽然基因的调控网络可用逻辑表达式表示其演化过程，但它不能融入基本数学运算框架，在系统分析及综合时也不方便。2011年，程代展教授提出了矩阵半张量积的概念 [1] ，作为普通矩阵乘法的推广，不再要求前一个矩阵的列数等于后一个矩阵的行数，还保持了普通矩阵乘法的基本性质。利用矩阵半张量积，逻辑动态方程可用矩阵表达成代数形式，进而，可利用控制理论中已有的数学工具和方法，有效地解决逻辑动态系统问题。程代展教授及其团队在专著 [2] [3] [4] 中详细介绍了矩阵半张量积的定义和性质，并讨论其在非线性系统、布尔网络、模糊逻辑等领域中的应用。利用半张量积解决布尔网络问题已有了一些优秀成果，如：逻辑动态系统的拓扑结构，逻辑控制系统的能控性、能观性、稳定性、镇定性、干扰解耦、最优控制等。

布尔网络的最优控制问题也是一个倍受关注的主题，应用半张量积的方法研究最优控制问题也有了一些结果，如文献 [5] [6] 基于网络的环结构，研究了布尔控制网络和多值逻辑控制网络的最优性条件，文献 [7] [8] 研究了单输入和多输入的布尔控制网络的一种Mayer型最优控制问题，文献 [9] 研究了无穷时域概率布尔网络最优控制问题等。在最优控制理论中，最小能量控制是现代控制中最基本、最重要的问题之一。经查阅相关文献，对布尔网络最小能量控制的研究比较少，其原因在于将逻辑形式和代数形式在统一的框架下处理有一定的难度。本文利用半张量积的方法研究布尔网络的最小耗能问题，在将布尔网络的逻辑动态表达式转化为代数状态表达式的基础上，给出目标泛函半张量积的表达形式，利用动态规划方法求解相应的最优控制问题，最后通过具体的算例说明算法的有效性。

2. 预备知识

2.1. 符号说明

· $N^{+}$ 表示正整数集合。

· ${ℝ}^n$ 是实数域上 $n$ 维向量空间。

· ${\mathcal{M}}_{n\times m}$ 为 $n\times m$ 实矩阵集合。

· ${\Delta }_n:=\left\{{\delta }_n^i|i=1,2,\cdots ,n\right\}$ ，其中 ${\delta }_n^i$ 为单位矩阵 $I_n$ 的第 $i$ 列，特别地 ${\Delta }_2=\Delta$ 。

· 矩阵 $L\in {\mathcal{R}}_{{}^{n\times m}}$ 称为逻辑矩阵，若它的列 $Col\left(L\right)\subset {\Delta }_n$ ，记 ${\mathcal{L}}_{n\times m}$ 为 $n\times m$ 阶逻辑矩阵集合。

· $L=\left[{\delta }_n^{i_1},{\delta }_n^{i_2},\cdots ,{\delta }_n^{i_m}\right]\in {\mathcal{L}}_{n\times m}$ ，记为 $L={\delta }_n\left[i_1,i_2,\cdots ,i_m\right]$ 。

· 逻辑变量 $x\in \mathcal{D}:=\left\{0,1\right\}$ ，将逻辑值用二维向量表示为 $1\sim {\delta }_2^1,0\sim {\delta }_2^2$ ，即逻辑变量 $x\sim \hat{x}\in \Delta =\left\{{\delta }_2^1,{\delta }_2^2\right\}$ 。

2.2. 半张量矩阵的定义及性质

矩阵半张量积是一种新的矩阵乘法，它是普通矩阵乘法的推广，推广后的乘法不仅保持了普通矩阵乘法的主要性质，还具有伪交换性。

定义2.2.1 [3] ：设 $A\in {\mathcal{M}}_{n\times m},B\in {\mathcal{M}}_{p\times q}$ ，记 $m$ 与 $p$ 的最小公倍数为 $\alpha =lcm\left(m,p\right)$ ，则矩阵 $A$ 和 $B$ 的左半张量积定义为

$A⋉B:=\left(A\otimes I_{\alpha /m}\right)\left(B\otimes I_{\alpha /P}\right)$ .

注2.2：当 $m=p$ 时，矩阵 $A,B$ 满足等维条件，半张量积退化为普通矩阵乘法， $\otimes$ 是矩阵的Kronecker积(亦称张量积)。下文所说的半张量积均为左半张量积。

命题2.2.1 [3] ：若 $A,B,C\in {\mathcal{M}}_{n\times m}$ ，则 $⋉$ 满足：

1) 分配律

$\left(A+B\right)⋉C=A⋉C+B⋉C$

$C⋉\left(A+B\right)=C⋉A+C⋉B$ .

2) 结合律

$\left(A⋉B\right)⋉C=A⋉\left(B⋉C\right)$ .

3) 转置

${\left(A⋉B\right)}^{\text{T}}=B^{\text{T}}⋉A^{\text{T}}$ .

为了进一步刻画和应用半张量积，定义如下换位矩阵。

定义2.2.2 [4] ：换位矩阵 $W_{\left[n,m\right]}$ 是一个 $nm\times nm$ 的矩阵，它的行和列是由双指标 $\left(i,j\right)$ 标注，列是按照索引 $Id\left(i,j;n,m\right)$ 排列，行是双指标 $\left(I,J\right)$ 标注按照索 $Id\left(I,J;m,n\right)$ 排列，并且位于 $\left[\left(I,J\right),\left(i,j\right)\right]$ 元素的值为

$w_{\left(I,J\right),\left(i,j\right)}=\{\begin{array}{l}1,I=i,J=j\\ 0,其他\end{array}$ .

当 $n=m$ ，记 $W_{\left[n\right]}=W_{\left[n,n\right]}$ 。

通过换位矩阵，引入半张量积的重要性质－伪交换性。

命题2.2.2 [4] ：1) 设 $X\in {ℝ}^t$ 为列向量， $A$ 为矩阵，则

$X⋉A=\left(I_t\otimes A\right)⋉X$ .

2) 设 $Y\in {ℝ}^t$ 为行向量， $A$ 为矩阵，则

.

3) 设两个列向量 $X\in {ℝ}^n,Y\in {ℝ}^m$ ，则

.

4) 设两个行向量 $X\in {ℝ}^n,Y\in {ℝ}^m$ ，则

.

命题2.2.2使矩阵乘法有了一定的可交换性，称为伪交换性。

3. 布尔控制网络最小能耗问题

布尔网络是一种理想化的模型，用于研究基因调控和细胞分化过程，基因的状态分为表达和不表达，用1和0表示，其网络每个基因之间的相互作用通过布尔函数描述。对于含有 $n$ 结点和 $m$ 个控制输入的布尔网络，用 $\mathcal{D}:=\left\{0,1\right\}$ 表示取值集合。设 $x_i\left(k\right)\left(i=1,2,\cdots ,n\right)$ 表示第 $i$ 个结点 $k$ 时刻基因的状态，

$u_i\left(k\right)\left(i=1,2,\cdots ,m\right)$ 表示 $m$ 个控制输入， $k+1$ 时刻的基因状态 $x\left(k+1\right)={\left(x_1\left(k+1\right),\cdots ,x_n\left(k+1\right)\right)}^{\text{T}}$ 完全由 $k$ 时刻各结点的基因状态 $x\left(k\right)={\left(x_1\left(k\right),\cdots ,x_n\left(k\right)\right)}^{\text{T}}$ 按已知的传播机理传播，用布尔函数 $f_i\left(x\left(k\right),u\left(k\right)\right)\left(i=1,2,\cdots ,n\right)$ 来描述，故控制状态方程可以描述为

$\{\begin{array}{l}{x}_1\left(k+1\right)=f_1\left(x_1\left(k\right),\cdots ,x_n\left(k\right),u_1\left(k\right),\cdots ,u_m\left(k\right)\right)\\ x_2\left(k+1\right)=f_2\left(x_1\left(k\right),\cdots ,x_n\left(k\right),u_1\left(k\right),\cdots ,u_m\left(k\right)\right)\\ ⋮\\ x_n\left(k+1\right)=f_n\left(x_1\left(k\right),\cdots ,x_n\left(k\right),u_1\left(k\right),\cdots ,u_m\left(k\right)\right)\end{array}k=0,1,\cdots$ (1)

其中， $x_i\left(k\right)\in \mathcal{D}\left(i=1,2,\cdots ,n\right)$ ， $u_i\left(k\right)\in \mathcal{D}\left(i=1,2,\cdots ,m\right)$ ； $f_i:{\mathcal{D}}^{n+m}\to \mathcal{D}$ 。令容许控制集为

。

最优控制问题(P)：寻找最优控制 $u^{*}\in {\mathcal{U}}_{ad}$ ， $u^{*}$ 满足使系统状态从给定的初始状态 $x\left(0\right)={\left(x_1\left(0\right),\cdots ,x_n\left(0\right)\right)}^{\text{T}}$ 在 $s$ 时刻运行到给定的终端状态 $x\left(s\right)={\left(x_1\left(s\right),\cdots ,x_n\left(s\right)\right)}^{\text{T}}$ ，并使系统的能耗最小，即

$J\left(u\right)={\displaystyle \underset{k=0}{\overset{s-1}{\sum }}{u}^{\text{T}}\left(k\right)Qu\left(k\right)}\to \min$ (2)

其中， $Q$ 为 $m\times m$ 维的正定对称矩阵，为简便，我们这里考虑 $Q$ 为正定的对角矩阵，各对角元的大小表达控制分量的权重。

此最优控制问题既包含了状态系统的逻辑运算，又包含了性能指标中的代数运算。用单一的逻辑网络或一般状态系统的最优控制方法不能处理。为了求解此问题，我们考虑用矩阵半张量积的方法处理，因矩阵半张量积这一工具可以将逻辑动态网络转化为代数状态方程形式。

4. 布尔控制网络最小能耗问题的半张量方法表示及问题的求解

4.1. 半张量积的方法表示布尔控制网络最小能耗问题

为了应用半张量积方法，引入如下定义及引理：

定义4.1.1 [4] ：设 $X=\left(x_1,x_2,\cdots ,x_s\right)$ 是一个行向量， $Y={\left(y_1,y_2,\cdots ,y_t\right)}^{\text{T}}$ 是一个列向量。

1) 如果 $t$ 是 $s$ 的因子，即 $s=t\times n$ ，则 $n$ 维行向量

${\langle X,Y\rangle }_L:={\displaystyle \underset{k=1}{\overset{t}{\sum }}{X}^k{y}_k\in {ℝ}^n}$

称为 $X$ 和 $Y$ 左半张量内积， $X=\left(X^1,X^2,\cdots ,X^t\right)$ ， $X^i\in {ℝ}^n,i=1,2,\cdots ,t$ 。

2) 如果 $s$ 是 $t$ 的因子，即 $t=s\times n$ ，则 $n$ 维行向量

${\langle X,Y\rangle }_L:={\left({\langle Y^{\text{T}},X^{\text{T}}\rangle }_L\right)}^{\text{T}}\in {ℝ}^n$

也称为 $Y$ 和 $X$ 左半张量内积。

引理4.1.1 [10] ：设 $x_1,\cdots ,x_n$ 是 $n$ 个逻辑变量，对于任意的 $n$ 元布尔函数 $f\left(x_1,\cdots ,x_n\right):{\mathcal{D}}^n\to \mathcal{D}$ ，存在唯一的逻辑矩阵 $M_f\in {\mathcal{L}}_{2\times 2^n}$ ，使得

$f\left(x_1,\cdots ,x_n\right)=M_f{⋉}_{i=1}^n{\hat{x}}_i,{\hat{x}}_i\in \Delta$

上式称为布尔函数 $f$ 的代数形式。

根据引理4.1.1、定义4.1.1和半张量矩阵的运算性质，我们可以将问题(P)等价于如下问题：

设 $p_l^j\left(j=1,\cdots ,m;l=1,2,\cdots ,2^{m-1}\right)$ 为 $m$ 个指标按照 $Id\left({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_m;n_1=\cdots =n_m=2\right)$ 的自然索引 ${\lambda }_j=1$ 时的第 $l$ 个元素对应的单指标索引。

状态方程

$\hat{x}\left(k+1\right)=L⋉\hat{u}\left(k\right)⋉\hat{x}\left(k\right)$ . (3)

初始状态 $\hat{x}\left(0\right)={\hat{x}}_0$ 和终端 $\hat{x}\left(s\right)={\hat{x}}_d$ 给定，为容许控制集。目标泛函为

$J\left(\hat{u}\right)={\displaystyle \underset{k=0}{\overset{s-1}{\sum }}{\langle {\left(diagQ\right)}^{\text{T}},{\left({\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^1}}\right)}^{\text{T}}{\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^2}}\right)}^{\text{T}}\cdots {\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^m}}\right)}^{\text{T}}\right)}^{\text{T}}\rangle }_L^{\text{T}}}\hat{u}\left(k\right)$ . (4)

最优控制问题( $\hat{P}$ )：寻找 ${\hat{u}}^{\ast }\in {\hat{\mathcal{U}}}_{ad}$

$s.t.J\left({\hat{u}}^{\ast }\right)\le J\left(\hat{u}\right),\forall \hat{u}\in {\hat{\mathcal{U}}}_{ad}$

其中 $\hat{x}\left(k\right)={⋉}_{i=1}^n{\hat{x}}_i\left(k\right)\in {\Delta }_{2^n}$ 是状态变量， $\hat{u}\left(k\right)={⋉}_{i=1}^m{\hat{u}}_i\left(k\right)\in {\Delta }_{2^m}$ 是控制变量， $L\in {\mathcal{L}}_{2^n\times 2^{n+m}}$ 为结构矩阵。

4.2. 最优控制问题的求解

最优控制问题求解常用的方法有变分法、动态规划法和庞特里亚金极大值原理。本文采用动态规划法求解最优控制问题(P)。根据最优性原理，针对半张量积表示的最优控制问题( $\hat{P}$ )，我们得到如下定理。

定理4.2.1 [11] ：(最优性原理)对于问题( $\hat{P}$ )，如果 $p_{os}^{\ast }=\left\{{\hat{u}}^{\ast }\left(0\right),\cdots ,{\hat{u}}^{\ast }\left(s-1\right)\right\}$ 是最优策略，则任意的 $1\le k\le s$ ，它的子策略 $p_{ks}^{\ast }=\left\{{\hat{u}}^{\ast }\left(k\right),\cdots ,{\hat{u}}^{\ast }\left(s-1\right)\right\}$ 对于由 $\hat{x}\left(0\right)$ ， $p_{ok-1}^{\ast }$ 确定的 ${\hat{x}}^{\ast }\left(k\right)$ 为起点的第 $k$ 到 $s$ 后部分子过程而言，也是最优策略。

下面我们将定理4.2.1的思想，转化为可计算的递归算法。对任意给定 $t\in \left\{0,1,\cdots ,s-1\right\}$ 和 $\hat{x}\in {\Delta }_{2^n}$ ，考虑如下受控系统

$\{\begin{array}{l}\hat{x}\left(k+1\right)=L⋉\hat{u}\left(k\right)⋉\hat{x}\left(k\right)\\ \hat{x}\left(t\right)=\hat{x}\end{array}k=t,t+1,\cdots ,s-1$ (5)

其中 $\hat{x}\left(k\right)\in {\Delta }_{2^n},\hat{u}\left(k\right)\in {\Delta }_{2^m}$ ，设其性能指标为

$\begin{array}{c}\hat{J}\left(\hat{u}(·);t,\hat{x}\right)={\displaystyle \underset{k=t}{\overset{s-1}{\sum }}{\langle {\left(diagQ\right)}^T,{\left({\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^1}}\right)}^{\text{T}}{\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^2}}\right)}^{\text{T}}\cdots {\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^m}}\right)}^{\text{T}}\right)}^{\text{T}}\rangle }_L^{\text{T}}}\hat{u}\left(k\right)\\ ={\displaystyle \underset{k=t}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}\left(k\right)\end{array}$ (6)

其中， $r={\langle {\left(diagQ\right)}^T,{\left({\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^1}}\right)}^{\text{T}}{\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^2}}\right)}^{\text{T}}\cdots {\left({\displaystyle \underset{l=1}{\overset{2^{m-1}}{\sum }}{\delta }_{2^m}^{p_l^m}}\right)}^{\text{T}}\right)}^{\text{T}}\rangle }_L$ 。

最优控制问题( $P_{t\hat{x}}$ )为：对于给定的 $t\in \left\{0,1,\cdots ,s-1\right\}$ 和 $\hat{x}\in {\Delta }_{2^n}$ ，对应于系统(5)，寻找序列 $\left\{{\hat{u}}^{*}\left(t\right),{\hat{u}}^{*}\left(t+1\right),\cdots ,{\hat{u}}^{*}\left(s-1\right)\right\}$ ，使得 ${\hat{x}}^{*}\left(s\right)$ 达到期待的终端值。即 ${\hat{x}}^{*}\left(s\right)={\hat{x}}_d$ ，且 $\hat{J}\left({\hat{u}}^{*}(·);t,{\hat{x}}^{*}\right)=\min$ 。

显然， $t=0$ 且 $\hat{x}\left(0\right)={\hat{x}}_0$ 时，问题( $P_{t\hat{x}}$ )即为我们需求的最优控制问题( $\hat{P}$ )。此处我们不考虑不可控问题，假设存在控制序列使状态从 ${\hat{x}}_0$ 到 ${\hat{x}}_d$ ，我们定义如下值函数

$\{\begin{array}{l}V\left(t,\hat{x}\right)=\underset{\hat{u}\left(t\right),\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)}{\min }\hat{J}\left(\hat{u}(·);t,\hat{x}\right),\forall t\in \left\{0,1,\cdots ,s-1\right\},\hat{x}\in {\Delta }_{2^n}\\ V\left(s,\hat{x}\right)=0,\forall \hat{x}\in {\Delta }_{2^n}\end{array}$

则可以得到如下定理。

定理4.2.2：对任何的 $t\in \left\{0,1,\cdots ,s-1\right\}$ 和 $\hat{x}\in {\Delta }_{2^n}$ ，有

$\{\begin{array}{l}V\left(t,\hat{x}\right)=\underset{\hat{u}\left(t\right)}{\min }\left\{r^{\text{T}}\hat{u}\left(t\right)+V\left(t+1,\hat{x}\left(t+1;\hat{u}(·)\right)\right)\right\},t=s-1,s-2,\cdots ,1,0\\ V\left(s,\hat{x}\right)=0,\forall \hat{x}\in {\Delta }_{2^n}\end{array}$

证明：由值函数 $V\left(t,\hat{x}\right)$ 的定义知

$\begin{array}{l}V\left(t,\hat{x}\right)\le \hat{J}\left(\hat{u}(·);t,\hat{x}\right)\\ ={\displaystyle \underset{k=t}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}\left(k\right)=r^{\text{T}}\hat{u}\left(t\right)+{\displaystyle \underset{k=t+1}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}\left(k\right),\forall \left\{\hat{u}\left(t\right),\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)\right\}\end{array}$

两端关于序列 $\left\{\hat{u}\left(t\right),\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)\right\}$ 取最小泛函

$\begin{array}{c}V\left(t,\hat{x}\right)\le \underset{\hat{u}\left(t\right),\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)}{\min }\left\{r^{\text{T}}\hat{u}\left(t\right)+{\displaystyle \underset{k=t+1}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}\left(k\right)\right\}\\ \le \underset{\hat{u}\left(t\right)}{\min }\left\{r^{\text{T}}\hat{u}\left(t\right)+V\left(t+1,\hat{x}\left(t+1;\hat{u}(·)\right)\right)\right\}\end{array}$

对任何序列 $\left\{\hat{u}\left(t\right),\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)\right\}$ ，有

$\hat{J}\left(\hat{u}(·);t,\hat{x}\right)={\displaystyle \underset{k=t}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}\left(k\right)\ge r^{\text{T}}\hat{u}\left(k\right)+\underset{\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)}{\min }{\displaystyle \underset{k=t+1}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}(\; k\; )$

故

$\begin{array}{c}V\left(t,\hat{x}\right)\ge \underset{\hat{u}\left(t\right)}{\min }\left\{r^{\text{T}}\hat{u}\left(k\right)+\underset{\hat{u}\left(t+1\right),\cdots ,\hat{u}\left(s-1\right)}{\min }{\displaystyle \underset{k=t+1}{\overset{s-1}{\sum }}{r}^{\text{T}}}\hat{u}\left(k\right)\right\}\\ =\underset{\hat{u}\left(t\right)}{\min }\left\{r^{\text{T}}\hat{u}\left(k\right)+V\left(t+1,\hat{x}\left(t+1;\hat{u}(·)\right)\right)\right\}\end{array}$

$\therefore$

$V\left(t,\hat{x}\right)=\underset{\hat{u}\left(t\right)}{\min }\left\{r^{\text{T}}\hat{u}\left(t\right)+V\left(t+1,\hat{x}\left(t+1;\hat{u}(·)\right)\right)\right\}$

证毕。

有了上述递归公式，我们可以使用计算机编程求其解。

4.3. 应用实例

例4.3.1设离散系统的状态方程为

给定初始状态 $x_1\left(0\right)=x_2\left(0\right)=0$ ，终端状态 $x_1\left(3\right)=x_2\left(3\right)=1$ ，性能指标为

$J\left(u\right)={\displaystyle \underset{k=0}{\overset{2}{\sum }}3u_1\left(k\right)+2u_2\left(k\right)}={\displaystyle \underset{k=0}{\overset{2}{\sum }}{u}^{\text{T}}\left(k\right)Qu(\; k\; )}$

其中， $x_i\left(k\right)\in \mathcal{D},i=1,2$ 逻辑变量， $u_i\left(k\right)\in \mathcal{D},i=1,2$ 控制变量， $u\left(k\right)={\left(u_1\left(k\right)u_2\left(k\right)\right)}^{\text{T}}$ ， $Q$ 为2阶的对角阵 $Q=diag\left\{3,2\right\}$ ，求使性能指标最小的控制序列。

解：将逻辑最优控制问题转化为代数形式：

$\hat{x}\left(k+1\right)=L⋉\hat{u}\left(k\right)⋉\hat{x}\left(k\right),k=0,1,2$

初始条件 $\hat{x}\left(0\right)={\delta }_4^4$ ，终端 $\hat{x}\left(3\right)={\delta }_4^1$ ，性能指标为

$J\left(\hat{u}\right)={\displaystyle \underset{k=0}{\overset{2}{\sum }}{\langle {\left(diagQ\right)}^{\text{T}},{\left({\left({\displaystyle \underset{l=1}{\overset{2}{\sum }}{\delta }_4^{p_l^1}}\right)}^{\text{T}}{\left({\displaystyle \underset{l=1}{\overset{2}{\sum }}{\delta }_4^{p_l^2}}\right)}^{\text{T}}\right)}^{\text{T}}\rangle }_L^{\text{T}}}\hat{u}(\; k\; )$

其中， $L=\left[\begin{array}{llllllllllllllll}0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right]$ ， ${\hat{x}}_i\left(k\right)\in \Delta$ 为状态变量， $\hat{x}\left(k\right)={⋉}_{i=1}^2{\hat{x}}_i\left(k\right)$ ， ${\hat{u}}_i\left(k\right)\in \Delta$ 为控制变量， $\hat{u}\left(k\right)={⋉}_{i=1}^2{\hat{u}}_i\left(k\right)$ 。求使性能指标最小的控制系列 ${\hat{u}}^{\ast }\left(0\right)$ ， ${\hat{u}}^{\ast }\left(1\right)$ ， ${\hat{u}}^{\ast }\left(2\right)$ 。

应用动态规划求解

情形1：由状态方程

$\hat{x}\left(3\right)=L⋉\hat{u}\left(2\right)⋉\hat{x}(\; 2\; )$

有， $J^{\ast }\left[\hat{u}\left(2\right)\right]=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\left\{\left(5320\right)\hat{u}\left(2\right)\right\}=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\{\begin{array}{l}3,\hat{u}\left(2\right)={\delta }_4^2\\ 2,\hat{u}\left(2\right)={\delta }_4^3\end{array}$

于是， ${\hat{u}}^{\ast }\left(2\right)={\delta }_4^3$ ， $J^{\ast }\left[\hat{u}\left(2\right)\right]=2$ ，此时 ${\hat{x}}^{\ast }\left(2\right)={\delta }_4^1$ 。

又由于 ${\hat{x}}^{\ast }\left(2\right)={\delta }_4^1$ ，则

$J^{\ast }\left[\hat{u}\left(1\right)\right]=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\left\{\left(5320\right)\hat{u}\left(1\right)+J^{\ast }\left[\hat{u}\left(2\right)\right]\right\}=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\{\begin{array}{l}3+2,\hat{u}\left(1\right)={\delta }_4^2\\ 2+2,\hat{u}\left(1\right)={\delta }_4^3\end{array}$

于是， ${\hat{u}}^{\ast }\left(1\right)={\delta }_4^3$ ， $J^{\ast }\left[\hat{u}\left(1\right)\right]=4$ ，此时 ${\hat{x}}^{\ast }\left(1\right)={\delta }_4^1$ 。

由于 ${\hat{x}}^{\ast }\left(1\right)={\delta }_4^1$ ，则

$J^{\ast }\left[\hat{u}\left(0\right)\right]=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\left\{\left(5320\right)\hat{u}\left(0\right)+J^{\ast }\left[\hat{u}\left(1\right)\right]\right\}=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\{\begin{array}{l}3+4,\hat{u}\left(0\right)={\delta }_4^2\\ 2+4,\hat{u}\left(0\right)={\delta }_4^3\end{array}$

于是， ${\hat{u}}^{\ast }\left(0\right)={\delta }_4^3$ ， $J^{\ast }\left[\hat{u}\left(0\right)\right]=6$ ， $\hat{x}\left(0\right)={\delta }_4^1$ ，由 $\hat{x}\left(0\right)={\delta }_4^4$ ，因此，此情形不是最优解。

情形2

${\hat{u}}^{\ast }\left(2\right)={\delta }_4^3$ ， $J^{\ast }\left[\hat{u}\left(2\right)\right]=2$ ，此时 ${\hat{x}}^{\ast }\left(2\right)={\delta }_4^1$ 。

${\hat{u}}^{\ast }\left(1\right)={\delta }_4^2$ ， $J^{\ast }\left[\hat{u}\left(1\right)\right]=5$ ，此时 ${\hat{x}}^{\ast }\left(1\right)={\delta }_4^2$ 。

$J^{\ast }\left[\hat{u}\left(0\right)\right]=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\left\{\left(5320\right)\hat{u}\left(0\right)+J^{\ast }\left[\hat{u}\left(1\right)\right]\right\}=\underset{\hat{u}\left(2\right)\in \Delta }{\min }\{\begin{array}{l}5+5,\hat{u}\left(0\right)={\delta }_4^2\\ 3+5,\hat{u}\left(0\right)={\delta }_4^2\\ 2+5,\hat{u}\left(0\right)={\delta }_4^3\\ 0+5,\hat{u}\left(0\right)={\delta }_4^3\end{array}$

又由于 $\hat{x}\left(0\right)={\delta }_4^4$ ，因此，此情形也不是最优解。

情形3

${\hat{u}}^{\ast }\left(2\right)={\delta }_4^2$ ， $J^{\ast }\left[\hat{u}\left(2\right)\right]=3$ ，此时 ${\hat{x}}^{\ast }\left(2\right)={\delta }_4^2$ 。

${\hat{u}}^{\ast }\left(1\right)={\delta }_4^3$ ， $J^{\ast }\left[\hat{u}\left(1\right)\right]=5$ ，此时 ${\hat{x}}^{\ast }\left(1\right)={\delta }_4^3$ 。

${\hat{u}}^{\ast }\left(0\right)={\delta }_4^4$ ， $J^{\ast }\left[\hat{u}\left(0\right)\right]=5$ ， $\hat{x}\left(0\right)={\delta }_4^4$ 。

又 $\hat{x}\left(0\right)={\delta }_4^4$ ，因此，所求的最优控制序列为 ${\hat{u}}^{\ast }\left(0\right)={\delta }_4^4$ ， ${\hat{u}}^{\ast }\left(1\right)={\delta }_4^3$ ， ${\hat{u}}^{\ast }\left(2\right)={\delta }_4^2$ ，最优轨线为 ${\hat{x}}^{\ast }\left(1\right)={\delta }_4^3$ ， ${\hat{x}}^{\ast }\left(2\right)={\delta }_4^2$ ， ${\hat{x}}^{\ast }\left(3\right)={\delta }_4^1$ ，性能指标 $J^{\ast }\left[\hat{u}\left(0\right)\right]=5$ 。

因为 ${\hat{u}}^{\ast }\left(k\right)={⋉}_{i=1}^2{\hat{u}}_i^{*}\left(k\right)$ ，所以 ${\hat{u}}_1^{*}\left(0\right)={\delta }_2^2$ ， ${\hat{u}}_2^{*}\left(0\right)={\delta }_2^2$ ， ${\hat{u}}_1^{*}\left(1\right)={\delta }_2^2$ ， ${\hat{u}}_2^{*}\left(1\right)={\delta }_2^1$ ， ${\hat{u}}_1^{*}\left(2\right)={\delta }_2^1$ ， ${\hat{u}}_2^{*}\left(2\right)={\delta }_2^2$ ，根据逻辑算子的向量表示，最优控制问题的最优控制序列为 $u^{*}\left(0\right)={\left(00\right)}^{\text{T}}$ ， $u^{*}\left(1\right)={\left(01\right)}^{\text{T}}$ ， $u^{*}\left(2\right)={\left(10\right)}^{\text{T}}$ ，同理得到最优轨线为 $x^{*}\left(1\right)={\left(01\right)}^{\text{T}}$ ， $x^{*}\left(2\right)={\left(10\right)}^{\text{T}}$ ， $x^{*}\left(3\right)={\left(11\right)}^{\text{T}}$ ，性能指标为 $J^{\ast }\left[u\left(0\right)\right]=5$ 。

注4.3：在工程实践中一般应用计算机编程求解。这一类问题的动态规划法采用”空间换时间”的办法，从后往前将每一步可能的值存储到相应单元中，然后根据初始条件确定其最优解。

5. 总结

本文利用半张量积的方法将逻辑控制系统的最小能耗问题转化为代数状态的表示方法，并给出了相应的能量指标泛函的表达式，进而对这一类问题推到了动态规划方程。

致谢

本文得到国家自然科学基金(NSFC)项目(11261011)的资助。