基于遺傳算法的預(yù)應(yīng)力二次張拉拐點識別研究

劉恒洋，盧 玲，黃賢英

（重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院，重慶400054）

0 引 言

預(yù)應(yīng)力二次張拉過程中產(chǎn)生的拐點數(shù)據(jù)在路橋施工中有著非常重要的作用，這些作用主要包括對預(yù)應(yīng)力器材的質(zhì)量檢測、自然災(zāi)害的動態(tài)檢測以及工程施工質(zhì)量的驗收等［1］。目前預(yù)應(yīng)力二次張拉拐點的識別方法包括手工識別和軟件自動識別，手工識別不僅工作量大效率低（主要集中在根據(jù)測量數(shù)據(jù)繪制曲線過程上），而且拐點結(jié)果的正確與否極大地依賴于工作人員的工作經(jīng)驗［2］。軟件自動識別一般將拐點的識別過程分為數(shù)據(jù)預(yù)處理和拐點計算兩個階段，在數(shù)據(jù)預(yù)處理階段主要是過濾異常數(shù)據(jù)和去除測量過程中由于外界干擾導(dǎo)致的明顯的非線性數(shù)據(jù)；計算拐點階段是拐點識別的關(guān)鍵過程，這個過程中一個比較主流的做法就是比較測量過程中的點跟第一個點組成的直線以及該點跟最后一個點組成的直線之間的斜率差，如果斜率差最大，則說明該點就是拐點。這種做法的缺點是隨著測量曲線的非線性坡度的增大，測量出的拐點位置跟實際拐點位置存在一定的差距。為了解決拐點計算過程中精度不夠的問題，本文將遺傳算法應(yīng)用到預(yù)應(yīng)力二次張拉拐點識別的過程中，以達到提高拐點識別精度的目的。

1 預(yù)應(yīng)力二次張拉的物理結(jié)構(gòu)和數(shù)學(xué)模型

1.1 預(yù)應(yīng)力二次張拉物理結(jié)構(gòu)概述

為了檢測鋼索質(zhì)量，或監(jiān)測工程狀況，在實際工程中，常常將鋼索進行如圖1所示的錨固安裝。

在圖1中，先將鋼索一端固定在A點，在施加指定張力F0使鋼索伸張后在B點通過夾持裝置固定，記AB段鋼索的彈性系數(shù)為k1。同時在B點外預(yù)留指定長度L2的鋼索，以便后續(xù)進行二次張拉。

圖1 錨索固定與張拉

在對C點進行二次張拉時，若施加的張力小于F0時，僅BC段鋼索進行張拉，原始長度記為L2，彈性系數(shù)記為k2。當施加的張力大于F0時，B點處的夾持裝置松動，AB段鋼索與BC段鋼索構(gòu)成整體同時進行張拉，根據(jù)胡克定律的串聯(lián)公式，此時AC段鋼索的彈性系數(shù)為k1k2/（k1＋k2），其張力－伸長量關(guān)系如式（1）所示

圖2 理想二次張拉曲線及拐點

1.2 預(yù)應(yīng)力二次張拉拐點的定義及其數(shù)學(xué)模型

根據(jù)前面的闡述，可以將預(yù)應(yīng)力二次張拉的拐點定義為［3］：在向預(yù)應(yīng)力錨固系統(tǒng)逐漸施加張力過程中，兩段不同彈性系數(shù)張拉曲線之間的交界點。根據(jù)拐點的定義，可將拐點辨識的本質(zhì)描述為：找到兩條直線方程，使得這兩條直線的軌跡在測量范圍內(nèi)與實測數(shù)據(jù)的軌跡誤差最小，則這兩條直線的交點即為拐點。該問題的數(shù)學(xué)描述如下［4－6］：

搜索參數(shù)：k1（直線方程1斜率）、k2（直線方程2斜率）、b1（直線方程1截距）、b2（直線方程2截距）、p（xG，yG）（兩直線預(yù)設(shè)交點坐標，即實測數(shù)據(jù)中的某一點）。

使得實測數(shù)據(jù)：D＝｛d1，…，di，…，dn｝，其中 di＝（fi，si）為實測數(shù)據(jù)點，fi為實測張力值，，si為實測伸長量。

與兩直線方程：y＝k1x＋b1，y＝k2x＋b2的離散采樣數(shù)據(jù)

的絕對誤差最小

則滿足此條件的p（xG，yG）為最優(yōu)拐點，k1，k2為兩段不同張拉過程的彈性系數(shù)。

2 遺傳算法及其在預(yù)應(yīng)力二次張拉拐點的應(yīng)用

2.1 確定拐點中心點

在利用遺傳算法進行拐點的優(yōu)化搜索前，首先需要確定前面所總結(jié)的模型中的5個參數(shù)（k1，k2，b1，b2，p（xG，yG））的可能取值范圍［7］。即根據(jù)數(shù)據(jù)集D的幾何特征，計算出參數(shù)可能取值范圍的中心點idxo（用 下 標idx 來 表 示 拐 點 位 置， 即 p（xG，yG）＝didx（fidx，sidx）），其算法步驟如下［8］：

（2）從數(shù)據(jù)點d1（f1，s1）開始對數(shù)據(jù)集D進行遍歷，記當前數(shù)據(jù)點為di（fi，si）。

（3）計算候選參數(shù)中心點k1，k2，b1，b2，ek

（4） 若e′k＞ek則，ek＝e′k，idxo＝i

（5）若已遍歷完De中所有數(shù)據(jù)，則轉(zhuǎn)第6步，否則轉(zhuǎn)第2步。

2.2 利用遺傳算法搜索最優(yōu)拐點參數(shù)

在3.1節(jié)計算得到了優(yōu)化參數(shù)的可行取值范圍的中心點，現(xiàn)以該中心點進行擴展得到可行區(qū)域如下

式中：α，β∈（0，1），γ ∈ ［1，idxo］——搜索區(qū)域擴展系數(shù)，取值越大則搜索到全局最優(yōu)解的可能性就愈大，但所耗時間就越長，收斂速度也越慢；反之，取值越小則得到全局最優(yōu)解的可能性就越小，但收斂速度會更快，耗時更短。

式（4）中的5個待優(yōu)化參數(shù)：k1，k2，b1，b2，idx分別為遺傳算法中的5個基因（gene），5個參數(shù)以實數(shù)編碼的方式組合構(gòu)成染色體（chromosome），如圖3所示。

圖3 染色體/個體組成

多個染色體構(gòu)成種群（population），如圖4所示。

圖4 種群構(gòu)成

而種群的從父代向子代的逐代進化過程則構(gòu)成了遺傳算法的參數(shù)優(yōu)化過程，如圖5所示。

圖5 種群進化過程

整個遺傳算法的程序流程圖如圖6所示，主要包括交叉、變異、選擇等操作，下面將對程序流程中的各個環(huán)節(jié)逐一闡述。

（1）初始化種群

采用統(tǒng)計學(xué)中的田口正交實驗方法［9］，進行種群的初始化操作，以便保證所有的個體能均勻分布在式（4）所確定的可行解超空間中。本處水平數(shù)為10（levels，即基因的取值范圍被分為幾個等級），因素個數(shù)為5（factors，即基因個數(shù)或參數(shù)個數(shù)），則正交表記為L100（10，5）。種群的初始化算法如式（5）所示

圖6 遺傳算法程序流程

式中：gij——種群中第j個染色體的第i個基因的取值，inf（gi）——第i個基因的取值下界，sup（gi）——第i個基因的取值上界，L100［i］［j］——正交表的第j行i列個元素。

種群大小設(shè)定為100，即初始化生成的染色體個數(shù)為100，以后每次經(jīng)過進化后生成的下一代種群染色體數(shù)也是100。

（2）計算適應(yīng)度

在遺傳算法中采用適應(yīng)度函數(shù)來計算個體（染色體）的適應(yīng)度值，從而評價個體的適應(yīng)性（優(yōu)劣程度），以便模擬 “優(yōu)勝劣汰”的自然進化法則。本處所選取的適應(yīng)度函數(shù)如式（6）所示

（3）交 叉

交＋叉環(huán)節(jié)包含兩個步驟：基于海明距離［10］的配對操作和可變精度的交叉操作。

基于海明距離的配對操作［11］：為避免近親繁殖，在進行交叉操作前，先計算個體之間的海明距離，只有個體間距離大于給定值時才能進行配對。兩個染色體（x＝｛g1x，g2x，g3x，g4x，g5x｝，y＝｛g1y，g2y，g3y，g4y，g5y｝）間 的 海 明距離定義如下

當兩個個體間的海明距離大于等于2時才能進行配對。

可變精度的交叉操作：兩個染色體（x＝｛g1x，g2x，g3x，g4x，g5x｝，y＝｛g1y，g2y，g3y，g4y，g5y｝）的可變精度交叉操作算法如下：

首先隨機生產(chǎn)交叉點位置：i＝rand（1，5），i∈ ［1，5］。

假設(shè)i＝3交叉后的新個體如下

其中：g′3x＝g3x＋μ（g3y－g3x），g′3y＝inf（g3）＋μ（sup（g3）－inf（g3）），μ∈ ｛0.0，0.1，0.2，…，1.0｝為隨機加權(quán)數(shù)，inf（g3）表示基因g3的取值下界，sup（g3）表示基因g3的取值上界。為了避免由于基因的多次選擇而導(dǎo)致算法收斂減速，被多次選擇的基因的精度會逐次增加。

設(shè)定交叉率為0.8，即要進行40次交叉配對，生成80個新的染色體。

（4）變 異

為避免算法早熟收斂，算法中采用了管理學(xué)中的凸集理論—多點變異，即隨機選擇單個染色體的多個基因進行凸組合變異，同時將兩點變異和多點點變異以概率的方式隨機進行，這就極大地增強了變異環(huán)節(jié)的精細調(diào)節(jié)能力，若染色體x＝｛g1x，g2x，g3x，g4x，g5x｝的第2和第4個基因被選擇進行變異，變異生成新的染色體x＇＝｛g1x，g′2x，g3x，g′4x，g5x｝，其中

其中，μ∈ ｛0.0，0.1，0.2，…，1.0｝

（5）選 擇

采用輪盤賭的方式進行選擇［12］，讓適應(yīng)度較低的個體也有被選擇的機會，以維護種群基因的多樣性。待選擇的范圍為父代的100個染色體和交叉操作生成的80個染色體，即從180個染色體中選擇出100個染色體作為下一代種群。其中這180個染色體的最高適應(yīng)度個體被無條件保留進入下一代，即只需要選擇出99個染色體。算法如下：

生成隨機數(shù)：rnd ∈（0.0，1.0），若rnd ≤P［i］則第i個染色體被選中，重復(fù)執(zhí)行該操作直到選中99個染色體。

（6）終止條件

經(jīng)過前面所采用的交叉、變異、選擇操作進行逐代進化，當達到性能指標（即兩直線方程軌跡與實測數(shù)據(jù)吻合度達到指定要求）或進化代數(shù)達到指定值（200代）時退出遺傳算法。

3 算法測試

根據(jù)前面對遺傳算法的應(yīng)用過程，本文采用C＃語言編程實現(xiàn)了基于遺傳算法的拐點識別功能（如圖7所示）。

圖7 拐點識別曲線

圖7（a）中為通過傳統(tǒng)的拐點識別方法（比較測量過程中的點跟第一個點組成的直線以及該點跟最后一個點組成的直線之間的斜率差的方法）識別出來的拐點數(shù)據(jù)圖。圖7（b）中為通過本文中描述的遺傳算法計算得到的拐點圖，圖7（b）的數(shù)據(jù)表明，不論是從拐點數(shù)據(jù)還是擬合出來的直線，都比圖7（a）中的數(shù)據(jù)有所提高。因此，本文描述的將遺傳算法應(yīng)用到預(yù)應(yīng)力二次張拉拐點的識別過程中能夠提升顯著提升拐點識別的精度，提高工程施工質(zhì)量。

4 結(jié)束語

本文通過分析預(yù)應(yīng)力二次張拉的物理結(jié)構(gòu)，建立了預(yù)應(yīng)力二次張拉拐點的數(shù)學(xué)模型；同時通過分析預(yù)應(yīng)力二次張拉拐點的定義，在拐點識別過程中引入了遺傳算法，并分別在遺傳算法的初始化、適應(yīng)度計算、交叉、變異和選擇過程中進行優(yōu)化搜索。通過實驗表明，跟傳統(tǒng)的拐點識別方法相比，通過遺傳算法進行搜索后得到的兩條拐點直線，能夠與原來的測量曲線進行很好的逼近，進而大大提高了這兩條曲線的交點（即拐點）的精度。

［1］SHAO Xudong，LI Xianchao，ZHOU Yadong.Application of twice－prestressed composite structure to high－speed railway bridges ［J］.Journal of Railway Science and Engineering，2006，3（6）：3－5（in Chinese）. ［邵旭東，李顯潮，周亞棟.二次預(yù)應(yīng)力組合結(jié)構(gòu)在高速鐵路橋梁上的應(yīng)用研究 ［J］.鐵道科學(xué)與工程學(xué)報，2006，3（6）：3－5.］

［2］WU Xiaolu，XU Bin.Analyses of second tension steel strand vertical pre－stressed system ［J］.New Technologies and Products，2010，18（16）：90－91（in Chinese）.［吳小陸，許斌.淺析二次張拉鋼絞線豎向預(yù)應(yīng)力錨固系統(tǒng) ［J］.中國新技術(shù)新產(chǎn)品，2010，18（16）：90－91.］

［3］CHEN Yu.The common errors in proof of sufficient conditions of judging inflection point ［J］.College Mathematics，2010，26（4）：187－190（in Chinese）.［陳玉.曲線拐點充分條件證明中的常見錯誤 ［J］.大學(xué)數(shù)學(xué)，2010，26（4）：187－190.］

［4］CAI Z X，WANG Y.A multiobjective optimization－based evolutionary algorithm for constrained optimization ［J］.IEEE Trans on Evolutionary Computation，2006，10（6）：658－675.

［5］WANG Y P，DANG C Y.An evolutionary algorithm for global optimization based on level－set evolution and Latin squares ［J］.IEEE Trans on Evolutionary Computation，2007，11（5）：579－595.

［6］GUO Qingsheng，HUANG Yuanlin，ZHANG Liping.The method of curve bend recognition ［J］.Geomatics and Information Science of Wuhan University，2008，33（6）：596－599（in Chinese）. ［郭慶勝，黃遠林，章莉萍.曲線的彎曲識別方法研究 ［J］.武漢大學(xué)學(xué)報信息科學(xué)版，2008，33（6）：596－599.］

［7］QANG Yanping，YUAN Jie，SU Xiangfang.Corner invariant and its application to pattern recognition ［J］.Journal of Image and Graphics，2006，4A（10）：854－858（in Chinese）.［王延平，袁杰，蘇祥芳.幾種拐點不變量及其在目標識別中的應(yīng)用［J］.中國圖像圖形學(xué)報，2006，4A（10）：854－858.］

［8］XU Jin，KE Yinglin，QU Weiwei.B－spline vurve approximation based on feature points automatic recognition ［J］.Journal of Mechanical Engineering，2009，45（11）：212－216（in Chinese）.［徐進，柯映林，曲嵬崴.基于特征點自動識別的B樣條曲線逼近技術(shù) ［J］.機械工程學(xué)報，2009，45（11）：212－216.］

［9］JIANG Zhongyang，CAI Zixing，WANG Yong，Hybridself－adaptive orthogonal genetic algorithm for solving global optimization problems ［J］.Journal of Software，2010，21（6）：1297－1302（in Chinese）.［江中央，蔡自興，王勇.求解全局優(yōu)化問題的混合自適應(yīng)正交遺傳算法 ［J］.軟件學(xué)報，2010，21（6）：1297－1302.］

［10］TIAN Feng，YAO Aimin，SUN Xiaoping.Dual population genetic algorithm based on individual similarity ［J］.Computer Engineering and Design，2011，32（5）：1789－1791（in Chinese）.［田豐，姚愛民，孫小平等.基于個體相似度的雙種群遺傳算法 ［J］.計算機工程與設(shè)計2011，32（5）：1789－1791.］

［11］ZHANG Lei.The influence of hamming distance parameter on genetic algorithm based on hamming distance ［J］.Journal of Beihua University，2010，11（3）：286－288（in Chinese）.［張雷.海明距離參數(shù)對基于海明距離遺傳算法的影響 ［J］.北華大學(xué)學(xué)報（自然科學(xué)版），2010，11（3）：286－288.］

［12］GU Feng，WU Yong.The improvement of genetic algorithm［J］.Microcomputer Development，2006，13（6）：80－86（in Chinese）.［古峰，吳勇，唐俊.遺傳算法的改進 ［J］.微機發(fā)展，2006，13（6）：80－86.］