基于模擬退火-粒子群算法的wMPS布局優(yōu)化

岳翀，熊芝,1b，薛彬

(1.湖北工業(yè)大學(xué)a.機(jī)械工程學(xué)院；b.現(xiàn)代制造質(zhì)量工程重點(diǎn)實(shí)驗(yàn)室，武漢430068；2.天津大學(xué)海洋科學(xué)與技術(shù)學(xué)院，天津300072)

基于模擬退火-粒子群算法的wMPS布局優(yōu)化

岳翀1a，熊芝1a,1b，薛彬2

(1.湖北工業(yè)大學(xué)a.機(jī)械工程學(xué)院；b.現(xiàn)代制造質(zhì)量工程重點(diǎn)實(shí)驗(yàn)室，武漢430068；2.天津大學(xué)海洋科學(xué)與技術(shù)學(xué)院，天津300072)

空間測(cè)量定位系統(tǒng)是一種在多測(cè)站協(xié)同作用下實(shí)現(xiàn)坐標(biāo)測(cè)量的大尺寸測(cè)量系統(tǒng)，因此測(cè)站布局優(yōu)化成為了重要研究問題。為解決此問題，本文提出了一種基于模擬退火粒子群算法的測(cè)站優(yōu)化部署方案，以定位精度，覆蓋度，使用成本作為優(yōu)化函數(shù)，運(yùn)用粒子群算法及模擬退火算法進(jìn)行協(xié)同搜索，并建立模擬退火粒子群算法的測(cè)站布局優(yōu)化流程，對(duì)兩到四個(gè)測(cè)站進(jìn)行仿真優(yōu)化分析。仿真結(jié)果表明，該方法能快速收斂于最優(yōu)解并獲得一種較優(yōu)的測(cè)站布局。

大尺寸測(cè)量；測(cè)站部署；空間測(cè)量定位系統(tǒng)；模擬退火粒子群算法

0 引言

空間測(cè)量定位系統(tǒng)(workspace Measuring and Positioning System,wMPS)是一種新型的網(wǎng)絡(luò)式多站測(cè)量系統(tǒng)，隨著測(cè)站數(shù)的增加，系統(tǒng)的測(cè)量范圍將會(huì)拓展，同時(shí)測(cè)量成本也將增加[1]。此外，測(cè)站的不同布局也會(huì)導(dǎo)致系統(tǒng)定位精度的顯著差別。研究測(cè)站布局對(duì)系統(tǒng)定位精度的影響能為提高系統(tǒng)覆蓋范圍，降低成本提供依據(jù)，因此成為wMPS系統(tǒng)設(shè)計(jì)的一個(gè)基本問題[2-4]。

在測(cè)站布局研究方面，德國(guó)亞琛工業(yè)大學(xué)機(jī)床與制造工程研究所的Robert Schmitthe等人[5]對(duì)該系統(tǒng)在機(jī)器人定位跟蹤時(shí)的幾種典型布局進(jìn)行了仿真分析，考慮了時(shí)間t的測(cè)量誤差和0.1 mm的發(fā)射站系統(tǒng)誤差，并和激光跟蹤儀的測(cè)量結(jié)果對(duì)比，結(jié)果表明標(biāo)準(zhǔn)型的測(cè)量效果最好。文獻(xiàn)[6]中作者從wMPS網(wǎng)絡(luò)布局和定位誤差關(guān)系入手，研究了典型布局對(duì)定位誤差的影響，實(shí)驗(yàn)結(jié)果表明O_4型布局整體測(cè)量精度最高。以上對(duì)測(cè)站網(wǎng)絡(luò)布局的研究均是對(duì)特定布局進(jìn)行了研究與對(duì)比實(shí)驗(yàn)，當(dāng)測(cè)量環(huán)境變得復(fù)雜時(shí)缺乏靈活性與通用性。近年來，隨著計(jì)算機(jī)技術(shù)的發(fā)展，智能算法逐漸成為解決網(wǎng)絡(luò)測(cè)站優(yōu)化布局最受歡迎的手段之一，文獻(xiàn)[7-8]運(yùn)用遺傳算法從wMPS發(fā)射站光平面在測(cè)量點(diǎn)的不同交匯方式對(duì)測(cè)量穩(wěn)定性的影響入手，建立數(shù)學(xué)模型，以此來評(píng)價(jià)布局的優(yōu)劣，仿真結(jié)果表明四站系統(tǒng)的測(cè)量穩(wěn)定性優(yōu)于三站和兩站系統(tǒng)。但由于遺傳算法中交叉和變異概率固定易造成早熟現(xiàn)象，常常收斂不到最優(yōu)解。

因此本文從wMPS測(cè)站網(wǎng)絡(luò)布局與定位精度，覆蓋度及使用成本的關(guān)系入手，設(shè)計(jì)了一種基于模擬退火-粒子群算法的wMPS測(cè)站優(yōu)化部署方法，運(yùn)用粒子群算法的快速收斂性及模擬退火算法的全局收斂性進(jìn)行協(xié)同作用，對(duì)兩到四個(gè)隨機(jī)測(cè)站布局組成的網(wǎng)絡(luò)布局進(jìn)行仿真研究，結(jié)果表明，本文提出的方法能快速收斂于最優(yōu)解并獲得一種較優(yōu)的測(cè)站布局。

1 wMPS系統(tǒng)中多目標(biāo)優(yōu)化問題基本描述

1.1測(cè)量原理

wMPS組網(wǎng)測(cè)量模型如圖1所示，主要包括發(fā)射站，接收器，解算工作站。當(dāng)系統(tǒng)工作時(shí)，發(fā)射站發(fā)射兩束旋轉(zhuǎn)激光平面，接收器接收光信號(hào)后，將光平面產(chǎn)生的脈沖轉(zhuǎn)化為相對(duì)應(yīng)的時(shí)間信號(hào)，并發(fā)送給解算工作站。解算工作站通過解算多個(gè)測(cè)站時(shí)間信號(hào)從而獲得空間點(diǎn)的三維坐標(biāo)值[9-11]。

1.2 目標(biāo)函數(shù)

1.2.1 定位精度分析

本文采用作者先前工作所得到的定位精度模型[6]，由于定位精度與下文提及的覆蓋度，使用成本分屬不同量綱，因此需將其進(jìn)行歸一化。定義空間上任意一點(diǎn)P的歸一化精度表達(dá)式：

其中：PDOP為用戶提出的測(cè)量精度，GDOP為精度幾何稀釋因子。

1.2.2 覆蓋度分析

圖2為wMPS單向通訊模型，Rmin和Rmax是發(fā)射站的有效工作距離，圖中陰影部分為測(cè)站的有效工作距離。

圖1 wMPS組網(wǎng)測(cè)量模型Fig.1Networking measurement model of wMPS

圖2 wMPS單站通訊模型Fig.2Constraint model of wMPS direction communication

在wMPS中，當(dāng)空間有2個(gè)及以上測(cè)站時(shí)，即可通過角度交匯實(shí)現(xiàn)坐標(biāo)測(cè)量，則對(duì)于有一定高度的平面區(qū)域，此時(shí)測(cè)站的覆蓋度為

式中：d(Pi,Tj)為被測(cè)目標(biāo)Pi與任意測(cè)站Tj之間的歐式距離，β為垂直角，φmax為測(cè)站光平面最大傾角，N為測(cè)站個(gè)數(shù)。文中將測(cè)站的覆蓋度問題定義為當(dāng)前布局覆蓋被測(cè)點(diǎn)的個(gè)數(shù)Nnum與總被測(cè)點(diǎn)個(gè)數(shù)Ntol之比。

1.2.3 使用成本分析

僅考慮測(cè)站完成測(cè)量任務(wù)時(shí)的投資成本。在所有測(cè)站都被部署完畢后，則每種布局下測(cè)站的成本消耗：

其中：Nact是實(shí)際使用的測(cè)站數(shù)，Nmax是可使用的測(cè)站數(shù)。

1.2.4 目標(biāo)函數(shù)的定義

基于上述目標(biāo)函數(shù)的分析，給每個(gè)目標(biāo)賦予一定的權(quán)重，則wMPS布局優(yōu)化函數(shù)為

式中：Ki(i=1,2,…,n)為權(quán)重，且值代表了被測(cè)點(diǎn)在此種布局下的適應(yīng)度值的大小，本文優(yōu)化的目的就是在給定的測(cè)量區(qū)域下獲得一種f值較高的空間任意布局。

2 優(yōu)化算法設(shè)計(jì)

2.1 模擬退火-粒子群算法

粒子群算法(Particle Swarm Optimization,PSO)是一種基于群體的隨機(jī)優(yōu)化方法，其思想是將每個(gè)可能的解表示為種群中的粒子，每個(gè)粒子均有自己的速度和位置，并有一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)度。所有粒子在搜索空間內(nèi)以一定速度飛行，通過追隨當(dāng)前最優(yōu)值來尋找全局最優(yōu)[12]。粒子群算法在早期收斂速度較快，但易受參數(shù)選取和優(yōu)化目標(biāo)函數(shù)性質(zhì)等問題的影響，導(dǎo)致算法中后期收斂速度慢，易陷入局部最優(yōu)。

為解決粒子群算法易陷入局部最優(yōu)的問題，本文設(shè)計(jì)了一種將模擬退火算法(SimulatedAnnealing,SA)與粒子群算法相結(jié)合的模擬退火粒子群算法[13]，將模擬退火思想引入至粒子的速度和位置更新過程，采用Metropolis接受準(zhǔn)則[14]，持續(xù)進(jìn)行“產(chǎn)生新解—判斷—接受或舍棄”，使得算法能從局部最優(yōu)值中跳出，自適應(yīng)調(diào)整退火溫度，從而收斂至全局最優(yōu)解。

2.2 基于模擬退火-粒子群的wMPS測(cè)站布局優(yōu)化流程

圖3 模擬退火粒子群算法wMPS測(cè)站布局流程圖Fig.3Flow chart of station deployment based on SA-PSO

基于模擬退火粒子群算法的wMPS測(cè)站布局流程如圖3所示。具體步驟如下：

1)初始化過程如下：

①初始化參數(shù)：種群規(guī)模m，粒子維度d，學(xué)習(xí)因子c1，c2，迭代次數(shù)。

②初始化粒子位置和速度：由于布站位置具有較高精度的要求，因此本文采用浮點(diǎn)數(shù)編碼方式進(jìn)行編碼，并隨機(jī)初始化一定規(guī)模的種群，則第i個(gè)測(cè)站第d維的空間位置和速度可表示為

其中：a，vmax和b，vmin分別代表布站區(qū)域和速度的上界和下界;

③初始化退火溫度：采用式(8)設(shè)定初始化退火溫度和退火操作。其中C∈(0,1)。

2)適應(yīng)度函數(shù)：本文采用式(5)作為待優(yōu)化的適應(yīng)度函數(shù)，將每個(gè)粒子的最優(yōu)適應(yīng)度值作為初始個(gè)體最優(yōu)適應(yīng)度值，選擇個(gè)體最優(yōu)的極值作為初始群體最優(yōu)極值；

3)循環(huán)操作如下：

①對(duì)每個(gè)粒子的個(gè)體最優(yōu)值進(jìn)行模擬退火鄰域搜索；

②采用下式更新粒子的速度和位置：

式中：vid(k+1)是粒子在k+1時(shí)刻的速度，vid(k)是粒子在k時(shí)刻的速度，pid(k)為k時(shí)刻個(gè)體當(dāng)前最好位置，pgd(k)為當(dāng)前全局最優(yōu)位置。壓縮因子其中C=c1+c2。

③更新粒子的個(gè)體極值和全局最優(yōu)值：重新計(jì)算每一個(gè)粒子的適應(yīng)值，與該個(gè)體初始值進(jìn)行比較，若優(yōu)于個(gè)體初始值，則更新個(gè)體最優(yōu)值，進(jìn)而更新全局最優(yōu)值。

4)模擬退火操作：計(jì)算兩個(gè)位置適應(yīng)度函數(shù)的差值Δf，若Δf＜0或exp(-Δf/T)＞rand則接受新解，利用式(8)進(jìn)行降溫，否則轉(zhuǎn)至第3)步。

5)終止條件：對(duì)迭代次數(shù)進(jìn)行判斷，如果達(dá)到最大迭代次數(shù)則輸出結(jié)果并停止運(yùn)算。

圖4 空間約束模型Fig.4Space constraint model

3 仿真結(jié)果與分析

3.1 仿真模型建立及算法參數(shù)設(shè)置

為了簡(jiǎn)化模型，在不考慮有障礙物的情況下，若被測(cè)區(qū)域?yàn)槟掣叨鹊钠矫?，如圖4所示，設(shè)測(cè)量區(qū)域的外圍邊界為p×q的矩形，h為被測(cè)區(qū)域的高度。以被測(cè)區(qū)域左下角頂點(diǎn)為原點(diǎn)建立局部坐標(biāo)系Gm,OB連線為x軸正向，OD方向?yàn)閥軸正向，以O(shè)點(diǎn)為坐標(biāo)系原點(diǎn)，則被測(cè)區(qū)域M(x,y,z)在Gm坐標(biāo)系下可表示為[2]

設(shè)測(cè)量區(qū)域q=8 m，p=6 m，h=3 m，同時(shí)假設(shè)測(cè)站均工作在理想狀態(tài)下，每臺(tái)測(cè)站的作用距離均為4 m～10 m。模擬退火粒子群算法的具體參數(shù)設(shè)置：種群的規(guī)模為50，最大迭代次數(shù)Gmax為100，c1，c2等于2，C等于0.5，vmax等于1，vmin等于-1。

3.2 算法仿真

空間約束模型對(duì)兩到四個(gè)測(cè)站優(yōu)化目標(biāo)運(yùn)用粒子群算法和模擬退火粒子群算法選取相同權(quán)重進(jìn)行仿真分析，優(yōu)化前的布局選取經(jīng)驗(yàn)布局。優(yōu)化前后測(cè)站位置目標(biāo)函數(shù)值變化如表1～表3所示。

表1 兩站系統(tǒng)優(yōu)化前后參數(shù)對(duì)比Table 1Parameters comparison of two-station system before and after optimization

表2 三站系統(tǒng)優(yōu)化前后參數(shù)對(duì)比Table 2Parameters comparison of three-station system before and after optimization

表3 四站系統(tǒng)優(yōu)化前后參數(shù)對(duì)比Table 3Parameters comparison of four-station system before and after optimization

圖5 兩站系統(tǒng)收斂圖Fig.5Convergence curve of network optimization of two stations

③四站系統(tǒng)

選取測(cè)站1布站區(qū)域?yàn)镸1={(x∈(-5,1),y∈(-6,-3),z∈(1,3))}，測(cè)站2的布站區(qū)域?yàn)镸2={(x∈(3,10),y∈(-6,-3),z∈(1,3))}，測(cè)站3的布站區(qū)域?yàn)镸3={(x∈(-5,1),y∈(7,9),z∈(1,3))}，測(cè)站4的布站區(qū)域?yàn)镸4={(x∈(3,10),y∈(7,9),z∈(1,3))}。優(yōu)化后算法最優(yōu)解收斂圖如圖7所示。

圖6 三站系統(tǒng)收斂圖Fig.6Convergence curve of network optimization of three stations

圖7 四站系統(tǒng)收斂圖Fig.7Convergence curve of network optimization of four stations

3.3 結(jié)果分析

從圖5到圖7兩站，三站，四站系統(tǒng)粒子群算法與模擬退火-粒子群算法收斂曲線可以看出，兩站系統(tǒng)的f值從0.709增加到0.723，三站系統(tǒng)f值從0.717增加到0.726，四站系統(tǒng)f值從0.643增加到0.651。從前面的目標(biāo)函數(shù)分析可知，f值的增加表明測(cè)站在給定的布站區(qū)域內(nèi)獲得了較優(yōu)的布局。在收斂速度方面，使用粒子群算法進(jìn)行尋優(yōu)普遍要在30代左右才能獲得最優(yōu)解，而運(yùn)用本文算法在15代左右就已經(jīng)獲得了最優(yōu)解，說明本文提出的算法收斂速度較快。而對(duì)比表1到表3的兩站，三站，四站仿真結(jié)果可以看出，相較于優(yōu)化前及粒子群算法優(yōu)化后的結(jié)果，使用本文提出的模擬退火粒子群算法在目標(biāo)函數(shù)值上都取得了較好的優(yōu)化結(jié)果，每一個(gè)目標(biāo)值都優(yōu)于或等于其他兩個(gè)方法獲得的最優(yōu)解。因此，基于模擬退火-粒子群算法的wMPS系統(tǒng)測(cè)站部署優(yōu)化方法是確定空間隨機(jī)布局的一種有效方法。

4 結(jié)論

1)本文從不同測(cè)站的交匯情況出發(fā)，推導(dǎo)了測(cè)站布局與測(cè)量系統(tǒng)的定位精度，覆蓋度，使用成本之間的關(guān)系，從而建立了多目標(biāo)優(yōu)化模型。同時(shí)提出了一種基于模擬退火算法與粒子群算法相混合的算法，此算法改善了粒子群算法易陷入局部最優(yōu)的問題，保證了全局收斂性。

2)通過此算法對(duì)測(cè)站的兩站，三站，四站系統(tǒng)的空間隨機(jī)布局情況進(jìn)行了仿真研究，并與粒子群算法和經(jīng)驗(yàn)布局的結(jié)果進(jìn)行對(duì)比，發(fā)現(xiàn)本文提出的算法能夠快速的找到較優(yōu)的布局，有效地改善系統(tǒng)的測(cè)量性能，提高了算法的收斂性。因此，這種方法可以適用于給定布站區(qū)域，測(cè)量區(qū)域?qū)Χㄎ痪?，覆蓋度，使

用成本有要求的空間隨機(jī)布局的優(yōu)化過程中。

3)由于本文采用的是等量權(quán)重對(duì)系統(tǒng)目標(biāo)函數(shù)進(jìn)行優(yōu)化設(shè)計(jì)，并未考慮各個(gè)子目標(biāo)函數(shù)對(duì)系統(tǒng)測(cè)量的重要程度不同，因此下一步將采用層次分析法對(duì)權(quán)重進(jìn)行優(yōu)化設(shè)計(jì)，以期能更好地發(fā)揮各子目標(biāo)的作用，為工程應(yīng)用提供參考。

[1]熊芝，邾繼貴，耿磊，等.旋轉(zhuǎn)激光平面測(cè)角精度測(cè)試方法研究[J].激光與紅外，2012，42(2)：133-137. XIONG Zhi，ZHU Jigui，GENG Lei，et al.Verification of angle measuring accuracy for rotating planar laser beams[J].Laser &Infrared，2012，42(2)：133-137.

[2]熊芝.wMPS空間測(cè)量定位網(wǎng)絡(luò)布局優(yōu)化研究[D].天津：天津大學(xué)，2012：19-57. XIONG Zhi.Research on network deployment optimization of workspace Measurement and Positioning System[D].Tianjin：Tianjin University，2012：19-57.

[3]Mautz R.Overview of Current Indoor Positioning Systems[J].Geodesy and Cartography(S2300-2581)，2009，35(1)：18-22.

[4]MaurizioG，BarbaraP.Optimalsensorpositioningforlargescalemetrologyapplications[J].Precision Engineering(S0141-6359)，2010，34：563-567.

[5]Schmitt R，Nisch S，Schonberg A.Performance evaluation of iGPS for industrial applications[C]//Proceedings of International Conference on Indoor Positioning and Indoor Navigation(IPIN)，Zurich Switerland，2010：1-8.

[6]熊芝，邾繼貴，薛彬，等.空間測(cè)量定位網(wǎng)絡(luò)的典型布局[J].光學(xué)精密工程，2013，21(9)：2354-2363. XIONG Zhi，ZHU Jigui，XUE Bin，et al.Typical deployments of workspace measurement and positioning system[J].Optics and Precision Engineering，2013，21(9)：2354-2363.

[7]薛彬，鄭迎亞，熊芝，等.室內(nèi)空間測(cè)量定位系統(tǒng)布局仿真研究[J].機(jī)械工程學(xué)報(bào)，2015，51(8)：1-8. XUE Bin，ZHENG Yingya，XIONG Zhi，et al.Simulation for network deployment of indoor workspace Measurement and Positioning System[J].Chinese Journal of Mechanical Engineering，2015，51(8)：1-8.

[8]鄭迎亞，邾繼貴，薛彬，等.室內(nèi)空間測(cè)量定位系統(tǒng)網(wǎng)絡(luò)布局優(yōu)化[J].光電工程，2015，42(5)：20-26. ZHENG Yingya，ZHU Jigui，XUE Bin，et al.Network Deployment Optimization of Indoor Workspace Measurement and Positioning System[J].Opto-Electronic Engineering，2015，42(5)：20-26.

[9]熊芝，邾繼貴，耿磊，等.空間測(cè)量定位系統(tǒng)測(cè)角不確定度分析及檢定[J].傳感技術(shù)學(xué)報(bào)，2012，25(2)：229-235. XIONG Zhi，ZHU Jigui，GENG Lei，et al.Verification of Angle Measuring Uncertainty for Workspace Measuring and Positioning System[J].Chinese Journal of Sensors and Actuators，2012，25(2)：229-235.

[10]XIONG Zhi，ZHU Jigui，ZHAO Ziyue.Workspace measuring and positioning system based on rotating laser planes[J]. Mechanika(S1392-1207)，2012，18(1)：94-98.

[11]王一，劉常杰，任永杰，等.通用機(jī)器人視覺檢測(cè)系統(tǒng)的全局校準(zhǔn)技術(shù)[J].光學(xué)精密工程，2009，17(12)：3028-3033. WANG Yi，LIU Changjie，REN Yongjie，et al.Global calibration of visual inspection system based on universal robots[J]. Optics and Precision Engineering，2009，17(12)：3028-3033.

[12]莫思敏，曾建潮，徐衛(wèi)濱.具有自組織種群結(jié)構(gòu)的微粒群算法[J].系統(tǒng)仿真學(xué)報(bào)，2013，25(3)：445-450. MO Simin，ZENG Jianchao，XU Weibin.Particle Swarm Optimization Based on Self-organization Topology[J].Journal of System Simulation，2013，25(3)：445-450.

[13]孟祥濤，王巍，向政.基于微粒群與模擬退火算法的光纖陀螺導(dǎo)航系統(tǒng)動(dòng)態(tài)補(bǔ)償方法[J].紅外與激光工程，2014，43(5)：1555-1560. MENG Xiangtao，WANG Wei，XIANG Zheng.Dynamic compensation of FOG navigation system based on particle swarm optimization and simulated annealing algorithm[J].Infrared and Laser Engineering，2014，43(5)：1555-1560.

[14]SHAO Wei，ZUO Yijun.Simulated annealing for higher dimensional projection depth[J].Computational Statistics&Data Analysis(S0167-9473)，2012，56(12)：4026-4036.

Station Deployment of Workspace Measuring and Positioning System Based on SimulatedAnnealing Particle SwarmAlgorithm

YUE Chong1a，XIONG Zhi1a,1b，XUE Bin2
(1.a.School of Mechanical Engineering;b.Key Lab of Modern Manufacturing Quality Engineering of Hubei Province, Hubei University of Technology,Wuhan430068,China; 2.School of Marine Science and Technology,Tianjin University,Tianjing300072,China)

Workspace Measuring and Positioning System(wMPS)is a kind of large-scale system,which depends on the multi-station synergy to achieve the coordinate measuring,so the station layout optimization is a common but important problem.Station optimal topological geometry based on simulated annealing particle swarm algorithm was proposed. Firstly,the positioning accuracy,coverage area and cost were taken as objectives to establish the multi-objective optimization function.Secondly,particle swarm algorithm and simulated annealing algorithm were cooperated to find the best solution,and simulated annealing particle swarm algorithm optimization process was established according to multi-objective function.Finally,simulation analysis for layout optimization algorithm of 2～4 stations was performed. The results show that the proposed method has reliable stability and is able to quickly converge to optimal solutions.

large-scale measurement;station deployment;wMPS;simulated annealing particle swarm algorithm

TB92

A

10.3969/j.issn.1003-501X.2016.07.011

1003-501X(2016)07-0067-07

2015-10-30；

2015-12-22

國(guó)家自然科學(xué)基金(51305130，61505140)；湖北工業(yè)大學(xué)博士科研啟動(dòng)基金(BSQD12123)資助項(xiàng)目

岳翀(1991-)，女(漢族)，貴州貴陽人。碩士研究生，主要從事大尺寸測(cè)量及智能優(yōu)化算法的研究。E-mail:yoona125@163.com。

熊芝(1985-)，女(漢族)，湖北荊州人。講師，博士，主要從事大尺寸測(cè)量、光電檢測(cè)方面的研究。E-mail:xiongzhi0611@163.com。