基于退火策略混沌遺傳算法的橋梁傳感器優(yōu)化布置研究

黃笑犬 張謝東 鄧雅思 董宇航

(武漢理工大學交通學院1) 武漢 430063) (招商局重慶交通科研設計院有限公司2) 重慶 400067)

0 引 言

橋梁在長期服役中，由于外界環(huán)境因素如環(huán)境腐蝕、車輛載重及交通流量的增加，橋梁結構發(fā)生損傷，可靠度下降，結構功能退化，如果不能夠及時地發(fā)現(xiàn)和修復，將會造成不可預估的后果[1].如何在最小成本投入下合理選取傳感器并優(yōu)化布置使監(jiān)測得到的橋梁狀態(tài)信息最為全面是橋梁結構健康監(jiān)測研究的課題之一.

傳感器優(yōu)化布置屬于一種組合優(yōu)化問題，隨著維數(shù)的增加，其求解難度也成指數(shù)增長.黃民水等[2]在基本遺傳算法的基礎上提出了一種基于二重結構編碼遺傳算法的橋梁傳感器優(yōu)化布置方法；張倍陽等[3]結合遺傳算法和嵌套分區(qū)算法提出了嵌套層迭遺傳算法運用于橋梁傳感器的布置，并校驗了算法的可行性；田莉等[4]提出自適應模擬退火遺傳算法對復合材料加筋板殼結構進行了傳感器數(shù)目和位置優(yōu)化，得到了較理想的結果.

采用啟發(fā)式智能算法，如遺傳算法、模擬退火算法、粒子群算法等來進行傳感器的優(yōu)化布置，目前已成為求解傳感器優(yōu)化布置問題的主要方法.遺傳算法(GA)具有良好的全局搜索能力，可以快速地對解空間的多個解進行評估，但是其局部搜索能力較差，容易產(chǎn)生早熟收斂問題；模擬退火算法(SA)具有較好的局部尋優(yōu)能力，但是全局搜索能力較低.為了充分利用這兩類算法的各自優(yōu)點，本文將遺傳算法和模擬退火算法結合，引入具有遍歷性和隨機性的混沌算子[5](chaos operator)，提出了一種基于退火策略的混沌遺傳算法(chaos genetic algorithm for simulating annealing，CGASA)來解決橋梁傳感器優(yōu)化布置問題，并通過一個橋梁工程實例驗證了該算法的有效性.

1 結合GA和SA的新型組合優(yōu)化算法

GA和SA兩種最優(yōu)化算法均是解決TSP,0-1背包等組合優(yōu)化問題的有效方法[6-7]，但是在解決解域龐大的傳感器優(yōu)化問題上仍然有缺陷，容易出現(xiàn)早熟收斂和全局搜索能力差等問題.文中提出的CGASA算法結合了兩種算法各自的優(yōu)點，將SA算法嵌入到GA算法中，選擇種群中部分優(yōu)良個體進入到SA算法中退火尋優(yōu)，加速種群的進化，提高了GA算法的局部搜索能力，同時也避免了少數(shù)優(yōu)秀個體占據(jù)整個種群，從而防止算法早熟收斂.在交叉、變異算子后引入具有遍歷性和隨機性的混沌算子，使得種群能夠以一定的混沌概率維持種群的多樣性.同時結合自適應機制，對遺傳操作中的交叉概率、變異概率、混沌概率按照種群適應度大小進行自適應調整.在進化后期，種群最終靠近最優(yōu)點位置.

2 CGASA算法在橋梁傳感器優(yōu)化布置上的應用

2.1 傳感器優(yōu)化布置模型

根據(jù)結構動力學知識，理論結構的各階模態(tài)向量之間相互正交.但是在實際結構中不可能將傳感器滿布于橋梁上，即實際測量的自由度遠小于實際結構的自由度數(shù)，實測模態(tài)向量難以保證正交性,因此，在傳感器測點布置上，應盡可能保證測量得到的模態(tài)向量之間具有足夠大的空間交角，使得實測模態(tài)有較好的區(qū)分度，較全面地獲得橋梁的整體動力信息.模態(tài)置信度MAC矩陣是評價模態(tài)向量正交性的一個很好的工具，為

(1)

式中：φi、φj分別為有限元模態(tài)矩陣Φn×l第i階和第j階模態(tài)向量；n為有限元模型節(jié)點自由度即傳感器預布置點的自由度；MACi,j為MAC矩陣中第i行第j列的元素.從n個自由度中選擇m個自由度作為傳感器的布置點，使得模態(tài)置信度MAC矩陣的非對角元最大值盡可能地小，以此建立目標函數(shù)，即：

(2)

當MAC矩陣的非對角元MACi,j等于0，則表明第i階模態(tài)和第j階模態(tài)振型可分辨，在實際橋梁健康監(jiān)測傳感器布置過程中，MACi,j非對角元值越小，可使模態(tài)具有較好的正交性，能夠較為準確地反映橋梁的動力信息.橋梁的傳感器優(yōu)化布置問題是一種典型的NP組合優(yōu)化問題，要求最小成本投入下合理選取傳感器并合理布置使得監(jiān)測得到的信息能夠反映橋梁的健康狀況，作為后續(xù)損傷修復和安全評估的依據(jù).

2.2 編碼方式的選擇

橋梁傳感器布置問題可以轉換為一個0-1規(guī)劃問題，0為該測點不布置傳感器，1為該測點布置傳感器，則傳感器布置的解向量可表示為[w1,w2,…,wr,…,wn]，其中wr=0或1.考慮二進制編碼在交叉和變異操作中難以滿足傳感器數(shù)目固定的約束條件，這里采用十進制的編碼的方式.首先確定一個編碼映射表見表1，假定預布置測點數(shù)目為n，傳感器數(shù)量為m,位置編號按照1～n的順序排列，然后隨機生成一組含有m個1，n～m個0的序列，此時1～n的序列分別和相應的0-1對應，構成整個算法的傳感器布置位置和解向量的映射表，映射表在整個算法中固定不變.所以一條染色體可以表示為整數(shù)1～n之間的隨機序列，在MATLAB程序中使用randperm(n)函數(shù)可以方便地產(chǎn)生整數(shù)1～n的隨機序列.

表1 編碼映射表

2.3 適應度函數(shù)

遺傳算法中以適應度函數(shù)進行種群的優(yōu)劣評估，一般是求最大值問題.本文優(yōu)化的目標函數(shù)是使得MAC矩陣非對角元最大值最小化，因此,將最小化函數(shù)轉為適應度最大化函數(shù)，由于MAC矩陣最大元素為1，最小元素為0，所以選擇fitness=1-max{MACi,j}作為適應度函數(shù).

2.4 選擇和最佳保留策略

選擇算子是根據(jù)每個個體適應度的大小對群體中的個體進行優(yōu)勝劣汰操作，適應度大的個體被選擇到下一代的機會越大.輪盤賭法選擇后種群的平均適應度波動比較大，文中計算采用了隨機聯(lián)賽選擇策略.為了不丟失最優(yōu)解，在選擇過程實施最優(yōu)保存策略.

2.5 遺傳算子

2.5.1交叉算子

由于算法采用十進制編碼，這里采用部分匹配交叉(PMX)操作，PMX操作是首先在父代隨機選擇兩個交叉點，根據(jù)兩個父個體在兩個交叉點中間段給出的映射關系生成兩個子代個體.例如對下面的父個體隨機選擇兩個交叉點“|”.

P1123456789P2435612978

首先對兩個父個體的中間段進行交換，然后保留中間段未選中的編碼8和3，如下.

P1'xx361298xP2'x3x4567x8

中間段的映射關系為4?6，5?1，6?2，7?9.根據(jù)映射關系，得到如下兩個子代個體.

P1*563612987P2*631456798

2.5.2變異算子

對于十進制編碼，首先在染色體上隨機選擇兩個變異點，變異方式為逆位變異為

P123456789P'127654389

2.5.3混沌算子

混沌是指發(fā)生在確定性系統(tǒng)中的一種非周期性的循環(huán)行為，混沌能夠不重復地經(jīng)歷一定范圍內(nèi)的所有狀態(tài)，具有極大的遍歷性.

利用混沌的隨機性和遍歷性構造混沌算子，將GA算法中交叉變異后種群中適應度最差的個體通過混沌擾動使其均勻分布在解空間，并同時進入SA算法中參與搜索，該算子防止了傳統(tǒng)遺傳算子由于隨機特性而出現(xiàn)群體聚集問題，增強了GA算法的全局搜索特性.混沌算子采用Logistic混沌序列產(chǎn)生具有一定遍歷性的解，其表達式為

(3)

(4)

2.6 自適應調整機制

采用自適應的參數(shù)選擇來提升算法的收斂性能，pc和pm隨著種群適應度的大小來自適應調整，防止算法出現(xiàn)過早收斂，ph隨著遺傳代數(shù)來自適應調整，使得尋優(yōu)過程在初期進行大范圍混沌搜索，隨著最優(yōu)解的逐步逼近，降低混沌概率.其自適應調整表達式為

(5)

(6)

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

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

(7)

式中：pcmax為最大交叉概率；pcmin為最小交叉概率；pmmax為最大變異概率；pmmin為最小變異概率；favg為種群平均適應度；fmax為種群最大適應度；f′為兩個待交叉?zhèn)€體的較大適應度；f為待變異個體適應度；ph(k)為第k代的混沌概率；p0為初始混沌概率；λ為衰減系數(shù).

2.7 退火策略

2.7.1鄰解產(chǎn)生方法的改進

SA算法基于鄰域搜索，傳統(tǒng)的SA算法是隨機產(chǎn)生一次擾動解，但是對于具有龐大自由度的傳感器優(yōu)化問題，一次擾動產(chǎn)生的解隨機性比較強，本文將“一次擾動”轉換為“n次擾動”，分別計算“n次擾動”對應解的目標函數(shù)值，選擇其中的最優(yōu)值作為鄰域的新解.

2.7.2鄰解接受準則

依據(jù)Metropolis準則，以擾動得到的新解和當前解的目標函數(shù)差Δ定義接受新解的概率 ，即

(8)

2.7.3冷卻進度表

1) 控制參數(shù)T的初值T0為使算法一開始就達到準平衡，初始狀態(tài)的接受概率接近于1，即p=exp(-Δ/T)≈1,計算得到T0很大，但也不能過大，需根據(jù)實際問題來確定，文中設置的初始溫度值為T0=1 000.

2) 控制參數(shù)T的衰減函數(shù) 利用T的衰減函數(shù)來控制SA算法的迭代循環(huán)次數(shù)是算法尋優(yōu)的關鍵.本文選用最常用的溫度衰減函數(shù)：

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

(9)

式中：α為一個常數(shù)，一般取值為0.8～0.99，其取值決定了整體降溫的過程，文中選取α=0.95.

3) Markov鏈長度Lk的確 Markov鏈長度是在每一個控制參數(shù)T下的內(nèi)循環(huán)迭代次數(shù)，確保系統(tǒng)每降到一個溫度，在一個Markov鏈長度內(nèi)達到平衡狀態(tài).一般使用Lk=λn，n為自變量的維數(shù)，λ為常數(shù)，通過試算，本文選取λ=50.

2.8 CGASA算法的運算步驟

在CGASA算法求解橋梁傳感器優(yōu)化布置問題中，通過建立橋梁的有限元模型并提取的模態(tài)振型矩陣Φn×l作為傳感器優(yōu)化的初始數(shù)據(jù)，n為有限元模型中節(jié)點數(shù)量，即預布置傳感器自由度，l為模態(tài)的階數(shù)，現(xiàn)從n個自由度中選擇m個自由度進行布置傳感器，按照式(2)給出的目標函數(shù)，使得MAC矩陣非對角元最大值最小時的對應點位置即為最終的傳感器布置點位.具體的優(yōu)化步驟如下.

步驟2設置GA算法最大迭代次數(shù)為max_generation，交叉概率pc，變異概率pm，混沌概率ph，混沌序列方程；SA算法的擾動新解產(chǎn)生數(shù)量new_n，冷卻進度表參數(shù)包括初始溫度T0，衰減函數(shù)，終值Tf，Markov鏈長度Lk.

步驟4j=0，對遺傳得到新的種群進行適應度大小排序，篩選部分優(yōu)秀個體進入SA算法局部尋優(yōu)；j=j+1，根據(jù)溫度衰減函數(shù)計算第j步溫度Tj.

步驟5l=0,在Tj溫度下對原解進行多次擾動取最優(yōu)解作為新解，并以Metropolis準則接受新解；l=l+1，在Markov鏈長度Lk內(nèi)進行循環(huán)迭代.最后對SA算法得到的新解和原種群解進行排序，選擇前N個個體進行下一代種群.

步驟6若l≤Lk，轉步驟5，否則轉下一步.

步驟7若Tj

步驟8若k≤max_generation，轉步驟3，否則退出整個循環(huán)，記錄每一代的種群平均適應度和最優(yōu)適應度值，得到最終的優(yōu)化結果.對最優(yōu)個體進行解碼得到傳感器的最終的布置位置.

3 橋梁傳感器優(yōu)化配置實例

3.1 實際工程算例

以烏海黃河大跨矮塔斜拉橋實際工程為例進行傳感器優(yōu)化布置，跨度為(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個節(jié)點，397個單元.主梁采用了梁單元進行模擬，共設256節(jié)點.通過模態(tài)分析得到前10階和前20階模態(tài)振型，構造模態(tài)振型矩陣.由于主梁主要以豎向振動為主，因此提取模態(tài)時選擇豎直Z方向的模態(tài)數(shù)據(jù).主梁預布置自由度數(shù)為n=256，加速度傳感器數(shù)目m=40.為了驗證文中提出的CGASA算法的優(yōu)化性能，這里與傳統(tǒng)GA算法的橋梁傳感器優(yōu)化布置方法進行比較.本文根據(jù)算法基本步驟，利用MATLAB R2013b進行編程對問題進行求解.

圖1 橋梁有限元模型圖

3.2 GA算法參數(shù)選擇

在基本的GA算法中，通過多次實驗試算進行參數(shù)調整，選擇算子采用隨機聯(lián)賽策略和最佳保留策略，種群的規(guī)模為100，染色體長度即基因的個數(shù)為256，交叉概率為0.7，變異概率為0.06，種群遺傳代數(shù)為5 000代.

3.3 CGASA算法參數(shù)選擇

在文中CGASA算法中，通過多次實驗試算進行參數(shù)調整，選擇算子采用隨機聯(lián)賽策略和最佳保留策略，種群規(guī)模為100，色體長度即基因的個數(shù)為256，由于算法采用自適應調整機制，最大交叉概率為0.9，最小交叉概率為0.3，最大變異概率為0.2，最小變異概率取0.01，初始混沌概率為0.6，冷卻進度表參數(shù)包括溫度初始值為1 000，溫度衰減系數(shù)0.95，Markov鏈長度為30，種群遺傳代數(shù)為300代.

3.4 優(yōu)化布置

為了評測CGASA算法對橋梁傳感器優(yōu)化布置的優(yōu)越性，分別選擇前10階模態(tài)振型和前20階模態(tài)振型與GA算法進行對比分析.

1) 10階模態(tài)振型 經(jīng)過多次算法運算，CGASA算法和GA算法的適應度進化曲線見圖2～3.

圖2 GA適應度進化過程曲線

由圖2a)可知，出現(xiàn)多次局部收斂，并沒有收斂于同一個解，說明對于具有龐大解域的傳感器優(yōu)化布置問題，通過一般尋優(yōu)算法很難得到全局最優(yōu)解；由圖2b)可知，遺傳代數(shù)不斷增大，但是依舊沒有突破最優(yōu)解的極限，而是收斂于同一個次優(yōu)解，MAC矩陣非對角元最大值為0.169 3.種群進化的平均適應度值隨遺傳代數(shù)波動很小，說明選擇得到的次優(yōu)個體占據(jù)了整個種群，導致了種群進化停滯不前，收斂于同一個次優(yōu)解.

圖3 CGASA適應度進化過程曲線

由圖4a)可知，在進化初期快速地向最優(yōu)解靠近，收斂速度較快，說明算法在局部尋優(yōu)過程達到了較為理想的結果；由圖4b)可知，在150代內(nèi)出現(xiàn)短暫的局部收斂現(xiàn)象，但很快跳出了局部最優(yōu)位置，在第300代基本達到收斂，MAC矩陣非對角元最大值為0.136 9，優(yōu)化結果較GA算法有了很大的提升，種群的平均適應度趨向于最優(yōu)的方向進化.

2) 20階模態(tài)振型 經(jīng)過多次算法運算，CGASA算法和GA算法的適應度進化曲線見圖4.由圖4a)可知，GA算法迭代1 000代基本達到收斂，但是很明顯看出運算過程至少在三個階段出現(xiàn)了過早收斂于局部最優(yōu)解現(xiàn)象，MAC矩陣非對角元最大值為0.183 6；由圖4b)可知，CGASA算法在300代基本達到收斂，收斂速度極快.并且完全避免了過早收斂和早熟現(xiàn)象，MAC矩陣非對角元最大值為0.176 7，相比較傳統(tǒng)GA算法的優(yōu)化效果有了較大的提升，最優(yōu)解的收斂效率得到了極大的改善.

圖4 GA和CGASA適應度進化過程曲線

由于算法中增加了混沌遍歷、局部多次擾動和自適應概率機制，使其在任何一代遺傳過程均可能產(chǎn)生全局范圍解，防止算法陷入局部最優(yōu)解而停止進化.算法的平均適應度進化曲線呈現(xiàn)平穩(wěn)波動變化趨勢，可以看出對于自由度數(shù)目龐大的傳感器優(yōu)化問題求解已經(jīng)十分復雜.正是由于自適應調整機制、混沌遍歷、局部多次擾動搜索的優(yōu)點，使得CGASA算法無論在全局收斂性和局部收斂性上均優(yōu)于傳統(tǒng)的GA算法.橋梁傳感器優(yōu)化布置點位見圖5.

圖5 傳感器優(yōu)化布置點位圖

圖6為兩種算法各運行10次后的結果變化曲線圖，由圖6可知，CGASA任何一次的運行結果均比GA更優(yōu)，由于算法運行計算的本身具有一定的隨機性，可以通過多次計算取得較優(yōu)的值.表2為前10階模態(tài)與前20階模態(tài)下的10次優(yōu)化指標結果對比，根據(jù)得到的均值、標準差、收斂代數(shù)和最優(yōu)結果四個指標可以看出CGASA算法不僅在收斂速度和解的穩(wěn)健性上有了顯著的提升，而且在一定程度上改善了解的質量.

綜上所述，CGASA算法具有優(yōu)良的全局尋優(yōu)特性、快速的收斂特性和較高的穩(wěn)健性，以及能夠避免傳統(tǒng)GA算法陷入局部最優(yōu)和過早收斂的現(xiàn)象，接近全局最優(yōu)解的概率較大，并且適用于預布置自由度數(shù)目較大的橋梁傳感器布置問題，可以較好的實現(xiàn)大跨度橋梁的傳感器優(yōu)化布置.由于算法對模態(tài)數(shù)據(jù)量大小有著較大的敏感性，隨著模態(tài)階數(shù)或者自由度數(shù)量的增加，此時算法全局搜索能力相應減弱；反之，該算法對中小跨徑橋梁傳感器優(yōu)化布置問題能夠快速地得到較為準確的最優(yōu)解.

圖6 算法優(yōu)化結果變化曲線

表2 算法優(yōu)化指標結果

4 結 束 語

根據(jù)大跨度橋梁傳感器優(yōu)化布置問題的特點，提出了一種基于退火策略的混沌遺傳算法.在傳統(tǒng)算法的基礎上，通過混沌算子對適應度最差的部分個體進行混沌擾動避免種群聚集現(xiàn)象，提高了算法的全局搜索能力，在退火策略中采用局部多次擾動尋優(yōu)方法增強了算法的局部收斂特性.

將基于退火策略的混沌遺傳遺傳算法用于一座斜拉橋的傳感器優(yōu)化布置當中，并將該算法與傳統(tǒng)的遺傳算法進行比較，驗證了改進算法的優(yōu)越性.數(shù)值結果表明該算法很大程度上克服了傳統(tǒng)遺傳算法的早熟收斂問題，在解的質量上也有很大的改善，并且具有較好的全局尋優(yōu)特性、快速的收斂特性和較高的穩(wěn)健性，能夠較好地解決橋梁傳感器優(yōu)化布置問題.改進過后的算法收斂性仍然較為復雜，運行時間也相對較長，理論體系尚不完善，并且隨著模態(tài)階數(shù)的增加，算法運算量急劇增大，此時全局搜索能力也會相對減弱，對算法性能的評價只能依賴于對比實驗，對計算結果的精確性和收斂效率等問題仍然需要進一步研究.