一類具有切換拓?fù)浜碗S機(jī)故障影響的集群演化模型分析

喬正陽(yáng)，劉易成

(國(guó)防科技大學(xué)數(shù)學(xué)系，湖南 長(zhǎng)沙410073)

1.引言

我們知道，多智能系統(tǒng)在生態(tài)學(xué)，物理學(xué)，社會(huì)學(xué)以及人工智能等學(xué)科中應(yīng)用廣泛.這類系統(tǒng)的顯著特點(diǎn)是通過(guò)分離獨(dú)立的個(gè)體間的信息交互，系統(tǒng)能涌現(xiàn)出預(yù)先設(shè)計(jì)的集群特征.Cucker和Smale在文[4-5]中給出了一類描述多智能體系統(tǒng)演化的模型(C-S模型)，并且刻畫了該模型的群體演化行為.隨后，很多學(xué)者研究了各種變形的C-S模型，進(jìn)一步刻畫該模型的復(fù)雜群體演化行為，其中包括時(shí)滯影響下的C-S模型和不同拓?fù)浣Y(jié)構(gòu)的C-S模型等.在文[14]中，SHEN研究了具有等級(jí)結(jié)構(gòu)的C-S模型.近年來(lái)，LI和XUE 在文[12]中研究了具有根結(jié)點(diǎn)領(lǐng)導(dǎo)的C-S模型.同時(shí)考慮了切換拓?fù)涞挠绊懬樾?，這類拓?fù)浣Y(jié)構(gòu)比等級(jí)結(jié)構(gòu)更具一般性.在文[8]中DONG和QIU研究了一般拓?fù)浣Y(jié)構(gòu)下的C-S 模型的群體演化行為，該文對(duì)拓?fù)浣Y(jié)構(gòu)的要求僅需要拓?fù)浣粨Q圖存在一個(gè)生成樹(shù)即可.隨后Cucker和DONG在文[2]中研究了一般情形下帶有切換拓?fù)涞腃-S 模型.由于多智能體系統(tǒng)中個(gè)體之間相互連接的拓?fù)浣Y(jié)構(gòu)往往是不斷變化的，在文[1]中，作者發(fā)現(xiàn)鴿群中個(gè)體之間采用間歇性交互機(jī)制，并不是每時(shí)每刻的都進(jìn)行組內(nèi)信息傳輸.因此具有切換拓?fù)涞腃-S模型具有很強(qiáng)的實(shí)際意義.

同時(shí)，多智能系統(tǒng)中的個(gè)體之間的連接會(huì)受到外界因素的干擾，導(dǎo)致相互作用發(fā)生改變，甚至連接失敗.帶有隨機(jī)故障的C-S模型能更好地描述這種影響.在文[6-7] 中，Dalmao和Mordecki研究了隨機(jī)故障下具有等級(jí)結(jié)構(gòu)的C-S模型.隨后RU，LI和XUE在文[13]中研究了隨機(jī)故障下具有根結(jié)構(gòu)的C-S模型.Dalmao和RU等人也考慮了具有固定故障概率的隨機(jī)故障C-S模型，這里故障概率是獨(dú)立同分布的伯努利隨機(jī)變量.近年來(lái)，HE和MU在文[10]中考慮了具有隨機(jī)故障的一般C-S模型，其中故障概率并不一定是獨(dú)立的，這里故障概率不再用伯努利隨機(jī)變量描述，而是利用齊次Markov鏈描述.本文以Cucker和DONG在文[2]中帶有切換拓?fù)涞腃-S模型為基礎(chǔ)，結(jié)合文[10]中的方法，對(duì)帶有切換拓?fù)浜碗S機(jī)故障影響的C-S模型的集群演化行為進(jìn)行了研究，獲得了系統(tǒng)幾乎必然發(fā)生集群演化行為的充分條件.

本文的結(jié)構(gòu)如下: 第2節(jié)將介紹有向圖以及切換系統(tǒng)的基本概念，描述具有切換拓?fù)浜碗S機(jī)故障影響的C-S模型，給出關(guān)于故障概率和切換方式的假設(shè)條件以及相關(guān)引理結(jié)論; 第3 節(jié)給出了具有切換拓?fù)浜碗S機(jī)故障影響的C-S模型的主要結(jié)果和證明過(guò)程.由于拓?fù)浣Y(jié)構(gòu)是可切換的，我們需要一種新的方法估計(jì)帶有切換拓?fù)浜碗S機(jī)故障的拓?fù)浣换D的遍歷系數(shù)，進(jìn)而證明系統(tǒng)幾乎必然發(fā)生集群演化行為.最后，通過(guò)數(shù)值仿真方法，獲得了故障概率和切換間隔增大時(shí)，系統(tǒng)的集群演化行為的變化特點(diǎn).

2.預(yù)備知識(shí)

本文利用有向圖描述集群中個(gè)體之間的相互作用拓?fù)?設(shè)G = (V，E)是由頂點(diǎn)集V ={1，2，···n}和邊集E ?V ×V構(gòu)成.如果(j，i) ∈E表示個(gè)體i可以直接從個(gè)體j處接收信息，此時(shí)稱個(gè)體j是個(gè)體i的一個(gè)鄰接點(diǎn).個(gè)體i的鄰接集記為Ni= {j ∈V : (j，i) ∈E}.若(i，i) ∈E，則圖G在點(diǎn)i處有一個(gè)自循環(huán).對(duì)于圖G的鄰接矩陣A = (aij)n×n，則當(dāng)(j，i) ∈E時(shí)，有aij＞0，否則aij= 0.稱邊序列(i0，i1)，(i1，i2)，··· ，(ik-1，ik)為從i0到ik的一條路徑.如果存在一條從i到j(luò)路徑，則稱頂點(diǎn)j關(guān)于頂點(diǎn)i是可達(dá)的.在有向圖中，如果存在一個(gè)頂點(diǎn)(稱為根結(jié)點(diǎn))可以到達(dá)圖中任何其他頂點(diǎn)，則稱圖是有根的.

集群個(gè)體之間的交互方式表示為有向圖，它可以在一個(gè)有限的模式集P = {1，2···p}中切換.切換方式由函數(shù)σ : [0，∞) →P表示，每一時(shí)刻σ對(duì)應(yīng)著一個(gè)有向圖，且σ為右連續(xù)的分段函數(shù).σ的不連續(xù)點(diǎn)集組成一個(gè)可數(shù)序列，其中每一個(gè)點(diǎn)表示切換時(shí)刻.不失一般性我們將切換時(shí)刻序列記為{ts}，其中t0= 0.圖Gσ(t)= (V，Eσ(t))表示t時(shí)刻的交互圖.表示t時(shí)刻圖Gσ(t)中頂點(diǎn)i的鄰接集.時(shí)間區(qū)間t ∈[t1，t2)上的聯(lián)合圖定義為

對(duì)于矩陣A=(aij)n×n，如果所有aij≥0且行和滿足則稱矩陣A為隨機(jī)矩陣.如果對(duì)任意的i和j都存在k，使得aik＞0和ajk＞0，則稱矩陣A為不規(guī)則的.矩陣A的遍歷系數(shù)定義為

由此可知，χ(A)＞0當(dāng)且僅當(dāng)A是不規(guī)則矩陣.如果A是隨機(jī)矩陣，則χ(A)∈[0，1].

此外對(duì)于任意矩陣A = (aij)n×n，B = (bij)n×n，我們定義A ≥B表示對(duì)任意的i，j有aij≥bij.

考慮n個(gè)個(gè)體組成的集群系統(tǒng)，集群拓?fù)浣Y(jié)構(gòu)對(duì)應(yīng)的交互圖為G，集群演化過(guò)程在離散時(shí)刻t ∈N滿足如下：

其中h ＞0表示時(shí)間步長(zhǎng)，1 ≤i ≤n，xi[t]和vi[t] ∈Rm(m ≥1)表示個(gè)體i在th時(shí)刻的位置和速度.表示個(gè)體i在th時(shí)刻的鄰接集.Gσ[t]= (V，Eσ[t]))表示th時(shí)刻的相互作用拓?fù)鋱D.如果(j，i) ∈Eσ[t])當(dāng)且僅當(dāng)j ∈此外假定i ∈我們考慮隨機(jī)故障的影響，引入影響函數(shù)

假設(shè)2.1假設(shè)當(dāng)t ∈N，j ∈時(shí)，隨機(jī)事件滿足：

其中Ft，ij表示一個(gè)雙狀態(tài)的齊次馬爾可夫鏈，狀態(tài)空間為{0，1}.Ft，ij包含從初始時(shí)刻到t時(shí)刻的隨機(jī)事件的所有信息，p表示t時(shí)刻未發(fā)生故障概率，p=1-λ.

由上述假設(shè)可知

接下來(lái)，給出隨機(jī)故障情況下的集群定義.本文中‖·‖均為2-范數(shù).定義

定義2.1如果系統(tǒng)(2.1)-(2.2)的解幾乎必然滿足如下條件

則稱系統(tǒng)(2.1)-(2.2)發(fā)生集群演化行為.

A[t] = (aij[t])n×n表示系統(tǒng)(2.1)-(2.2)的鄰接矩陣.令L[t] = D[t]-A[t]為矩陣A[t]對(duì)應(yīng)的Laplacian矩陣，D[t] = diag(d1[t]，d2[t]···dn[t])為度矩陣，其中di[t] = ∑aij[t].因此系統(tǒng)(2.1)可表示為

其中x[t]=(x1[t]，x2[t]，··· ，xn[t])，v[t]=(v1[t]，v2[t]，··· ，vn[t]).與文[2]中一樣，我們需要假設(shè)系統(tǒng)的交互拓?fù)湓谇袚Q過(guò)程中保持一定連通性.

假設(shè)2.2令t0= 0，對(duì)于遞增的切換時(shí)刻序列{ts}s∈N存在正整數(shù)T，使得任意s ∈N滿足ts+1-ts≤T，并且聯(lián)合圖G([ts，ts+1))存在根結(jié)點(diǎn).

注2.1根據(jù)假設(shè)2.2，在切換過(guò)程中，并不需要圖G在每時(shí)每刻都具有生成樹(shù)，僅要求時(shí)間間隔不超過(guò)T的時(shí)間段([ts，ts+1))內(nèi)的聯(lián)合圖G([ts，ts+1))具有生成樹(shù)即可.這在一定程度上保證了交互圖在切換過(guò)程的連通性，使得圖G在連續(xù)有限時(shí)間內(nèi)的聯(lián)合圖具有生成樹(shù).該假設(shè)比文[8]要求圖G時(shí)刻具有生成樹(shù)要弱.

為了刻畫系統(tǒng)發(fā)生集群演化行為的條件，先給出如下引理.

引理2.1[15]設(shè)k為一正整數(shù)，矩陣Ai(1 ≤i ≤k)為非負(fù)n×n矩陣，并且滿足對(duì)角元素大于零，對(duì)任意i圖G(Ai)有根結(jié)點(diǎn)，則乘積A1A2···Ak是不規(guī)則矩陣.

引理2.2[10]設(shè)v ∈Rmn，A=(aij)n×n是一個(gè)隨機(jī)矩陣，ω =(A ?Im)v，則

引理2.3[2]假設(shè)則對(duì)任意t ＞0有

引理2.4(Borel-Cantelli定理) 假設(shè){fk}是一個(gè)隨機(jī)事件列，則有

2)若fk是獨(dú)立事件且

引理2.5[3]設(shè)c1，c2＞0并且p ＞q ＞0，則方程

存在唯一正零點(diǎn)z*，并且滿足

當(dāng)z ∈[0，z*]時(shí)，F(xiàn)(z)≤0.

3.主要結(jié)果

在本章中，將研究具有切換和隨機(jī)故障影響下的C-S模型的群體演化行為.首先建立關(guān)于遍歷系數(shù)期望的不等式，然后借助Borel-Cantelli定理得到關(guān)于遍歷系數(shù)的估計(jì).最后利用代數(shù)方程F(z) = zp-c1zq-c2= 0解的性質(zhì)，證明系統(tǒng)(2.1)的解滿足定義2.1，從而證明系統(tǒng)在隨機(jī)故障影響下發(fā)生群體演化行為.根據(jù)定義2.1中集群行為的定義，以下推導(dǎo)在依概率1成立情形下進(jìn)行.

令α=2(n-1)T，根據(jù)方程(2.5)以及Kronecker積的性質(zhì)，可以得到

注意到L=D-A，因此上式可寫成：

因此

由于隨機(jī)故障的影響，A[t]的元素均為隨機(jī)變量，為此先給出隨機(jī)變量序列的期望不等式.

引理3.1假設(shè)為任意遞增時(shí)間序列，為系統(tǒng)(2.1)-(2.2)的鄰接矩陣序列，Ai=(aij[ti])n×n，則有如下期望不等式

證利用數(shù)學(xué)歸納法證明.當(dāng)k =1時(shí)，結(jié)論自然成立.假設(shè)當(dāng)1 ≤j ≤k-1時(shí)，

成立.Ai可以寫成Ai=+Qi，其中的元素非負(fù)，并且有對(duì)任意的1 ≤u，v ≤k，鑒于Au與Av是獨(dú)立的，根據(jù)期望的性質(zhì)可知

又因?yàn)镋((pKIn+Qu))=E(Au)，E((pKIn+Qv))=E(Av)，故

注意到

因此

根據(jù)引理3.1，可得

這里E([αt-2T(i+1)，αt-2Ti))為聯(lián)合圖G([αt-2T(i+1)，αt-2Ti))的邊集.令

由于Bi相互獨(dú)立，從而可得

另一方面，根據(jù)假設(shè)2.2以及區(qū)間[αt-2T(i+1)，αt-2Ti)長(zhǎng)度大于T，因而存在其子區(qū)間[tk′，tk′+1)使得G([tk′，tk′+1))有根節(jié)點(diǎn)，從而G([αt-2T(i+1)，αt-2Ti))=G(Ci)有根結(jié)點(diǎn).進(jìn)而根據(jù)引理2.1，可知矩陣∏Ci是不規(guī)則矩陣.因此

根據(jù)遍歷系數(shù)的定義得

故

引理3.2對(duì)于系統(tǒng)(2.1)-(2.2)，如果假設(shè)2.1和假設(shè)2.2成立，且存在與t無(wú)關(guān)的隨機(jī)變量τ0，使得當(dāng)t ＞τ0時(shí)有

證由于Bi是隨機(jī)矩陣，可知也為隨機(jī)矩陣.所以對(duì)?t ＞0，

因此

若ρ=∞，則有φ*=0，因此當(dāng)t ≥1時(shí)，(3.1)式顯然成立.若ρ ＜∞，則φ*＞0，ξφ*＜1，進(jìn)而根據(jù)Markov不等式可得

事件At表示集合由上面得根據(jù)引理2.4(Borel-Cantelli定理)，我們可得即所以這里為At的補(bǔ).令顯然Bk?Bk-1，定義與t無(wú)關(guān)的隨機(jī)變量τ0，其滿足τ0(ω) = k當(dāng)且僅當(dāng)ω ∈Bk-Bk-1.所以對(duì)任意t ≥k，有ω ∈Bk因而ω ∈又因?yàn)樗援?dāng)t ＞τ0時(shí)依概率1有又因?yàn)橐虼?/p>

定理3.1具有切換拓?fù)浜碗S機(jī)故障影響的系統(tǒng)(2.1)-(2.2)滿足假設(shè)2.1和2.2以及并且下面條件之一成立:

證令(3.2)式成立對(duì)于ρt=ρ，φ[t]=φ*，因此引理3.2可以寫成: 存在隨機(jī)變量τ0，當(dāng)t ＞τ0時(shí)

由于v[at]=(Ψα(τ-1)?Im)v[α(t-1)]，根據(jù)引理2.2有

當(dāng)t足夠大時(shí)，由式(2.5)可得

因此

記z[t]=(1+Γ[t*]2)，則上式可改寫為

從而對(duì)任意t 有

因此，當(dāng)t ＞ατ0+1時(shí)，

另一方面，對(duì)任意時(shí)刻t2＞t1＞τ0，ij，

由此可知存在yij＜∞使得limt→+∞‖xi(t)-xj(t)‖→yij.

從而對(duì)任意t，Γ[t*]有界.類似情形1，易知系統(tǒng)(2.1)-(2.2)發(fā)生集群演化行為.

注意到2β(n-1)＞1，故F′(z)有且只有一個(gè)零點(diǎn)鑒于

以及F(0) = -c2＜0和limt→+∞F(t) = -∞，我們可知方程F(z) = 0存在兩個(gè)零點(diǎn)z1和z2使得z1＜z*＜z2以及F(z)＞0對(duì)所有z ∈(z1，z2)成立.注意到

從而z[0]＜z*，且F(z[0])＜0.故z[0]＜z1.

下面證明對(duì)任意t ＞0，不等式z[t]＜z1成立.

事實(shí)上，反設(shè)存在t′，使得z[t′]≥z1，且t′為首個(gè)滿足此條件的點(diǎn).由于F(z[t′])＜0，這意味著z[t′]＞z2，即因此另一方面，因t′為首個(gè)滿足此條件的點(diǎn)，故有即從而有

由微分中值定理可知，存在ε ∈(z1，z*)使得

又因?yàn)?/p>

所以F(z*)≤hΛ[0].這與情形3的條件矛盾.因此對(duì)任意t有z[t]≤z1≤z*.故

從而對(duì)任意t，Γ[t*]有界.類似情形1，易知系統(tǒng)(2.1)-(2.2)發(fā)生集群演化行為.定理證畢.

4.數(shù)值仿真

本節(jié)我們將對(duì)帶有切換拓?fù)浜碗S機(jī)故障影響的C-S模型進(jìn)行數(shù)值仿真分析，進(jìn)一步探索切換拓?fù)湟约半S機(jī)故障對(duì)系統(tǒng)的動(dòng)力學(xué)行為的影響.

首先，我們通過(guò)數(shù)值仿真方法驗(yàn)證定理3.1.為此，假定個(gè)體數(shù)n = 6，模式集P由3種不同的拓?fù)淠Ｊ浇M成，即P = {G0，G1，G2}，對(duì)應(yīng)拓?fù)浣Y(jié)構(gòu)見(jiàn)圖4.1-4.3所示，其中G0，G1具有根結(jié)點(diǎn)(圖中有生成樹(shù)).而G2并沒(méi)有根結(jié)點(diǎn)，因?yàn)镚2中任意一點(diǎn)都不能到達(dá)節(jié)點(diǎn)4.構(gòu)造選擇函數(shù)顯然選擇函數(shù)滿足假設(shè)2.2.

數(shù)值仿真結(jié)果如下:

圖4.1 G0

圖4.2 G1

圖4.3 G2

圖4.4

圖4.5 β ＜0.1，速度v變化

圖4.6 β ＜0.1，位移差Γ變化

圖4.7 β =0.1，速度v變化

圖4.8 β =0.1，位移差Γ變化

圖4.9 β ＞0.1，速度v變化

圖4.10 β ＞0.1，位移差Γ變化

圖4.11 故障概率λ=0.05，速度v變化

圖4.12 故障概率λ=0.3，速度v變化

圖4.13 故障概率λ=0.5，速度v變化

圖4.14 故障概率λ=0.7，速度v變化

圖4.15 最大切換間隔1s，速度v變化

圖4.16 最大切換間隔3s，速度v變化

圖4.17 最大切換間隔5s，速度v變化

關(guān)于故障概率對(duì)集群演化行為的影響，數(shù)值仿真結(jié)果顯示: 集群收斂速度與故障概率密切相關(guān)，故障概率λ = 1-p越大，收斂速度越慢.取β =T = 1，K = 2，h = 0.1，初始速度和位置為V0= [1，3，2，4，5，6]，X0= [1，3，2，4，5，6].故障概率分別取0.05，0.3，0.5，0.7，對(duì)應(yīng)的收斂時(shí)間為3.2s，4.8s，5.8s，9.6s.從圖4.11-4.14中可以看出故障概率越大收斂速度越慢.這與定理2.1的結(jié)論是一致的.另外切換時(shí)間和切換函數(shù)σ(t)有關(guān).如果改變切換函數(shù)使得切換間隔變長(zhǎng).如果要繼續(xù)滿足假設(shè)2.2則T將變大，這將會(huì)影響集群演化.將圖4.3所示的拓?fù)浣Y(jié)構(gòu)改變?yōu)閳D4.4中所示的拓?fù)浣Y(jié)構(gòu).顯然沒(méi)有生成樹(shù)，且數(shù)值模擬表明在該拓?fù)湎孪到y(tǒng)2.1不能形成集群.圖4.15-4.17分別表示最大切換間隔為1s，3s，5s時(shí)系統(tǒng)2.1速度變化.

從圖中可以看出，如果模式集P中存在不能形成集群的拓?fù)淠Ｊ?，隨著切換間隔增大，集群收斂速度變慢.當(dāng)切換間隔趨于無(wú)窮時(shí)，系統(tǒng)的集群演化行為將會(huì)遭到破壞.

5.總結(jié)

本文研究了具有切換拓?fù)浜碗S機(jī)故障影響的C-S模型的集群演化行為，證明了當(dāng)β ＜時(shí)，系統(tǒng)幾乎必然發(fā)生無(wú)條件群體行為; 當(dāng)時(shí)，在特定約束條件下，系統(tǒng)也幾乎必然發(fā)生群體演化行為.特別的，當(dāng)約束條件與初始速度有關(guān)，而與初始位移無(wú)關(guān); 當(dāng)時(shí)，約束條件與初始速度和初始位移都有關(guān).進(jìn)一步研究發(fā)現(xiàn)，隨機(jī)故障也會(huì)影響集群演化速度，并且集群收斂速度隨著故障概率λ的增大而減慢.