混雜系統(tǒng)優(yōu)化建模與分析

王曉江，陳俊碩

(1.中國飛行試驗研究院，西安 710089；2.長安大學，西安 710064)

混雜系統(tǒng)優(yōu)化建模與分析

王曉江1，陳俊碩2

(1.中國飛行試驗研究院，西安 710089；2.長安大學，西安 710064)

針對組合混雜系統(tǒng)中由于不同工作模式數(shù)量隨系統(tǒng)組成部分數(shù)以指數(shù)形式增長而導致系統(tǒng)更加復雜的問題，提出了一個基于超平面規(guī)劃的模式枚舉法.其根據(jù)組合離散混雜自動機之間的依賴關(guān)系和連接順序依次進行，只枚舉出組合系統(tǒng)的可行模式，去掉了由于離散混雜自動機之間交互和外部約束導致的不可行模式，降低了需要考慮的模式數(shù)量.基于混雜系統(tǒng)不同形式模型之間的等效性，可以在枚舉同時將組合離散混雜自動機模型轉(zhuǎn)換為能夠進行離線最優(yōu)控制的分段仿射模型.建立了二階積分器的組合混雜模型，仿真結(jié)果表明了算法的可行性和有效性.

混雜系統(tǒng)；枚舉算法；優(yōu)化建模

混雜系統(tǒng)是一組相互交互數(shù)字有限狀態(tài)機的集合，并且每個狀態(tài)機都有一個模擬部分與之對應(yīng).目前對于混雜系統(tǒng)可以建立三種類型的模型，分別為離散自動機(Discrete Hybrid Automata, DHA)模型，混合邏輯動態(tài)(Mixed Logical Dynamical, MLD)模型和分段仿射(Piecewise Affine, PWA)模型[1].其中三種模型各有優(yōu)點，DHA模型能夠很容易用HYSDEL(Hybrid Systems Description Language, HYSDEL)語言描述，建模最簡單也最方便[2-3].MLD模型比較適合計算量較小的混雜系統(tǒng)在線最優(yōu)控制，一般都是由描述DHA模型的HYSDEL語言轉(zhuǎn)換而來，也是目前應(yīng)用最多的最優(yōu)控制模型[4-5].而當推導離線最優(yōu)控制率作為狀態(tài)反饋控制率和設(shè)計混雜系統(tǒng)滾動時域觀測器時[6]，則首先需要建立PWA模型，才能對系統(tǒng)進行分析計算，PWA模型適應(yīng)于計算量較大，較復雜的混雜系統(tǒng).

混雜系統(tǒng)也可是由幾個混雜系統(tǒng)構(gòu)成的組合混雜系統(tǒng)，其中不同工作模式的數(shù)量是以系統(tǒng)組成部分的指數(shù)形式增長，并且由于很多算法的時間和空間的復雜程度都是隨著運行模式的數(shù)量增加而變得更加復雜，相應(yīng)邏輯狀態(tài)規(guī)模的暴增導致計算非常困難.在一些情況下，一個組合系統(tǒng)可以分解為一個可以在分層混雜系統(tǒng)[7]中被用到的分層結(jié)構(gòu)，并且可以運用假設(shè)可靠的方法，將一個大問題化分成為幾個小問題.但在更多情況下由于各個部分之間的交叉耦合太緊密，建立分層模型是根本不可能的.由于交叉耦合實質(zhì)為一些有效約束，即使能夠建立分層模型，也經(jīng)常呈現(xiàn)出很多不可行的模式.所以通過顯式計算和只考慮可行模式能夠有效降低系統(tǒng)的復雜程度，本文提出了一個有效的枚舉組合混雜系統(tǒng)可行模式的方法.

由于DHA中的閾值是由超平面定義的，所以枚舉單個離散自動機的可行模式是很容易通過算法來計算超平面規(guī)劃的單元來求解.由于這是一個計算機幾何學中的典型的問題，可以用最優(yōu)化和高效的算法.對于組合DHA系統(tǒng)，本文提出的算法可以根據(jù)組合DHA中的交互和依賴關(guān)系來枚舉出一個組合混雜系統(tǒng)的可行模式.這個算法有兩個特點，第一，為了枚舉單個DHA的可行模式，用到了超平面規(guī)劃中單元的概念和逆搜索方法，使得復雜程度與可能模式數(shù)量是比例關(guān)系而非指數(shù)關(guān)系.第二，當多個DHA組合成一個組合DHA時，模式枚舉可以根據(jù)DHA的排列順序的逐步進行計算.本文方法不同于蠻力法，不用將組合系統(tǒng)中每一個可能的模式都去討論，因為組合DHA之間的交互及外部的約束的作用使得其中大部分模式是不可行的.

1 基于超平面規(guī)劃的多面體分區(qū)

假設(shè)A為一組d維歐式空間內(nèi)n個不同的超平面{Hi}i=1,…,n，其中每個超平面都是由一個線性等式Hi={x∈Rd|aiTx=bi}確定.如果A中沒有互相平行的超平面并且空間中任意一點最多屬于d個超平面，則稱A中的超平面是一般位置超平面.

圖1 二維空間內(nèi)的4個超平面分布

圖1中的超平面1、2、3、4為一般位置超平面，定義一個符號向量S表示為

Pm= {x∈Rd|S(x)=m},該集合為超平面規(guī)劃的一個單元，由于其為線性不等式定義的超平面，也可稱之為一個多面體，其中m表示A中的第m個多面體(也可稱之為單元).定義M(R)為空間中所有點所屬的多面體或單元的集合，如圖1所示M(R)包含10個多面體.定義“*”為單元的并集，如圖1所示，m1=----和m2=+---，則m=*---就是等同于{m1,m2}表示為Pm1∪Pm2.當超平面不為一般位置超平面時，即R≠Rd需要定義其相應(yīng)的多面體分區(qū)如下：

多面體的集合{Pm}滿足

(i)∪m∈M(R)Pm=R(ii)Pi∩Pj=?,?i,j∈M(R),i≠j

則稱該多面體集合{Pm}為空間R的一個多面體分區(qū).

2 離散線性混雜模型

2.1 離散混雜自動機

如圖2所示，離散混雜自動機主要由描述混雜系統(tǒng)離散部分的離散有限狀態(tài)機和描述連續(xù)部分的切換仿射系統(tǒng)組成.它們由事件發(fā)生器和模式選擇器相連，事件發(fā)生器提取連續(xù)部分的輸入ur(k)和狀態(tài)xr(k)得到相應(yīng)二進制開關(guān)信號δe(k)，開關(guān)量信號δe(k)和外部二進制輸入的信號ub(k)共同觸發(fā)有限狀態(tài)機的狀態(tài)xb(k).模式選擇器結(jié)合所有的二進制變量信號(狀態(tài)xb(k)，輸入ub(k)和事件δe(k))來選擇模式i(k)及相應(yīng)的切換仿射系統(tǒng)連續(xù)動態(tài).其中下標b表示二進制變量，r表示連續(xù)變量，下面詳細定義4個部分.

圖2 離散混雜自動機結(jié)構(gòu)圖

切換仿射系統(tǒng)(Switched Affine System, SAS)：是仿射系統(tǒng)的集合，由模式i(k)選擇相應(yīng)的動態(tài)

xr(k+1)=Ai(k)xr(k)+Bi(k)ur(k)+fi(k),

yr(k)=Ci(k)xr(k)+Di(k)ur(k)+gi(k).

(1)

其中:k∈N為離散化的時間常數(shù)，xr∈Xr是實際的狀態(tài)，ur∈Ur為實際的外部輸入，yr∈Yr是實際輸出，Ai,Bi,fi,Ci,Di,gi為一系列相應(yīng)維數(shù)的矩陣，模式i∈I表示一個選擇仿射狀態(tài)更新和輸出函數(shù)的控制信號.

事件發(fā)生器(Event Generator, EG)：為依據(jù)仿射約束或閾值產(chǎn)生二進制的事件信號δe

δe(k)=fH(xr(k),ur(k)).

(2)

有限狀態(tài)機(Finite State Machine, FSM)：是一個離散的動態(tài)過程，通過一個二進制的狀態(tài)更新方程進行迭代更新

xb(k+1)=fB(xb(k),ub(k),δe(k)),

xb(k)=gB(xb(k),ub(k),δe(k)).

(3)

其中：xb,ub分別為二進制的狀態(tài)和外部輸入，yb為二進制的外部輸出，δe為事件發(fā)生器輸出的事件，fB，gB為確定的二元函數(shù)，例如

xb(k+1)=┐δe(k)∨(xb(k)∧ub(k)).

(4)

模式選擇器(Mode Selector, MS): 其是通過方程fM結(jié)合二進制狀態(tài)xb，二進制輸入ub和事件δe，選擇切換仿射系統(tǒng)的模式i(k)

i(k)=fM(xb(k),ub(k),δe(k)).

(5)

為當前模式，例如

(6)

其共有3個模式分別為[1;0]、[0;0]、[1;1]，只有當i(k-1) ≠i(k)時，模式才進行切換.有限狀態(tài)機的一個確定的狀態(tài)xb對應(yīng)一個模式，但是事件δe對應(yīng)的模式不只一個.

定理1 一個離散狀態(tài)自動機如果在一個給定的初始狀態(tài)x(0)∈X下，對于任何一個輸入u(k)∈U其狀態(tài)軌跡x(k)∈X和輸出軌跡y(k)∈y都是唯一確定的，其中k∈N，則稱該離散狀態(tài)自動機在X，U，y上為適定的.

2.2 分段放射系統(tǒng)

分段仿射系統(tǒng)通過把狀態(tài)空間分割成幾個多面體，每個多面體對應(yīng)一個仿射狀態(tài)更新方程和一個輸出方程

x(k+1)=Aj(k)x(k)+Bj(k)u(k)+fj(k),

y(k)=Cj(k)x(k)+Dj(k)u(k)+gj(k),

(7)

(7)

其中:x(k)，u(k)，y(k)分別表示在k時刻實際狀態(tài)，輸入和輸出.Aj(k),Bj(k),Cj(k),Dj(k),fj(k),gj(k)分別為j(k)∈J時一定維數(shù)的常數(shù)矩陣和向量.本文用j(k)表示系統(tǒng)的一個模式，#J表示相應(yīng)模式的代號，Pj(k)代表輸入狀態(tài)(X×U)空間中多面體集{Pj}j∈J.

定理2 假設(shè)∑PWA為如式(7)中所示的PWA模型，{Pj}是一個基于輸入狀態(tài)空間X×U的一個多面體分區(qū)，則∑PWA是適定的.

上述定理，相反的條件一般不成立，因為PWA系統(tǒng)可以是定義在重疊的多面體集上的.

3 枚舉算法

根據(jù)上述兩種模型的定義，本文給出了枚舉出單個DHA的可行模式并將其轉(zhuǎn)換為PWA模型的算法1，對于單一的DHA來說，在給定的二進制狀態(tài)xb和輸入ub，找到可行模式J∈I，多面體集{Pj}和相應(yīng)的PWA動態(tài){Sj}，這里Sj={Aj，Bj，fj，Cj，Dj，gj}，I為模式選擇器的形象化.

算法1：

1)首先初始化j=0,J=?;

2)然后通過對集合M(R)中的每個多面體進行迭代，得到每個多面體Pj及其對應(yīng)的事件發(fā)生器的信號δe;

3)進而由每個δe得到相應(yīng)的模式選擇器的模式值i(k);

4)最后由

上述算法枚舉出給定輸入ub和狀態(tài)xb，單個DHA在該輸入狀態(tài)下對應(yīng)的可行模式.如果二進制輸入和狀態(tài)的組合沒有可行模式或者相應(yīng)的狀態(tài)空間為空集，該算法返回的多面體集合和動態(tài)集合都為空集.重復調(diào)用該算法就得到了在整個狀態(tài)輸入空間X×U上的PWA模型的集合，每個PWA模型對應(yīng)一個可行的二進制輸入和狀態(tài)組合.如果對于給定的狀態(tài)和輸入，需要求得其對應(yīng)的狀態(tài)更新和輸出，則該算法通過二分法查找選擇相應(yīng)的PWA模型是很有優(yōu)勢的，并且模型可以很容易的轉(zhuǎn)換為一個定義在X×U上的PWA模型.

由上述定理1、2及多面體的定義可得，如果DHA∑是適定的，則所得的PWA模型也是適定的并且多面體集合{Pj}組成了一個X×U上的多面體分區(qū).

但是在實際應(yīng)用中，很多模型都是組合自動機，對于一個組合的DHA，包括s個DHA，每個定義為∑i,i∈{1,2,…,s}，其對應(yīng)狀態(tài)、輸入和輸出分別為xi∈Xi，ui∈Ui和yi∈Yi.Ii為每個DHA的可行模式集合，整個組合系統(tǒng)的外部輸入為u，外部輸出為y.則組合系統(tǒng)的實際和二進制狀態(tài)空間集合為Xr=Xr1×Xr2…Xrs和Xb=Xb1×Xb2…Xbs，其中組合向量xr=[(xr1)T, (xr2)T…, (xrs)T]T，xb=[(xb1)T, (xb2)T…, (xbs)T]T，為按順序排列的各個子系統(tǒng)的實數(shù)和二進制狀態(tài).這樣可得組合系統(tǒng)的組合狀態(tài)向量為x=[xr,xb]T.

各個子系統(tǒng)之間的聯(lián)系可以用DHA之間的輸出和輸入的等式約束來表示.假設(shè)第i個DHA的輸入為其他的DHA的輸出和外部輸入的線性組合如下所示

(8)

其中：Lmi和Li分別為相應(yīng)維數(shù)的矩陣，其中Lmi為第m個DHA與第i個之間關(guān)系矩陣，其行數(shù)為第i個DHA的輸入個數(shù)(包括二進制輸入和實際連續(xù)輸入)，列數(shù)為第m個DHA的輸入的個數(shù)(同樣也包括二進制輸入和實際連續(xù)輸入)，并且i，m∈{1,2,…,s}.由于組合是線性組合，并且表示的只是兩個DHA之間的關(guān)系，單個DHA只能連接一個DHA的輸出或者一個外部輸入，這樣矩陣[L1iL2i…LsiLi]的每行的和為1.

根據(jù)有向圖的定義：一個有向圖G是一個有序的二元組(V(G),A(G))其中集合V(G)是非空的頂點集，集合A(G)是一個V×V的子集，為帶有方向的邊的集合，稱為弧集，A(G)中的元素稱為有向邊.

由上述定義可以直接運用到組合DHAs中通過定義DHA為相應(yīng)的頂點，輸出和輸入的連接定義為邊.這里的邊可以表述為兩個DHA之間的幾種連接，其中組合系統(tǒng)連接方式的拓撲圖可以用鄰接矩陣來表示，并且該矩陣可以很簡單的由連接方式得到.

定義：G為一個有s個頂點的圖，每條邊只對應(yīng)一對頂點(沒有平行邊)，則圖G鄰接矩陣A=[aij]是一個s×s的0,1矩陣，如果有邊直接從頂點i到頂點j則aij=1，否則aij=0.A中元素的排列順序為{1,2,…,s}.

圖3為由5個按順序排列過的兩輸入兩輸出的DHA組合系統(tǒng)，其中∑1和∑4有外部輸入，∑4和∑5有外部輸出.

圖3 組合DHA系統(tǒng)框圖

其中∑3輸入的鄰接矩陣如下

與單個DHA類似，對于定義在X×U空間上的組合系統(tǒng)，通過對給定的二進制狀態(tài)xb和外部輸入ub來確定其可行模式集J?I1×I2×…×Is，多面體集合{Pj}j∈J和相應(yīng)的PWA動態(tài){Sj}j∈J.

首先，將鄰接矩陣A通過矩陣變換轉(zhuǎn)變?yōu)樯先切尉仃?，這樣就給組合DHA中每單個DHA編好了順序，其中后面的DHA∑i的輸入只取決于外部輸入和前面∑j的輸出(i>j).第一個DHA∑1，其輸入向量僅是外部輸入向量的子集(輸入與其他的DHA無關(guān)).這里實際的狀態(tài)和輸入都是已知的，則可以用算法1來確定其模式J1，多面體集合(多面體分區(qū)){Pj}和相應(yīng)的PWA動態(tài){Sj}，其中j∈J1.這里的多面體是對Xr×Ur狀態(tài)輸入空間的分區(qū).

由于每個模式j(luò)∈Jm和其對應(yīng)的PWA動態(tài)Sj一起定義了其連接的后面的組合DHA的輸入，所以首先我們需要將后面的DHA的輸入通過用關(guān)于初始狀態(tài)x和外部輸入u的函數(shù)替換.如果鄰接矩陣中ami=1，表示∑m的輸出與∑i輸入的相連i∈{m+1,…,s}，即ym=ui，則需把∑i的輸入ui替換為Lmiym,j+Liu，其中ym,j=Cjx+Dju+gj.這里的Cj,Dj,gj是DHA∑m的PWA動態(tài)Sj中的元素，x和u為已知的狀態(tài)和外部輸入.其中j表示輸入的方程只對應(yīng)模式j(luò)∈Jm.替換以后就能保證后面的DHA∑m+1僅取決于組合狀態(tài)和外部輸入.

此后，對于一個給定的模式j(luò)∈Jm，隨著m每增加1，算法2被再次調(diào)用，用后面的DHA∑m+i的超平面來將該模式下對應(yīng)的多面體Pj分成由幾個多面體組成的多面體集.所有剩下的模式j(luò)∈Jm再依次進行，當m達到最大值s時，當前DHA∑s對應(yīng)的多面體集合加到前面的多面體集以后就構(gòu)成了完整的定義在了整個狀態(tài)輸入空間組合DHA多面體集{Pj}j∈J和相應(yīng)的PWA動態(tài){Sj}j∈J.

概括上述方法，對于給定的二進制狀態(tài)向量和外部輸入向量，其中A已為上三角矩陣.

算法2：1)對于組合DHA系統(tǒng)，先對一個DHA∑m運用算法1，得到一個其最初的多面體集合P和PWA動態(tài)集S;

2)然后通過對其每個模式j(luò)下與后面DHA∑i,i∈{m+1,…,s}的連接方式，當有連接時用函數(shù)將后面DHA∑i的輸入替換為DHA∑m的輸出，重新運用算法1，對多面體進行進一步劃分，得到新的多面體結(jié)合集Pnew和PWA動態(tài)集Snew，每次都將這些新的集合納入到總的集合中，當每個模式都算完后就得到了該DHA∑m的多面體集{Pj}j∈Jm和PWA動態(tài)集{Sj}j∈Jm;

3)直到對最后一個DHA∑s運用過算法2以后，得到DHA∑s最終的多面體集{Pj}j∈Js和PWA動態(tài)集{Sj}j∈Js，將所有的單個DHA的多面體集和PWA動態(tài)集合并，得到最終的多面體集{Pj}j∈J和PWA動態(tài)集{Sj}j∈J;

對于圖3中前兩個連接系統(tǒng)如圖4

圖4 兩個DHA組成的組合系統(tǒng)

DHA∑1和DHA∑2分別為：

其中

狀態(tài)x1∈X=[0,8]，外部輸入u1∈U=[0,6]，外部輸出為y2，由圖4可見，u2=y1，由于已經(jīng)按照連接順序排列過，鄰接矩陣已經(jīng)為上三角矩陣.先通過算法1來獲得DHA∑1的超平面分布，其包含2個超平面，{[x1, u1]T∈X×U | x1=3}和{[x1, u1]T∈X×U | x1=6}.然后通過枚舉超平面中的單元法，將整個狀態(tài)輸入X×U空間分成了3個多面體分區(qū){Pj}, j∈J1={1, 2, 3}，如圖5(A)所示其中還有每個多面體所對應(yīng)的超平面規(guī)劃的標示符號，同時相應(yīng)的PWA動態(tài)輸出函數(shù)為Si, i∈{1,2,3}如圖5(C)所示.

4 仿真結(jié)果

為了驗證算法的有效性，對于式(9)所示二階積分器，對其進行優(yōu)化建模分析，首先將其視為兩個一階積分器的串聯(lián)，這樣其就是兩個DHA組成的組合DHA

(9)

通過取采樣時間T=1s進行線性化，將其轉(zhuǎn)化為離散模型得到離散的狀態(tài)空間表示方式為

(10)

圖5 組合系統(tǒng)的多面體分區(qū)和PWA動態(tài)輸出函數(shù)

并且在狀態(tài)約束x∈[-2, 2]，輸入約束u∈[-2, 2]時，可得到其狀態(tài)空間的多面體分區(qū)如下，其中黑色線段表示閉環(huán)預測控制在各個多面體區(qū)間的運行軌跡.如圖6所示在給定初始狀態(tài)和輸入時，通過組合PWA模型預測下一步輸出y從而得到最優(yōu)的輸入u使y能夠快速達到期望值1，其中輸入狀態(tài)空間由在初始模式5最終到達模式1.

圖6 對上述混雜模型進行預測控制，得到相應(yīng)的輸入和輸出曲線及工作模式軌跡

5 結(jié) 語

本文對引入圖論的概念對組合混雜系統(tǒng)的DHA進行PWA模型轉(zhuǎn)換給出了相應(yīng)的算法，其不僅能枚舉出所有的可行模式并且隨之能判斷組合系統(tǒng)是否適定，由于其對已經(jīng)處理過的超平面有保存功能，大大減少了離散計算的時間.最后通過對串聯(lián)積分器的建模和控制，仿真結(jié)果表明所設(shè)計算法能夠有效的將其轉(zhuǎn)化為PWA模型并且枚舉出其可行的模式，對給定參考值的輸入控制輸入能使輸出很好的達到參考值.

[1] HEEMELS W P M H, SCHUTTER B D, BEMPORAD A. On the equivalence of classes of hybrid dynamical models[C]// Orlando: Conference on Decision and Control, 2001. 364-369.

[2] 張 悅, 王東風, 韓 璞, 等. 一類混雜系統(tǒng)的推廣自動機模型及其仿真[J]. 系統(tǒng)仿真學報, 2007, 19(15): 3546-3549.

[3] 李繼方, 湯天浩, 姚 剛. 共直流母線交流傳動節(jié)能系統(tǒng)的混雜系統(tǒng)建模與分析[J]. 電工技術(shù)學報, 2011, 26(7): 181-187.

[4] 李 凌, 袁德成, 井元偉. 模擬移動床過程的混雜系統(tǒng)建模方法[J]. 控制與決策, 2013, 28(2): 299-302.

[5] 李 寧, 李穎暉, 朱喜華. 新型容錯逆變器的混雜系統(tǒng)建模與故障診斷[J]. 電機與控制學報, 2012, 16(9): 53-58.

[6] 孫云平, 劉 赟, 李俊民. 一類二階時變非線性系統(tǒng)的混合自適應(yīng)重復學習控制[J]. 西安電子科技大學學報, 2006, 33(3): 495-499.

[7] 仝慶貽, 顏鋼鋒. 混雜系統(tǒng)及其在電力系統(tǒng)中的應(yīng)用[J]. 電力系統(tǒng)及其自動化學報, 2003, 15(2): 14-18.

Study on optimization modeling and analysis of hybrid system

WANG Xiao-jiang1, CHEN Jun-shuo2

(1.Chinese Flight Test Institute, Xi’an 710089, China; 2. Chang’an University, Xi’an 710064, China)

Compositional hybrid systems are very complex, as the number of different operational modes depends exponentially on the number of component systems. Enumerative algorithm was proposed, which was based on hyperplane arrangements. The sequential enumeration greatly reduced the number of modes considered by pruning unnecessary modes from the resulting system. Based on the equivalence of discrete hybrid automatas and piecewise affine systems, an algorithm was presented, which enumerated the modes of a composition of discrete hybrid automatas and transforms it into an equivalent piecewise affine representation. Second-order integrator was presented illustrating the algorithm and showing its feasibility and effectiveness.

hybrid system; enumerative algorithm; optimization modeling

2016-08-15.

王曉江(1985-)，男，碩士，工程師，研究方向：飛機性能試飛.

N945.12

A

1672-0946(2017)02-0202-06