劉書新，韓佳敏，杜海霞，曹若薇

（新疆農(nóng)業(yè)大學數(shù)理學院，新疆烏魯木齊，830052）

多智能體系統(tǒng)[1]作為分布式人工智能的一個重要分支，主要研究多個智能體在復雜環(huán)境下如何處理協(xié)同合作等問題。多智能體系統(tǒng)的一致性問題主要是基于多智能體系統(tǒng)中的智能體相互之間的信息交換，通過設(shè)計一致性協(xié)議[2]使得智能體的狀態(tài)趨于一致。近年來，多智能體系統(tǒng)的一致性問題得到了廣泛的應用，例如分布式傳感器網(wǎng)絡、機器人系統(tǒng)的協(xié)作等[3]。另一方面,隨著人工智能和大數(shù)據(jù)等新興領(lǐng)域的發(fā)展，基于多智能體一致性的分布式優(yōu)化理論[4]得到了越來越多的關(guān)注，并逐漸在協(xié)同控制、工程計算等各個領(lǐng)域得到廣泛應用。多智能體系統(tǒng)分布式優(yōu)化是通過多智能體之間的有效合作完成優(yōu)化任務，在多智能體系統(tǒng)一致性的框架下求解分布式最優(yōu)問題，其中有代表性的算法有基于迭代框架下的離散時間算法[5]、基于協(xié)調(diào)控制的連續(xù)時間算法[6]、基于有限時間收斂的不連續(xù)算法[7]和基于固定時間收斂的連續(xù)算法[8]。基于以上討論，提出了一個求解多智能體優(yōu)化問題的分布式指數(shù)時間收斂的算法。

1 預備知識和問題表述

1.1 代數(shù)圖論

多智能體系統(tǒng)各智能體之間的通訊拓撲可以用圖進行描述。令G={V,E,B} 表示一個拓撲圖，其中V={v1,v2,…,vn} 表示其節(jié)點的集合，n為圖中節(jié)點個數(shù)，節(jié)點的下標集合為In；E?V×V表示邊的集合，eij=(vi,vj)表示圖的邊；鄰接矩陣B=[bij]，其中bij為非負實數(shù)，表示節(jié)點vi到節(jié)點vj的連接權(quán)重。如果節(jié)點vi可以接收到節(jié)點vj的信息，則bij>0；否則，bij=0，假設(shè)相連節(jié)點之間連接權(quán)重均為1，拓撲圖中每個節(jié)點沒有自連，即對于所有i∈In，bij=0。如果一個拓撲圖的鄰接矩陣B是對稱矩陣，則稱該拓撲圖是無向的。一個圖的Laplacian 矩陣定義為L=[lij]∈Rn×n。當i=j時當i≠j時，lij=-bij。對于任意節(jié)點vi，定義其鄰域節(jié)點集為Ni={vj∈V∶(vi,vj∈E)}。如果對于兩個節(jié)點vi,vj，存在下標集合{k1,k2,…,ki} 滿足，則稱節(jié)點vi到節(jié)點vj之間存在一條有向信息傳輸路徑。對于一個無向圖，如果圖中任意兩個節(jié)點都存在至少一條有向連接路徑，則稱該圖G是連通的。矩陣L所有特征根都是非負實數(shù)。矩陣L第二最小特征根λ2(L)>0，其又被稱作該撲圖的代數(shù)連通度，且因此，如果1Tε=0，則有εTLε≥λ2(L)εTε。

引理對于一個無向連通圖的Laplacian 矩陣L具有如下的性質(zhì)：

(1)0 是矩陣L的一個特征值，1 是其相應的特征向量；

(2)對任意向量ε=[ε1,ε2,…,εn]T，有下式成立

1.2 指數(shù)收斂

考慮方程

其中，f∶Rn→Rn為一個連續(xù)函數(shù)。

定義1方程(1)的解為有界的。如果對于任意的(t0,x0)∈R×Rn，都存在M=M(t0,x0)，使得對于一切t≥t0，有‖x(t0,x0)‖≤M[10]。

定義2方程(1)的解為全局指數(shù)收斂的。若存在正常數(shù)k,δ，使得任意解x(t)對唯一平衡解x0，當t≥t0時，有

1.3 問題表述

考慮由n個智能體組成的多智能體系統(tǒng)，其中每個智能體具有局部目標函數(shù)hi(xi)。要討論的問題是在保持全局等式約束的同時，最小化所有局部目標函數(shù)的和，即

x=[x1,x2,…,xn]T是一個決策向量，h(x)是全局目標函數(shù)，hi(xi)是局部目標函數(shù)，Ci0表示變量，xi是一個常量。

注1問題(2)的等式約束來自一些物理約束，如資源配置、供需平衡、借貸平衡等。

假設(shè)1智能體之間的通信拓撲是無向連通圖。

假設(shè)2目標函數(shù)hi(xi)是強凸的，存在正常數(shù)σ使得?2hi(xi)≥σ>0。

由假設(shè)2可知問題(2)具有唯一的最優(yōu)解。

2 指數(shù)時間收斂的算法設(shè)計

為求解優(yōu)化問題(2)，提出下面的分布式算法：

其中，r是常數(shù)，yi和θi是輔助變量。事實上，根據(jù)假設(shè)1和bij=bji，則有

表示算法(3)始終滿足問題(2)的等式約束，同時，將問題(2)轉(zhuǎn)化為下面的無約束優(yōu)化問題：

其中，y=[y1,y2,…,yn]T是輔助決策向量。

根據(jù)(3)式中的第二個式子，把xi(i=1,2,…,n)對yj(j=1,2,…,n)求導得

進一步，有

注意到h(x)的梯度為?h(x)=(θ1,…,θn)T。

由(4)式，得到

其中，L代表通信圖對應的拉普拉斯矩陣。顯然，h(y)的Hessian矩陣滿足

證明算法(3)的收斂性。

定理在假設(shè)1 和2 的條件下，分布式算法(3)可以在指數(shù)時間內(nèi)求解問題(2)。

證明假設(shè)凸優(yōu)化問題(2)的唯一最優(yōu)解用z=[z1,z2,…,zn]T表示。a是任意常數(shù)，如果z=a1，則z是平凡解。探討非平凡解的情況。對于任意的凸緊集Q?Rn/a1，和任意的y,w∈Q，由h(y)的強凸性可得

因為通信圖是無向連通的，所以通信圖拉普拉斯矩陣L特征向量1，ξ2,…,ξn的特征值相應的表示為0=λ1<λ2≤…≤λn，其 中‖ξi‖=1,i=2,…,n。向量y-z可以表示如下

其中，τi(i=1,2,…,n)是常數(shù)，ξ=τ2ξ2+…+τn ξn，則

注意到

根據(jù)假設(shè)2，得

由(8)式，進一步得到

將(5)式代入上式的右邊

由于0 是拉普拉斯矩陣L特征向量1 的單特征值，則L1=0。因此

對于(7)式，設(shè)w=z。當?h(z)=0，有

將(6)式代入(10)式得

根據(jù)假設(shè)2得

結(jié)合(9)和(11)有

注意，‖ξ‖≠0對非平凡解成立。因此

選取Lyapunov函數(shù)

對(14)式求導得

再由(10)式可得y指數(shù)收斂到z。即算法(3)在指數(shù)時間內(nèi)能求解問題(2)。

3 數(shù)值模擬

用電力調(diào)度問題來測試算法(3)的性能?？紤]一個由3 臺發(fā)電機和3 個負載組成的電力系統(tǒng)，其中節(jié)點1、2、3 表示發(fā)電機，節(jié)點4、5、6 表示對應的負載，如圖1所示。

圖1 電力系統(tǒng)

設(shè)xi(i=1,2,3)和C分別表示由第i臺發(fā)電機產(chǎn)生的有效功功率和總負載需求。在電力工程中，發(fā)電機的成本函數(shù)hi(xi)一般由二次函數(shù)近似：hi(xi)=其中τi，βi和ηi代表成本系數(shù)?？紤]的電力系統(tǒng)經(jīng)濟調(diào)度問題可以表達為

顯然，算法(3)可以直接用于解決經(jīng)濟調(diào)度問題(16)。假設(shè)總負荷需求C為420 MW，成本系數(shù)τi，βi和ηi如表1所示。將初始狀態(tài)設(shè)為

表1 發(fā)電機成本參數(shù)

利用算法(3)得到的經(jīng)濟調(diào)度問題(16)解的動態(tài)軌跡，模擬結(jié)果顯示最優(yōu)解為

4 結(jié)語

對一類等式約束的分布凸優(yōu)化問題，基于多智能體系統(tǒng)設(shè)計了一個指數(shù)時間收斂的算法，利用Lyapunov 函數(shù)理論，證明了算法的指數(shù)收斂性。最后通過實例模擬驗證了理論分析的有效性。