李光河， 馮志國

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 重慶 401331)

0 引 言

切換系統(tǒng)通常是由一系列可控的子系統(tǒng)和子系統(tǒng)間的調(diào)度方案構(gòu)成.在實際生活中切換系統(tǒng)已經(jīng)被廣泛地應(yīng)用于各個領(lǐng)域，如空中交通管理，傳感器數(shù)據(jù)收集，電壓功率變換等[1-3].

目前，針對切換系統(tǒng)的最優(yōu)調(diào)度研究主要集中在連續(xù)系統(tǒng)調(diào)度序列給定的前提下尋找最優(yōu)的駐留時間.基于目標(biāo)函數(shù)關(guān)于駐留時間的梯度表達(dá)式，文獻(xiàn)[4]提出了兩階段法.文獻(xiàn)[5]利用控制參數(shù)增強(qiáng)轉(zhuǎn)換技巧系統(tǒng)地解決了類似問題.但是，針對調(diào)度中存在的離散事件卻很難處理.為了尋找最優(yōu)的調(diào)度序列，文獻(xiàn)[6]用離散填充函數(shù)來搜索局部最優(yōu)解.文獻(xiàn)[7]用松弛法將無約束切換系統(tǒng)轉(zhuǎn)化為連續(xù)優(yōu)化問題求解.文獻(xiàn)[8]結(jié)合了遺傳算法的搜索方法.

針對的是有約束的線性切換系統(tǒng)的最優(yōu)調(diào)度問題，利用矩陣跡的相關(guān)性質(zhì)構(gòu)造了一個動態(tài)下界，進(jìn)而提出了深度優(yōu)先的分支定界算法來精確搜索全局最優(yōu)解.在數(shù)值實驗中，驗證了算法的有效性.

1 問題描述

在離散切換系統(tǒng)中假設(shè)存在如下N個自治子系統(tǒng)：

x(t+1)=Ai(t)x(t)，x(0)=x0

t∈I，i=1，2，…，N，

s.t.qT(t+1)x(t+1)≤b(t+1)

x(t+1)=Λσt(t)x(t)

x(0)=x0

其中，對于任意的t∈I，σt∈Λ.

b(t+1)∈R+.

在問題中，離散的切換序列是唯一的決策變量，所以是一個NP難問題.為了有效地求解動態(tài)離散優(yōu)化問題，分支定界是一種比較有效的思路，但前提條件是必須能夠構(gòu)造出一個適用于動力系統(tǒng)的有效的上下界作為分支的準(zhǔn)則.

2 方法分析

2.1 邊界分析

證明由矩陣的跡可知

證明 對任意的k∈{1，2，…N}，M-Ak≤0.

根據(jù)定理1， 結(jié)論易證.

定理2 若系統(tǒng)中的前m個序列固定，即σ0，σ1，…，σm-1已知，則一定存在目標(biāo)函數(shù)和約束的下界L0(m)和L1(t)，t>m，使得對任意的σm，σm+1，…，σT-1∈Λ，恒有L0(m)≤J(σ)，L1(t)≤qT(t)x(t)，t>m.

證明由矩陣跡的性質(zhì)知tr(x(t+1)qT(t+1))=qT(t+1)x(t+1)≤b(t+1).

將目標(biāo)函數(shù)分為兩個部分：

令，

M(t)=min{A1(t)，A2(t)，…，AN(t)}

由推論1可得

J(σ)，

同理， 在t>m時，對于約束條件也可以得到一個動態(tài)下界，表達(dá)式為

L1(t)=tr(M(t-1)…M(m)x(m)qT(t))≤

tr(Aσt-1(t-1)…Aσm(m)x(m)qT(t))=

qT(t)x(t).

2.2 深度優(yōu)先分支定界算法

步驟1 令σt=1，2，…，N，分別計算目標(biāo)函數(shù)和約束的下界L0(σ0，…，σt)和L1(σ0，…，σt)， 并按照升序法則排序.

若L0(σ0，…，σt)≥Jmin或L1(σ0，…，σt)≥Jmin或kt>N，終止當(dāng)前階段， 令t=t-1轉(zhuǎn)步驟4. 否則， 轉(zhuǎn)步驟2.

步驟2 令t=t+1，若t=T-1，轉(zhuǎn)步驟3，否則，轉(zhuǎn)步驟1.

步驟3 令σt=1，2，…，N，計算

x(T)=AσT-1(T-1)…Aσ0(0)x0

當(dāng)qT(T)x(T)≤b(T)時， 計算目標(biāo)函數(shù)J(σ)， 并更新上界Jmin={J(σ)，Jmin}. 令t=t-1，轉(zhuǎn)步驟4.

步驟4 若t<0，終止并輸出最優(yōu)解.否則， 令t=t+1，kt=kt+1轉(zhuǎn)步驟1.

3 數(shù)值實驗

考慮如下時變切換系統(tǒng)的最優(yōu)切換問題.假設(shè)在系統(tǒng)中存在4個子系統(tǒng)，它們的動態(tài)系數(shù)矩陣分別為

令系統(tǒng)中的其他時變參數(shù)分別為

b(t)=8t+9t-1

T=11

由此可知需要對系統(tǒng)進(jìn)行11次切換.為了驗證所提出的算法的有效性，首先按照樹搜索方法列舉出所有可能的情形尋找出滿足動態(tài)約束條件的全局最優(yōu)解，然后利用深度優(yōu)先的分支定界算法進(jìn)行數(shù)值驗證和搜索性能的比較.所有程序均在Matlab 2012a中編寫并在配置為CPU 2.5 GHz， RAM 4 G的筆記本電腦上運(yùn)行.先列舉出所有可能的調(diào)度方案并最終確定子系統(tǒng)的全局最優(yōu)調(diào)度方案為(4 3 2 3 4 4 3 2 3 2 4)，其中搜索次數(shù)為1 048 576，搜索時間為459.66 s，最優(yōu)目標(biāo)值為1.790 1×104. 用方法得到的結(jié)果也是(4 3 2 3 4 4 3 2 3 2 4)，但搜索次數(shù)為724，搜索時間為29.92 s.因此，算法能夠精確搜索到全局最優(yōu)解且搜索效率很高.

4 總 結(jié)

考慮了一種帶約束的離散切換系統(tǒng)的最優(yōu)切換問題.為了尋找到全局最優(yōu)解，將動態(tài)優(yōu)化問題轉(zhuǎn)化為離散優(yōu)化問題進(jìn)行求解.通過分析系統(tǒng)的動態(tài)結(jié)構(gòu)特征，分別針對目標(biāo)函數(shù)和動態(tài)約束構(gòu)造了下界系統(tǒng)，通過與當(dāng)前最優(yōu)值的上界比較，提出了一種深度優(yōu)先的分支定界法進(jìn)行求解.方法在搜索全局最優(yōu)解時具有很高的搜索效率.

參考文獻(xiàn)(References)：

[1] 戚薇.面向地面時敏目標(biāo)跟蹤的多傳感器智能切換技術(shù)[J].電光與控制，2012，19(7)：94-97

QI W. Multi Sensor Intelligent Handoff Technology for Ground Time Sensitive Target Tracking [J].Electronics Optics & Control，2012，19(7)：94-97

[2] 劉艷紅，李超，楚冰.有源電力濾波器切換跟蹤與優(yōu)化控制[J].控制與決策，2014，29(9)：1599-1604

LIU Y H， LI C， CHU B. Switching Tracking and Optimal Control of Active Power Filter[J]. Control and Decision Making，2014，29(9)：1599-1604

[3] SOLER M， OLIVARES A， STAFFETT E. Hybrid Optimal Control Approach to Commercial Aircraft Trajectory Planning[J]. Journal of Guidance Control and Dynamics，2010，33(3)：985-991

[4] XU X， ANTSAKLIS P J. Optimal Control of Switched Systems Based on Parameterizat-ion of the Switching Instants[J]. IEEE Transactions on Automatic Control，2004，49(1)：2-16

[5] 趙瑞艷，林旭梅，李樹榮.基于切換時刻參數(shù)化的切換系統(tǒng)問題求解[J].控制工程，2015；22(4)：737-741

ZHAO R Y， LIN X M， LI S R. Solution of Switched System Problem Based on Switching Time Parameterization[J].Control Engineering，2015，22(4)：737-741

[6] FENG Z G， TEO K L， REHBOCK V. A Discrete Filled Function Method for the Optimal Control of Switched Systems in Discrete Time[J]. Optimal Control Applications and Methods，2009，30(6)：585-593

[7] HE J F， XU W， FENG Z G.On the Global Optimal Solution for Linear Quadratic Problems of Switched System[J]. Journal of Industrial and Management Optimization，2012，30(2)：428-432

[8] 方志明，向崢嶸.一類切換系統(tǒng)切換序列的優(yōu)化設(shè)計[J].兵工學(xué)報，2011，32(1)：124-128

FANG Z M， XIANG Z R. Optimal Design of Switching Sequences for a Class of Switched Systems[J]. Acta Armamentarii，2011，32(1)：124-128