有限值動態(tài)系統(tǒng)的分析與控制研究進(jìn)展

李海濤 李雅璐 王淑玲 劉玉娜

( 山東師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，250358，濟(jì)南 )

1 引 言

有限值動態(tài)系統(tǒng)(Finite-Value Dynamical Systems)是狀態(tài)、輸入和輸出都在有限集上進(jìn)行取值的非線性系統(tǒng)，其動態(tài)方程由多值/混合值邏輯函數(shù)表示[1].該類系統(tǒng)的特點是動態(tài)方程不含參數(shù)，可用于建模較大規(guī)模的系統(tǒng)，便于計算機(jī)仿真驗證等.在過去的半個多世紀(jì)，有限值動態(tài)系統(tǒng)被廣泛地應(yīng)用于基因調(diào)控、電路設(shè)計、信息安全、博弈論等眾多領(lǐng)域[2，3]，成為一個多學(xué)科交叉的熱門研究課題.多位諾貝爾獎獲得者的研究成果與有限值動態(tài)系統(tǒng)密切相關(guān)，包括1965年諾貝爾生理醫(yī)學(xué)獎獲得者 F. Jacob 和 J. Monod，1994年諾貝爾經(jīng)濟(jì)學(xué)獎獲得者J. Nash，以及2012年諾貝爾經(jīng)濟(jì)學(xué)獎獲得者L. Shapley.

目前為止，有限值動態(tài)系統(tǒng)主要分為四種：邏輯動態(tài)系統(tǒng)、網(wǎng)絡(luò)演化博弈、有限域網(wǎng)絡(luò)和非線性反饋移位寄存器.邏輯動態(tài)系統(tǒng)是一個離散時間的動態(tài)系統(tǒng)，其狀態(tài)變量在一個有限集上進(jìn)行取值[4].邏輯動態(tài)系統(tǒng)在許多領(lǐng)域具有重要應(yīng)用，比如生物學(xué)中的布爾網(wǎng)絡(luò)[5，6].布爾網(wǎng)絡(luò)最早是在1969年由Kauffman提出，它被用來建?；蛘{(diào)控網(wǎng)絡(luò)并被應(yīng)用到各種生物現(xiàn)象的建模[7].演化博弈最早源于Fisher、Hamilton、Tfive等生物學(xué)家對動物和植物的沖突與合作行為的博弈分析.以動態(tài)系統(tǒng)的觀點來分析演化博弈，程代展等提出了網(wǎng)絡(luò)演化博弈[8，9].有限域網(wǎng)絡(luò)是指每個自主體的狀態(tài)分量在一個合適的有限域上進(jìn)行取值的多智能體系統(tǒng)[10].有限域網(wǎng)絡(luò)的主要優(yōu)勢為：它只需要較為有限的存儲、計算和通信資源，并且所設(shè)計的算法能夠保證系統(tǒng)在有限時間收斂.因此，有限域網(wǎng)絡(luò)適用于容量、內(nèi)存和時間受限的網(wǎng)絡(luò)，特別是對網(wǎng)絡(luò)帶寬和傳感器通信能力有較強(qiáng)依賴的無線傳感器網(wǎng)絡(luò).非線性反饋移位寄存器在密碼學(xué)中具有重要作用，它所產(chǎn)生的輸出序列通過當(dāng)前存在的密碼分析方法是很難預(yù)測到的，因此非線性反饋移位寄存器在手機(jī)、數(shù)字電視、通訊、故障檢測以及密碼系統(tǒng)等領(lǐng)域具有重要應(yīng)用[11-13].

目前現(xiàn)實世界中的系統(tǒng)主要分為兩類：一類是基于數(shù)量關(guān)系的系統(tǒng)，一般用微分方程或者差分方程來描述；一類是基于邏輯的系統(tǒng).對于第一類系統(tǒng)，目前已有比較完善的處理方法，比如卡爾曼的狀態(tài)空間方法.遺憾的是，對于第二類系統(tǒng)目前卻缺少有效的處理方法，雖然數(shù)理邏輯可以將布爾網(wǎng)絡(luò)轉(zhuǎn)化成邏輯動態(tài)系統(tǒng)，但卻不能用來分析系統(tǒng)的性能.近年來，程代展教授及其科研團(tuán)隊提出了一種新的矩陣乘法——矩陣的半張量積[14，15]，它將普通矩陣乘法推廣到前陣列數(shù)和后陣行數(shù)不等的情況.推廣后的矩陣乘法不僅具有推廣前矩陣乘法的性質(zhì)，并且還具有偽交換性等普通矩陣乘法沒有的性質(zhì).它的主要優(yōu)點是可以將一個邏輯變量轉(zhuǎn)化為一個向量，將一個邏輯函數(shù)轉(zhuǎn)換成一個等價的代數(shù)形式.因此，有限值動態(tài)系統(tǒng)可以轉(zhuǎn)化為經(jīng)典線性離散系統(tǒng)的形式，從而方便我們將現(xiàn)代控制理論中的已有結(jié)果應(yīng)用到有限值動態(tài)系統(tǒng).到目前為止，利用矩陣半張量積方法，布爾網(wǎng)絡(luò)中許多富有挑戰(zhàn)性的問題被解決，比如能控性[16-19]，能觀性[20-23]，穩(wěn)定性[24-27]，鎮(zhèn)定控制[28-31]和最優(yōu)控制[32-34].除此之外，矩陣半張量積方法在圖的著色問題、非線性反饋移位寄存器、有限自動機(jī)、網(wǎng)絡(luò)演化博弈、模糊控制和數(shù)字電路等方面都得到了重要的應(yīng)用.

近幾年來，已有多位學(xué)者對有限值動態(tài)系統(tǒng)的分析與控制方面的研究成果做了詳細(xì)地總結(jié).盧劍權(quán)等在矩陣半張量積框架下，對邏輯網(wǎng)絡(luò)系統(tǒng)及其應(yīng)用給出了一個全面的介紹[35].李海濤等綜述了矩陣半張量積方法在基因調(diào)控網(wǎng)絡(luò)、電力系統(tǒng)以及智能電網(wǎng)等工程領(lǐng)域中的應(yīng)用[36].然而，據(jù)我們所知，對于近三年有限值動態(tài)系統(tǒng)的分析與控制方面的研究進(jìn)展，鮮有文章總結(jié).因此，本文的目的，就是要對有限值動態(tài)系統(tǒng)的基本研究問題以及近三年來的熱點研究問題進(jìn)行綜合概述，并給出有限值動態(tài)系統(tǒng)現(xiàn)存的問題以及研究前景.

2 數(shù)學(xué)基礎(chǔ)

2.1符號介紹

(i)Mm×n為m×n階實矩陣構(gòu)成的集合；

(ii) 1m×n為元素全為1的m×n階矩陣，1n為元素全為1的n維列向量；

(vi) 將矩陣A的第i列記為Coli(A)，第i行記為Rowi(A)，并將其(i,j)元記為ai,j；

(vii) 若一個矩陣B的每一個元素都是從D2中取值，則稱其為布爾矩陣.Bm×n為m×n階布爾矩陣構(gòu)成的集合；

2.2矩陣半張量積矩陣半張量積將普通矩陣乘法推廣到任意維數(shù)的兩個矩陣，即，設(shè)A∈Mm×n，B∈Mp×q,記s=lcm(n,p)為n和p的最小公倍數(shù)，則其半張量積定義為

A?B=(A?Is/n)(B?Is/p).

近幾年來，矩陣半張量積在多個領(lǐng)域，尤其是在邏輯網(wǎng)絡(luò)系統(tǒng)的控制中得到了廣泛應(yīng)用.在本文中，默認(rèn)矩陣乘法為矩陣半張量積，并將符號“?”省略.

因此，利用矩陣半張量積方法，人們可以方便地將有限值動態(tài)系統(tǒng)轉(zhuǎn)化為代數(shù)狀態(tài)空間表示形式，從而為利用經(jīng)典控制理論來研究有限值動態(tài)系統(tǒng)奠定了基礎(chǔ).

為便于讀者理解，下面我們用一個例子來說明如何將一個邏輯函數(shù)轉(zhuǎn)化為其等價的代數(shù)形式.

給定一個邏輯函數(shù)f(x1,x2,x3)=x1∧x2∨x3，其中x1，x2，x3為布爾變量，，∧，∨分別為邏輯算子“非”，“合取”和“析取”，其相應(yīng)的結(jié)構(gòu)矩陣分別為以及則在向量形式下有

f(x1,x2,x3)=MdMcx1Mnx2x3

=MdMc(I2?Mn)x1x2x3

:=Mfx1x2x3，

關(guān)于矩陣半張量積的更多性質(zhì)，讀者可參見文獻(xiàn)[14].

3 邏輯動態(tài)系統(tǒng)研究進(jìn)展

眾所周知，現(xiàn)有的對于邏輯動態(tài)系統(tǒng)進(jìn)行數(shù)學(xué)分析的工具較少.鑒于此，程代展教授提出了矩陣半張量積理論，并將這一方法引入到邏輯動態(tài)系統(tǒng)的研究之中.程代展教授和他的合作者得到了矩陣半張量積的一些基本結(jié)果[14,15-37]，它們詳細(xì)介紹了矩陣半張量積以及基于矩陣半張量積邏輯動態(tài)系統(tǒng)的一些研究結(jié)果.運(yùn)用矩陣半張量積方法，邏輯動態(tài)系統(tǒng)可以轉(zhuǎn)化成等價的代數(shù)形式，從而方便使用經(jīng)典的控制理論來研究邏輯動態(tài)系統(tǒng).利用矩陣半張量積方法，對于邏輯控制動態(tài)系統(tǒng)的研究取得了突破性的進(jìn)展.

3.1歷史回顧邏輯動態(tài)系統(tǒng)是指其狀態(tài)變量x=(x1,…,xn)都只取有限值的離散時間系統(tǒng).設(shè)xi∈Dki,i=1,…,n，那么，這個邏輯動態(tài)系統(tǒng)可以表示為如下形式：

(1)

能控性是現(xiàn)代控制理論的一個基本概念，最早由卡爾曼在20世紀(jì)60年代初提出[38,39].能控性作為一種描述系統(tǒng)狀態(tài)可由外部輸入進(jìn)行控制的性能，它的研究為系統(tǒng)控制器和估計器的分析和設(shè)計提供了理論基礎(chǔ).文獻(xiàn)[40] 提出了兩種布爾控制網(wǎng)絡(luò)的能控性定義，并給出布爾控制網(wǎng)絡(luò)能控的充要條件.在此基礎(chǔ)上，文獻(xiàn)[41]提出了輸入-狀態(tài)關(guān)聯(lián)矩陣和能控矩陣，利用能控矩陣給出了判定系統(tǒng)是否能控的充要條件.文獻(xiàn)[17,42-46]分別將狀態(tài)受限、時滯、切換、概率等情況引入布爾網(wǎng)絡(luò)，研究其系統(tǒng)的能控性并給出充要條件.

能觀性是系統(tǒng)估計理論的基本概念，在生物學(xué)具有重要應(yīng)用.文獻(xiàn)[40]給出了能觀性的四種定義，并給出了判定系統(tǒng)是否能觀的充要條件.文獻(xiàn)[22]比較了文獻(xiàn)[40]中的四種能觀性定義，給出了它們之間的相互關(guān)系，并在四種能觀性的定義基礎(chǔ)上增加了第五種定義.在文獻(xiàn)[22]的基礎(chǔ)上，得到了很多布爾控制網(wǎng)絡(luò)能觀的優(yōu)秀結(jié)果，包括具有時滯、切換布爾控制網(wǎng)絡(luò)的能觀性、具有脈沖效應(yīng)的布爾控制網(wǎng)絡(luò)的能觀性等.

布爾網(wǎng)絡(luò)的穩(wěn)定性在本質(zhì)上等價于離散迭代的收斂性.作為邏輯控制網(wǎng)絡(luò)研究中最基本的問題之一，鎮(zhèn)定問題的解決不僅可以指導(dǎo)醫(yī)學(xué)工作者設(shè)計合適的治療干預(yù)措施，引導(dǎo)生物系統(tǒng)達(dá)到理想狀態(tài)，而且可以揭示系統(tǒng)的結(jié)構(gòu)對系統(tǒng)穩(wěn)定性的影響.近十年來，邏輯控制網(wǎng)絡(luò)的鎮(zhèn)定控制設(shè)計吸引了眾多學(xué)者的研究興趣，并在這一問題上取得了許多優(yōu)異的成果.文獻(xiàn)[47]利用矩陣半張量積方法研究了具有開環(huán)控制和狀態(tài)反饋控制的布爾控制網(wǎng)絡(luò)的穩(wěn)定性和鎮(zhèn)定性，并給出系統(tǒng)鎮(zhèn)定的充要條件.利用文獻(xiàn)[47]的結(jié)果，文獻(xiàn)[48]將穩(wěn)定和鎮(zhèn)定推到了更一般的情況：集合穩(wěn)定和集合鎮(zhèn)定，并給出其充要條件.文獻(xiàn)[28]提出了能達(dá)集方法來研究布爾控制網(wǎng)絡(luò)的狀態(tài)反饋鎮(zhèn)定問題.

以上結(jié)果是過去十幾年來得到的部分結(jié)果，詳情可以參考文獻(xiàn)[49].下面我們具體介紹近三年來邏輯動態(tài)系統(tǒng)的最新成果.

3.2邏輯動態(tài)系統(tǒng)的最新研究進(jìn)展目前關(guān)于邏輯動態(tài)系統(tǒng)的研究問題有很多，這里，我們根據(jù)廣大學(xué)者們的最新研究，只對邏輯動態(tài)系統(tǒng)的控制設(shè)計問題、集合能控問題、依分布穩(wěn)定問題、函數(shù)攝動問題進(jìn)行綜述.

3.2.1 控制設(shè)計方法 邏輯動態(tài)系統(tǒng)中的控制類型主要包括狀態(tài)反饋控制、自由控制序列以及牽制控制.近年來，采樣控制、事件觸發(fā)控制被相繼引入到邏輯動態(tài)系統(tǒng).

事件觸發(fā)控制(Event-Triggered Control)最早是在20世紀(jì)90年代后期提出的[50]，它主要由兩部分構(gòu)成：確定控制輸入的反饋控制器和一種觸發(fā)機(jī)制，它決定何時再次更新控制輸入.事件觸發(fā)控制的主要優(yōu)點是大大減少了控制執(zhí)行次數(shù)，節(jié)省了計算成本[51].近二十年來，事件觸發(fā)控制在非線性系統(tǒng)[52，53]，網(wǎng)絡(luò)控制系統(tǒng)[54，55]等領(lǐng)域得到了廣泛的研究.文獻(xiàn)[56]研究了具有事件觸發(fā)控制的布爾控制網(wǎng)絡(luò)的干擾解耦問題，文獻(xiàn)[57]利用代數(shù)狀態(tài)空間表示方法研究了k值邏輯控制網(wǎng)絡(luò)的魯棒集鎮(zhèn)定問題，并給出了事件觸發(fā)控制的設(shè)計方法.文獻(xiàn)[58]將文獻(xiàn)[57]的結(jié)果推廣到切換k值邏輯控制網(wǎng)絡(luò)的狀態(tài)輸出同步問題，并給出事件觸發(fā)控制的設(shè)計方法.文獻(xiàn)[59]和文獻(xiàn)[60]分別通過事件觸發(fā)反饋控制研究了布爾控制網(wǎng)絡(luò)和概率布爾控制網(wǎng)絡(luò)的鎮(zhèn)定問題.

采樣控制(Sample-Data Control)是一種重要的現(xiàn)代控制技術(shù)，其目的是通過在一個或多個位置設(shè)計脈沖序列或數(shù)字序列的信號來實現(xiàn)控制目標(biāo)[61].在采樣控制系統(tǒng)中，控制器在每個采樣點更新，同時在每個時刻更新傳統(tǒng)控制器.采樣控制的主要優(yōu)點是不僅可以提高系統(tǒng)的控制精度和抗干擾能力，而且可以節(jié)省控制器的成本[62].在過去的幾十年中，采樣控制已經(jīng)應(yīng)用于雷達(dá)跟蹤系統(tǒng)、溫控系統(tǒng)和網(wǎng)絡(luò)控制系統(tǒng)等領(lǐng)域[30,63-66].文獻(xiàn)[30]首次將采樣控制引入到k值邏輯動態(tài)系統(tǒng)，研究了k值邏輯動態(tài)系統(tǒng)采樣控制反饋鎮(zhèn)定問題，并給出了系統(tǒng)鎮(zhèn)定的充要條件和采樣控制的設(shè)計方法.文獻(xiàn)[67]進(jìn)一步研究了受限的k值邏輯動態(tài)系統(tǒng)采樣能達(dá)性和狀態(tài)反饋鎮(zhèn)定.文獻(xiàn)[68]和文獻(xiàn)[69]分別研究了采樣控制下布爾控制網(wǎng)絡(luò)的能控性和能觀性.此外，采樣控制下控制布爾網(wǎng)絡(luò)的許多問題得到廣泛研究，例如輸出調(diào)節(jié)問題[70]、魯棒采樣控制不變集[71]、同步問題[72]等.

3.2.2 集合能控 文獻(xiàn)[73]首次提出了布爾控制網(wǎng)絡(luò)的集合能控這一概念，并利用集合能控解決了布爾網(wǎng)絡(luò)的能觀性問題.這個想法主要來自文獻(xiàn)[21]，考慮的狀態(tài)受限是集合能控的一種特殊情況.因此，集合能控可以說是文獻(xiàn)[21]結(jié)果的推廣和一般化.文獻(xiàn)[74]利用受限集合能控方法，解決了狀態(tài)受限邏輯控制網(wǎng)絡(luò)的輸出跟蹤和輸出同步問題.考慮如下形式的布爾控制網(wǎng)絡(luò)：

(2)

定義1 考慮系統(tǒng)(2)，假設(shè)初始集和最終集分別為P0和Pd.

定理1 考慮系統(tǒng)(2)，假設(shè)初始集和最終集分別為P0和Pd，其集合能控矩陣Cs=(cij)定義如上.

(iii) 系統(tǒng)(2)是集合能控的，當(dāng)且僅當(dāng)Cs=1β×α.

3.2.3 李雅普諾夫穩(wěn)定 李雅普諾夫理論在非線性動力系統(tǒng)的穩(wěn)定性分析和控制綜合中起著重要的作用[75,76].特別地，在非線性系統(tǒng)理論中控制李雅普諾夫函數(shù)(Lyapunov Function)被用來設(shè)計狀態(tài)反饋控制器[3]，在多智能體系統(tǒng)、模糊控制系統(tǒng)和混雜系統(tǒng)中得到了廣泛應(yīng)用.布爾網(wǎng)絡(luò)是一種特殊的離散時間動態(tài)系統(tǒng)，因此，布爾網(wǎng)絡(luò)應(yīng)該也具有控制李雅普諾夫函數(shù).

近年來，李雅普諾夫理論已被推廣到k值邏輯動態(tài)系統(tǒng)的穩(wěn)定性分析中.文獻(xiàn)[77]不僅首次對一般布爾網(wǎng)絡(luò)定義了李雅普諾夫函數(shù)的概念，提出了兩種構(gòu)造李雅普諾夫函數(shù)的方法，而且建立了布爾網(wǎng)絡(luò)的李雅普諾夫理論的一個新框架，得到了若干基于李雅普諾夫的穩(wěn)定性結(jié)果，其中包括一個逆李雅普諾夫定理.眾所周知，構(gòu)造一般動態(tài)系統(tǒng)的李雅普諾夫函數(shù)仍然是一個開放的問題.然而，通過文獻(xiàn)[77]的方法，對任意給定的布爾網(wǎng)絡(luò)都可以構(gòu)造一個或多個有效李雅普諾夫函數(shù).

考慮如下形式的布爾網(wǎng)絡(luò)：

x(t+1)=Lx(t).

(3)

下面給出布爾網(wǎng)絡(luò)(3)李雅普諾夫函數(shù)的定義.

定義2 一個偽布爾函數(shù)V(x1,…,xn):Dn→R是布爾網(wǎng)絡(luò)的李雅普諾夫函數(shù)，如果以下條件成立：

(i)V(x1,…,xn)>0,?(x1,…,xn)∈DnOe,且V(x1,…,xn)=0對任意的(x1,…,xn)∈Oe成立，其中Oe表示布爾網(wǎng)絡(luò)的不動點集.

(ii) 對于布爾網(wǎng)絡(luò)的所有軌跡，ΔV(x1,…,xn)<0對(x1(t),…,xn(t))?S成立，且ΔV(x1(t),…,xn(t))=0對(x1(t),…,xn(t))∈S成立，其中S表示不動點和環(huán)構(gòu)成的集合.

下面列出文獻(xiàn)[77]建立的布爾網(wǎng)絡(luò)李雅普諾夫函數(shù)構(gòu)造方法.

第一步：計算矩陣L，并找出集合Oe的指標(biāo)集Ie和集合S的指標(biāo)集Is;

V(x1,…,xn)=c0+c1x1+…+cnxn+cn+1x1x2+…+c2n-1x1x2…xn.

在文獻(xiàn)[77]之后，邏輯網(wǎng)絡(luò)的李雅普諾夫方法得到了迅猛發(fā)展.文獻(xiàn)[78]將控制李雅普諾夫函數(shù)推廣到了有限博弈，通過求解一組等式不等式構(gòu)造出了控制李雅普諾夫函數(shù).文獻(xiàn)[79]將正系統(tǒng)的Lyapunov理論推廣到具有馬爾可夫跳躍參數(shù)的布爾網(wǎng)絡(luò)的穩(wěn)定性和l1增益分析.在此之后，文獻(xiàn)[80]提出了一種控制李雅普諾夫方法來研究k值邏輯動態(tài)系統(tǒng)的反饋鎮(zhèn)定問題.文獻(xiàn)[81]將李雅普諾夫控制方法推廣到了概率布爾網(wǎng)絡(luò)，給出了概率布爾網(wǎng)絡(luò)采樣狀態(tài)反饋鎮(zhèn)定的充要條件.

4 網(wǎng)絡(luò)演化博弈研究進(jìn)展

馮·諾依曼的著作《博弈與經(jīng)濟(jì)行為理論》標(biāo)志著現(xiàn)代博弈論的誕生.自此，博弈論的研究極大地促進(jìn)了經(jīng)濟(jì)學(xué)、工程學(xué)、哲學(xué)、心理學(xué)等眾多學(xué)科的發(fā)展.大致來說，博弈論主要有兩個分支：非合作博弈和合作博弈.在競爭對手之間的互動過程中，每個參與者都獨(dú)立地選擇自己的策略來提高自己的效用.非合作博弈理論研究了由此過程產(chǎn)生的策略選擇.在非合作博弈理論中，“納什均衡”在策略選擇中起著核心作用.合作博弈理論為研究合作者的行為提供了分析工具.與非合作博弈不同，在合作博弈中沒有如同“納什均衡”的最佳解決方案.在過去的幾十年里，合作博弈的求解問題得到了國內(nèi)外學(xué)者的廣泛研究.從有效性公理、對稱性公理以及可加性公理出發(fā)，L. S. Shapley于1953年提出Shapley值的概念[82]，并獲得諾貝爾經(jīng)濟(jì)學(xué)獎.由于Shapley值是唯一一個滿足三個公理的分配，因此在合作博弈中得到了廣泛的應(yīng)用，并發(fā)揮了重要的作用.下面，我們首先對博弈的基本知識進(jìn)行簡單介紹，然后對近幾年來博弈論中的熱點研究問題，如有限博弈的向量空間分解以及基于勢博弈的控制問題進(jìn)行總結(jié).讀者可參考文獻(xiàn)[83]來學(xué)習(xí)博弈論的基礎(chǔ)知識.

其中

稱為ci的結(jié)構(gòu)向量.

如果一個有限博弈被重復(fù)多次，則每個玩家都根據(jù)已有信息來最大化自身收益.這樣，就可以得到演化方程.常見的一種演化方程為下一時刻的策略只依賴于當(dāng)前時刻策略，即

其中xi(t)，i=1,2,…,n表示t時刻第i個玩家的策略.在向量形式下，可以得到上述演化方程的代數(shù)形式

x(t+1)=Fx(t)，

利用矩陣半張量積方法，文獻(xiàn)[84]首次對采取“短視最優(yōu)響應(yīng)”更新規(guī)則的網(wǎng)絡(luò)演化博弈進(jìn)行了建模，文獻(xiàn)[9]研究了采取一般的更新規(guī)則的網(wǎng)絡(luò)演化博弈的建模.

4.2最新研究進(jìn)展基于矩陣的半張量積方法，博弈論得到了國內(nèi)外眾多學(xué)者的廣泛研究.在本部分，我們對近幾年來博弈論中的幾個熱點研究問題進(jìn)行總結(jié).

一個有限博弈G=(N,S,C)，如果存在一個函數(shù)P:S→R，使得對任意i∈N成立

ci(xi,s-i)-ci(yi,s-i)=P(xi,s-i)-P(yi,s-i)，xi,yi∈Si,s-i∈S-i，

則稱G為勢博弈，相應(yīng)的P稱為勢函數(shù).勢博弈在網(wǎng)絡(luò)化系統(tǒng)的優(yōu)化和控制問題中起著關(guān)鍵的作用.然而，勢博弈的檢驗卻是一個長期未得到解決的問題.利用矩陣半張量積方法，文獻(xiàn)[85]將勢博弈的驗證問題轉(zhuǎn)化為勢方程解的存在性問題，并給出了相應(yīng)勢函數(shù)的結(jié)構(gòu)向量.基于此，文獻(xiàn)[86]提出了一個具有更低計算復(fù)雜度的驗證條件.另外，文獻(xiàn)[87]和文獻(xiàn)[88]分別給出了判斷策略受限的以及連續(xù)策略的博弈是否勢博弈的檢驗方法.

近年來，基于勢博弈[89-92]的控制方法被廣泛應(yīng)用于許多實際工程問題，如資源配置、電力調(diào)度等.一般來說，基于勢博弈的控制問題包含兩個步驟.對于一個給定優(yōu)化目標(biāo)的系統(tǒng)，首先設(shè)計每個自主體的收益函數(shù)，使整個系統(tǒng)成為一個以目標(biāo)函數(shù)為勢函數(shù)的勢博弈；其次通過設(shè)計每個自主體的控制策略或算法，使整個系統(tǒng)收斂到勢函數(shù)的納什均衡點，從而達(dá)到整體目標(biāo)的最優(yōu).基于博弈控制論的這一思想，利用擁塞博弈與勢博弈的等價性，文獻(xiàn)[93]給出了一個資源型系統(tǒng)可以成為擁塞博弈的充要條件，文獻(xiàn)[94]考慮了系統(tǒng)用戶具有特定代價的情形，提出了一種具有用戶特定代價的擁塞博弈，有效地解決了資源配置問題.另外，文獻(xiàn)[95]和文獻(xiàn)[96]分別研究了有限時域收益的線性動態(tài)博弈和基于狀態(tài)的演化博弈，分別給出了所考慮的博弈是勢博弈的充分條件，文獻(xiàn)[96]建立了相應(yīng)的控制設(shè)計方法.

作為博弈論中的一個基本問題，有限博弈的向量空間結(jié)構(gòu)在工程領(lǐng)域也具有重要應(yīng)用[97].因此，這一問題的研究具有重要的理論與應(yīng)用價值.利用矩陣半張量積方法，文獻(xiàn)[97]給出了有限非合作博弈的正交分解，文獻(xiàn)[98]提出了加權(quán)調(diào)和博弈的概念，利用加權(quán)的勢博弈和調(diào)和博弈給出了有限非合作博弈的另一正交分解.另外，關(guān)于對稱博弈[99]的向量空間結(jié)構(gòu)，也有許多優(yōu)秀的研究成果，包括文獻(xiàn)[100-102].

基于矩陣半張量積方法，還有許多博弈論中的重要問題得到了解決，包括合作博弈中Shapley值的矩陣表示，網(wǎng)絡(luò)演化博弈中的穩(wěn)定和鎮(zhèn)定問題[78]、策略一致性[103]、策略同步[104].另外，關(guān)于一些其他類型的博弈也取得了許多優(yōu)秀的研究成果，包括隨機(jī)演化博弈[105-108]、競爭擴(kuò)散博弈[109]、變拓?fù)渚W(wǎng)絡(luò)演化博弈[110]、及具有破產(chǎn)風(fēng)險的網(wǎng)絡(luò)演化博弈[111-114]等.

5 有限域網(wǎng)絡(luò)研究進(jìn)展

隨著現(xiàn)代網(wǎng)絡(luò)信息技術(shù)的快速發(fā)展，網(wǎng)絡(luò)化控制系統(tǒng)成為當(dāng)今學(xué)術(shù)界的一個熱點研究領(lǐng)域[115-118].作為一類重要的網(wǎng)絡(luò)化控制系統(tǒng)，多智能體系統(tǒng)由一組通過圖進(jìn)行局部通信的自主體組成，其目的是解決單個智能體系統(tǒng)難以或不可能解決的問題[119]. 相較于單個智能體系統(tǒng)，多智能體系統(tǒng)效率更高，靈活性更強(qiáng)，可靠度更高.因此，網(wǎng)絡(luò)化多智能體系統(tǒng)在過去的幾十年中引起了國內(nèi)外許多學(xué)者的廣泛關(guān)注[120，121]. 然而，在實數(shù)域上進(jìn)行建模的網(wǎng)絡(luò)化多智能體系統(tǒng)不僅需要大量的存儲和通信資源，并且在對在實數(shù)域上進(jìn)行建模的網(wǎng)絡(luò)化多智能體系統(tǒng)進(jìn)行控制設(shè)計時，所設(shè)計的算法往往不能保證系統(tǒng)有限時間收斂，因此很難適用于容量、內(nèi)存和時間受限的網(wǎng)絡(luò).鑒于此， F. Pasqualetti 等學(xué)者利用有限域來建模網(wǎng)絡(luò)化多智能體系統(tǒng)，即每個自主體的狀態(tài)分量在一個合適的有限域上進(jìn)行取值，從而提出了有限域網(wǎng)絡(luò)的模型[10].

有限域網(wǎng)絡(luò)由四部分組成: (i) 有限域Fp={0,1,…,p-1}，其中p是素數(shù).(ii)n個自主體，每個自主體都從Fp取值. (iii) 有向圖G=(V,E).其中V:={1,2,…,N}表示節(jié)點集，E∈V×V表示邊集.i∈V表示第i個節(jié)點.如果存在自節(jié)點i到節(jié)點j的有向邊，則(i,j)∈E. (iv) 線性分配協(xié)議: 每個自主體根據(jù)它的入度鄰居的加權(quán)平均來更新自己的狀態(tài).

作為多智能體系統(tǒng)中最重要的問題之一，一致問題在機(jī)器人等工程領(lǐng)域有著廣泛的應(yīng)用[122].特別是領(lǐng)導(dǎo)者-跟隨者一致問題得到了廣泛的研究[123，124].有限域一致作為一種特殊的一致問題，近十年來得到了廣泛的研究[125，126].

x(t+1)=Ax(t),

(4)

其中A表示網(wǎng)絡(luò)圖的鄰接矩陣，且式(4)中所有運(yùn)算都是有限域上的模運(yùn)算.

F. Pasqualetti 研究了這種有限域網(wǎng)絡(luò)的一致性，從網(wǎng)絡(luò)拓?fù)涞慕嵌冉o出了判斷有限域網(wǎng)絡(luò)一致性的充要條件，并且說明與實數(shù)域上的一致不同，有限域一致能夠在有限時間實現(xiàn)[127].文獻(xiàn)[10] 給出了具有離散時間迭代的固定網(wǎng)絡(luò)有限域一致的充要條件，與此同時，作者還提供了它在傳感器網(wǎng)絡(luò)中平均一致性和姿態(tài)估計中的應(yīng)用.文獻(xiàn)[128]研究了有限域網(wǎng)絡(luò)的結(jié)構(gòu)能控性和能觀性, 利用有限域上的線性系統(tǒng)理論給出了有限域網(wǎng)絡(luò)結(jié)構(gòu)能控和能觀的判據(jù). 研究結(jié)果表明, 如果圖包含生成森林, 則有限域上的多智能體系統(tǒng)是結(jié)構(gòu)能控的.

具有時滯的有限域網(wǎng)絡(luò)表示如下：

(5)

文獻(xiàn)[129]分別研究了具有單常時滯、多常時滯和時變時滯的有限域網(wǎng)絡(luò)的一致問題，給出了多項式形式的判定條件.文獻(xiàn)[130] 研究了具有切換拓?fù)浜蜁r滯的有限域網(wǎng)絡(luò)的一致性問題，并利用有限域趨同矩陣的性質(zhì)建立了趨同的分布式控制協(xié)議.文獻(xiàn)[126] 利用矩陣半張量積方法給出了具有切換的有限域網(wǎng)絡(luò)的一致性的矩陣判定條件，這一條件與之前的結(jié)果相比更容易驗證.

5.2領(lǐng)導(dǎo)者-跟隨者模型考慮有限域Fp上由一個領(lǐng)導(dǎo)者和N個跟隨者構(gòu)成的多智能體系統(tǒng)，領(lǐng)導(dǎo)者的動態(tài)方程描述如下：

x0(t+1)=Ax0(t)，

(6)

xi(t+1)=Axi(t)+bui(t)，

(7)

文獻(xiàn)[131]研究了有限域上多智能體系統(tǒng)的主從一致問題，利用有限域線性系統(tǒng)理論給出了主從一致的分布式控制協(xié)議.文獻(xiàn)[132]考慮了具有二階非線性動力學(xué)的領(lǐng)導(dǎo)者-跟隨者多智能體有向網(wǎng)絡(luò)的魯棒有限時間一致問題.利用矩陣?yán)碚摚鷶?shù)圖論和有限時間控制方法，給出了使得領(lǐng)導(dǎo)者-跟隨者系統(tǒng)在有限時間內(nèi)實現(xiàn)一致的連續(xù)分布式控制設(shè)計算法.文獻(xiàn)[133]研究了領(lǐng)導(dǎo)者-跟隨者多智能體系統(tǒng)的能控性，并說明了領(lǐng)導(dǎo)者-跟隨者多智能體系統(tǒng)能控性與圖的連通性之間的關(guān)系.文獻(xiàn)[134]在跟隨者系統(tǒng)中引入時滯，并利用矩陣半張量積方法給出了有限域上具有時滯的領(lǐng)導(dǎo)者-跟隨者多智能體系統(tǒng)主從一致的充要條件.文獻(xiàn)[135]在文獻(xiàn)[136]的基礎(chǔ)上在領(lǐng)導(dǎo)者系統(tǒng)中引入時滯，研究了領(lǐng)導(dǎo)者系統(tǒng)跟隨者系統(tǒng)都有時滯的情況下的有限域上的領(lǐng)導(dǎo)者-跟隨者多智能體系統(tǒng)主從一致問題.

6 非線性反饋移位寄存器研究進(jìn)展

隨著網(wǎng)絡(luò)信息技術(shù)的迅猛發(fā)展，信息安全不僅對于個人十分重要，甚至可能影響到社會穩(wěn)定和國家安全.因此，隨著人們對信息安全要求的不斷提高，密碼技術(shù)得到了迅速發(fā)展.密碼學(xué)中有兩種常見的密碼體制：一種是單鑰密碼體制，一種是公鑰密碼體制.序列密碼作為一類特殊的單鑰密碼體制，因其具有硬件實現(xiàn)簡單、有限的錯誤傳播以及加密和解密速度快的優(yōu)點，序列密碼在軍事和外交等領(lǐng)域得到廣泛應(yīng)用.2004年以前，線性反饋移位寄存器是用于序列密碼設(shè)計的主要序列源生成器，例如日本政府征集的Toyocrypt算法等[137].然而近年來，隨著相關(guān)攻擊[138，139]及代數(shù)攻擊思想[140]的相繼提出，基于線性反饋移位寄存器的序列密碼算法面臨很大的安全威脅.于是非線性反饋移位寄存器得到越來越廣泛的關(guān)注[13].

一個帶有n個寄存器的Galois型非線性反饋移位寄存器可以被表示為如下n階非線性方程組：

(8)

其中fi:Dn→D,i∈{0,1,2,…,n-1}是邏輯函數(shù)，并且xi(t)表示第i個寄存器在t時刻的值，(x0(t),x1(t),…,xn-1(t))表示Galois型非線性反饋移位寄存器在t時刻的狀態(tài).

一個有n個寄存器的Fibonacci型非線性反饋移位寄存器可以表示為如下形式：

(9)

其中xi(t)表示第i個寄存器在t時刻的值，xi(t)∈D，i∈{0,1,2,…,n-1}.

Galois型線性反饋移位寄存器和Fibonacci型線性反饋移位寄存器之間存在一個映射，一個Galois型線性反饋移位寄存器可以產(chǎn)生一個給定的Fibonacci型線性反饋移位寄存器同樣的輸出序列.對于非線性反饋移位寄存器來說，這個映射不一定存在.近年來，文獻(xiàn)[141]利用代數(shù)方法研究了Galois型線性反饋移位寄存器和Fibonacci型線性反饋移位寄存器之間的映射，并且給出了一個將Fibonacci型線性反饋移位寄存器轉(zhuǎn)化成等價的Galois型線性反饋移位寄存器的代數(shù)方法.文獻(xiàn)[142]用矩陣半張量積方法重新解決了這個問題，并給出了一個轉(zhuǎn)化等價的算法.

近年來，隨著矩陣半張量積方法的引入，國內(nèi)外學(xué)者對于非線性反饋移位寄存器的研究取得很多優(yōu)秀的研究結(jié)果.文獻(xiàn)[143]利用布爾網(wǎng)絡(luò)方法實現(xiàn)了非線性反饋移位寄存器的線性化，構(gòu)造的新的狀態(tài)轉(zhuǎn)移矩陣比現(xiàn)存的更容易計算.文獻(xiàn)[144]將這一結(jié)果推廣到多值非線性反饋移位寄存器的情況.非線性反饋移位寄存器是驅(qū)動穩(wěn)定的當(dāng)且僅當(dāng)可達(dá)集是吸引盆的子集.由于缺乏有效的代數(shù)工具，對具有輸入的非線性反饋移位寄存器的驅(qū)動穩(wěn)定性的研究較少.文獻(xiàn)[145]將具有輸入的非線性反饋移位寄存器看作布爾控制網(wǎng)絡(luò)來解決這一問題.文獻(xiàn)[146]將非線性反饋移位寄存器作為一種特殊的布爾網(wǎng)絡(luò)，利用矩陣半張量積和邏輯的矩陣表達(dá)式，將其動態(tài)方程轉(zhuǎn)化為等價的代數(shù)方程.在此基礎(chǔ)上，提出了一些新的、通用的方法來研究非線性反饋移位寄存器.文獻(xiàn)[147]給出了最大長度非線性反饋寄存器的充要條件.

7 開放性問題

近年來，有限值動態(tài)系統(tǒng)由于其在基因調(diào)控、電路設(shè)計、信息安全、博弈論等眾多領(lǐng)域中的重要應(yīng)用而得到國內(nèi)外學(xué)者的廣泛關(guān)注.針對有限值動態(tài)系統(tǒng)的分析與控制這一課題，目前已取得了一系列優(yōu)秀的研究成果，然而仍有許多問題尚未解決.

首先，有限值動態(tài)系統(tǒng)中的基本問題仍需完善.如何將經(jīng)典線性、非線性系統(tǒng)中的控制方法，如模型預(yù)測控制、自適應(yīng)控制等引入到有限值動態(tài)系統(tǒng)的研究中，從而推動有限值動態(tài)系統(tǒng)控制理論的發(fā)展，是一個重要的研究課題.

其次，利用有限值動態(tài)系統(tǒng)理論，文獻(xiàn)[148]已實現(xiàn)了對電動汽車的建模.隨著人工智能的發(fā)展，從數(shù)學(xué)上對更多智能系統(tǒng)，如無人機(jī)，機(jī)器人等，進(jìn)行有限值動態(tài)系統(tǒng)建模，將會是未來的研究方向.

再次，對于由邏輯動態(tài)系統(tǒng)和一般微分/差分系統(tǒng)構(gòu)成的混雜系統(tǒng)的研究，目前僅是初步嘗試階段[149，150]，仍有許多問題亟待解決.

最后，代數(shù)狀態(tài)空間方法為利用現(xiàn)代控制理論來研究有限值動態(tài)系統(tǒng)奠定了基礎(chǔ).作為代數(shù)狀態(tài)空間方法的主要數(shù)學(xué)基礎(chǔ)，如何進(jìn)一步完善矩陣的半張量積理論，并將其應(yīng)用到擴(kuò)維系統(tǒng)的研究中，是一個有意義的研究課題.