一階一致性收斂速率的拓?fù)鋬?yōu)化方法綜述

陳新莊，郭志偉，李江榮

（1. 延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西延安 716000；2. 西北工業(yè)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西西安 710072）

多智能體系統(tǒng)是分布式人工智能領(lǐng)域的前沿和研究熱點(diǎn)，在傳感器網(wǎng)絡(luò)［1］、智慧電網(wǎng)［2］、智能交通［3］、機(jī)器人［4］、數(shù)據(jù)網(wǎng)絡(luò)［5］、分布式計(jì)算［6］、航空航天［7-9］等多個(gè)領(lǐng)域都有重要的應(yīng)用。在多智能體系統(tǒng)的研究中，一致性問(wèn)題［10-13］是研究其他分布式協(xié)同控制問(wèn)題的基礎(chǔ)，受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注和深入研究。

多智能體系統(tǒng)一致性協(xié)議的收斂速率，決定了多智能體系統(tǒng)從初始狀態(tài)達(dá)到一致的快慢，是一致性協(xié)議的重要性能量化指標(biāo)。為了提高多智能體系統(tǒng)達(dá)到一致性的收斂速率，通常從改進(jìn)一致性協(xié)議和優(yōu)化通信拓?fù)?個(gè)方面進(jìn)行研究。早期的一致性協(xié)議是漸近收斂的，為了提高多智能體系統(tǒng)達(dá)到一致的收斂速度，大量學(xué)者對(duì)一致性協(xié)議進(jìn)行了深入研究并進(jìn)行了持續(xù)的改進(jìn)，設(shè)計(jì)了有限時(shí)間收斂［14］和指定時(shí)間收斂［15］的一致性協(xié)議。然而，相比于控制協(xié)議，從網(wǎng)絡(luò)拓?fù)浣嵌葘?duì)收斂速度的研究相對(duì)滯后，很多問(wèn)題依然沒有有效解決。

當(dāng)多智能體系統(tǒng)的一致性協(xié)議給定時(shí)，收斂速度是由多智能體系統(tǒng)的通信拓?fù)涞奶卣髦禌Q定的［11-13］。例如，一階多智能體系統(tǒng)在漸近收斂的一致性協(xié)議下［11-12］，當(dāng)通信拓?fù)錇闊o(wú)向圖時(shí)，系統(tǒng)的收斂速度由網(wǎng)絡(luò)拓?fù)涞拇鷶?shù)連通度［16］（拉普拉斯矩陣的第二小特征值）決定，代數(shù)連通度越大，收斂速率越高。對(duì)高階多智能體系統(tǒng)，一致性通常由網(wǎng)絡(luò)拓?fù)涞拇鷶?shù)連通度和譜半徑（拉普拉斯矩陣的最大特征值）共同決定，代數(shù)連通度越大、譜半徑越小，系統(tǒng)的一致性收斂速度越快［17-18］。受智能體個(gè)體通信能力、通信范圍和環(huán)境等約束，往往無(wú)法讓任意2個(gè)智能體間都進(jìn)行通信。如何在給定的限制條件下設(shè)計(jì)網(wǎng)絡(luò)或優(yōu)化已有網(wǎng)絡(luò)，使得一致性收斂速率最高，是非常有意義的問(wèn)題。

一階連續(xù)多智能體系統(tǒng)是最簡(jiǎn)單的一類多智能體系統(tǒng)，即所有的智能體的狀態(tài)是關(guān)于時(shí)間的連續(xù)函數(shù)，且動(dòng)力學(xué)是一階積分器模型。連續(xù)模式的一致性協(xié)議設(shè)計(jì)了理想情況下系統(tǒng)達(dá)到一致的控制算法。然而，由于受通信硬件、通信帶寬和計(jì)算能力等限制，智能體間無(wú)法在短時(shí)間進(jìn)行無(wú)數(shù)次通信。因此，學(xué)者們開發(fā)了周期采樣和事件觸發(fā)模式的一致性協(xié)議［19-22］，減少了智能體間的通信量，降低了系統(tǒng)通信的要求，讓多智能體系統(tǒng)的工程應(yīng)用成為可能。在保證收斂的前提下，這三類一階一致性協(xié)議的收斂速率由通信拓?fù)涞拇鷶?shù)連通度決定的。優(yōu)化調(diào)整通信拓?fù)浣Y(jié)構(gòu)，是提高多智能體系統(tǒng)一致性收斂速率的有效方法。學(xué)者們對(duì)代數(shù)連通度的最大化進(jìn)行了大量的研究。由于代數(shù)連通度最大化問(wèn)題是NP-難問(wèn)題［23］，若同時(shí)考慮各種約束和限制，問(wèn)題會(huì)更加復(fù)雜。

針對(duì)通信拓?fù)錇闊o(wú)向圖的一階多智能體系統(tǒng)，將在第二節(jié)介紹連續(xù)、周期采樣和事件觸發(fā)模式的一致性協(xié)議及其收斂速度。第三節(jié)針對(duì)以提高收斂速率為目標(biāo)的代數(shù)連通度最大化問(wèn)題，對(duì)當(dāng)前采用的方法進(jìn)行分類總結(jié)。最后，針對(duì)多智能體系統(tǒng)收斂速度和通信量的優(yōu)化，提出了當(dāng)前可進(jìn)一步研究的若干問(wèn)題。

1 多智能體系統(tǒng)的拓?fù)浣＜皥D論基本知識(shí)

一個(gè)包含n 個(gè)智能體的多智能體系統(tǒng)，其通信拓?fù)溆脠D論中的圖進(jìn)行建模。單個(gè)智能體i用圖中的頂點(diǎn)vi表示，兩個(gè)智能體之間的通信用圖中的邊表示。若智能體i和智能體j能相互通信，則用圖中的無(wú)向邊vivj表示其通信關(guān)系；若智能體i能接收到智能體j的信息，但是智能體能j不能接收到智能體i的信息，則用圖中的有向邊(vj，vi)表示其通信關(guān)系。本文僅考慮多智能體系統(tǒng)通信拓?fù)錇楹?jiǎn)單無(wú)向圖的場(chǎng)景，即所有通信的智能體進(jìn)行雙向通信。

令G =(V(G)，E(G)) 是 一 個(gè) 無(wú) 向 圖，其 中V(G) ={v1，…，vn}表示圖G 的頂點(diǎn)集合，E(G)表示圖G 中邊的集合。如果圖G 的每一條邊vivj都賦予一個(gè)非負(fù)權(quán)值wij，則稱圖G 為賦權(quán)圖。非賦權(quán)圖可以看作邊上權(quán)值為1的特殊賦權(quán)圖。Ga是一個(gè)非賦權(quán)簡(jiǎn)單無(wú)向圖，圖Gb是與Ga有相同邊集的賦權(quán)無(wú)向圖。如果v是圖G 的頂點(diǎn)，那么將v及其與之關(guān)聯(lián)的邊都刪除得到的圖記作G - v。如果vivj是圖G 的一條邊，那么將這條邊刪除得到的圖記作G - vivj；否則，將邊vivj添加到圖G 得到的圖記作G + vivj。圖論相關(guān)的符號(hào)和定義，參考圖論教材［24］。

假設(shè)圖G 是一個(gè)賦權(quán)圖，其鄰接矩陣A(G) =[auv]∈Rn×n定義為：如果uv ∈E(G)，則aij= wij，否則aij= 0。令Ni={vj|vivj∈E(G)}表示頂點(diǎn)vi的鄰居集合。圖G 中頂點(diǎn)vi的賦權(quán)度定義為di=令D(G) = diag(d1，…，dn)為頂點(diǎn)的度構(gòu)成的對(duì)角矩陣，則圖G 的拉普拉斯矩陣為L(zhǎng)(G) =D(G) - A(G)。為了簡(jiǎn)化描述，圖G的拉普拉斯矩陣L(G)的特征值λk(L(G))或特征向量uk(L(G))簡(jiǎn)稱為圖G的特征值λk(G)或特征向量uk(G)。

由于無(wú)向圖G 的拉普拉斯矩陣L(G)是半正定的實(shí)對(duì)稱矩陣，其特征值可以按照非遞減的順序排列為λ1(G) ≤λ2(G) ≤…≤λn(G)，其中λ1(G) = 0且對(duì)應(yīng)的特征向量為1。圖G 的第二小特征值λ2(G) 稱 為 圖 G 的 代 數(shù) 連 通 度（algebraic connectivity），其對(duì)應(yīng)的特征向量稱為Fiedler 向量。圖G 的最大特征值λn(G) 稱為圖G 的譜半徑（Spectral radius）。圖G 是連通的，當(dāng)且僅當(dāng)其代數(shù)連通度大于0，即λ2(G) > 0。

2 一階多智能體系統(tǒng)的一致性協(xié)議及其收斂速度

當(dāng)通信拓?fù)錇闊o(wú)向圖時(shí)，在連續(xù)、周期采樣和事件觸發(fā)模式的一致性協(xié)議下，通信拓?fù)涞拇鷶?shù)連通度越大，收斂速率越高。并且，對(duì)周期采樣和事件觸發(fā)模式的一致性協(xié)議，為了讓系統(tǒng)的通信負(fù)荷更小，還需要通信拓?fù)涞淖V半徑越小越好。

2.1 連續(xù)模式的一致性協(xié)議及其收斂速率

假設(shè)多智能體系統(tǒng)有n個(gè)智能體，智能體i的狀態(tài)ξi(t)表示一組表征智能體特征、隨時(shí)間變化的物理量，如溫度、位置、速度、加速度等。例如，如果智能體為平面上移動(dòng)的質(zhì)點(diǎn)，二維坐標(biāo)位置表示其狀態(tài)，狀態(tài)向量記為ξi(t) =[xi(t)，yi(t)]T；如果智能體為在平面上的運(yùn)動(dòng)的無(wú)人車，二維坐標(biāo)位置和速度表示其狀態(tài)，此時(shí)ξi(t) =[xi(t)，yi(t)，vxi(t)，vyi(t)]T為其狀態(tài)向量。

假設(shè)每個(gè)智能體的動(dòng)力學(xué)為一階積分器ξi(t) =ui(t)，其中ui(t)為控制輸入。在通用的一致性協(xié)議［12-13］下，頂點(diǎn)i的控制量為

其中，Ni為智能體i的鄰居集合。在一致性協(xié)議（1）作 用 下，如 果 對(duì) 任 意 的i，j = 1，2，…，n 都 有則 稱 多 智 能 體 系 統(tǒng) 達(dá) 到一致。

定理1［12，13］對(duì)一階多智能體系統(tǒng)，如果通信拓?fù)銰 為無(wú)向圖，那么在一致性協(xié)議（1）作用下，系統(tǒng)能夠達(dá)到一致當(dāng)且僅當(dāng)通信拓?fù)錇檫B通圖。一致性協(xié)議的收斂速度為e-λ2，其中λ2為通信拓?fù)涞拇鷶?shù)連通度。

由定理1，當(dāng)一階多智能體系統(tǒng)的通信拓?fù)錇闊o(wú)向圖時(shí)，代數(shù)連通度越大，一致性協(xié)議（1）的收斂速率越高。

2.2 周期采樣模式的一致性協(xié)議及其收斂速率

周期采樣模式下，每間隔固定時(shí)間h（也稱為采用周期），多智能體系統(tǒng)中的智能體間進(jìn)行一次信息交互，并更新控制輸入。

由XIE等［19］設(shè)計(jì)的周期采樣一致性協(xié)議如下

其中，ui(t)為智能體i 在時(shí)刻t 的控制輸入，h > 0 為采樣周期，為采樣次數(shù)。由一致性協(xié)議（2），控制輸入ui(t)為分段函數(shù)，在2 次采樣間隔的時(shí)間內(nèi)，保持不變。

定理2［19］對(duì)一階多智能體系統(tǒng)，如果通信拓?fù)銰為無(wú)向圖，那么在周期采樣一致性協(xié)議（2）作用下，系統(tǒng)能夠達(dá)到一致當(dāng)且僅當(dāng)通信拓?fù)錇檫B通圖，且采樣周期滿足條件0 < h < 2/λn(G)。一致性協(xié)議（2）具有指數(shù)收斂速率，指數(shù)系數(shù)由通信拓?fù)涞拇鷶?shù)連通度λ2決定。

由定理2，一階多智能體系統(tǒng)的通信拓?fù)錇闊o(wú)向圖時(shí)，譜半徑越小，可選擇更長(zhǎng)的采樣周期，收斂過(guò)程的通信負(fù)荷更小。并且，通信拓?fù)涞拇鷶?shù)連通度越大，一階一致性協(xié)議（2）的收斂速率越高。

周期采樣的一致性協(xié)議，解決了連續(xù)一致性協(xié)議模式下智能體硬件無(wú)法支持的缺陷。研究發(fā)現(xiàn)，周期采樣模式下，尤其是采樣周期的值較小時(shí)，依然存在大量無(wú)效通信［20］。

2.3 事件觸發(fā)模式的一致性協(xié)議及其收斂速率

為解決周期采樣模式下存在大量無(wú)效通信的問(wèn)題，學(xué)者們開發(fā)了事件觸發(fā)模式的一致性協(xié)議［21］。在事件觸發(fā)模式下，智能體間只在需要的時(shí)候進(jìn)行通信，極大地減少了冗余通信和冗余計(jì)算。

事件觸發(fā)模式下，智能體上都設(shè)計(jì)有事件觸發(fā)函數(shù)，當(dāng)函數(shù)滿足預(yù)設(shè)的條件時(shí)，智能體會(huì)與其鄰居智能體進(jìn)行通信。為了描述其工作原理，下面介紹DIMAROGONAS 等［22］設(shè)計(jì)的集中式事件觸發(fā)一致性協(xié)議。

假設(shè)t0，t1，…為事件觸發(fā)時(shí)刻，在一致性協(xié)議下，智能體i在時(shí)刻t的控制輸入為

其中，Ni為智能體i 的鄰居集合。由一致性協(xié)議（3），控制輸入ui(t)為分段函數(shù)，在兩次事件觸發(fā)的時(shí)間間隔內(nèi)，保持不變。

為確定事件觸發(fā)時(shí)間，定義時(shí)刻t ∈[ts，ts+1)的誤 差 向 量err(t) = ξ(ts)- ξ(t)，其 中 向 量ξ(t) =(ξ1(t)，…，ξn(t))T為系統(tǒng)的狀態(tài)向量。無(wú)向圖拓?fù)涞囊浑A系統(tǒng)在一致性協(xié)議作用下，任意時(shí)刻系統(tǒng)狀態(tài)的平均值是常數(shù)一致性協(xié)議（3）的事件觸發(fā)條件為

其中，參數(shù)0 < σ < 1，λ2和λn分別為通信拓?fù)涞淖V半徑。

定理3［21，22］對(duì)一階多智能體系統(tǒng)，如果通信拓?fù)錇闊o(wú)向圖，一致性協(xié)議（3）的事件觸發(fā)條件為（4），系統(tǒng)能夠達(dá)到一致當(dāng)且僅當(dāng)通信拓?fù)錇檫B通圖。一致性協(xié)議（3）具有指數(shù)收斂速率e2(σ-1)λ2，并且事件觸發(fā)的最小時(shí)間間隔下界為τ =其中λ2和λn分別為通信拓?fù)涞拇鷶?shù)連通度和譜半徑。

由定理3，通信拓?fù)涞淖V半徑越小，事件觸發(fā)的時(shí)間間隔會(huì)越大，收斂過(guò)程的通信負(fù)荷更小。并且，通信拓?fù)涞拇鷶?shù)連通度越大，事件觸發(fā)一致性協(xié)議（3）在觸發(fā)條件（4）下的收斂速率越高。

3 一致性收斂速率的拓?fù)鋬?yōu)化方法

一階多智能體系統(tǒng)的通信拓?fù)浯鷶?shù)連通度越大，一致性協(xié)議收斂速率越高。因此，大量學(xué)者對(duì)代數(shù)連通度的最大化問(wèn)題進(jìn)行了研究。代數(shù)連通度是量化圖連通性的重要參數(shù)［25］，在復(fù)雜網(wǎng)絡(luò)［10，26］、多智能體系統(tǒng)［12］、傳感器網(wǎng)絡(luò)［27］、交通網(wǎng)絡(luò)［28］、數(shù)字網(wǎng)絡(luò)［5］和腦科學(xué)［29］等研究領(lǐng)域都有重要應(yīng)用。例如，在復(fù)雜網(wǎng)絡(luò)中，代數(shù)連通度是體現(xiàn)網(wǎng)絡(luò)魯棒性、可靠性和同步能力的參數(shù)。在這些學(xué)科的研究中，通常要求網(wǎng)絡(luò)的代數(shù)連通度越大越好。下面針對(duì)提高一階多智能體系統(tǒng)收斂速率的研究，總結(jié)當(dāng)前采用的方法，重點(diǎn)介紹調(diào)整邊連接方式提高收斂速率的方法。

代數(shù)連通度的最大化問(wèn)題是指如何尋找一個(gè)滿足給定約束條件的拓?fù)?，使其具有最大的代?shù)連通度。MOSK-AOYAMA 證明了代數(shù)連通度增廣問(wèn)題為NP-難問(wèn)題［23］，此問(wèn)題定義為：對(duì)給定的無(wú)向圖G、非負(fù)整數(shù)k 和閾值r，能否給G 增加最多k 條邊，使得加邊后圖的代數(shù)連通度不小于閾值r。因此，當(dāng)圖的頂點(diǎn)數(shù)和邊數(shù)給定時(shí)，尋找代數(shù)連通度最大的拓?fù)浣Y(jié)構(gòu)也是NP-難問(wèn)題。

實(shí)際應(yīng)用中，受限于智能體通信鏈路數(shù)、通信半徑和通信帶寬等限制，以及通信網(wǎng)絡(luò)的連通性和抗毀性等指標(biāo)要求，代數(shù)連通度的最大化問(wèn)題會(huì)附加更多的約束條件和目標(biāo)要求。通常，這些限制和要求可以用圖中的連邊約束和參數(shù)表示，如通信鏈路數(shù)對(duì)應(yīng)于頂點(diǎn)的度限制、通信半徑可對(duì)應(yīng)表示為頂點(diǎn)的連邊限制、連通性可對(duì)應(yīng)于圖的點(diǎn)連通度或邊連通度。與僅有頂點(diǎn)數(shù)和邊數(shù)要求的代數(shù)連通度最大化問(wèn)題相比，在這些限制和需求下尋找代數(shù)連通度最大的拓?fù)浣Y(jié)構(gòu)更加困難。

3.1 特殊圖類的代數(shù)連通度

為刻畫代數(shù)連通度與圖結(jié)構(gòu)的關(guān)系，學(xué)者們研究了一些特殊圖類上的代數(shù)連通度上下界及其對(duì)應(yīng)的極圖。

對(duì)邊數(shù)較少的連通圖，由于拓?fù)浣Y(jié)構(gòu)相對(duì)簡(jiǎn)單，如樹［30］、單圈圖［31-32］和雙圈圖［33-34］，代數(shù)連通度的上下界及其極圖都有明確的刻畫。在給定頂點(diǎn)數(shù)的樹圖中，星圖的代數(shù)連通度最大、路圖的代數(shù)連通度最小。對(duì)特殊的樹圖，如毛毛蟲圖［35-36］、平衡二叉樹［37］、直徑相同的樹［38］，代數(shù)連通度的上下界和極圖也有一些比較明確的結(jié)論。單圈圖的邊數(shù)和頂點(diǎn)數(shù)相等，文獻(xiàn)［31］中研究了單圈圖的代數(shù)連通度，并對(duì)可能的拓?fù)溥M(jìn)行了排序。如果單圈圖的圈長(zhǎng)已知，那么代數(shù)連通度最大的拓?fù)渲挥袘覓爝叄?9］，代數(shù)連通度最小的拓?fù)錇榘舭籼菆D［40］。

當(dāng)圖的邊數(shù)較多時(shí)，其拓?fù)浣Y(jié)構(gòu)比較復(fù)雜，無(wú)法給出代數(shù)連通度最大或最小的拓?fù)浣Y(jié)構(gòu)，甚至無(wú)法給出代數(shù)連通度的上下界。目前，對(duì)代數(shù)連通度的上下界研究較多，主要研究的特殊圖類有二部圖、超立方體圖、哈密爾頓圖［23，25，41-42］以及給定特點(diǎn)參數(shù)特征的圖，如給定直徑、圍長(zhǎng)、周長(zhǎng)、團(tuán)數(shù)、獨(dú)立數(shù)、匹配數(shù)和控制數(shù)等［43-48］。通過(guò)結(jié)構(gòu)分析和大量實(shí)驗(yàn)，認(rèn)為邊比在頂點(diǎn)之間分布較均勻，并且直徑比較小的圖，可能具有較大的代數(shù)連通度。

3.2 代數(shù)連通度最大化問(wèn)題的數(shù)學(xué)規(guī)劃方法

為獲得代數(shù)連通度最大的通信拓?fù)洌恍W(xué)者將該問(wèn)題建模為優(yōu)化問(wèn)題，利用優(yōu)化算法進(jìn)行求解。給定一個(gè)圖G =(V0，E0)和可增加的邊數(shù)k，代數(shù)連通度的增廣問(wèn)題描述為如下的模型

式中，Ec為圖G 補(bǔ)圖的邊集。這里只有新增的邊數(shù)限制，根據(jù)實(shí)際使用，可能還有每個(gè)頂點(diǎn)的度限制di≤Δi、邊的最大權(quán)值限制wij≤ωˉ和點(diǎn)連通度限制等。

問(wèn)題（5）并不是一個(gè)嚴(yán)格凸的規(guī)劃問(wèn)題，并且被證明為NP-難問(wèn)題［39］。問(wèn)題（5）轉(zhuǎn)化為變量維數(shù)為|Ec|的0-1 整數(shù)規(guī)劃問(wèn)題，再把變量松弛為連續(xù)類型的半正定規(guī)劃問(wèn)題（SDP），進(jìn)而求解代數(shù)連通度的上界［49-50］。通常，在SDP問(wèn)題得到初始解之后，需要設(shè)計(jì)算法尋找滿足整數(shù)條件的可行解，在可行解上尋找近似最優(yōu)解。在點(diǎn)連通度大于κ 的約束下，文獻(xiàn)［51］使用分枝定界法；在給定最大直徑限制下，文獻(xiàn)［52］使用割平面法和二分法，這些算法都得到了代數(shù)連通度較大的拓?fù)浣Y(jié)構(gòu)?；谒沙诤蟮腟DP 問(wèn)題，有些學(xué)者設(shè)計(jì)了啟發(fā)式算法求解可行解，進(jìn)而得到較優(yōu)的拓?fù)?。文獻(xiàn)［53］中，作者設(shè)計(jì)了3 種計(jì)算SDP 問(wèn)題可行解的方法，提高了航空運(yùn)輸網(wǎng)絡(luò)的代數(shù)連通度。文獻(xiàn)［54］中，作者提出了2 種貪婪式啟發(fā)算法求解SDP 問(wèn)題，對(duì)代數(shù)連通度進(jìn)行了優(yōu)化，改進(jìn)了異構(gòu)光衛(wèi)星網(wǎng)絡(luò)的代數(shù)連通度。文獻(xiàn)［5］中，為提高數(shù)字物流網(wǎng)絡(luò)的代數(shù)連通度，作者提出了基于預(yù)算約束的最大-最小整數(shù)規(guī)劃模型，并提出了貪婪算法、禁忌搜索算法你和帶舍入的SDP算法進(jìn)行求解。

值得注意的是，一個(gè)分布式的多智能體系統(tǒng)，通常無(wú)法在一個(gè)計(jì)算單元獲取其全部的通信拓?fù)?，設(shè)計(jì)分布式算法對(duì)代數(shù)連通度進(jìn)行計(jì)算、估計(jì)和優(yōu)化顯得尤為重要。學(xué)者們利用多智能體系統(tǒng)分布式估計(jì)和求解分布式優(yōu)化問(wèn)題的能力，設(shè)計(jì)了估計(jì)系統(tǒng)自身拓?fù)渚W(wǎng)絡(luò)代數(shù)連通度的分布式估計(jì)算法，目前已有相當(dāng)多的結(jié)果［55-57］。最近也出現(xiàn)了使用分布式優(yōu)化思想對(duì)代數(shù)連通度進(jìn)行優(yōu)化的文獻(xiàn)［58-59］。

3.3 結(jié)構(gòu)或權(quán)值調(diào)整的代數(shù)連通度優(yōu)化方法

針對(duì)給定的無(wú)向圖，在約束（如頂點(diǎn)的度）條件限制下，可采用調(diào)整連邊方式或調(diào)整邊權(quán)值的方法，使代數(shù)連通度增加。圖的連邊方式調(diào)整通常采用的方法有加邊、邊重連（刪邊再加邊）、邊旋轉(zhuǎn)、邊交換等操作。用這些操作可構(gòu)造貪婪算法，迭代進(jìn)行結(jié)構(gòu)優(yōu)化，進(jìn)而提高代數(shù)連通度。因此，這些操作優(yōu)化之后得到的圖，無(wú)法保證是最優(yōu)的結(jié)構(gòu)。

3.3.1 增加邊的方法

對(duì)給定的無(wú)向圖，添加k條邊，使得加邊之后得到的圖具有最大的代數(shù)連通度。文獻(xiàn)［49］指出，通過(guò)向給定圖添加邊來(lái)最大化代數(shù)連通度是一個(gè)困難的組合問(wèn)題。當(dāng)增加的邊數(shù)k 較大時(shí)，求最優(yōu)解是異常困難的。因此，學(xué)者們研究添加一條邊，使代數(shù)連通度增加最大的方法，進(jìn)而設(shè)計(jì)貪婪算法，使得添加k 條邊后，得到的拓?fù)渚哂休^大的代數(shù)連通度［53，60-61］。

給無(wú)向圖增加一條邊，所有的特征值都不會(huì)減小，拓?fù)渥兓昂蟮奶卣髦禎M足如下的交錯(cuò)引理。

引 理1［32］假 設(shè)G 是n 個(gè)頂 點(diǎn) 的無(wú) 向圖，vi和vj是圖G 的兩個(gè)頂點(diǎn)，且vivj?E(G)。令G′= G +vivj，則 有λ1(G) ≤λ1(G′)≤λ2(G) ≤λ2(G′)≤…≤λn(G) ≤λn(G′)。

由上述引理可知，當(dāng)圖G 的代數(shù)連通度重?cái)?shù)大于等于2時(shí)，新增一條邊，其代數(shù)連通度依然保持不變。然而，當(dāng)圖G 的代數(shù)連通度重?cái)?shù)大于等于2時(shí)，刪除一條邊，代數(shù)連通度可能會(huì)減小。

利用交錯(cuò)引理，以及特征多項(xiàng)式在相鄰兩個(gè)特征值區(qū)間的單調(diào)性，用二分法可以快速計(jì)算加一條邊之后的代數(shù)連通度。基于此理論，KIM 設(shè)計(jì)了加多條邊的迭代算法［62］，在每一步迭代中選擇使代數(shù)連通度增加最多的邊。

圖的特征向量也可用于預(yù)測(cè)增加邊之后圖的特征值變化情況。根據(jù)圖的特征值和特征向量，分析和預(yù)測(cè)圖結(jié)構(gòu)發(fā)生變化之后的特征值是非常有意義工作。如下定理給出了增加或刪除一條邊之后特征值保持不變的場(chǎng)景。

定理4［63］假設(shè)G 是無(wú)向圖，vi和vj是圖G 的兩個(gè)頂點(diǎn)。令λk為圖G 的特征值，uk為其對(duì)應(yīng)的特征向量。當(dāng)vivj?E(G)時(shí)，如果uk(i) = uk(j)，那么λk也是圖G + vivj的特征值；當(dāng)vivj∈E(G) 時(shí)，如果uk(i) = uk(j)，那么λk也是圖G - vivj的特征值。

由上述定理4 可知，如果u2(i) = u2(j)，那么新增一條邊vivj，圖的代數(shù)連通度λ2保持不變。實(shí)驗(yàn)發(fā)現(xiàn)，如果頂點(diǎn)vi和vj對(duì)應(yīng)的值|u2(i) - u2(j)|越大，那么圖G + vivj的代數(shù)連通度可能越大。研究發(fā)現(xiàn)，添加邊vivj時(shí)，|u2(i) - u2(j)|可近似為代數(shù)連通度增加函數(shù)的一階導(dǎo)數(shù)［53，62］?；诖死碚?，可設(shè)計(jì)貪婪的算法［53，60-62，64-65］，每次迭代僅需計(jì)算Fiedler 向量u2，然后尋找|u2(i) - u2(j)|值最大的兩個(gè)頂點(diǎn)，再添加一條邊。

事實(shí)上，基于最大|u2(i) - u2(j)|添加的一條邊vivj，無(wú)法保證vivj是最優(yōu)的，即存在其他的邊，添加該邊后，代數(shù)連通度更大。但由于|u2(i) - u2(j)|的計(jì)算簡(jiǎn)單，可解釋性強(qiáng)，依然被很多學(xué)者用于選擇增加連邊的策略。例如，邊重連的方法［65-66］，先刪除若干條|u2(i) - u2(j)|值較小的邊，然后再增加|u2(i) - u2(j)|值較大的邊。

基于Fiedler向量的加邊方法需要計(jì)算圖的特征向量，當(dāng)頂點(diǎn)數(shù)目較多時(shí)，準(zhǔn)確地計(jì)算特征向量的是比較困難的。因此，有些學(xué)者研究了其他的加邊策略，如以最小度頂點(diǎn)為端點(diǎn)，隨機(jī)選擇一個(gè)頂點(diǎn)添加一條邊［60］或選擇與之距離最遠(yuǎn)的頂點(diǎn)添加邊［67］。這些連邊策略能夠?qū)Υ鷶?shù)連通度進(jìn)行較大的改進(jìn)，并且具有較小的計(jì)算量，適用于規(guī)模較大的網(wǎng)絡(luò)。

3.3.2 邊旋轉(zhuǎn)操作的方法

設(shè)G是一個(gè)賦權(quán)圖，uv1∈E(G)且v2是圖G中不同于的u和v1頂點(diǎn)。將邊uv1從頂點(diǎn)v1旋轉(zhuǎn)到v2的操作定義為：如果uv2∈E(G)，那么設(shè)置wuv2= wuv1+ wuv2，再刪除邊uv1；否則，在G 中增加邊uv2，設(shè)置wuv2=wuv1，再刪除邊uv1。將邊uv1從頂點(diǎn)v1旋轉(zhuǎn)到v2得到的圖記作G′= rotate(G，uv1，uv2)。

由定義可知，邊的旋轉(zhuǎn)操作有兩類。如圖1 所示，v1v5是圖Ga的一條邊，將邊v1v5的頂點(diǎn)v5旋轉(zhuǎn)到v2，得到圖Gb= rotate(Ga，v1v5，v1v2)，此時(shí)圖中減少一條邊；將邊v1v5的頂點(diǎn)v5旋轉(zhuǎn)到v4，得到圖Gc=rotate(Ga，v1v5，v1v4)，此時(shí)圖中邊數(shù)保持不變。

圖在邊的旋轉(zhuǎn)操作之后，雖然某些頂點(diǎn)的賦權(quán)度發(fā)生變化，但所有頂點(diǎn)賦權(quán)度的和保持不變。在非賦權(quán)圖中，指定的邊不能旋轉(zhuǎn)到已經(jīng)存在的邊上，即不能出現(xiàn)重邊。

如下定理推廣了非賦權(quán)圖上邊旋轉(zhuǎn)操作的結(jié)論［68］，給出了邊旋轉(zhuǎn)操作使代數(shù)連通度減小的充分條件。

定理5 設(shè)G 是一個(gè)賦權(quán)無(wú)向圖，uv1∈E(G)且v2是圖G 中不同于的u 和v1頂點(diǎn)。圖G′=rotate(G，uv1，uv2)為將G 中邊uv1從頂點(diǎn)v1旋轉(zhuǎn)到v2得到的圖。假設(shè)u2是圖G 代數(shù)連通度λ2(G)對(duì)應(yīng)的一個(gè)特征向量。如果|u2(u) - u2(v1)| ≥|u2(u) -u2(v2)|成立，那么λ2(G′)≤λ2(G)。并且，如果條件的不等式是嚴(yán)格的，那么λ2(G′)< λ2(G)。

圖1 賦權(quán)圖中一條邊的兩類邊旋轉(zhuǎn)操作

為了通過(guò)邊旋轉(zhuǎn)操作，改變連邊方式或改變邊的權(quán)值，進(jìn)而提高代數(shù)連通度，由定理5 得到如下推論。

推論1 設(shè)G 是一個(gè)賦權(quán)無(wú)向圖，uv1∈E(G)且v2是圖G 中不同于的u 和v1頂點(diǎn)。圖G′=rotate(G，uv1，uv2)為將G 中邊uv1從頂點(diǎn)v1旋轉(zhuǎn)到v2得到的圖。如果λ2(G′)> λ2(G)，那么對(duì)λ2(G)的任一特征向量uk都有|u2(u) - u2(v1)| < |u2(u) -u2(v2)|成立。

由推論1，基于λ2(G)的特征向量可選擇合適的邊旋轉(zhuǎn)操作，使得代數(shù)連通度增加。

3.3.3 邊交換操作的方法

設(shè)G是一個(gè)賦權(quán)無(wú)向圖，u1v1和u2v2圖G中兩條沒有公共端點(diǎn)的邊。假設(shè)u1v2和u2v2都不是圖G 的邊，則u1v1和u2v2的邊交換操作定義［69］：刪除邊u1v1和u2v2，如果圖中存在邊u1u2或v1v2，那么設(shè)置權(quán)值wu1u2= wu1u2+ wu1v1或wv1v2= wv1v2+ wu2v2；否則，新增邊u1u2和 邊v2v1，設(shè) 置 權(quán) 值wu1u2= wu1v1或wv1v2= wu2v2。如果新增加邊為u1u2和v2v1，邊交換之后得到的圖記作G′= swap(G，u1v1，u2v2)；如果新增加邊為u1v2和 u2v1，邊 交 換 之 后 得 到 的 圖 記 作 G′=swap(G，u1v1，v2u2)。

由邊交換的定義可知，邊交換操作連邊方式的不同，邊交換操作后得到兩個(gè)不同的圖。為了區(qū)別這兩個(gè)圖，符號(hào)中的兩個(gè)邊的頂點(diǎn)默認(rèn)是有順序的，新連接邊的方式按照兩條邊中頂點(diǎn)出現(xiàn)的順序一一對(duì)應(yīng)。如圖2 中，邊v1v2和v2v4在交換時(shí)，可能出現(xiàn)兩個(gè)組合。在圖Gb= swap(Ga，v1v5，v2v4)中，刪除這兩條邊后，頂點(diǎn)v1和v2為新增邊對(duì)應(yīng)的頂點(diǎn)，由于邊v1v2已經(jīng)存在，修改其權(quán)值即可；同樣，頂點(diǎn)v5和v4為新增邊對(duì)應(yīng)的頂點(diǎn)，由于邊v5v4已經(jīng)存在，修改其權(quán)值即可。在圖Gc= swap(Ga，v1v5，v4v2)中，新增邊v1v4和v5v2，分別將邊v1v5和v2v4的權(quán)值賦予新增邊。

圖2 賦權(quán)圖中兩條邊的兩類邊旋轉(zhuǎn)操作

文獻(xiàn)［69］中，針對(duì)非賦權(quán)的無(wú)向圖，給出了邊旋轉(zhuǎn)操作之后代數(shù)連通度減小的充分條件。作者在文中說(shuō)明，此充分條件可直接推廣到賦權(quán)圖。如下定理給出了賦權(quán)圖中，兩條邊在邊交換操作后，代數(shù)連通度減小的充分條件。

定 理6［69］設(shè)G 是 一 個(gè) 無(wú) 向 圖，u1v1和u2v2是圖G 中兩條沒有公共端點(diǎn)的邊。圖G′=swap(G，u1v1，u2v2)為將u1v1和u2v2進(jìn)行邊交換操作得到的圖。假設(shè)u2是圖G 代數(shù)連通度λ2(G)對(duì)應(yīng)的一個(gè)特征向量。如果(uk(u1)- uk(v2))(uk(v1)-uk(u2)) ≤0成立，那么λ2(G′)≤λ2(G)。

為了使用邊交換操作，改變圖的拓?fù)浣Y(jié)構(gòu)或邊上的權(quán)重，進(jìn)而提高代數(shù)連通度，必須選擇合適的邊進(jìn)行邊交換操作。由定理6得到如下推論。

推論2［69］設(shè)G 是一個(gè)無(wú)向圖，u1v1和u2v2是圖G 中兩條沒有公共端點(diǎn)的邊。圖G′= swap(G，u1v1，u2v2)為將u1v1和u2v2進(jìn)行邊交換操作得到的圖。如果λ2(G′)> λ2(G)，那么對(duì)λ2(G)的任一特征向量uk都有|u2(u) - u2(v1)| < |u2(u) - u2(v2)| > 0成立。

本節(jié)提出的加邊操作、邊旋轉(zhuǎn)和邊交換操作可組合使用設(shè)計(jì)算法，能對(duì)圖進(jìn)一步優(yōu)化，得到代數(shù)連通度更大的拓?fù)浣Y(jié)構(gòu)。

4 結(jié)語(yǔ)

通信拓?fù)錇闊o(wú)向圖的一階多智能體系統(tǒng)，收斂速度由通信拓?fù)涞拇鷶?shù)連通度決定的，代數(shù)連通度越大，系統(tǒng)達(dá)到一致性的收斂速度越快。由于代數(shù)連通度最大化問(wèn)題是NP-難問(wèn)題，當(dāng)系統(tǒng)規(guī)模較大時(shí)無(wú)法得到最大值和最優(yōu)拓?fù)?。目前?duì)通信拓?fù)浯鷶?shù)連通度的優(yōu)化，主要采用的方法有數(shù)學(xué)規(guī)劃方法和邊或邊權(quán)值調(diào)整方法。數(shù)學(xué)規(guī)劃方法將代數(shù)連通度最大化問(wèn)題建模為非凸的整數(shù)規(guī)劃問(wèn)題，松弛處理后，設(shè)計(jì)優(yōu)化算法可得到較好的拓?fù)浣Y(jié)構(gòu)。但是這類優(yōu)化問(wèn)題算法復(fù)雜性高，網(wǎng)絡(luò)規(guī)模較大時(shí)無(wú)法有效應(yīng)用。邊或邊權(quán)值調(diào)整方法，通常先考慮一到兩條邊的最優(yōu)調(diào)整方案，然后設(shè)計(jì)貪婪算法，每步迭代都能提高代數(shù)連通度。該方法計(jì)算量小，通常能得到較好的拓?fù)浣Y(jié)構(gòu)，但是無(wú)法保證得到的拓?fù)涫亲顑?yōu)的。

針對(duì)多智能體系統(tǒng)拓?fù)鋬?yōu)化，目前依然有很多待改進(jìn)和未解決的問(wèn)題。首先，當(dāng)前大部分的優(yōu)化基于已知拓?fù)浣Y(jié)構(gòu)進(jìn)行的。實(shí)際上由于多智能體系統(tǒng)的分布式特征，無(wú)法在一個(gè)計(jì)算單元獲取所有的通信拓?fù)湫畔ⅰＲ虼?，采用分布式估?jì)和分布式優(yōu)化方法對(duì)多智能體系統(tǒng)拓?fù)鋮?shù)進(jìn)行估計(jì)和優(yōu)化是后續(xù)研究的趨勢(shì)。其次，考慮新增若干個(gè)智能體接入到多智能體網(wǎng)絡(luò)，如何設(shè)計(jì)最優(yōu)的連邊方式，使得系統(tǒng)的收斂速率最大？另外，如果某個(gè)智能體發(fā)生故障，如何進(jìn)行拓?fù)渲剡B使得收斂速率最大？這些系統(tǒng)中智能體個(gè)數(shù)發(fā)生變化的問(wèn)題，由于問(wèn)題的復(fù)雜性，目前很少有研究。最后，如果多智能體系統(tǒng)中存在有向邊時(shí)，由于網(wǎng)絡(luò)拓?fù)鋵?duì)應(yīng)的拉普拉斯矩陣為非對(duì)稱矩陣，特征值可能為復(fù)數(shù)，一階多智能體系統(tǒng)的收斂速率由非零特征值的最小實(shí)部決定。因此，當(dāng)多智能體系統(tǒng)的通信拓?fù)錇橛邢驁D時(shí)，收斂速度的優(yōu)化將更加有挑戰(zhàn)性。