利用分布式狼群算法進行三維傳感器優化布置的方法研究

伊廷華， 王傳偉， 李宏男

(大連理工大學建設工程學部土木工程學院， 遼寧 大連 116023)

引 言

交通運輸關系國計民生和經濟命脈，而大跨橋梁則是公路和鐵路連接的關鍵結點。為了確保大跨橋梁的服役安全，對其在施工及服役期間進行健康監測與安全性評估是十分必要的。為了實現該目的，首先需要獲取結構的重要響應，而這些響應數據需要由合理布設在結構上的傳感器來測得，考慮傳感器本身需要一定的成本，與其配套使用的數據采集和處理設備的造價也都較高，從經濟方面考慮，希望采用盡可能少的傳感器來達到監測的目的，因此傳感器位置和數量優化的問題應運而生。一種好的傳感器布設方案應滿足[1]：1) 在含噪音的環境中，能夠利用盡可能少的傳感器獲取全面而精確的結構響應信息；2) 測得的結構響應信息應能夠與數值分析的結果相對應；3) 對感興趣的振動響應數據能夠進行重點采集；4) 監測結果具有良好的可視性和魯棒性；5) 監測系統的設備投入、數據傳輸和結果處理的費用能夠最少。

傳感器優化布置屬于組合優化問題，同時也是多維優化問題。以往算法只能針對結構的某一方向進行傳感器的優化布置，如果將多維傳感器布置在這些測點上，會造成傳感器在優化的結構振動方向最優，而在其余方向不是最優。針對此問題，各國學者已開展了一些初步的研究，如Kammer和Tinker在有效獨立法的基礎上[2]，提出了一種將三維加速度傳感器作為獨立單位進行優化布置的方法，并以X-33航天器為例，與其他方法進行對比驗證；江祥林和程高以有效獨立法為準則[3]，開發了三維加速度傳感器優化布置MATLAB工具箱，并計算給出了九江長江大橋的三維傳感器優化布置方案，模態試驗結果驗證了該布置方案的合理性。采用傳統的傳感器布置方法有其簡單、實用的優點，但這些方法得到的結果卻往往是次優的，即通過此類方法所得到的傳感器布置位置無法保證理論與實測信息之間的誤差最小。近些年，一些新型智能優化算法如粒子群算法、遺傳算法、蟻群算法和猴群算法等的出現，因其具有較好的尋優能力而取得了較快的發展。一些研究已表明，將智能算法與優化準則相結合，可取得更好的優化效果。He等提出了一種Moran′s I法[4]，解決了多維傳感器布置信息冗余問題，以黃河上游的拉西瓦拱壩為例，通過改進的粒子群算法對其進行優化計算，驗證了該方法的有效性和算法的高效性；劉宇等給出了基于遺傳算法的加速度傳感器布置的實施過程[5]，并以潤楊大橋斜拉橋為例，對比分析了多目標函數優化布置方法與單目標函數方法相比的優越性；Fidanova等提出無線傳感器網絡布置問題[6]，以傳感器數量為目標函數，利用蟻群算法進行優化布置，結果表明：蟻群算法的搜索結果優于進化算法。伊廷華等提出改進猴群算法的傳感器優化布置方法[7]，以大連世貿大廈為例，證明了該算法較經典序列法有較大的優越性。

本文建立了一種傳感器的三維模態置信準則，基于新型智能算法——狼群算法(Wolf algorithm，簡稱WA)[8]，提出了一種分布式狼群算法(Distributed wolf algorithm，簡稱DWA)，通過在狼群中引入分組的策略，大幅提高了算法的并行搜索效率，文末通過一個基準模型驗證了該方法的可行性和有效性。

1 三維優化準則的建立

1.1 理論基礎

眾所周知，Fisher信息陣(Fisher information matrix，簡稱FIM)等價于待估參數估計誤差的最小協方差矩陣，其能夠度量測試響應中所包含信息的多少，表達式為

F=ΦTΦ

(1)

式中F為Fisher信息陣；Φ為模態振型矩陣；ΦT為Φ的轉置。

根據文獻[2]，F可以表示為各個自由度貢獻之和，即

(2)

式中F為全部自由度的FIM；Fk為第k個自由度的FIM；φk,*為Φ的第k行；nc為結構的自由度個數。

結構的每個節點包括三個平動和三個轉動自由度，由于轉動自由度在實際測試中較難直接測到，因此這里只考慮三個平動自由度的優化布置。將節點在x,y,z三個方向上的模態向量作為一個單元，此時FIM可表示為

(3)

式中F為全部節點的FIM；F3k為第k個節點的FIM；φ3k,*為Φ中第k個節點的三個平動自由度所對應的模態向量組成的矩陣；n為節點數目。

模態置信準則(Modal assurance criterion，簡稱MAC)是判斷結構的實測模態向量間是否相互線性獨立的基本要求[9]，其表達式為

(4)

式中φ*,i和φ*,j分別為振型矩陣Φ中的第i列和第j列。

1.2 三維優化準則

借鑒式(3)以節點為單位的方法，可得到待布置傳感器的Fisher信息陣Q

(5)

式中Q3k為第k個三維傳感器位置所對應節點的FIM；φ3k,*為Φ中第k個節點的三個平動自由度所對應的模態向量組成的矩陣；nsp為待布置的三維傳感器數量。

因此，可以借鑒MAC的方法來衡量Q的優劣，進而建立起三維模態置信準則(Triaxial modal assurance criterion，簡稱TMAC)，即

(6)

式中Qi,j為待布置傳感器的FIM的第i行第j列元素；TMACi,j為TMAC中第i行第j列元素，且TMACi,j∈[0,1]。

TMAC矩陣非對角元的值越小，各階測試節點振型的獨立性越好，線性相關性越小，傳感器的布設效果也就越好；反之，傳感器布設效果越差。因此，可以以TMAC非對角元元素的最大值的最小化為三維傳感器的優化目標，即本文提出的三維優化準則可寫為

min(f)

(7)

2 基于分布式狼群算法的三維傳感器優化布置方法

WA由鄢小虎和柳長安于2010年提出的一種模擬狼群捕食的群智能優化算法[8]，主要用于解決帶有連續變量的全局優化問題，其基本思想是模擬狼群捕食的三個過程，即游獵、圍攻和食物分配。其中：游獵過程主要是狼個體依據自身的力量搜索當前所在位置附近的局部最優值；圍攻過程是狼群利用群體中最優狼個體的信息搜索全局最優值；食物分配過程通過隨機產生新個體取代目標函數值差的狼個體，以避免算法陷入局部最優。與傳統優化算法相比，WA的優點主要包括：1) 不要求目標函數連續或可微，對于線性或非線性的問題均可求解；2) 算法的實現過程較為簡單，且能夠以較快速度搜索到高維數優化問題的最優解或次優解。由于WA只適用于連續變量問題的求解，若將其用于傳感器優化布置，需要對其編碼方式進行改進。此外，通過計算可以發現狼群在圍攻的過程中，由于狼群中的每只狼個體都向獵物逼近，這會極大地降低狼群的多樣性，使得算法在迭代過程中易陷入局部最優。為此，本文建立了一種分布式狼群算法，將狼群分為多個組，通過限制組內參與圍攻的狼個體數量，僅采用組內最差個體向最優個體逼近的搜索機制，既避免了狼群多樣性的降低，又使得組內的信息能夠充分共享，大幅提高算法的求解效率。

2.1 狼群的編碼及其初始化

對欲布置傳感器的結構建立有限元模型，通過模態分析，獲取結構的振型矩陣，并對傳感器的候選布置位置進行編號。所有節點位置即為傳感器的候選優化位置。考慮傳感器優化布置的特點，這里引入雙重編碼方式進行解的表達[10]，即利用有序對(x,s)來表示狼群的個體，來對應傳感器布置問題的可行解。其中，x為位置向量，即在搜索過程中是以此向量進行迭代搜索的；s為二進制向量，即表示傳感器的布置位置。狼群編碼及初始化的步驟如下：

步驟 1：假設所有節點的數目為n，對其進行編號，即1～n。

步驟 2：以狼群中第i只狼個體為例(i=1,2,…,P，P為狼群個體數目)，其相應的解可表示為：pi=(xi,si)={(xi,1,si,1),(xi,2,si,2),…,(xi,n,si,n)}。位置向量xi為從區間[xdown,xup]之間隨機產生的實數數組，其各維分量可按下式產生

xi,j=rand×(xup-xdown)+xdown

(8)

式中rand為[0,1]內的隨機數。

si,j為xi,j通過下式中的函數轉換而得到二進制編碼向量

(9)

采用式(9)時，需要首先設定一個判斷閾值ε和區間[xdown,xup]，若sig(xi,j)>ε，則該分量si,j取1，即表示在該節點的位置處布置傳感器；若sig(xi,j)≤ε，則該分量取0，即代表在該節點位置上不布置傳感器。通過試算可以發現，當xi,j在[-5,5]之間取值時，0.006 7≤sig(xi,j)≤0.993 3，可見取值是合理的，因此本文取xdown=-5，xup=5。

對于初始化產生的解，si中傳感器的布置數目可能會出現不等于nsp的情況，即不滿足編碼要求，則此時應重新進行初始化，重復步驟2直到初始化的解滿足編碼的要求為止，本文后面的各個過程遇到類似情況均做同樣處理。

因為狼個體的初始化是隨機的，而產生的有效狼個體需要滿足編碼要求，這就意味著產生的狼個體并不都是有效的。為了提高有效狼個體的產生效率，這里提出一種基于概率法判定閾值ε的方法。以狼個體pi的第j維分量pi,j為例，使si,j取值為1的概率為nsp/n，而si,j取值為0的概率為1-nsp/n，這樣即可保證產生的狼個體在統計上能夠滿足編碼要求。若xi,j∈[xdown,-xseta]，則si,j=0，對應si,j取值為0的概率為1-nsp/n；若xi,j∈(-xseta,xup]，則si,j=1，對應si,j取值為1的概率為nsp/n。因此，xseta的取值為

xseta=(nsp/n)×(|xdown|+|xup|)-|xup|

(10)

即區間[xdown,xup]以-xseta為界進行分割，因此ε的適宜取值為1/(1+exseta)。ε的這種取值方式不但能夠加快有效初始狼群的產生速度，而且能夠保證狼群個體各維分量的均勻性。

2.2 狼群分組

原WA僅通過單個狼群進行搜索，這對于解決多自由度優化的問題時，全局搜索能力不強，耗費時間也較長。基于此，本文提出通過設定多個狼群進行同步并行搜索的方法，即將初始化狼群個體以一定的方式將其分配到多個組內，然后進行同步并行迭代計算，較好地解決了這一問題。

設初始產生的狼群的個體數為P，將其分為M個組，每個組內有N只狼個體。這里將每個組內目標函數值最優的狼個體記為頭狼。狼群分組的步驟如下：

步驟1：狼群中狼個體目標函數的求解。設第i只狼個體位置向量為xi，利用其相應的二進制向量si，得到布置傳感器的節點編號，代入式(5)計算Q，然后把Q代入式(6)計算TMAC，最后把TMAC代入目標函數，即得到其值f(pi)。

步驟 2：將狼群中狼個體按目標函數值由差到優進行排序，然后把第1只狼個體放入第1組，第2只狼個體放入第2組，…，第N只狼個體放入第N組，第N+1只狼個體放入第1組，第N+2只狼個體放入第2組，依次重復直到P只狼個體分配完畢。

2.3 游獵行為

分組后每個組內的狼個體都參與游獵找尋獵物。狼個體在每走一步之前，先計算向周圍h個方向前進一步的位置，然后找到h個位置中的最優位置da，若da比當前位置優，則該狼個體向前移動到位置da,并以da為當前位置繼續向前搜索；若找不到更優的位置，則該狼個體的游獵行為結束。狼個體的游獵方程可表示為

yc,j=xi,j+(2×rand-1)×stepa

(11)

式中rand為[0,1]內的隨機數；stepa為搜索步長；xi,j為第i只狼個體的第j維分量(j=1,2,…,n)，yc,j為xi,j周圍第c(c=1,2,…,h)個位置的第j維分量。

設狼群經上述分組后，以第m(m=1,2,…,M)個組第l只狼個體位置向量xe為例，游獵步驟如下：

步驟2：計算各個yc的目標函數值，若這h個新位置中最優的位置比之前的位置優，則將狼個體的位置向量變為此向量；反之，狼個體位置保持不動。

步驟3：重復步驟1和步驟2直到設定的搜索次數Nh。

2.4 圍攻行為

Δx(w,j)d=rand×stepb×(x(best,j)d-x(worst,j)d)，

(Δxmin≤Δx(w,j)d≤Δxmax)

(12)

式中stepb為狼個體圍攻獵物的步長；x(best,j)d為第d次迭代中頭狼第j維分量(j=1,2,…,n)，x(worst,j)d為第d次迭代中目標函數值最差的狼個體第j維分量。Δx(w,j)d為第d次迭代中目標函數值最差的狼個體第j維分量的圍攻距離，為防止狼群在圍攻過程中因圍攻距離過大而容易錯過全局最優值，采用閾值Δxmin和Δxmax來限制狼個體的圍攻距離，即若Δx(w,j)d>Δxmax，取Δx(w,j)d=Δxmax；若Δx(w,j)d<Δxmin，取Δx(w,j)d=Δxmin。

x(worst,j)d+1=x(worst,j)d+Δx(w,j)d

(13)

式中x(worst,j)d和x(worst,j)d+1為圍攻前和圍攻后的組內最差狼個體的第j維分量。

圍攻步驟如下：

步驟 1：游獵完成后，對狼群重新分組。通過分組可保證狼群組內的頭狼位置的優越性。

步驟 2：以第m個組為例，通過組內目標函數值最差的狼個體xworst和組內目標函數值最優的狼個體xbest，利用式(12)和(13)更新最差狼個體的位置，得到更新后的狼個體。

2.5 食物分配原則

狼群的食物分配原則為先強后弱，即狼群捕捉到的大部分獵物會被強壯的狼占有，弱小的狼分配到的食物很少，盡管這種方式可能會餓死一些弱小的狼，但能保證強壯的狼在下次能更好地撲捉到獵物，不至于使整個狼群餓死，提高了狼群的生存能力。

本文模擬狼群的這種食物分配行為，去除每組中較差的t只狼個體，同時隨機產生t只新狼個體，這能夠顯著增加狼群的多樣性。狼群的食物分配原則步驟為：

半個多世紀以來，科學大洋鉆探已經證明了板塊構造理論的正確，開創了古海洋學，并通過揭示深海生物圈中種類繁多、數量龐大的生命，重新定義了我們對地球生命的看法，而且還有更多的東西需要學習和探索。

步驟1：按照狼群分組的步驟將圍攻行為完成后的狼群重新進行分組，使得淘汰的狼個體為群體內的最差的個體。

步驟 2：利用狼群數據初始化的步驟每組產生t只新的狼個體，并用這t只狼個體取代組內目標函數值最差的t只原有的狼個體。

關于狼群分組的說明：本文方法在狼群游獵、圍攻和食物分配過程前均進行狼群分組，即多次采用分組的方式。這是由于狼群經過某一步搜索過程后，各個組會得到不同的結果，分組可將這些結果進行比較，然后分配到新的組內，保證每個組內個體的均衡性。這種方式大大增強了不同組內狼個體的信息交流，提高算法的尋找最優值的效率。

2.6 算法終止條件

狼群算法的運行需要一定的循環次數Nc，當達到循環次數時優化布置過程終止，整個計算過程可通過科學計算軟件MATLAB實現。

3 工程算例

3.1 計算模型簡介

為了評價結構健康監測中各種算法的優劣，美國中佛羅里達大學開發了一個橋梁基準模型(圖1)，本文即采用這一基準模型進行傳感器位置的優化研究。該模型共兩跨，總長5.486 4 m，寬1.828 8 m。橋梁沿縱向的主梁將荷載轉移到支撐上，側向穩定性由橫向每隔0.914 4 m的次梁提供。基準模型梁截面都相同，均采用S3×5.7型鋼。采用SAP2000進行建模[11]，有限元模型的數據被導到MATLAB中，以供使用者運行分析。模型共有177個節點，182個單元，每個節點包含3個自由度，分別對應x,y,z三個方向的信息。提取模型的剛度矩陣和質量矩陣，通過模態分析可得到結構的前10階模態振型矩陣Φ。

圖1 基準模型實物圖

圖2 基準模型的有限元模型

3.2 傳感器優化布置

如圖2所示，有限元模型的節點數為177，除去橋墩與地面接觸部位沒有平動自由度的6個節點，因此結構要考慮的節點數n=171。設需要布設的傳感器數目nsp=20，傳感器類型為三維加速度傳感器。為了說明本文提出的DWA的優越性，同時采用另外兩種方法進行對比研究，即：

工況1：原狼群算法，即WA；

工況2：分布式狼群算法，即DWA；

工況3：全節點三維傳感器布置。

(1) 參數敏感性

優化算法中的參數取值會直接影響到算法的收斂性，因此在進行傳感器優化布置之前，應對DWA進行參數敏感性分析，以便為選取合理的參數作參考。設狼群個體數目P=50，共分為M=5個組，這樣每組內有N=10只狼個體，搜索區間上下限分別為xdown=-5和xup=5，圍攻距離Δx的限定范圍Δxmin=-0.5和Δxmax=0.5，算法的迭代次數Nc=200。這里選取影響DWA性能的4個重要參數進行分析：游獵搜索次數h×Nh，搜索步長stepa，圍攻步長stepb，每組淘汰個數t。通過正交試驗設計構成正交試驗表L9(34)，分別表示：試驗1～9號；4個因素t，stepa，stepb，h×Nh；每個因素有1，2，3三個水平，每個水平的取值如表1括號內的數值。每組試驗獨立運行5次，取其計算值的最優值，如表1所示。

表1 正交試驗表及試驗結果

圖3 由工況1和工況2得到的TMAC柱狀圖

圖4 TMAC非對角元列向量最大值

圖5 基準模型基于原狼群算法的三維傳感器布置

圖6 基準模型基于分布式狼群算法的三維傳感器布置

從表1中可以看出：1) 對于參數t，取值偏小較好，若t取值較大，計算得到的目標函數值比較差，即會影響狼群搜索能力，這里建議t取值為1；2) 搜索步長stepa，對狼群的局部搜索能力有很大的影響，若取值較小，搜索效果不好；若取值過大，則容易錯過全局最優值，對搜索結果不利。stepa取值為2比較合適；3) 圍攻步長stepb，若取值較小，導致算法的全局搜索能力降低；若取值較大，會因錯過全局最優值而使得搜索結果較差。當其值為1時能夠搜索到較優的極值，建議stepb取值1；4) 游獵搜索次數h×Nh，可以得出增多搜索次數可以提高整體的尋優能力，但提高的幅度有限，因此，建議Nh取值20，h取值為3。為便于與工況2進行對比，工況1中的數據采用上述分析建議的取值。

(2) 優化布置結果分析

表2給出了各種工況傳感器布置方案的TMAC非對角元最大值。圖3(a)給出了工況1布置20個傳感器時的TMAC矩陣柱狀圖，此時TMAC非對角元最大值為0.001 9；圖3(b)給出了工況2布置20個傳感器時的TMAC矩陣柱狀圖，此時TMAC非對角元最大值為0.000 5，優化效果增幅73.68%，效果明顯。但由于0.000 5和0.001 9遠小于1，表現為在圖(3)中TMAC柱狀圖的非對角元都非常小，很難對兩種工況加以直觀對比。為了更好地體現出本文所提出算法的有效性，圖4給出了TMAC非對角元列向量最大值的比較。從圖4可以看到，工況2的每階模態列向量非對角元最大值都小于工況1，說明了DWA算法要優于WA。從表2中TMAC非對角元的最大值可以發現，工況2為0.000 5，而工況3為0.001 6，這說明對于結構所有的節點都布置傳感器并不合理，不一定能得到最優布置效果，分析其原因是：模態置信準則的目的是實現各階模態向量之間的可區分，即各階模態向量之間的夾角最大化，但其權重矩陣用單位矩陣代替質量矩陣，使得各階模態向量之間無正交性關系，因此會造成結構所有的節點都布置傳感器并不合理的狀況。圖5和6給出了基準模型基于WA和DWA的三維傳感器布置方案。

表2 不同傳感器布置方案的TMAC非對角元最大值

4 結 論

本文建立了一種新的三維傳感器優化布置準則，提出基于DWA的傳感器優化布置的方法，并以基準模型為例進行驗證，得到以下結論：

(1)針對MAC只能對結構的某一方向進行傳感器優化布置研究，而不能確保在三個方向同時實現優化的問題，本文提出了TMAC，解決了三維傳感器優化布置目標函數的問題。

(2)采用雙重編碼方式，有效地克服了原WA只能解決連續變量優化的問題；提出一種基于概率法判定閾值ε的方法，采用概率法初始化狼群個體，不僅加快了有效初始狼群的產生速度，而且保證了狼群個體各維分量的均勻性。

(3)引進了分組搜索的策略，狼群以組為單位并行搜索目標函數最優值，算例結果表明，分組并行搜索極大地加強了找尋大規模的目標最優值的能力。

(4)參數敏感性分析表明，狼群算法中的參數對算法的尋優效果影響較大，搜索步長和圍攻步長如果偏小，則會降低算法的計算效率；如果偏大，則可能跳過全局最優解。每組中的狼個體淘汰數目不宜過多，否則會對算法的搜索能力和收斂速度不利；游獵搜索次數過多，對尋優能力的改善并不明顯，還會增加算法的運行時間，應適當取值。

參考文獻:

[1] 伊廷華,李宏男,顧明.結構健康監測中基于多重優化策略的傳感器布置方法[J].建筑結構學報,2011,32(12):217—223.YI Tinghua, LI Hongnan, Gu Ming. Multiple optimization strategies based sensor placement method for structural health monitoring[J]. Journal of Building Structures,2011,32(12):217—223.

[2] Daniel C Kammer, Michael L Tinker. Optimal placement of triaxial accelerometers for modal vibration tests[J]. Mechanical Systems and Signal Processing, 2004,18(1):29—41.

[3] 江祥林,程高.基于EfI法的橋梁模態測試中傳感器優化布置[J].橋梁建設,2012,42(2):59—65.JIANG XIANG-lin, CHENG Gao. Optimal sensor placement for bridge modal testing based on EfI method[J]. Bridge Construction,2012,42(2):59—65.

[4] He L J, Lian J J, Ma B, et al.Optional multiaxial sensor placement for modal identification of large structures[J]. Structural Control and Health Monitoring, 2013, DOI: 10.1002/stc.1550.

[5] 劉宇,畢丹,李兆霞.大跨斜拉橋基于遺傳算法的傳感器優化布置方法[J].東南大學學報,2009,39(4):825—829.Liu Yu, Bi Dan, Li Zhaoxia. Optimal placement of accelerometers in long cable-stayed bridges based on genetic algorithm[J]. Journal of Southeast University, 2009,39(4):825—829.

[6] Fidanova S, Marinov P, Alba E. Ant Algorithm for Optimal Sensor Deployment[M]. Computational Intelligence, Springer Berlin Heidelberg, 2012:21—29.

[7] 伊廷華,張旭東,李宏男.基于改進猴群算法的傳感器優化布置方法研究[J].計算力學學報,2013,30(2):218—223.YI Ting-hua, ZHANG Xu-dong, LI Hong-nan. Research on optimal sensor placement based on improved monkey algorithm[J]. Chinese Journal of Computational Mechanics,2013,30(2):218—223.

[8] 鄢小虎,柳長安.基于生物智能的移動機器人路徑規劃研究[D].保定:華北電力大學,2010.YAN Xiao-hu, LIU Chang-an. Research on path planning for mobile robot based on the biological intelligence[D]. Baoding: North China Electric University, 2010.

[9] Carne T G, Dohmann C R. A modal test design strategy for modal correlation[A]. Proceedings of the 13th International Modal Analysis Conference,Schenectady[C]. New York,USA,February,1995.

[10] Yi T H, Li H N, Zhang X D. Sensor placement on Canton Tower for health monitoring using asynchronous-climb monkey algorithm[J]. Smart Materials and Structure,2012,21(12):1—12.

[11] Catbas F N, Caicedo J M, Dyke S J. Development of a benchmark problem for bridge health monitoring[A]. Proceedings of the International Conference on Bridge Maintenance, Safety and Management, IABMAS[C]． Porto, Portugal, July, 16-19, 2006.