布爾控制網(wǎng)絡(luò)的能觀測性綜合問題

謝壹冬，陳曉艷，韓曉光

(天津科技大學(xué)電子信息與自動化學(xué)院，天津 300222)

1969年，Kauffman首次提出了布爾網(wǎng)絡(luò)[1]的概念，用此概念描述蛋白質(zhì)或基因間的邏輯行為和聯(lián)系.布爾網(wǎng)絡(luò)采用數(shù)值“0”(非激活的)或“1”(激活的)對其狀態(tài)節(jié)點進行量化，使用邏輯函數(shù)表征基因之間的相互作用，并且每個狀態(tài)節(jié)點依靠邏輯函數(shù)更新其值.至今，布爾網(wǎng)絡(luò)已經(jīng)被廣泛應(yīng)用于諸多實際問題，如細(xì)胞分化[2]、免疫應(yīng)答[3]、三神經(jīng)元網(wǎng)絡(luò)[4]及其他領(lǐng)域[5].布爾網(wǎng)絡(luò)在施加外部輸入和系統(tǒng)輸出后，能夠擴展為布爾控制網(wǎng)絡(luò)[6].

在2001年，程代展研究員提出了矩陣半張量積(semi-tensor product of matrices，STP)[7]的概念，這是一種新的矩陣乘積，它將矩陣的普通乘法擴展到任意兩個矩陣，使矩陣技術(shù)更易于應(yīng)用到邏輯函數(shù)、高維數(shù)組和非線性系統(tǒng)等問題.STP理論已成功應(yīng)用于布爾控制網(wǎng)絡(luò)研究中.利用STP技術(shù)，一個布爾控制網(wǎng)絡(luò)的邏輯行為可等價表示為雙線性方程的形式.基于該雙線性方程，布爾控制網(wǎng)絡(luò)的一些動態(tài)性質(zhì)得到深入研究，如能控性[8]、能觀測性[8-11]、可探測性(也稱可重構(gòu)性)[11]及其他性質(zhì)[12].

能觀測性是布爾控制網(wǎng)絡(luò)的一個基本性質(zhì)，4種不同類型的能觀測性概念在文獻[8-11]中被相繼提出.能觀測性描述了是否可以通過輸入-輸出值確定一個系統(tǒng)的初始狀態(tài).Zhang等[13]基于加權(quán)對圖和有限狀態(tài)自動機的方法設(shè)計了一種有效算法，用以驗證4種類型的能觀測性.當(dāng)一個系統(tǒng)不具有能觀測性時，研究能觀測性綜合問題具有重要意義.為此，Zhang[14]開啟了布爾控制網(wǎng)絡(luò)能觀測性綜合問題的研究，證明了狀態(tài)反饋有時能夠增強任意實驗?zāi)苡^測性[11]，并給出了這種類型能觀測性的標(biāo)準(zhǔn)狀態(tài)反饋控制器的設(shè)計算法.本文關(guān)注的是多實驗?zāi)苡^測性[10]，研究了標(biāo)準(zhǔn)狀態(tài)反饋控制器和帶有外部輸入的狀態(tài)反饋控制器對這種類型能觀測性的影響.

1 預(yù)備知識

1.1 基本符號

(1)N：自然數(shù)集；

(2)Z+：正整數(shù)集；

(3)R：實數(shù)集；

(4)Rn×m：n×m維實矩陣集合；

(5)Col(B)：矩陣B的列向量構(gòu)成的集合；

(6)D：由0和1組成的集合，即D={0,1}；

(7)[n,m]：{n,n+1,…,m}，其中n,m∈N，n≤m；

(8)：單位矩陣In的第i列；

(9)1n=；

(10)Δn={|i=1,2,…,n}；

(11)若矩陣B∈Rn×m滿足Col(B)∈Δn，則稱其為一個邏輯矩陣.方便起見，簡記為，其中ik∈[1,n]，1≤k≤m；

(12)Ln×m：n×m維邏輯矩陣集合.

1.2 矩陣半張量積

設(shè)矩陣B∈Rm×n，C∈Rp×q，s為n與p的最小公倍數(shù)，則矩陣B和C的半張量積定義為：BC=(B?Is/n)(C ?Is/p)，其中?表示Kronecker積.特別當(dāng)n=p時，有BC=BC，因此，普通矩陣乘積是STP的一種特殊情況.方便起見，在下文中常略去符號“”.

本文用到STP的一些基本性質(zhì)如下：考慮兩個列向量X∈Rm×1和Y∈Rn×1，則XX=ΦmX，XY=X?Y，YX=W[m,n]XY ，其中設(shè)x,y∈Δ2，?x表示x的邏輯非運算，x∨y表示析取運算，x∧y表示合取運算，x→y表示蘊含運算，即?x=Mnx ，x∨y=Mdxy ，x∧y=Mcxy ，x→y=Mixy，其中Mn=δ2[2,1]，Md=δ2[1,1,1,2]，Mc=δ2[1,2,2,2]，Mi=δ2[1,2,1,1].關(guān)于STP的更多性質(zhì)詳見文獻[15].

1.3 布爾控制網(wǎng)絡(luò)及其代數(shù)形式

本文研究具有n個狀態(tài)節(jié)點、m個輸入節(jié)點和q個輸出節(jié)點的布爾控制網(wǎng)絡(luò)，其動態(tài)方程表示為

其中xi(t)、yj(t)和uk(t)分別表示t時刻的狀態(tài)節(jié)點、輸出節(jié)點和輸入節(jié)點，即xi(t)∈D，yj(t)∈D，uk(t)∈D，t∈N；fi:Dn+m→Dn和hj:Dn→Dq分別表示狀態(tài)和輸出邏輯函數(shù)，i∈[1,n]，k∈[1,m].

在STP框架下，方程(1)等價地轉(zhuǎn)換為

1.4 有限狀態(tài)自動機

一個確定型有限狀態(tài)自動機(deterministic finitestate automaton，DFA)是一個5元組A=(S,E,σ,s0,F)，其中S表示有限狀態(tài)集，E表示有限事件集，s0∈S表示初始狀態(tài)，F(xiàn)?S表示最終狀態(tài)集，σ:S×E→S表示轉(zhuǎn)移函數(shù)并且可以擴展為σ:S×E*→S ，E*=.有限狀態(tài)自動機A生成的語言表示為L(A)={ω∈E*|σ(s0,ω)∈F}.當(dāng)L(A)=E*時，稱有限狀態(tài)自動機A是完備的.

1.5 能觀測性

在文獻[13]中，作者證明了布爾控制網(wǎng)絡(luò)的4種不同類型能觀測性概念兩兩不等價.在文獻[14]中，作者討論了最強類型的能觀測性綜合問題.本文研究另一種類型的能觀測性(稱為多實驗?zāi)苡^測性)綜合問題.

定義1[13]若對于布爾控制網(wǎng)絡(luò)(2)的任意兩個不同初始狀態(tài)，皆存在一個輸入序列，使得對應(yīng)的輸出序列和不相同，則稱布爾控制網(wǎng)絡(luò)(2)是多實驗?zāi)苡^測的.

注：在本文表述中，多實驗?zāi)苡^測性簡稱為能觀測性.

定義2[13]布爾控制網(wǎng)絡(luò)(2)的加權(quán)對圖描述為一個3元組G=(V,E,W)，其中頂點集V×V|存在，使得，或者，加權(quán)函數(shù)W :E→2ΔM，或者稱為一個非對角頂點；否則稱其為一個對角頂點，并用記號◇表示.值得注意的是，表示為同一個頂點.

下例說明了如何計算一個給定布爾控制網(wǎng)絡(luò)的加權(quán)對圖.

例1考慮布爾控制網(wǎng)絡(luò)

圖1 布爾控制網(wǎng)絡(luò)(3)的加權(quán)對圖Fig.1 Weighted pair graph of Boolean control network(3)

下面的命題給出了布爾控制網(wǎng)絡(luò)能觀測性的驗證方法.

命題1[13]布爾控制網(wǎng)絡(luò)(2)是不能觀測的，當(dāng)且僅當(dāng)其加權(quán)對圖中存在非對角頂點以及由算法1生成對應(yīng)的DFA是完備的.

算法1[13]一個新的DFA定義為：

(1) 事件集ΔM，初始狀態(tài)；

(3) 剩余的頂點構(gòu)成最終狀態(tài)集.

例2再次考慮布爾控制網(wǎng)絡(luò)(3)，其加權(quán)對圖為圖1，基于算法1得到每一個非對角頂點對應(yīng)的DFA，如圖2所示.因為是完備的，根據(jù)命題1，布爾控制網(wǎng)絡(luò)(3)是不能觀測的.

圖2 布爾控制網(wǎng)絡(luò)(3)每一個非對角頂點對應(yīng)DFAFig.2DFA of each non-diagonal vertex with respect to Boolean control network(3)

1.6 狀態(tài)反饋控制器

考慮布爾控制網(wǎng)絡(luò)(2)，帶有外部輸入的狀態(tài)反饋控制器定義為

其中v(t)表示外部輸入，v(t)∈DP；g:DN+P→DM表示布爾函數(shù)，P∈N.借助于STP，控制器(4)可等價轉(zhuǎn)換為

方程(6)進一步表示為

特別當(dāng)P=1時，帶有外部輸入的狀態(tài)反饋控制器變?yōu)闃?biāo)準(zhǔn)狀態(tài)反饋控制器，即

在這種情況下，方程(7)簡化為

其中g(shù)i∈LM×1，i∈[1,N].

2 主要結(jié)果

2.1 能觀測性綜合

在這一小節(jié)，研究帶有外部輸入的狀態(tài)反饋控制器(5)對布爾控制網(wǎng)絡(luò)(2)能觀測性的影響.事實上，控制器(5)有時可使一個不能觀測的布爾控制網(wǎng)絡(luò)變?yōu)槟苡^測的，有時不能；反之，控制器(5)也可以使一個能觀測的布爾控制網(wǎng)絡(luò)變?yōu)椴荒苡^測的.

首先，下面例子表明了控制器(5)可使一個不能觀測的布爾控制網(wǎng)絡(luò)變?yōu)槟苡^測的.

例3由例2可知，布爾控制網(wǎng)絡(luò)(3)是不能觀測的.若選取帶有外部輸入的狀態(tài)反饋控制器

將其代入布爾控制網(wǎng)絡(luò)(3)中，得到閉環(huán)系統(tǒng)

閉環(huán)系統(tǒng)(10)的加權(quán)對圖和每一個非對角頂點對應(yīng)的DFA如圖3所示.根據(jù)命題1，閉環(huán)系統(tǒng)(10)是能觀測的.

圖3 閉環(huán)系統(tǒng)(10)的加權(quán)對圖和每個DFA Fig.3 Weighted pair graph and each DFA of closed-loop system(10)

其次，下面例子表明了控制器(5)無法使一個不能觀測的布爾控制網(wǎng)絡(luò)變?yōu)槟苡^測的.

例4考慮布爾控制網(wǎng)絡(luò)

圖4 布爾控制網(wǎng)絡(luò)(11)的加權(quán)對圖和每個DFA Fig.4 Weighted pair graph and each DFA of Boolean control network(11)

將其代入布爾控制網(wǎng)絡(luò)(11)中，得到閉環(huán)系統(tǒng)

最后，下面例子表明了控制器(5)可使一個能觀測的布爾控制網(wǎng)絡(luò)變?yōu)椴荒苡^測的.

例5考慮布爾控制網(wǎng)絡(luò)

圖5 布爾控制網(wǎng)絡(luò)(13)的加權(quán)對圖和每個DFA Fig.5Weighted pair graph and each DFA of Boolean control network(13)

將其代入布爾控制網(wǎng)絡(luò)(13)中，得到閉環(huán)系統(tǒng)

2.2 P=1和P＞1狀態(tài)反饋控制器對能觀測性的影響

在文獻[14]中，作者證明了對于一個不滿足任意實驗?zāi)苡^測性的布爾控制網(wǎng)絡(luò)(2)，若存在帶有外部輸入的狀態(tài)反饋控制器(P＞1)使其閉環(huán)系統(tǒng)滿足這種類型的能觀測性，則必然存在標(biāo)準(zhǔn)狀態(tài)反饋控制器(P=1)使其閉環(huán)系統(tǒng)也滿足這種類型的能觀測性，反之亦然.然而，這兩種類型的狀態(tài)反饋控制器對布爾控制網(wǎng)絡(luò)的多實驗?zāi)苡^測性有不同的影響.

定理1對于不能觀測的布爾控制網(wǎng)絡(luò)(2)，如果存在標(biāo)準(zhǔn)狀態(tài)反饋控制器使其對應(yīng)的閉環(huán)系統(tǒng)能觀測，則一定存在帶有外部輸入的狀態(tài)反饋控制器使其對應(yīng)的閉環(huán)系統(tǒng)也能觀測，反之不成立.

證明：設(shè)布爾控制網(wǎng)絡(luò)(2)是不能觀測的，若存在標(biāo)準(zhǔn)狀態(tài)反饋控制器使閉環(huán)系統(tǒng)(9)能觀測，則令Gi=[gi,gi,…,gi]，i∈[1,N].顯然帶有外部輸入的狀態(tài)反饋控制器也可使閉環(huán)系統(tǒng)(7)能觀測.反之不成立，詳見下例.

例6再次考慮例1所示的布爾控制網(wǎng)絡(luò)(3).例3表明了存在一個帶有外部輸入的狀態(tài)反饋控制器可使布爾控制網(wǎng)絡(luò)(3)變?yōu)槟苡^測的.下面證明不存在標(biāo)準(zhǔn)狀態(tài)反饋控制器(8)使布爾控制網(wǎng)絡(luò)(3)變?yōu)槟苡^測的.為此，羅列所有標(biāo)準(zhǔn)狀態(tài)反饋控制器

其中∈Δ2.將控制器(15)代入布爾控制網(wǎng)絡(luò)(3)，可得所有閉環(huán)系統(tǒng)

其中∈.每一個閉環(huán)系統(tǒng)的加權(quán)對圖和每個非對角頂點對應(yīng)的DFA如圖6所示.因此，根據(jù)命題1，閉環(huán)系統(tǒng)(16)都是不能觀測的.

圖6 閉環(huán)系統(tǒng)(16)中每個系統(tǒng)的加權(quán)對圖和對應(yīng)DFAFig.6 Weighted pair graph and corresponding DFA for each system in closed-loop system(16)

3 結(jié) 語

本文研究了標(biāo)準(zhǔn)狀態(tài)反饋控制器和帶有外部輸入的狀態(tài)反饋控制器對布爾控制網(wǎng)絡(luò)多實驗?zāi)苡^測性的影響，并證明了如果存在標(biāo)準(zhǔn)狀態(tài)反饋控制器使一個不能觀測的布爾控制網(wǎng)絡(luò)變?yōu)槟苡^測的，則一定存在帶有外部輸入的狀態(tài)反饋控制器使一個不能觀測的布爾控制網(wǎng)絡(luò)變?yōu)槟苡^測的，反之不成立.此外，本文獲得的初步研究結(jié)果開啟了對布爾控制網(wǎng)絡(luò)多實驗?zāi)苡^測性綜合問題的研究.未來工作需要針對一個不能觀測的布爾控制網(wǎng)絡(luò)，設(shè)計一個有效算法，尋找使該布爾控制網(wǎng)絡(luò)變?yōu)槟苡^測的所有狀態(tài)反饋控制器.