基于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.