基于Memetic算法的橋梁傳感器優化布置

彭珍瑞，趙宇，殷紅，彭寶瑞（.蘭州交通大學機電工程學院，甘肅蘭州730070；.蘭州大學土木工程與力學學院，甘肅蘭州730000）

基于Memetic算法的橋梁傳感器優化布置

彭珍瑞1，趙宇1，殷紅1，彭寶瑞2
（1.蘭州交通大學機電工程學院，甘肅蘭州730070；2.蘭州大學土木工程與力學學院，甘肅蘭州730000）

針對橋梁傳感器優化布置問題，提出了一種基于Memetic算法的傳感器優化布置方法。首先將傳感器優化布置問題轉化為最優化問題，建立其數學模型，并運用Memetic優化算法求解傳感器最優化布置。該算法將遺傳算法的全局搜索與模擬退火算法的局部搜索相結合，克服了遺傳算法易早熟和陷入局部最優等問題。某懸索橋算例表明，該算法可以解決橋梁傳感器優化布置問題，且與遺傳算法對比，Memetic算法顯示出較好的收斂速度及尋優能力。

橋梁；傳感器優化布置；Memetic算法；遺傳算法；模擬退火算法

橋梁在材料老化和載荷的長期效應、疲勞效應和突變效應等災害因素的共同作用下將不可避免地導致橋梁結構的損傷累積和抗力衰減，從而導致抵抗自然災害甚至正常環境作用的能力下降，極端情況下造成災難性的突發事故。為此，需要采用有效的技術手段監測和評定橋梁結構的安全狀況，并及時修復和控制結構損傷。因此，橋梁結構實施健康監測，最終實現對橋梁結構健康狀態的評估具有重要的意義［1］。

傳感器系統作為橋梁結構健康監測的子系統之一，主要用來獲取橋梁結構的信息。合理地布置傳感器是保證橋梁結構健康監測質量的前提。將最少的傳感器布置在最合理的位置得到最全面的信息這是典型的組合優化問題。

傳感器的優化布置可分為傳統優化算法和非傳統優化算法。傳統優化算法，如有效獨立法（effec?tive independence，EFI）、模態動能法（modal kinetic energy，MKE）、Guyan模型縮減法等［2?4］。非傳統算法主要有遺傳算法、模擬退火算法等。覃柏英、林賢坤等［5?6］利用遺傳算法以GARTEUR飛機模型為研究對象對其進行傳感器優化布置，并將優化結果與有效獨立法、模態動能法等傳統優化算法對比，遺傳算法優化結果較優于上述算法，后來，又將微粒群算法用于該模型的傳感器優化布置。文獻［7］提出了基于自適應模擬退火遺傳算法的加筋板殼結構的傳感器優化布置，在模擬退火算法之前加入遺傳操作（選擇、交叉、變異）和自適應算子。這些非傳統算法能較好地解決組合優化問題，但是單純地利用某一種算法易早熟、陷入局部最優。Memetic算法是在遺傳操作時引入局部搜索策略，高亮等［8］將Memetic算法應用于求解有時間約束的TSP問題中，采用雙重策略的局部搜索算法。文獻［9］構造了一種基于Memetic算法的要地防空優化部署方法，分別將遺傳算法和領域搜索作為全局和局部搜索策略，解決這一組合優化問題。本文提出了結合遺傳算法（genetic algorithm，GA）和模擬退火算法（simulated annealing algorithm，SA）的Memetic算法，在遺傳算法中加入模擬退火算法作為局部搜索策略，將該算法應用于橋梁傳感器優化布置問題的求解。

1 Memetic算法橋梁傳感器優化布置

1.1 Memetic算法

Memetic算法是一種結合遺傳算法和局部搜索策略的新型智能算法［10］。通過與局部優化策略的結合，局部調整進化后產生的新個體，強化了算法的局部搜索能力。Memetic算法區別于遺傳算法的關鍵是局部搜索，局部搜索策略的效率及可靠性決定Memetic算法的求解速度和質量。本文基于模擬退火Memetic算法求解橋梁傳感器優化布置問題。模擬退火算法（SA）是模擬物理退火過程中的加溫、等溫、冷卻等過程，基于固體物質退火過程的優化算法，是一種迭代自適應啟發式概率性搜索算法，利用Metropolis準則控制溫度下降過程［7］。

1.2 橋梁傳感器優化布置數學模型

首先，建立橋梁有限元模型，進行模態分析，提取其模態振型。設橋梁有限元模態振型矩陣Φn×l，n為有限元模型節點自由度即傳感器待布置點的自由度，l為模態振型的階數。從中選取m個節點自由度作為傳感器最終布置點，使目標函數MAC矩陣的非對角線元達到最優，即：使得MAC矩陣的最大非對角線元最小，由于Memetic算法中的全局搜索策略一般處理最大化問題，故將適應度函數構造為

1.3 Memetic算法傳感器優化布置

本文通過遺傳算法進行全局搜索，將模擬退火算法作為局部搜索策略，在遺傳操作選擇、交叉、變異后分別進行局部搜索，進行2次局部優化。

1.3.1 染色體編碼

采用整數編碼方式，例如對于n個節點自由度（每個節點有平動或轉動2種自由度，平動x、y、z，轉動Ux、Uy、Uz）的橋梁傳感器優化布置問題，將染色體分為n段，每一段與橋梁結構有限元模型節點自由度相對應，即傳感器待布置點自由度，編碼為1－n。選取m個節點自由度作為最終布置點，所得布置點的MAC最大非對角元最優。

1.3.2 Memetic算法步驟

1）種群初始化，確定Memetic算法的相關參數：種群規模N、算法迭代次數M、選擇概率ps、交叉概率pc、變異pm、初始溫度T0、結束溫度Tend以及降溫速率q。

2）適應度評價，根據式（1）的適應度函數，計算染色體S的適應度值f（S）。

3）選擇操作，采用輪盤賭選擇方法，根據2）計算的適應度值進行選擇操作，染色體適應度值越大，被選中的概率越大。

4）交叉操作，采用2點交叉法對染色體S進行交叉操作，確定交叉操作的父代，將父代樣本兩兩分組，產生2個自由度區間內的隨機數，確定2個位置，對兩位置的中間自由度進行交叉。交叉后，同一個個體有重復的自由度編號，不重復的數字保留，有沖突的自由度采用部分映射的方法消除沖突。

5）執行模擬退火局部搜索策略：

①對4）中的每一個染色體S1隨機進行擾動產生新的染色體S2。

②計算d f＝f（S2）－f（S1），其中，f（S）為S的適應度值，根據Metropolis準則：

若d f＞0，接受S2作為當前新的染色體，且S1＝；否則計算的接受概率exp（－，若exp（－＞rand（rand為[0，1]上均勻分布的隨機數）接受S2作為當前新的染色體，且S1＝S2。

③利用T＝qT降溫，若T＜Tend，終止模擬退火算法局部搜索策略。

6）變異操作，對5）所得的新染色體進行對換變異，隨機選取2個自由度區間內的自由度，將其位置對換。

7）再次執行模擬退火局部搜索策略，與5）相同。

8）逆轉操作，為改善算法的搜索能力在選擇、交叉、變異之后進行逆轉操作，產生2個自由度范圍內的隨機整數，確定2個位置，對換其位置。

9）判斷是否達到算法最大迭代次數，若滿足，輸出最優解，傳感器優化最終布置的m個節點自由度，否則，繼續執行2）。

2 算例分析

2.1 懸索橋有限元模型

本文對一座懸索橋進行傳感器優化配置，該橋采用鋼筋混凝土加勁桁架懸索體系，主塔材料采用鋼筋混凝土，橫橋采用H型塔，加勁梁采用鋼筋混凝土桁架。利用ANSYS13.0建立拱橋有限元模型，橋面板使用SHELL63單元，加勁桁架、橋塔使用BEAM4單元，主纜、吊索使用LINK10單元，有限元模型如圖1所示。

2.2 基于Memetic算法的懸索橋傳感器優化布置

對圖1懸索橋有限元模型進行模態分析，同時考慮到結構的低階模態具有較大的振型參與系數［12］，提取模型前10階振型，各階頻率如表1。

圖1 懸索橋有限元模型Fig.1 Finite elementmodel of suspension b ridge

表1 懸索橋前10階模態頻率Table 1 The first 10 modal frequencies of the suspension bridge

考慮到懸索橋橋梁結構的對稱性，為減少計算時間，提高收斂速度，對橋梁1／4結構進行傳感器優化布置，其他部分參照布置，選取縱梁與桁架交點及桁架、主纜節點作為傳感器候選測點。除去加勁桁梁、主纜所約束的節點，共297個節點，選擇豎向模態為目標模態，即y方向的自由度，根據所得數據構造模態振型矩陣Φ297×10。利用MATLAB R2009b根據Memetic算法步驟編程，對算例進行求解。由于參數設置會對算法結果的影響，運行程序多次，選取求解效果較好的參數組合，算法的參數設置如表2。

根據上述參數設置運行程序，從297個節點自由度中選取m（2＜m＜297）個節點自由度作為傳感器最終布置點，使適應度值最大。為提高程序的運行效率，在自由度范圍內選擇5的倍數個節點自由度布置傳感器，所得適應度值變化曲線如圖2所示。

表2 Memetic算法參數設置Table 2 Param eters setting of memetic algorithm

圖2 適應度值變化曲線Fig.2 Change curve of fitness value

由圖2可知，節點自由度在5～25之間適應度值迅速增大，節點自由度在60以后緩慢減小，最大適應度值為0.923 0（節點自由度為25），當節點自由度為15時，適應度值等于0.917 6，而所有節點自由度297時適應度值為0.855 9，從傳感器布置的經濟性及布置要求（適應度值接近于1越好）出發，最終所選傳感器數目為15個。傳感器布置方案如表3。

表3 傳感器布置方案Table 3 Plan of optimal sensor placement

表3所得傳感器節點位置多數處于懸索橋的加勁梁梁端、主梁中心處，這與反映懸索橋最不利的工況一致，故可以全面地獲取有效的橋梁健康狀況信息。

2.3 結果對比分析

為了驗證Memetic算法的優越性將優化結果與遺傳算法對比，選取與Memetic算法全局搜索策略相同的參數，采用遺傳算法對懸索橋傳感器進行優化布置，圖3分別給出了布置15個、25個傳感器時，Memetic算法與遺傳算法收斂對比曲線。

由圖3（a）來看，在第5到40次的迭代中，遺傳算法搜索能力較好，但在迭代42次以后，Memeic算法所得適應度值接近0.92。顯然，所得結果比遺傳算法要好。圖3（b）可以看出，Memeic算法收斂速度快，迭代次數在20次后，適應度值已經到達0.875，而遺傳算法的適應度值均小于Memeic算法，可見Memeic算法尋優能力強。Memetic算法與遺傳算法結果對比（m＝15）如表4所示。

圖3 Memetic算法與遺傳算法收斂對比曲線圖Fig.3 The contrast curves of convergence be?tween m emetic algorithm and genetic al?gorithm

從表4中可知，利用Memeic算法所得的優化結果、程序平均運行時間均優于遺傳算法。

綜合圖3（a）、（b）以及表4可知，同遺傳算法相比，Memeic算法表現出較強的搜索能力，總體效果比遺傳算法好，故利用Memeic算法可以實現橋梁傳感器優化布置，且收斂速度快，不易陷入局部最優解。

表4 Memetic算法與遺傳算法結果對比Table 4 Com parison of com putational results between M emetic algorithm and GA

3 結束語

為了實現橋梁傳感器優化布置，針對遺傳算法易陷入早熟的特點，提出了將遺傳算法和局部搜索策略結合的Memetic算法，將其應用于一座懸索橋傳感器的優化布置問題中，建立了數學模型和相應算法。結果證明，在求解橋梁傳感器優化布置問題時，Memetic算法收斂速度快、尋優能力強。

［1］李愛群，繆長青.橋梁結構健康監測［M］.北京：人民交通出版社，2009：1?9.LI Aiqun，MIAO Changqing.Health monitoring of bridge structures［M］.Beijing：China Communications Press，2009：1?9.

［2］KAMMER D C.Sensor placement for on?orbitmodal identi?fication of large space structures［J］.Journal of Guidance，Control，and Dynamics，1991，14（2）：252?259.

［3］LID S，LIH N，FRITZEN C P.The connection between effective independence andmodal kinetic energymethods for sensor placement［J］.Journal of Sound and Vibration，2007，305（4／5）：945?955.

［4］吳子燕，代鳳娟，宋靜，等.損傷檢測中的傳感器優化布置方法研究［J］.西北工業大學學報，2007，25（4）：503?507.WU Ziyan，DAIFengjuan，SONG Jing，et al.A more effi?cent optimal sensor placementmethod for structure damage detection［J］.Journalof Northwest Polytechnical University，2007，25（4）：503?507.

［5］覃柏英，林賢坤，張令彌，等.基于整數編碼遺傳算法的傳感器優化配置研究［J］.振動與沖擊，2011，30（2）：252?257.QIN Boying，LIN Xiankun，ZHANG Lingmi，et al.Optimal sensor placementbased on integer?coded genetic algorithm［J］.Journal of Vibration and Shock，2011，30（2）：252?257.

［6］林賢坤，覃柏英.微粒算法在傳感器優化配置中的應用［J］.控制工程，2013，20（1）：84?92.LIN Xiankun，QIN Boying.Application of particle swarm optimization to optimal placement［J］.Control Engineering of China，2013，20（1）：84?92.

［7］田莉，陳換過，祝俊，等.基于自適應模擬退火遺傳算法的傳感器優化配置研究［J］.振動工程學報，2012，25（3）：238?243.TIAN Li，CHEN Huanguo，ZHU Jun，et al.A study of opti?mal placementbased on the improved adaptive simulated an?nealing genetic algorithm［J］.Journal of Vibration Engineer?ing，2012，25（3）：238?243.

［8］高亮，劉文君，周馳.用Memetic算法求解有時間約束的TSP問題［J］.華中科技大學學報：自然科學版，2008，36（7）：93?96.GAO Liang，LIUWenjun，ZHOU Chi.Solving of TSP with time restraints by memetic algorithm［J］.Journal of Hua?zhong University of Science and Technology：Natural Sci?ence Edition，2008，36（7）：93?96.

［9］陳杰，陳晨，張娟，等.基于Memetic算法的要地防空優化部署方法［J］.自動化學報，2010，36（2）：242?248.CHEN Jie，CHEN Chen，ZHANG Juan，et al.Deployment optimization for piont air defense based on memetic algo?rithm［J］.Acta Automatic Sinica，2010，36（2）：242?248.

［10］吳雷，魏臻，葛方振.基于Memetic算法的帶時間窗車輛路徑問題研究［J］.計算機應用研究，2012，29（1）：60?62.WU Lei，WEIZhen，GE Fangzhen.Memetic algorithm for vehicle routing problem with time widows［J］.App lication Research of Computers，2012，29（1）：60?62.

［11］GARNE TG，DOHMANN C.Amodal test design strategy for model correlation［C］／／Proceedings 13th Intl Modal Analysis Conference.New York：Union College，1995：927?933.

［12］秦仙蓉，張令彌.一種基于QR分解的逐步累積法傳感器配置［J］.振動、測試與診斷，2001，21（3）：168?173.QIN Xiangrong，ZHANG Lingmi.Successive sensor place?ment formodal paring based?on QR?factorization［J］.Jour?nal of Vibration，Measurement＆Diagnosis，2001，21（3）：168?173.

彭珍瑞，男，1972年生，教授，博士，主要研究方向為智能優化、測控技術。主持國家自然科學基金項目1項、甘肅省自然科學基金2項、隴原青年創新人才扶持計劃項目1項和甘肅省教育廳項目1項，發表學術論文30余篇，獲得實用新型專利2項。

趙宇，女，1990年生，助教，主要研究方向智能優化、檢測技術。發表學術論文3篇。

Optimal sensor p lacement of a bridge based on memetic algorithm

PENG Zhenrui1，ZHAO Yu1，YIN Hong1，PENG Baorui2
（1.School of Mechatronics Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China；2.School of Civil Engineering and Mechanics，Lanzhou University，Lanzhou 730000，China）

In this paper，an optimal sensor placement algorithm based on thememetic algorithm is proposed to solve the problem of optimal sensor placementof a bridge.Firstly the optimal sensor placement is transformed into an op?timization problem.Next，themathematicmodel is established and thememetic algorithm is used to solve the prob?lem.Thememetic algorithm combines global search of the genetic algorithm with local search of the simulated an?nealing algorithm to overcome the premature convergence problem and local best solution in genetic algorithm.This algorithm was applied in the optimal sensor placementof a suspension bridge.The results indicated that thememetic algorithm can be used to solve the problem，showing better optimization performance and faster convergence speed in comparison with the genetic algorithm.

bridge；optimal sensor placement；memetic algorithm；genetic algorithm；simulated annealing algorithm

TP18

A

1673?4785（2014）06?0685?05

彭珍瑞，趙宇，殷紅，等.基于Memetic算法的橋梁傳感器優化布置［J］.智能系統學報，2014，9（6）：685?689.

英文引用格式：PENG Zhenrui，ZHAO Yu，YIN Hong，et al.Optimal sensor placement of a bridge based on memetic algorithm［J］.CAAI Transactions on Intelligent Systems，2014，9（6）：685?689.

10.3969／j.issn.1673?4785.201309018

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673?4785.201309018.htm l

2013?09?06.

日期：2014?11?20.

國家自然科學基金資助項目（61463028）；甘肅省高等學校基本科研業務費資助項目（213054）；甘肅省教育廳科研資助項目（213027）.

彭珍瑞.E?mail：pzrui＠163.com.