吳正平 (三峽大學(xué)電氣信息學(xué)院 ，湖北 宜昌 443002)

謝學(xué)文 (大慶鉆探工程公司測(cè)井二公司完井大隊(duì)，吉林 松原 138003)

規(guī)則網(wǎng)絡(luò)中多智能體系統(tǒng)一致性收斂速度研究

吳正平 (三峽大學(xué)電氣信息學(xué)院 ，湖北 宜昌 443002)

謝學(xué)文 (大慶鉆探工程公司測(cè)井二公司完井大隊(duì)，吉林 松原 138003)

通過(guò)分析和仿真，對(duì)最臨近耦合網(wǎng)絡(luò)、星網(wǎng)絡(luò)和全耦合網(wǎng)絡(luò)的一致性收斂速度進(jìn)行了研究。研究結(jié)果表明，最臨近耦合網(wǎng)絡(luò)的收斂速度是最慢的，星網(wǎng)絡(luò)作為一個(gè)邊較少的網(wǎng)絡(luò)具有很快的一致性收斂速度，而全耦合網(wǎng)絡(luò)是所有網(wǎng)絡(luò)中一致性收斂速度最快的。該研究對(duì)多智能體網(wǎng)絡(luò)的設(shè)計(jì)具有指導(dǎo)意義。

規(guī)則網(wǎng)絡(luò)；多智能體系統(tǒng)；一致性

1 多智能體復(fù)雜網(wǎng)絡(luò)中的一致性問(wèn)題

(1)

(2)

式中，x(t)={x1,x2,…,xN}為狀態(tài)矢量；A={aij} ∈RN×N稱為網(wǎng)絡(luò)的耦合矩陣。記L=-A，則L為圖G的拉譜拉斯矩陣。矩陣A表示網(wǎng)絡(luò)的通信拓?fù)浣Y(jié)構(gòu)，如果智能體i和智能體j(i≠j)之間有通信連接，則aij=aji=1；否則，aij=aji=0(i≠j)。如果節(jié)點(diǎn)i的度記為ki,則有:

為了分析的方便，給出下面引理。

引理1[7]對(duì)于網(wǎng)絡(luò)系統(tǒng)(2)，當(dāng)A為對(duì)稱不可約矩陣時(shí)，則系統(tǒng)(2)是收斂的。

根據(jù)引理1，筆者研究的幾種規(guī)則網(wǎng)絡(luò)對(duì)應(yīng)的矩陣耦合A為對(duì)稱不可約矩陣，因此相應(yīng)的多智能體系統(tǒng)的一致性問(wèn)題都是收斂的。

在開發(fā)房地產(chǎn)之前，必須要考慮好供求關(guān)系，這對(duì)于房?jī)r(jià)、成本計(jì)算以及開發(fā)時(shí)間和房屋的數(shù)量等起到了重要的價(jià)值，也可以促進(jìn)房地產(chǎn)行業(yè)的發(fā)展?？梢源龠M(jìn)城市的建設(shè)，在規(guī)劃當(dāng)中，還需要控制風(fēng)險(xiǎn)來(lái)讓規(guī)劃變得更具有可行性。

引理2[8]設(shè)圖L(L=-A)是強(qiáng)連接和平衡的，則在系統(tǒng)(2)中，x以速度β=λ2(L)收斂到x*。其中，λ2為L(zhǎng)的最小非零特征值。

由引理2知，多智能體系統(tǒng)的拓?fù)浣Y(jié)構(gòu)決定了系統(tǒng)一致性問(wèn)題的收斂速度特性，而與拓?fù)浣Y(jié)構(gòu)相對(duì)應(yīng)的拉譜拉斯矩陣L的最小非零特征值λ2的大小度量了該系統(tǒng)的一致性收斂速度。

2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其一致性問(wèn)題分析

下面分析最臨近耦合網(wǎng)絡(luò)、星網(wǎng)絡(luò)和全耦合網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其λ2的特性，從而進(jìn)一步分析相應(yīng)的多智能體系統(tǒng)一致性收斂速度的特性。

2.1最鄰近耦合網(wǎng)絡(luò)

在最鄰近耦合網(wǎng)絡(luò)中，N個(gè)節(jié)點(diǎn)圍成一個(gè)環(huán)狀，其中任一節(jié)點(diǎn)i和它相鄰的節(jié)點(diǎn)i±1,i±2,…,i±l(l為一正整數(shù))相連。相應(yīng)的耦合矩陣Anc=(aij)N×N可以表示為:

拉普拉斯矩陣L=-Anc，其特征值為:

則當(dāng)N?m時(shí):

(3)

從式(3)可以看出，最臨近耦合網(wǎng)絡(luò)的λ2值是較小的，因此其一致性速度很慢。

2.2星網(wǎng)絡(luò)

在星形耦合結(jié)構(gòu)中，所有的節(jié)點(diǎn)連接到一個(gè)節(jié)點(diǎn)上，該節(jié)點(diǎn)稱為中心節(jié)點(diǎn)。星網(wǎng)絡(luò)相應(yīng)的耦合矩陣為:

拉普拉斯矩陣L=-Asc，其特征值為:

λ1=0λ2=λ3=…=λN-1=1λN=N

星網(wǎng)絡(luò)的λ2=1，因此其一致性收斂速度遠(yuǎn)遠(yuǎn)大于與其具有相近平均度的最臨近耦合網(wǎng)絡(luò)。該網(wǎng)絡(luò)的主要特點(diǎn)是網(wǎng)絡(luò)連邊少，網(wǎng)絡(luò)構(gòu)建成本低，一致性收斂速度快。但從其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)看，當(dāng)中心節(jié)點(diǎn)癱瘓時(shí)，整個(gè)網(wǎng)絡(luò)也就癱瘓了，因此該網(wǎng)絡(luò)對(duì)蓄意攻擊魯棒性差。

2.3全耦合網(wǎng)絡(luò)

全耦合網(wǎng)絡(luò)中每一對(duì)節(jié)點(diǎn)都是直接相連的網(wǎng)絡(luò)，其相應(yīng)的耦合矩陣為:

拉普拉斯矩陣L=-Agc有一單0特征值，其他的特征值均為N，因此λ2=N。在全耦合網(wǎng)絡(luò)中，λ2的值最大，網(wǎng)絡(luò)的一致性收斂速度最快。但全耦合網(wǎng)絡(luò)是連邊數(shù)最多的網(wǎng)絡(luò)，因而也被認(rèn)為是最復(fù)雜、構(gòu)建成本最高的網(wǎng)絡(luò)。

3 網(wǎng)絡(luò)一致性收斂速度的仿真研究

下面，通過(guò)仿真來(lái)進(jìn)一步研究最鄰近耦合網(wǎng)絡(luò)、相應(yīng)的星網(wǎng)絡(luò)(平均度約為2)和全耦合網(wǎng)絡(luò)的一致性收斂速度。一致性問(wèn)題的狀態(tài)方程如式(2)所示，誤差評(píng)價(jià)函數(shù)定義為[7]:

φ(x)=xTLx

初始條件均為xi(0)=i，i=0,1,…,N；節(jié)點(diǎn)數(shù)N=200，平均度k=2。仿真結(jié)果如圖1和圖2所示。

圖1 誤差函數(shù) 圖2 全耦合網(wǎng)絡(luò)的誤差函數(shù)

從圖1可以看出，對(duì)于節(jié)點(diǎn)數(shù)為200，平均度為2的最臨近耦合網(wǎng)絡(luò)，當(dāng)誤差函數(shù)值達(dá)到0.01以下時(shí)大約需要1400s，而與其節(jié)點(diǎn)數(shù)相同、平均度近似的星網(wǎng)絡(luò)則只需要約8s的時(shí)間，可見，星網(wǎng)絡(luò)的一致性收斂速度遠(yuǎn)遠(yuǎn)大于與其節(jié)點(diǎn)數(shù)相同、平均度近似的最臨近耦合網(wǎng)絡(luò)。

由圖2可以看出，全耦合網(wǎng)絡(luò)的收斂速度是最快的，并且和網(wǎng)絡(luò)的規(guī)模(節(jié)點(diǎn)數(shù))無(wú)關(guān)，它的一致性問(wèn)題的誤差函數(shù)都能在1s左右收斂到0.01以下。仿真結(jié)果與上面分析一致。

4 結(jié) 語(yǔ)

筆者對(duì)多智能體系統(tǒng)在最臨近耦合網(wǎng)絡(luò)、星網(wǎng)絡(luò)和全耦合網(wǎng)絡(luò)中的一致性收斂速度進(jìn)行了研究。通過(guò)理論分析和數(shù)字仿真發(fā)現(xiàn)，星網(wǎng)絡(luò)在通信連接較少(平均度約為2)的情況下，具有很快的收斂速度，其收斂速度要比與其具有相同節(jié)點(diǎn)數(shù)和相近平均度的最臨近耦合網(wǎng)絡(luò)快很多倍；全耦合網(wǎng)絡(luò)的一致性收斂速度是最快，所有節(jié)點(diǎn)在1s左右即可達(dá)到一致性，且和節(jié)點(diǎn)數(shù)無(wú)關(guān)，但全耦合網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)通信連邊數(shù)太多，當(dāng)網(wǎng)絡(luò)規(guī)模較大的時(shí)候，實(shí)現(xiàn)起來(lái)比較困難。

[1]Estrada E, Rodriguez-Velazquez J A. Subgraph centrality in complex networks[J].Phys Rev E， 2005，71:056103～056111.

[2]Estrada E, Rodriguez-Velazquez J A.Spectral measure of bipartivity in complex networks[J].Phys Rev E, 2005，72: 046105～046110.

[3]Zhengping Wu, ZhiHong Guan, Xianyong Wu，etal.Consensus Based Formation Control and Trajectory Tracing of Multi-Agent Robot Systems, Journal of Intelligent and Robotic Systems[J].Springer Netherlands, 2007, 48:397～410.

[4]Zhengping Wu, ZhihongGuan , Xianyong Wu.Consensus problem in Multi-Agent Systems with physical position neighborhood evolving network[J].Physica A,2007, 379:681～690.

[5]Saber R O. Ultrafast consensus in small-world network[A].Proc. ACC, Portland, OR, 2005, 4:2371～2378.

[6]Saber R O, Murray R M. Consensus problems in networks of agents with switching topology and time-delays[J].IEEE Trans Automat Contr, 2004, 49(9):1520～1533.

[7]Ren W , Beard R W. Consensus of information under dynamically changing interaction topologies[A].Proc 2004 ACC, Boston, MA,2004.4939～4944.

[8]Saber R O, Murray R M. Agreement problems in networks with directed graphs and switching topology[A].In Proc 2003 CDC, 2003,4:4126～4132.

[編輯] 易國(guó)華

TP273

A

1673-1409(2009)02-N060-03

2009-02-24

吳正平(1966-)，男，1988年大學(xué)畢業(yè)，博士，副教授，現(xiàn)主要從事復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)和復(fù)雜非線性系統(tǒng)以及檢測(cè)技術(shù)與自動(dòng)化裝置等方面的教學(xué)與研究工作。