基于連續(xù)時(shí)間的二階多智能體分布式資源分配算法

時(shí)俠圣 楊 濤 林志赟 王雪松

隨著控制技術(shù)的發(fā)展,將控制技術(shù)與優(yōu)化算法相結(jié)合,以分布式方式求解網(wǎng)絡(luò)優(yōu)化問(wèn)題成為近年來(lái)的研究熱點(diǎn)[1-7].作為網(wǎng)絡(luò)優(yōu)化領(lǐng)域里一個(gè)重要分支,資源分配在網(wǎng)絡(luò)系統(tǒng)中有很廣泛的應(yīng)用,例如能源系統(tǒng)中的經(jīng)濟(jì)調(diào)度和通訊網(wǎng)絡(luò)中的網(wǎng)絡(luò)利用率最優(yōu)化等問(wèn)題.

近些年來(lái),基于離散時(shí)間算法的分布式優(yōu)化問(wèn)題已經(jīng)得到了一些很好的結(jié)果.例如,文獻(xiàn)[8-10]等針對(duì)有約束或無(wú)約束最優(yōu)協(xié)調(diào)問(wèn)題設(shè)計(jì)了一種基于梯度的算法.而對(duì)于強(qiáng)連通有向網(wǎng)絡(luò)下的資源分配問(wèn)題,文獻(xiàn)[11-13]等基于多智能體一致性理論,分別設(shè)計(jì)一種基于余量和基于Push-sum (推和)的分布式優(yōu)化算法.更多離散時(shí)間算法可參考文獻(xiàn)[14-19]及它們的引用文獻(xiàn),其中收斂速度最快的為文獻(xiàn)[17]的線性收斂,但是依然無(wú)法預(yù)知其收斂時(shí)間.另一方面,隨著信息物理系統(tǒng)和連續(xù)時(shí)間控制技術(shù)的發(fā)展[20-25],利用基于連續(xù)時(shí)間的分布式控制策略也已被廣泛應(yīng)用于解決資源分配問(wèn)題,特別是其中的有限/固定/預(yù)定時(shí)間收斂理論,更符合實(shí)際系統(tǒng)需求.為了解決無(wú)向網(wǎng)絡(luò)下的無(wú)約束資源分配問(wèn)題,基于多智能體一致性理論,文獻(xiàn)[26]設(shè)計(jì)了一種指數(shù)收斂速度二階連續(xù)時(shí)間算法.不同于文獻(xiàn)[26]的漸近式收斂,文獻(xiàn)[27-30]分別設(shè)計(jì)一種基于固定時(shí)間和預(yù)定時(shí)間收斂的連續(xù)時(shí)間算法.在此基礎(chǔ)上,文獻(xiàn)[31-35]提出了一種考慮不等式約束的分布式算法,該算法利用映射算子將節(jié)點(diǎn)狀態(tài)限制在不等式約束集合內(nèi),從而得到了一種無(wú)初值約束分布式算法,并在文獻(xiàn)[35]中實(shí)現(xiàn)了固定時(shí)間收斂.與映射法不同,文獻(xiàn)[36-38]和文獻(xiàn)[39]利用精確罰函數(shù)法將局部等式約束轉(zhuǎn)移到目標(biāo)函數(shù)中,分別設(shè)計(jì)了一階和二階連續(xù)時(shí)間算法.而對(duì)于有向網(wǎng)絡(luò)下的資源分配問(wèn)題,也有很多學(xué)者提出了解決方法,例如奇異攝動(dòng)算法[40]、原始對(duì)偶算法[41]、映射法[42]、二階連續(xù)時(shí)間算法[43]以及微分映射法[44].

從前面的討論可以看出,目前只有一階分布式優(yōu)化算法在連續(xù)時(shí)間和離散時(shí)間情況下都取得了顯著的效果.而有關(guān)二階多智能體分布式優(yōu)化算法的文獻(xiàn)不是很多.其中文獻(xiàn)[26,45-46]研究了無(wú)約束資源分配問(wèn)題,并沒(méi)有將節(jié)點(diǎn)局部不等式約束考慮進(jìn)來(lái).但在許多工程應(yīng)用中,節(jié)點(diǎn)的決策會(huì)受到局部約束,這些約束可能來(lái)自安全考慮、生產(chǎn)能力、執(zhí)行能力等,如電力系統(tǒng)中發(fā)電機(jī)的輸出功率的邊界限制[1].文獻(xiàn)[39]和文獻(xiàn)[43]分別利用精確罰函數(shù)法和微分映射法解決了資源分配問(wèn)題中的局部不等式約束.但是上述兩篇文獻(xiàn)所提出的算法都對(duì)初始狀態(tài)進(jìn)行限定.而這種初始化協(xié)調(diào)過(guò)程可能只適應(yīng)于靜態(tài)網(wǎng)絡(luò).然而對(duì)于一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)來(lái)說(shuō),一旦網(wǎng)絡(luò)發(fā)生變化或者節(jié)點(diǎn)生產(chǎn)約束發(fā)生突變時(shí),就必須重新分配資源配置更改.因此這些優(yōu)化算法重新啟動(dòng)時(shí),必須重新進(jìn)行初始化協(xié)調(diào),這大大降低了它們的適用性.此外,文獻(xiàn)[26,39,45-46]中考慮的都是無(wú)向網(wǎng)絡(luò).

然而,由于通信延遲等造成的通信中斷會(huì)使得無(wú)向網(wǎng)絡(luò)變成有向網(wǎng)絡(luò),進(jìn)而可能會(huì)使得一些基于無(wú)向網(wǎng)絡(luò)的分布式算法失效.另外,無(wú)向網(wǎng)絡(luò)是有向平衡網(wǎng)絡(luò)的一個(gè)特例,在工程應(yīng)用中,有向平衡網(wǎng)絡(luò)比無(wú)向網(wǎng)絡(luò)也更易于實(shí)現(xiàn),因此研究有向平衡網(wǎng)絡(luò)上的資源分配問(wèn)題是有意義的.由于二階多智能體系統(tǒng)的廣泛存在,如:移動(dòng)機(jī)器人、發(fā)電機(jī)等,本文考慮二階多智能體的分布式資源分配問(wèn)題.針對(duì)有向平衡網(wǎng)絡(luò)下的資源分配問(wèn)題,本文首先利用局部不等式及其梯度設(shè)計(jì)第一種算法,其次利用固定時(shí)間理論和映射算子設(shè)計(jì)第二種算法,其中映射算子用于處理不等式約束,且確保此不等式在固定時(shí)間內(nèi)即可滿足,此方法可推廣到同類型帶局部不等式約束的分布式優(yōu)化問(wèn)題中.

本文所提算法創(chuàng)新點(diǎn)如下:

1) 相比于文獻(xiàn)[26,45-46],本文將二階多智能體節(jié)點(diǎn)的局部不等式約束考慮進(jìn)來(lái);

2) 與文獻(xiàn)[39]的無(wú)向網(wǎng)絡(luò)相比,我們研究有向平衡網(wǎng)絡(luò)下的資源分配問(wèn)題;

3) 相比于文獻(xiàn)[43],本文所提兩種算法均對(duì)初始值無(wú)要求,且分別實(shí)現(xiàn)漸近和指數(shù)收斂;

4) 針對(duì)節(jié)點(diǎn)局部不等式約束,本文結(jié)合了固定時(shí)間收斂理論和映射算子,使得收斂速度上會(huì)比單純使用映射算子方法的算法要快,并通過(guò)案例仿真可以驗(yàn)證此性質(zhì).

本文后續(xù)內(nèi)容結(jié)構(gòu)如下:在第1 節(jié)中,將完成問(wèn)題描述以及預(yù)備知識(shí),其中預(yù)備知識(shí)包括代數(shù)圖論、固定時(shí)間收斂理論等;在第2 節(jié)中,首先進(jìn)行算法設(shè)計(jì),分別是漸近收斂算法和指數(shù)收斂算法,其次給出相應(yīng)的最優(yōu)性引理以及各自算法的收斂性分析;在第3 節(jié)中,給出3 個(gè)仿真案例;本文的總結(jié)與展望放在第4 節(jié)中.

1 問(wèn)題描述及預(yù)備知識(shí)

1.1 問(wèn)題描述

本文所研究的二階多智能體系統(tǒng)包含n個(gè)智能體節(jié)點(diǎn),每個(gè)智能體i都采用如下動(dòng)力學(xué)模型:

1.2 代數(shù)圖論

針對(duì)式 (1)所示的多智能體系統(tǒng),智能體節(jié)點(diǎn)間的通信鏈路可以用圖G=(V,E,A) 表示,其中V={1,2,···,n} 表示節(jié)點(diǎn)集合,E表示節(jié)點(diǎn)間的通信鏈路集合,A表示各節(jié)點(diǎn)間的通信權(quán)重.若存在有向?qū)?(i,j)∈E,則表示節(jié)點(diǎn)i能夠接收到來(lái)自節(jié)點(diǎn)j的信息,此時(shí)就有aij＞0.此外,本文中不考慮節(jié)點(diǎn)存在自環(huán),即aii=0.若網(wǎng)絡(luò)G中存在一組有向?qū)?(i,i1),(i1,i2),···,(ik,j),則稱節(jié)點(diǎn)j到節(jié)點(diǎn)i是可達(dá)的.若網(wǎng)絡(luò)G任意一點(diǎn)到其他節(jié)點(diǎn)都是可達(dá)的,則稱網(wǎng)絡(luò)G是強(qiáng)連通的.定義網(wǎng)絡(luò)G的拉普拉斯矩

2 分布式連續(xù)時(shí)間控制算法

針對(duì)問(wèn)題 (2),基于多智能體固定時(shí)間理論,本節(jié)將設(shè)計(jì)兩種基于映射的分布式優(yōu)化算法,首先設(shè)計(jì)一類漸近收斂算法,其次設(shè)計(jì)一類指數(shù)收斂算法,并給出算法的收斂性分析.

2.1 算法設(shè)計(jì)

由引理1 可知,解決問(wèn)題 (2)的關(guān)鍵是找到最優(yōu)拉格朗日乘子.為實(shí)現(xiàn)算法分布式演化,本文為每個(gè)智能體都分配一個(gè)本地拉格朗日乘子λi∈Rm,基于狀態(tài)反饋和梯度下降法,利用局部不等式約束的梯度信息,每個(gè)節(jié)點(diǎn)將通過(guò)以下算法自主收斂到問(wèn)題 (2)的最優(yōu)分配方案:

2.2 算法收斂性分析

3 案例仿真

現(xiàn)在我們提供仿真案例來(lái)驗(yàn)證之前所提算法的有效性.第一個(gè)案例數(shù)據(jù)來(lái)自文獻(xiàn)[43],第二個(gè)仿真案例數(shù)據(jù)來(lái)自文獻(xiàn)[44].

案例 1.針對(duì)6 發(fā)電機(jī)系統(tǒng),每個(gè)發(fā)動(dòng)機(jī)的代價(jià)函數(shù)采用如下二次函數(shù)形式:各發(fā)電機(jī)代價(jià)函數(shù)系數(shù)、初始值xi(0)、期望功率di和輸出功率約束總結(jié)在表1 中.令算法(8)和算法(9)中控制參數(shù)為α=2.75,β=380,γ=30,μ=0.5,ν=2.從任意初始狀態(tài)出發(fā),詳細(xì)的仿真軌跡分別如如圖1和圖2所示,從圖中可知問(wèn)題的最優(yōu)值為x*=[23.01;35;50;31.01;45.78;30.19]T,此結(jié)果與文獻(xiàn)[43]一致.相比于算法(8)中的梯度法,由于算法(9)采用映射算子和固定時(shí)間收斂理論處理問(wèn)題(2)中的局部不等式約束,所以算法(9)可以很快地將超出約束范圍的節(jié)點(diǎn)快速拉回到約束范圍內(nèi).所以圖1 相比圖2,在算法到達(dá)約束邊界時(shí),有更大的波動(dòng)性.基于案例1 中的數(shù)據(jù),接下來(lái)從同一初始狀態(tài)出發(fā),將本文所設(shè)計(jì)算法與文獻(xiàn)[43]和文獻(xiàn)[39]進(jìn)行收斂速度對(duì)比,結(jié)果如圖3 所示(文獻(xiàn)[43]中控制參數(shù)設(shè)置與本文相同).其中算法誤差定義為,其中最優(yōu)值由集中式拉格朗日乘子法求得.則e表示算法運(yùn)行解與理論最優(yōu)解的差值.從圖3 可以看出,本文所設(shè)計(jì)算法下誤差下降較快,即擁有更快的收斂速度,且算法在穩(wěn)定點(diǎn)時(shí)有更好的穩(wěn)定性.而文獻(xiàn)[39]由于在端點(diǎn)處梯度不唯一,會(huì)導(dǎo)致算法在穩(wěn)定點(diǎn)時(shí)有輕微波動(dòng).此外,算法 (9)和文獻(xiàn)[39]在邊界點(diǎn)的波動(dòng)性導(dǎo)致其誤差e要比算法 (8)和文獻(xiàn)[43]中的誤差稍大.

圖1 案例1 中算法(8)的各發(fā)電機(jī)曲線圖Fig.1 The trajectories of each generator by algorithm (8) in case 1

圖2 案例1 中算法(9)的各發(fā)電機(jī)曲線圖Fig.2 The trajectories of each generator by algorithm (9) in case 1

圖3 基于案例1 數(shù)據(jù)的算法性能對(duì)比Fig.3 The comparison between the existence algorithms and ours based on case 1

表1 案例1 各節(jié)點(diǎn)參數(shù)Table 1 System parameters in case 1

案例2.針對(duì)4 節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò),其中資源決策變量xi∈R2,且節(jié)點(diǎn)目標(biāo)函數(shù)分別為

其中

虛擬資源量d設(shè)定為d1=[2,1]T,d2=[2,3]T,d3=[2,4]T,d4=[1,5]T.算法初始值設(shè)定為x1(0)=[2,0]T,x2(0)=[1.5,0.5]T,x3(0)=[1,1]T,x4=[4,6]T,算法控制參數(shù)設(shè)定為α=2,β=75,γ=30,μ= 0.2,ν=2.其仿真曲線分別如圖4 和圖5 所示,星點(diǎn)表示各節(jié)點(diǎn)的最優(yōu)解位置.通過(guò)仿真案例2 可以發(fā)現(xiàn),本文所設(shè)計(jì)算法對(duì)高維資源分配問(wèn)題亦是有效的.為了展示各算法在二維資源分配問(wèn)題上的收斂速度,現(xiàn)將本文所設(shè)計(jì)算法與文獻(xiàn)[43]進(jìn)行對(duì)比,收斂速度圖展示在圖6,從圖中可以看出,指數(shù)收斂算法 (9)比漸近收斂算法 (8)收斂稍快,該結(jié)果與一維資源問(wèn)題圖3 所得結(jié)論一致.

圖4 案例2 中算法 (8)的各節(jié)點(diǎn)仿真結(jié)果軌跡Fig.4 The trajectories of each agent by algorithm (8) in case 2

圖5 案例2 中算法 (9)各節(jié)點(diǎn)仿真結(jié)果軌跡Fig.5 The trajectories of each agent by algorithm (9) in case 2

圖6 基于案例2 數(shù)據(jù)的算法性能對(duì)比Fig.6 The comparison between the existence algorithms and ours based on case 2

案例3.針對(duì)IEEE-39 總線系統(tǒng),包含10 個(gè)發(fā)電單元,各發(fā)電單元的通信鏈路及其權(quán)重如下圖7 所示.各發(fā)電單元的發(fā)電成本為且有a1=[0.096 0.082]T∈R10和a2=[1.22,3.41,2.53,4.02,2.90,0.072,0.105,0.082,0.078,0.90,0.085,0.092,0.155,2.72,1.22,4.20,3.53,3.02]T∈R10,其中a1=[a1,1,···,an,1],a2=[a1,1,···,an,1]∈R10.各節(jié)點(diǎn)的局部不等式約束和虛擬分配量分別為xi∈[0,300] 和di=250.以零初始狀態(tài)出發(fā),在控制參數(shù)α=2.75,β=380,γ=30作用下,算法 (8)和 (9)各自對(duì)應(yīng)的狀態(tài)軌跡如圖8 和圖9 所示.此外兩種算法的誤差e軌跡如圖10所示,其中誤差e定義同案例1.從圖10可知,上述系統(tǒng)最終收斂到最優(yōu)分配方案x*=[243.6524,300,216.5298,268.1785,289.1107,251.5626,275.1839,238.0504,143.4557,274.2760].

圖7 案例3 中各發(fā)電單元的通信鏈路Fig.7 The communication links of each generator in case 3

圖8 案例3 中算法 (8)的各節(jié)點(diǎn)仿真結(jié)果軌跡Fig.8 The trajectories of each agent by algorithm (8) in case 3

圖9 案例3 中算法 (9)各節(jié)點(diǎn)仿真結(jié)果軌跡Fig.9 The trajectories of each agent by algorithm (9) in case 3

圖10 案例3 中算法 (8)和 (9)的收斂速度比較Fig.10 The convergence rate comparison between algorithms (8) and (9) in case 3

4 總結(jié)

本文針對(duì)有向平衡網(wǎng)絡(luò)下的帶約束分布式資源分配問(wèn)題,基于固定時(shí)間映射算子和基于多智能體一致性的梯度下降法,設(shè)計(jì)了兩種基于二階多智能體系統(tǒng)的連續(xù)時(shí)間算法.所設(shè)計(jì)算法對(duì)節(jié)點(diǎn)初始狀態(tài)無(wú)約束,并且控制參數(shù)全為常數(shù).通過(guò)對(duì)一維和二維資源分配問(wèn)題數(shù)值仿真,本文所提算法的有效性也得以保證.然而在實(shí)際系統(tǒng)中,通信網(wǎng)絡(luò)通常會(huì)存在信息交互延遲,而信息延遲給算法分析帶來(lái)了很大的困難.此外,非平衡有向網(wǎng)絡(luò)在實(shí)際系統(tǒng)中也是存在的,所以在后續(xù)研究中,我們將考慮由通信延遲等造成的有向非平衡網(wǎng)絡(luò)下二階多智能體資源分配問(wèn)題.