一類具有切換拓撲和隨機故障影響的集群演化模型分析

喬正陽，劉易成

(國防科技大學數學系，湖南 長沙410073)

1.引言

我們知道，多智能系統在生態學，物理學，社會學以及人工智能等學科中應用廣泛.這類系統的顯著特點是通過分離獨立的個體間的信息交互，系統能涌現出預先設計的集群特征.Cucker和Smale在文[4-5]中給出了一類描述多智能體系統演化的模型(C-S模型)，并且刻畫了該模型的群體演化行為.隨后，很多學者研究了各種變形的C-S模型，進一步刻畫該模型的復雜群體演化行為，其中包括時滯影響下的C-S模型和不同拓撲結構的C-S模型等.在文[14]中，SHEN研究了具有等級結構的C-S模型.近年來，LI和XUE 在文[12]中研究了具有根結點領導的C-S模型.同時考慮了切換拓撲的影響情形，這類拓撲結構比等級結構更具一般性.在文[8]中DONG和QIU研究了一般拓撲結構下的C-S 模型的群體演化行為，該文對拓撲結構的要求僅需要拓撲交換圖存在一個生成樹即可.隨后Cucker和DONG在文[2]中研究了一般情形下帶有切換拓撲的C-S 模型.由于多智能體系統中個體之間相互連接的拓撲結構往往是不斷變化的，在文[1]中，作者發現鴿群中個體之間采用間歇性交互機制，并不是每時每刻的都進行組內信息傳輸.因此具有切換拓撲的C-S模型具有很強的實際意義.

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

本文的結構如下: 第2節將介紹有向圖以及切換系統的基本概念，描述具有切換拓撲和隨機故障影響的C-S模型，給出關于故障概率和切換方式的假設條件以及相關引理結論; 第3 節給出了具有切換拓撲和隨機故障影響的C-S模型的主要結果和證明過程.由于拓撲結構是可切換的，我們需要一種新的方法估計帶有切換拓撲和隨機故障的拓撲交互圖的遍歷系數，進而證明系統幾乎必然發生集群演化行為.最后，通過數值仿真方法，獲得了故障概率和切換間隔增大時，系統的集群演化行為的變化特點.

2.預備知識

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

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

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

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

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

考慮n個個體組成的集群系統，集群拓撲結構對應的交互圖為G，集群演化過程在離散時刻t ∈N滿足如下：

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

假設2.1假設當t ∈N，j ∈時，隨機事件滿足：

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

由上述假設可知

接下來，給出隨機故障情況下的集群定義.本文中‖·‖均為2-范數.定義

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

則稱系統(2.1)-(2.2)發生集群演化行為.

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

其中x[t]=(x1[t]，x2[t]，··· ，xn[t])，v[t]=(v1[t]，v2[t]，··· ，vn[t]).與文[2]中一樣，我們需要假設系統的交互拓撲在切換過程中保持一定連通性.

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

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

為了刻畫系統發生集群演化行為的條件，先給出如下引理.

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

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

引理2.3[2]假設則對任意t ＞0有

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

2)若fk是獨立事件且

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

存在唯一正零點z*，并且滿足

當z ∈[0，z*]時，F(z)≤0.

3.主要結果

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

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

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

因此

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

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

證利用數學歸納法證明.當k =1時，結論自然成立.假設當1 ≤j ≤k-1時，

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

又因為E((pKIn+Qu))=E(Au)，E((pKIn+Qv))=E(Av)，故

注意到

因此

根據引理3.1，可得

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

由于Bi相互獨立，從而可得

另一方面，根據假設2.2以及區間[αt-2T(i+1)，αt-2Ti)長度大于T，因而存在其子區間[tk′，tk′+1)使得G([tk′，tk′+1))有根節點，從而G([αt-2T(i+1)，αt-2Ti))=G(Ci)有根結點.進而根據引理2.1，可知矩陣∏Ci是不規則矩陣.因此

根據遍歷系數的定義得

故

引理3.2對于系統(2.1)-(2.2)，如果假設2.1和假設2.2成立，且存在與t無關的隨機變量τ0，使得當t ＞τ0時有

證由于Bi是隨機矩陣，可知也為隨機矩陣.所以對?t ＞0，

因此

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

事件At表示集合由上面得根據引理2.4(Borel-Cantelli定理)，我們可得即所以這里為At的補.令顯然Bk?Bk-1，定義與t無關的隨機變量τ0，其滿足τ0(ω) = k當且僅當ω ∈Bk-Bk-1.所以對任意t ≥k，有ω ∈Bk因而ω ∈又因為所以當t ＞τ0時依概率1有又因為因此

定理3.1具有切換拓撲和隨機故障影響的系統(2.1)-(2.2)滿足假設2.1和2.2以及并且下面條件之一成立:

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

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

當t足夠大時，由式(2.5)可得

因此

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

從而對任意t 有

因此，當t ＞ατ0+1時，

另一方面，對任意時刻t2＞t1＞τ0，ij，

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

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

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

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

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

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

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

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

又因為

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

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

4.數值仿真

本節我們將對帶有切換拓撲和隨機故障影響的C-S模型進行數值仿真分析，進一步探索切換拓撲以及隨機故障對系統的動力學行為的影響.

首先，我們通過數值仿真方法驗證定理3.1.為此，假定個體數n = 6，模式集P由3種不同的拓撲模式組成，即P = {G0，G1，G2}，對應拓撲結構見圖4.1-4.3所示，其中G0，G1具有根結點(圖中有生成樹).而G2并沒有根結點，因為G2中任意一點都不能到達節點4.構造選擇函數顯然選擇函數滿足假設2.2.

數值仿真結果如下:

圖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變化

關于故障概率對集群演化行為的影響，數值仿真結果顯示: 集群收斂速度與故障概率密切相關，故障概率λ = 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，對應的收斂時間為3.2s，4.8s，5.8s，9.6s.從圖4.11-4.14中可以看出故障概率越大收斂速度越慢.這與定理2.1的結論是一致的.另外切換時間和切換函數σ(t)有關.如果改變切換函數使得切換間隔變長.如果要繼續滿足假設2.2則T將變大，這將會影響集群演化.將圖4.3所示的拓撲結構改變為圖4.4中所示的拓撲結構.顯然沒有生成樹，且數值模擬表明在該拓撲下系統2.1不能形成集群.圖4.15-4.17分別表示最大切換間隔為1s，3s，5s時系統2.1速度變化.

從圖中可以看出，如果模式集P中存在不能形成集群的拓撲模式，隨著切換間隔增大，集群收斂速度變慢.當切換間隔趨于無窮時，系統的集群演化行為將會遭到破壞.

5.總結

本文研究了具有切換拓撲和隨機故障影響的C-S模型的集群演化行為，證明了當β ＜時，系統幾乎必然發生無條件群體行為; 當時，在特定約束條件下，系統也幾乎必然發生群體演化行為.特別的，當約束條件與初始速度有關，而與初始位移無關; 當時，約束條件與初始速度和初始位移都有關.進一步研究發現，隨機故障也會影響集群演化速度，并且集群收斂速度隨著故障概率λ的增大而減慢.