基于退火策略混沌遗传算法的桥梁传感器优化布置研究

黄笑犬 张谢东 邓雅思 董宇航

(武汉理工大学交通学院1) 武汉 430063) (招商局重庆交通科研设计院有限公司2) 重庆 400067)

0 引 言

桥梁在长期服役中，由于外界环境因素如环境腐蚀、车辆载重及交通流量的增加，桥梁结构发生损伤，可靠度下降，结构功能退化，如果不能够及时地发现和修复，将会造成不可预估的后果[1].如何在最小成本投入下合理选取传感器并优化布置使监测得到的桥梁状态信息最为全面是桥梁结构健康监测研究的课题之一.

传感器优化布置属于一种组合优化问题，随着维数的增加，其求解难度也成指数增长.黄民水等[2]在基本遗传算法的基础上提出了一种基于二重结构编码遗传算法的桥梁传感器优化布置方法；张倍阳等[3]结合遗传算法和嵌套分区算法提出了嵌套层迭遗传算法运用于桥梁传感器的布置，并校验了算法的可行性；田莉等[4]提出自适应模拟退火遗传算法对复合材料加筋板壳结构进行了传感器数目和位置优化，得到了较理想的结果.

采用启发式智能算法，如遗传算法、模拟退火算法、粒子群算法等来进行传感器的优化布置，目前已成为求解传感器优化布置问题的主要方法.遗传算法(GA)具有良好的全局搜索能力，可以快速地对解空间的多个解进行评估，但是其局部搜索能力较差，容易产生早熟收敛问题；模拟退火算法(SA)具有较好的局部寻优能力，但是全局搜索能力较低.为了充分利用这两类算法的各自优点，本文将遗传算法和模拟退火算法结合，引入具有遍历性和随机性的混沌算子[5](chaos operator)，提出了一种基于退火策略的混沌遗传算法(chaos genetic algorithm for simulating annealing，CGASA)来解决桥梁传感器优化布置问题，并通过一个桥梁工程实例验证了该算法的有效性.

1 结合GA和SA的新型组合优化算法

GA和SA两种最优化算法均是解决TSP,0-1背包等组合优化问题的有效方法[6-7]，但是在解决解域庞大的传感器优化问题上仍然有缺陷，容易出现早熟收敛和全局搜索能力差等问题.文中提出的CGASA算法结合了两种算法各自的优点，将SA算法嵌入到GA算法中，选择种群中部分优良个体进入到SA算法中退火寻优，加速种群的进化，提高了GA算法的局部搜索能力，同时也避免了少数优秀个体占据整个种群，从而防止算法早熟收敛.在交叉、变异算子后引入具有遍历性和随机性的混沌算子，使得种群能够以一定的混沌概率维持种群的多样性.同时结合自适应机制，对遗传操作中的交叉概率、变异概率、混沌概率按照种群适应度大小进行自适应调整.在进化后期，种群最终靠近最优点位置.

2 CGASA算法在桥梁传感器优化布置上的应用

2.1 传感器优化布置模型

根据结构动力学知识，理论结构的各阶模态向量之间相互正交.但是在实际结构中不可能将传感器满布于桥梁上，即实际测量的自由度远小于实际结构的自由度数，实测模态向量难以保证正交性,因此，在传感器测点布置上，应尽可能保证测量得到的模态向量之间具有足够大的空间交角，使得实测模态有较好的区分度，较全面地获得桥梁的整体动力信息.模态置信度MAC矩阵是评价模态向量正交性的一个很好的工具，为

(1)

式中：φi、φj分别为有限元模态矩阵Φn×l第i阶和第j阶模态向量；n为有限元模型节点自由度即传感器预布置点的自由度；MACi,j为MAC矩阵中第i行第j列的元素.从n个自由度中选择m个自由度作为传感器的布置点，使得模态置信度MAC矩阵的非对角元最大值尽可能地小，以此建立目标函数，即：

(2)

当MAC矩阵的非对角元MACi,j等于0，则表明第i阶模态和第j阶模态振型可分辨，在实际桥梁健康监测传感器布置过程中，MACi,j非对角元值越小，可使模态具有较好的正交性，能够较为准确地反映桥梁的动力信息.桥梁的传感器优化布置问题是一种典型的NP组合优化问题，要求最小成本投入下合理选取传感器并合理布置使得监测得到的信息能够反映桥梁的健康状况，作为后续损伤修复和安全评估的依据.

2.2 编码方式的选择

桥梁传感器布置问题可以转换为一个0-1规划问题，0为该测点不布置传感器，1为该测点布置传感器，则传感器布置的解向量可表示为[w1,w2,…,wr,…,wn]，其中wr=0或1.考虑二进制编码在交叉和变异操作中难以满足传感器数目固定的约束条件，这里采用十进制的编码的方式.首先确定一个编码映射表见表1，假定预布置测点数目为n，传感器数量为m,位置编号按照1～n的顺序排列，然后随机生成一组含有m个1，n～m个0的序列，此时1～n的序列分别和相应的0-1对应，构成整个算法的传感器布置位置和解向量的映射表，映射表在整个算法中固定不变.所以一条染色体可以表示为整数1～n之间的随机序列，在MATLAB程序中使用randperm(n)函数可以方便地产生整数1～n的随机序列.

表1 编码映射表

2.3 适应度函数

遗传算法中以适应度函数进行种群的优劣评估，一般是求最大值问题.本文优化的目标函数是使得MAC矩阵非对角元最大值最小化，因此,将最小化函数转为适应度最大化函数，由于MAC矩阵最大元素为1，最小元素为0，所以选择fitness=1-max{MACi,j}作为适应度函数.

2.4 选择和最佳保留策略

选择算子是根据每个个体适应度的大小对群体中的个体进行优胜劣汰操作，适应度大的个体被选择到下一代的机会越大.轮盘赌法选择后种群的平均适应度波动比较大，文中计算采用了随机联赛选择策略.为了不丢失最优解，在选择过程实施最优保存策略.

2.5 遗传算子

2.5.1交叉算子

由于算法采用十进制编码，这里采用部分匹配交叉(PMX)操作，PMX操作是首先在父代随机选择两个交叉点，根据两个父个体在两个交叉点中间段给出的映射关系生成两个子代个体.例如对下面的父个体随机选择两个交叉点“|”.

P1123456789P2435612978

首先对两个父个体的中间段进行交换，然后保留中间段未选中的编码8和3，如下.

P1'xx361298xP2'x3x4567x8

中间段的映射关系为4↔6，5↔1，6↔2，7↔9.根据映射关系，得到如下两个子代个体.

P1*563612987P2*631456798

2.5.2变异算子

对于十进制编码，首先在染色体上随机选择两个变异点，变异方式为逆位变异为

P123456789P'127654389

2.5.3混沌算子

混沌是指发生在确定性系统中的一种非周期性的循环行为，混沌能够不重复地经历一定范围内的所有状态，具有极大的遍历性.

利用混沌的随机性和遍历性构造混沌算子，将GA算法中交叉变异后种群中适应度最差的个体通过混沌扰动使其均匀分布在解空间，并同时进入SA算法中参与搜索，该算子防止了传统遗传算子由于随机特性而出现群体聚集问题，增强了GA算法的全局搜索特性.混沌算子采用Logistic混沌序列产生具有一定遍历性的解，其表达式为

(3)

(4)

2.6 自适应调整机制

采用自适应的参数选择来提升算法的收敛性能，pc和pm随着种群适应度的大小来自适应调整，防止算法出现过早收敛，ph随着遗传代数来自适应调整，使得寻优过程在初期进行大范围混沌搜索，随着最优解的逐步逼近，降低混沌概率.其自适应调整表达式为

(5)

(6)

ph(k)=p0exp[λ(1-k)]

(λ>0，k=0,1,2,…,n)

(7)

式中：pcmax为最大交叉概率；pcmin为最小交叉概率；pmmax为最大变异概率；pmmin为最小变异概率；favg为种群平均适应度；fmax为种群最大适应度；f′为两个待交叉个体的较大适应度；f为待变异个体适应度；ph(k)为第k代的混沌概率；p0为初始混沌概率；λ为衰减系数.

2.7 退火策略

2.7.1邻解产生方法的改进

SA算法基于邻域搜索，传统的SA算法是随机产生一次扰动解，但是对于具有庞大自由度的传感器优化问题，一次扰动产生的解随机性比较强，本文将“一次扰动”转换为“n次扰动”，分别计算“n次扰动”对应解的目标函数值，选择其中的最优值作为邻域的新解.

2.7.2邻解接受准则

依据Metropolis准则，以扰动得到的新解和当前解的目标函数差Δ定义接受新解的概率 ，即

(8)

2.7.3冷却进度表

1) 控制参数T的初值T0为使算法一开始就达到准平衡，初始状态的接受概率接近于1，即p=exp(-Δ/T)≈1,计算得到T0很大，但也不能过大，需根据实际问题来确定，文中设置的初始温度值为T0=1 000.

2) 控制参数T的衰减函数 利用T的衰减函数来控制SA算法的迭代循环次数是算法寻优的关键.本文选用最常用的温度衰减函数：

Tk+1=αTk，k=0,1,2,…

(9)

式中：α为一个常数，一般取值为0.8～0.99，其取值决定了整体降温的过程，文中选取α=0.95.

3) Markov链长度Lk的确 Markov链长度是在每一个控制参数T下的内循环迭代次数，确保系统每降到一个温度，在一个Markov链长度内达到平衡状态.一般使用Lk=λn，n为自变量的维数，λ为常数，通过试算，本文选取λ=50.

2.8 CGASA算法的运算步骤

在CGASA算法求解桥梁传感器优化布置问题中，通过建立桥梁的有限元模型并提取的模态振型矩阵Φn×l作为传感器优化的初始数据，n为有限元模型中节点数量，即预布置传感器自由度，l为模态的阶数，现从n个自由度中选择m个自由度进行布置传感器，按照式(2)给出的目标函数，使得MAC矩阵非对角元最大值最小时的对应点位置即为最终的传感器布置点位.具体的优化步骤如下.

步骤2设置GA算法最大迭代次数为max_generation，交叉概率pc，变异概率pm，混沌概率ph，混沌序列方程；SA算法的扰动新解产生数量new_n，冷却进度表参数包括初始温度T0，衰减函数，终值Tf，Markov链长度Lk.

步骤4j=0，对遗传得到新的种群进行适应度大小排序，筛选部分优秀个体进入SA算法局部寻优；j=j+1，根据温度衰减函数计算第j步温度Tj.

步骤5l=0,在Tj温度下对原解进行多次扰动取最优解作为新解，并以Metropolis准则接受新解；l=l+1，在Markov链长度Lk内进行循环迭代.最后对SA算法得到的新解和原种群解进行排序，选择前N个个体进行下一代种群.

步骤6若l≤Lk，转步骤5，否则转下一步.

步骤7若Tj

步骤8若k≤max_generation，转步骤3，否则退出整个循环，记录每一代的种群平均适应度和最优适应度值，得到最终的优化结果.对最优个体进行解码得到传感器的最终的布置位置.

3 桥梁传感器优化配置实例

3.1 实际工程算例

以乌海黄河大跨矮塔斜拉桥实际工程为例进行传感器优化布置，跨度为(120 m +220 m +120 m)，标准桥面宽33.5 m，梁高为4.0～8.5 m，主梁为单箱三室截面.主梁为C55混凝土材料，弹性模量E为3.55×107kN/m2，泊松比为0.2，容重为26 kN/m3.

采用MIDAS/CIVIL建立桥梁有限元模型，见图1，模型共设446个节点，397个单元.主梁采用了梁单元进行模拟，共设256节点.通过模态分析得到前10阶和前20阶模态振型，构造模态振型矩阵.由于主梁主要以竖向振动为主，因此提取模态时选择竖直Z方向的模态数据.主梁预布置自由度数为n=256，加速度传感器数目m=40.为了验证文中提出的CGASA算法的优化性能，这里与传统GA算法的桥梁传感器优化布置方法进行比较.本文根据算法基本步骤，利用MATLAB R2013b进行编程对问题进行求解.

图1 桥梁有限元模型图

3.2 GA算法参数选择

在基本的GA算法中，通过多次实验试算进行参数调整，选择算子采用随机联赛策略和最佳保留策略，种群的规模为100，染色体长度即基因的个数为256，交叉概率为0.7，变异概率为0.06，种群遗传代数为5 000代.

3.3 CGASA算法参数选择

在文中CGASA算法中，通过多次实验试算进行参数调整，选择算子采用随机联赛策略和最佳保留策略，种群规模为100，色体长度即基因的个数为256，由于算法采用自适应调整机制，最大交叉概率为0.9，最小交叉概率为0.3，最大变异概率为0.2，最小变异概率取0.01，初始混沌概率为0.6，冷却进度表参数包括温度初始值为1 000，温度衰减系数0.95，Markov链长度为30，种群遗传代数为300代.

3.4 优化布置

为了评测CGASA算法对桥梁传感器优化布置的优越性，分别选择前10阶模态振型和前20阶模态振型与GA算法进行对比分析.

1) 10阶模态振型 经过多次算法运算，CGASA算法和GA算法的适应度进化曲线见图2～3.

图2 GA适应度进化过程曲线

由图2a)可知，出现多次局部收敛，并没有收敛于同一个解，说明对于具有庞大解域的传感器优化布置问题，通过一般寻优算法很难得到全局最优解；由图2b)可知，遗传代数不断增大，但是依旧没有突破最优解的极限，而是收敛于同一个次优解，MAC矩阵非对角元最大值为0.169 3.种群进化的平均适应度值随遗传代数波动很小，说明选择得到的次优个体占据了整个种群，导致了种群进化停滞不前，收敛于同一个次优解.

图3 CGASA适应度进化过程曲线

由图4a)可知，在进化初期快速地向最优解靠近，收敛速度较快，说明算法在局部寻优过程达到了较为理想的结果；由图4b)可知，在150代内出现短暂的局部收敛现象，但很快跳出了局部最优位置，在第300代基本达到收敛，MAC矩阵非对角元最大值为0.136 9，优化结果较GA算法有了很大的提升，种群的平均适应度趋向于最优的方向进化.

2) 20阶模态振型 经过多次算法运算，CGASA算法和GA算法的适应度进化曲线见图4.由图4a)可知，GA算法迭代1 000代基本达到收敛，但是很明显看出运算过程至少在三个阶段出现了过早收敛于局部最优解现象，MAC矩阵非对角元最大值为0.183 6；由图4b)可知，CGASA算法在300代基本达到收敛，收敛速度极快.并且完全避免了过早收敛和早熟现象，MAC矩阵非对角元最大值为0.176 7，相比较传统GA算法的优化效果有了较大的提升，最优解的收敛效率得到了极大的改善.

图4 GA和CGASA适应度进化过程曲线

由于算法中增加了混沌遍历、局部多次扰动和自适应概率机制，使其在任何一代遗传过程均可能产生全局范围解，防止算法陷入局部最优解而停止进化.算法的平均适应度进化曲线呈现平稳波动变化趋势，可以看出对于自由度数目庞大的传感器优化问题求解已经十分复杂.正是由于自适应调整机制、混沌遍历、局部多次扰动搜索的优点，使得CGASA算法无论在全局收敛性和局部收敛性上均优于传统的GA算法.桥梁传感器优化布置点位见图5.

图5 传感器优化布置点位图

图6为两种算法各运行10次后的结果变化曲线图，由图6可知，CGASA任何一次的运行结果均比GA更优，由于算法运行计算的本身具有一定的随机性，可以通过多次计算取得较优的值.表2为前10阶模态与前20阶模态下的10次优化指标结果对比，根据得到的均值、标准差、收敛代数和最优结果四个指标可以看出CGASA算法不仅在收敛速度和解的稳健性上有了显著的提升，而且在一定程度上改善了解的质量.

综上所述，CGASA算法具有优良的全局寻优特性、快速的收敛特性和较高的稳健性，以及能够避免传统GA算法陷入局部最优和过早收敛的现象，接近全局最优解的概率较大，并且适用于预布置自由度数目较大的桥梁传感器布置问题，可以较好的实现大跨度桥梁的传感器优化布置.由于算法对模态数据量大小有着较大的敏感性，随着模态阶数或者自由度数量的增加，此时算法全局搜索能力相应减弱；反之，该算法对中小跨径桥梁传感器优化布置问题能够快速地得到较为准确的最优解.

图6 算法优化结果变化曲线

表2 算法优化指标结果

4 结 束 语

根据大跨度桥梁传感器优化布置问题的特点，提出了一种基于退火策略的混沌遗传算法.在传统算法的基础上，通过混沌算子对适应度最差的部分个体进行混沌扰动避免种群聚集现象，提高了算法的全局搜索能力，在退火策略中采用局部多次扰动寻优方法增强了算法的局部收敛特性.

将基于退火策略的混沌遗传遗传算法用于一座斜拉桥的传感器优化布置当中，并将该算法与传统的遗传算法进行比较，验证了改进算法的优越性.数值结果表明该算法很大程度上克服了传统遗传算法的早熟收敛问题，在解的质量上也有很大的改善，并且具有较好的全局寻优特性、快速的收敛特性和较高的稳健性，能够较好地解决桥梁传感器优化布置问题.改进过后的算法收敛性仍然较为复杂，运行时间也相对较长，理论体系尚不完善，并且随着模态阶数的增加，算法运算量急剧增大，此时全局搜索能力也会相对减弱，对算法性能的评价只能依赖于对比实验，对计算结果的精确性和收敛效率等问题仍然需要进一步研究.