董文軒，陳建國，黃 宇，蘇國鋒

（1.清華大學(xué)工程物理系，北京100084；2.北京信息科技大學(xué)自動化學(xué)院，北京100192）

1 引 言

氣體源定位是通過測量監(jiān)測節(jié)點(diǎn)的氣體濃度，結(jié)合定位算法估計氣體泄漏源位置的技術(shù)［1］，主要應(yīng)用于火災(zāi)早期監(jiān)測和危險氣體泄露預(yù)警，有助于應(yīng)對城市管網(wǎng)老化、復(fù)雜化等現(xiàn)象帶來的安防挑戰(zhàn)。近年來，由于低成本、低功耗的傳感器網(wǎng)絡(luò)的普及，國內(nèi)外出現(xiàn)了一系列方法多樣的氣體溯源定位研究。源定位算法是無人系統(tǒng)溯源技術(shù)的核心部分，其根據(jù)傳感器測得的部分歷史數(shù)據(jù)，計算出運(yùn)載器當(dāng)前的移動目標(biāo)，并經(jīng)過迭代最終預(yù)測泄露源位點(diǎn)。

當(dāng)前，國內(nèi)外研究人員主要采用機(jī)動式傳感器（群），在無人運(yùn)載器上構(gòu)建機(jī)器主動嗅覺，結(jié)合動態(tài)路徑規(guī)劃算法，從而使無人系統(tǒng)經(jīng)過迭代達(dá)到最優(yōu)化位置。傳統(tǒng)的嗅覺算法包括瞬時濃度梯度法、單純形搜索法、半隨機(jī)移動法、Z字型搜索法等［2-3］。此類算法一般認(rèn)為氣體分布具有平滑的濃度梯度，可供利用對煙羽進(jìn)行跟蹤定位；算法的搜索步長一般保持固定，系統(tǒng)逐步前進(jìn)，移動速度慢，智能化程度較低。Hayes 提出的外螺旋（SS）算法，基于多風(fēng)源的湍流環(huán)境進(jìn)行設(shè)計，擺脫了對于局部濃度梯度的依賴，并且經(jīng)過了實(shí)驗(yàn)驗(yàn)證［4］，但其在搜索路徑效率和氣體源確認(rèn)上仍有不足。李飛將生物遺傳和進(jìn)化觀點(diǎn)引入定位算法之后，國內(nèi)相繼出現(xiàn)大量群智能算法，如蟻群算法、粒子群算法等［5］，全局搜索能力和收斂精度持續(xù)提高。然而，此類算法對環(huán)境的已知信息量的要求普遍提高，需要在連續(xù)的柵格內(nèi)采集數(shù)據(jù)，影響了算法在大型區(qū)域內(nèi)的可用性。

受限于被動式傳感器的氣敏性能，無人小車用于采集濃度數(shù)據(jù)的時間不可忽略。低濃度傳感器的響應(yīng)時間參數(shù)和溯源路徑上的檢測節(jié)點(diǎn)數(shù)目，是制約目前算法溯源能力的首要因素。由于高昂的時間成本，現(xiàn)有算法主要面向室內(nèi)搜尋場景，實(shí)驗(yàn)場地的典型尺度在10m 以下［6］，始終受限于較小場域空間和特定的擴(kuò)散場模型，在很大程度上難以滿足大型工業(yè)場地的使用需求。因此，現(xiàn)階段氣體源定位算法研究的主要矛盾，即是氣體擴(kuò)散行為的復(fù)雜性與安保時間緊迫性之間的矛盾。

如何在檢測位點(diǎn)盡可能精簡的前提下，控制合理的搜索范圍，同時保證溯源定位的高精度和高成功率，是本文的研究目標(biāo)。本文以搭載單個濃度傳感器的智能小車為例，聚焦于準(zhǔn)靜態(tài)濃度場的平面搜尋場景，對三邊定位法和單純形算法兩種傳統(tǒng)算法加以改造和整合，提出一種不依賴于先驗(yàn)知識的混合型溯源定位遺傳算法。

王巍等認(rèn)為，目前氣體源定位方法的普適性不強(qiáng)，針對湍流環(huán)境的氣體源定位方法大部分具有風(fēng)信息依賴性，而針對分子擴(kuò)散環(huán)境和湍流主控微弱流體環(huán)境的方法，會因?yàn)槭ミB續(xù)的濃度梯度而無法對氣體源進(jìn)行定位［7］。本文算法弱化了對風(fēng)信息和梯度信息的依賴，對于解決不同流場環(huán)境的普適性問題具有一定的啟示意義。

2 問題描述

假設(shè)無人系統(tǒng)由n輛無人小車組成，在未知的平面環(huán)境中搜索，問題可以描述為：

（1）E=｛（i，j）|i=1，2，…，Lx，j=1，2，…，Ly｝為一個矩形待搜索區(qū)域，區(qū)域內(nèi)存在一個氣體源，坐標(biāo)未知；

（2）每一個坐標(biāo)網(wǎng)格對應(yīng)一個氣體濃度值c（i，j|t），在比較穩(wěn)定的濃度場里，濃度c近似不隨時間變化，假設(shè)氣體源所在網(wǎng)格的濃度值最大；

（3）用x表示坐標(biāo)位置，代替實(shí)數(shù)對（i，j）；用data或DATA表示一組坐標(biāo)數(shù)據(jù)x和該位置處的濃度數(shù)據(jù)cx組成的結(jié)構(gòu)體變量；

（4）無人小車n輛，配備了相同的傳感器和通訊設(shè)備，當(dāng)小車在某一位置靜止時，可以測得此處的濃度值；

（5）通過算法對測量結(jié)果以及坐標(biāo)數(shù)據(jù)進(jìn)行計算，獲得小車的運(yùn)動路徑，使之快速抵達(dá)泄露源點(diǎn)。

3 混合型平面溯源定位算法的設(shè)計

3.1 三邊定位-單純形算法

為了提高求解的科學(xué)性和保證逐代優(yōu)化的趨勢，保存一些節(jié)點(diǎn)的數(shù)據(jù)，并且使用遺傳進(jìn)化思想是有必要的。然而，根據(jù)前述精簡測量節(jié)點(diǎn)的原則，并考慮到歷史測量值的時效性，應(yīng)優(yōu)先選用信息量需求較小的算法。

針對平面溯源問題，現(xiàn)存兩種簡單的算法，即三邊測量定位算法（Trilateration）和單純形算法（Simplex Algorithm）［8］。兩種傳統(tǒng)算法均采用三組坐標(biāo)位置的數(shù)據(jù)進(jìn)行迭代計算，且具備良好的優(yōu)勢互補(bǔ)特征，在此基礎(chǔ)上提出混合型算法，可以有效兼顧搜索效率和收斂穩(wěn)定性。

3.1.1 啟發(fā)式的三邊定位求解

三邊定位法的基本假設(shè)認(rèn)為，平面內(nèi)任意一點(diǎn)與源點(diǎn)的距離r，和該點(diǎn)的濃度值c呈負(fù)相關(guān)關(guān)系。由此，可以通過三點(diǎn)濃度的測量值來建立以下的平面距離關(guān)系：

以三個測量點(diǎn)為圓心，給定半徑的比例關(guān)系畫圓，當(dāng)計算得到三個圓的共交點(diǎn)時，即作為預(yù)測源點(diǎn)位置的更新值。在本實(shí)驗(yàn)場景中，由于缺乏先驗(yàn)?zāi)Ｐ停沟梅匠探M（1）不封閉，共交點(diǎn)的求解經(jīng)常無法唯一確定（如圖1），最多可能存在4個可行解。合適的半徑取值需要用試值法得到?？紤]到溯源起點(diǎn)通常位于濃度場邊緣，實(shí)驗(yàn)認(rèn)為，按照從大到小的方式試值，優(yōu)先選用半徑較大的解有利于提高搜尋效率。

圖1 三邊定位法多解示意圖Fig.1 Trilateration method and possible multiple solution

具體的求解及篩選過程如下：

步驟一：定義三個圓Oi（i=1，2，3）的半徑為ri，其中r3最大，在三個圓兩兩有交點(diǎn)的前提下，從大到小對半徑進(jìn)行試值；

步驟二：半徑被賦值后，計算O1與O2的兩個交點(diǎn)，選出距離O3的圓心較近的一個；

步驟三：計算該交點(diǎn)的坐標(biāo)與半徑r3是否匹配，即是否是三圓的共交點(diǎn)，若不匹配，本次試值失敗，更改半徑的賦值并重復(fù)以上過程。

三邊定位算法在預(yù)測源點(diǎn)方向上具有啟發(fā)式的意義，有助于彌補(bǔ)單純形算法的不足。在長距離搜索過程中，初始化三角形遠(yuǎn)小于濃度場的幾何尺度，單純形算法易表現(xiàn)出搜索點(diǎn)分布特征單一、方向性差、自由度下降或退化為一維搜索、逐代移動步長非嚴(yán)格遞減、易于陷入局部最優(yōu)等特點(diǎn)（如圖9）。而三邊定位解在調(diào)整移動步長、跳出局部最優(yōu)上具備優(yōu)勢，有效緩解了單純形算法發(fā)生失效的概率，將搜索能力維持在較高水平。

3.1.2 改進(jìn)的單純形求解

單純形求解與三邊定位法使用相同的三個測量數(shù)據(jù)點(diǎn)，該算法認(rèn)為，氣體源的預(yù)測位置在三角形的一條中位線及其延長線上，這條射線經(jīng)過濃度最低的頂點(diǎn)（如圖2）。標(biāo)準(zhǔn)的三邊定位法是不收斂和不可靠的，其解空間嚴(yán)重不完備。由于一般的濃度場與無風(fēng)情況下的理想點(diǎn)源擴(kuò)散模型差距較大，任取三點(diǎn)易陷入無解情況，或共交點(diǎn)位置超出場地范圍，進(jìn)而對算法的可用性造成損害。實(shí)驗(yàn)中以第一代初始化數(shù)據(jù)代入該算法，計算成功率僅達(dá)20%左右。

圖2 基本的單純形算法Fig.2 Basic simplex algorithm

本文算法利用此特點(diǎn)，輔助單純形算法進(jìn)行條件句判斷，以代替其傳統(tǒng)的判斷方式［9］，減少路徑規(guī)劃中的冗余折返。判斷邏輯見3.1.3 節(jié)的偽代碼。假設(shè)三邊定位計算成功，則定義該計算處于啟發(fā)定向階段；若失敗，則定義處于保守的梯度步進(jìn)階段。以下分別介紹兩種階段下的單純形求解步驟。

（1）啟發(fā)定向階段

如圖2示，xL為最小值點(diǎn)坐標(biāo)，xG、xH為另兩個頂點(diǎn)的坐標(biāo)，直接求解xext的坐標(biāo)即為單純形解。

（2）梯度步進(jìn)階段

此階段中，三邊定位法處于失效狀態(tài)。單純形算法宜取xmid和xext之間的點(diǎn)作為較保守的解，以確保算法運(yùn)行的安全性。此外，為了緩解單純形算法中搜索區(qū)域縮小的問題，在該步驟中加入了隨機(jī)性因素，偽代碼見3.1.3節(jié)。

3.1.3 兩種算法的混合求解

本節(jié)以偽代碼的形式，給出了三邊定位-單純形算法進(jìn)行一次計算的完整步驟。其中，混合型算法在梯度步進(jìn)階段直接取單純形解；啟發(fā)定位階段的最終解，取三邊定位解與單純形解的加權(quán)平均值，這樣既充分發(fā)揮了三邊定位的啟發(fā)性作用，也可以過濾掉搜索步長相對過大的解［10］。實(shí)驗(yàn)選取加權(quán)參數(shù)k=0.35。

此外，有且僅有一種情況三邊定位法與單純形算法同時失效，即三組親代數(shù)據(jù)點(diǎn)位于同一坐標(biāo)方格中。算法特別定義，在此狀態(tài)下，輸出的子代坐標(biāo)點(diǎn)于該方格附近一定距離處隨機(jī)跳動，從而實(shí)現(xiàn)跳出局部最優(yōu)解，繼續(xù)在周圍保持一定范圍的游走。游走距離可以根據(jù)實(shí)際流場條件進(jìn)行規(guī)定，在本實(shí)驗(yàn)中設(shè)置為5m。

3.2 遺傳進(jìn)化結(jié)構(gòu)

為測試以上算法的可行性，首先進(jìn)行了一次預(yù)實(shí)驗(yàn)。實(shí)驗(yàn)使用混合型平面溯源定位算法，輸入任意一張濃度場分布圖，初始化三個數(shù)據(jù)點(diǎn)進(jìn)行遺傳迭代。結(jié)果表明，如果只使用三組數(shù)據(jù)點(diǎn)，路徑節(jié)點(diǎn)會迅速形成共線，陷入一維的局部搜索，溯源效果與單純形算法基本無異。圖3（a）中顯示了預(yù)實(shí)驗(yàn)前50代的搜索目標(biāo)點(diǎn)，坐標(biāo)單位為0.4m，可見其分布過于緊密。圖3（b）為搜索路徑的局部放大圖，算法初步具備了步長調(diào)節(jié)和跳出共線的能力，但很快又陷入共線狀態(tài)。

由此可見，三邊定位-單純形算法的求解質(zhì)量并不高，而低質(zhì)量的迭代會使算法向基礎(chǔ)的單純形算法退化，收斂速度極慢，甚至定位失敗。如果在遺傳過程中適當(dāng)擴(kuò)大備選子代的規(guī)模，殺死一些低質(zhì)量的種群，則能夠有效維護(hù)算法的有效性，提高算法魯棒性。

為解決上述問題，算法引入了排列組合策略，使用五組數(shù)據(jù)點(diǎn)進(jìn)行遺傳迭代。圖4左側(cè)表示親代數(shù)據(jù)集，其中2～5號數(shù)據(jù)點(diǎn)按照濃度大小降序排列。圖5所示為遺傳進(jìn)化算法的流程圖。

圖3 預(yù)實(shí)驗(yàn)前50代搜尋點(diǎn)分布圖Fig.3 Distribution of search points of 50 generations in pre-experiment

圖4 引入排列組合策略的數(shù)據(jù)遺傳結(jié)構(gòu)Fig.4 Data genetic structure introducing combination strategy

混合型算法進(jìn)行一次運(yùn)算需要使用三組數(shù)據(jù)，第一組數(shù)據(jù)固定選取圖4中的DATA1，余下兩組從2～5 號數(shù)據(jù)點(diǎn)中任選，可以取出總計C（4，2）= 6 種組合形式，即得到六組不同的子代（如圖4右側(cè)data1～6）。無人小車抵達(dá)六個目標(biāo)點(diǎn)進(jìn)行探測，選取其中濃度值最大的點(diǎn)，用來更新親代數(shù)據(jù)集。

親代數(shù)據(jù)集的更新方法為，先用DATA1 替代濃度較低的DATA5，然后以最優(yōu)子代作為DATA1的更新值，最后對DATA2～5 重新定序。這種更新策略有效地維護(hù)了數(shù)據(jù)的優(yōu)化趨勢，DATA2～4 三組數(shù)據(jù)分別隨迭代次數(shù)非嚴(yán)格遞增，該特征可以作為判斷溯源結(jié)束的標(biāo)志；而鎖定DATA1 的組合方式，保證了逐代計算中，至少有一組數(shù)據(jù)點(diǎn)始終保持更新，子代之間幾乎不產(chǎn)生重復(fù)計算，這有助于維護(hù)親代數(shù)據(jù)集的更新能力，從而加快收斂速度。

4 建模及參數(shù)設(shè)置

4.1 點(diǎn)源泄露氣體擴(kuò)散模型

本文采用經(jīng)典的高斯擴(kuò)散方程對氣體擴(kuò)散過程進(jìn)行模擬，適用于大多數(shù)氣體探測場景的需求［11］。同時，為了體現(xiàn)濃度場分布的一般性特點(diǎn)，盡量減少場的先驗(yàn)形狀對算法的影響，在計算中引入了時變因素，模擬了在二維平面（z=0）內(nèi)0～750min的擴(kuò)散過程。

實(shí)驗(yàn)假設(shè)，氣體源由1500 個位置相同、相互獨(dú)立的點(diǎn)源，在時間維度上相繼連續(xù)觸發(fā)所形成，任一時刻濃度場視為1500個點(diǎn)源濃度場的代數(shù)疊加。每個源在初始化位置上泄露30s，形成穩(wěn)定的高斯煙團(tuán)；泄露時間結(jié)束以后，在設(shè)定的風(fēng)力作用下，煙團(tuán)中心在平面內(nèi)以一定速度和方向漂移。依此過程，最終形成時間顆粒度為30s 的變源強(qiáng)、變風(fēng)向、變風(fēng)速的開闊區(qū)域氣體擴(kuò)散模型。如圖6所示，氣體源高度0.25m，坐標(biāo)位置（5m，50m），中心區(qū)域氣體濃度達(dá)到10-4kg/m3量級。

仿真實(shí)驗(yàn)條件為準(zhǔn)靜態(tài)場，不考慮小車在溯源過程中引起的濃度變化，故只選取任一時間切片的濃度場分布數(shù)據(jù)作為靜態(tài)索引對象。

4.2 小車及運(yùn)動場地模型

仿真實(shí)驗(yàn)場地設(shè)置為100m×200m 的開闊平地區(qū)域；坐標(biāo)網(wǎng)格以0.4m為單位刻度，將場地劃分成250×500 個方格，所有實(shí)驗(yàn)采用同樣的地圖作算法的驗(yàn)證。

在平面內(nèi)運(yùn)動的智能小車，理論上自由度為3。實(shí)驗(yàn)中為了適當(dāng)降低路徑規(guī)劃的難度，將小車模型簡化為自由運(yùn)動質(zhì)點(diǎn)，并且省略了運(yùn)動場地中的障礙物。參考算法過程可以說明，作出該簡化是合理的。給定小車的典型平均速度為2m/s。小車數(shù)量與迭代計算過程無關(guān)。

智能小車上搭載有浸入式的氣體濃度傳感器探頭。以低濃度甲烷探測器為例，市場現(xiàn)有探測器每次測量的最短響應(yīng)時間約5s［12］。在測量時間內(nèi)，假設(shè)小車于測量點(diǎn)處靜止。

5 仿真結(jié)果及分析

5.1 場外巡檢與煙羽發(fā)現(xiàn)

本文數(shù)字仿真實(shí)驗(yàn)基于MATLAB 環(huán)境。單次實(shí)驗(yàn)中，隨機(jī)設(shè)定任一時刻的氣體濃度場，設(shè)定小車位置起始點(diǎn)在場地邊緣（如圖7右上角），風(fēng)速、風(fēng)向?yàn)橐阎獥l件。

圖6 不同時刻下的點(diǎn)源氣體擴(kuò)散濃度場模型Fig.6 Point source gas diffusion concentration field model at different moments

圖7 場外搜尋及煙羽發(fā)現(xiàn)路徑模擬Fig.7 Off-site search path simulation

無人系統(tǒng)溯源過程，通?？梢詣澐譃闊熡鸢l(fā)現(xiàn)、煙羽追溯、確認(rèn)氣體源三個階段。在前溯源階段，小車沿逆風(fēng)向?qū)θ珗鲞M(jìn)行Z字形排查搜索［13］，如圖粉紅色虛線為初次路徑規(guī)劃軌跡。重規(guī)劃使用貝塞爾曲線，將小車的模擬運(yùn)動軌跡處理成黑色光滑曲線，紅色六角星表示小車位置，算法在此處達(dá)到濃度探測閾值（實(shí)驗(yàn)設(shè)置為10-6kg/m3），進(jìn)入溯源定位階段。

二階貝塞爾曲線表達(dá)式為：

其中，p0、p2為各段局部路徑的起點(diǎn)和終點(diǎn)，p1為控制點(diǎn)。

5.2 溯源定位算法仿真

小車模型進(jìn)入濃度場之后，繼續(xù)在同一準(zhǔn)靜態(tài)場中運(yùn)動，使用本文混合型平面溯源定位算法執(zhí)行迭代過程。本實(shí)驗(yàn)設(shè)定，當(dāng)DATA2、DATA3、DATA4三組數(shù)據(jù)經(jīng)過5 次迭代不再更新時，小車退出迭代算法，輸出源點(diǎn)坐標(biāo)及濃度［14］。圖8為部分仿真結(jié)果，實(shí)心圓點(diǎn)表示溯源算法中所有子代的坐標(biāo)數(shù)據(jù)，即小車搜索過的目標(biāo)點(diǎn)，虛線代表小車運(yùn)動經(jīng)過的平均路徑。實(shí)驗(yàn)表明，輸出數(shù)據(jù)在源點(diǎn)所在方格處（濃度最高）精確收斂。

為保證實(shí)驗(yàn)的可重復(fù)性，研究選取150～500min內(nèi)不同時間的濃度分布場共進(jìn)行了100組實(shí)驗(yàn)。結(jié)果顯示，在絕大多數(shù)場景下，本文算法精確溯源的成功率為100%，迭代次數(shù)穩(wěn)定在20～45 代左右，預(yù)計溯源時間為750～1400s；平均路徑與煙羽的飄散方向基本吻合，在不具備先驗(yàn)知識的情況下，較好地符合了煙羽的形狀，滿足了對提高搜尋效率的要求；小車搜索的目標(biāo)點(diǎn)分布在平均路徑附近，拐點(diǎn)處和終點(diǎn)處分布增多；退化成一維的共線狀態(tài)偶有出現(xiàn)，該現(xiàn)象對溯源結(jié)果的精確性不造成影響，但會使迭代次數(shù)明顯增加。

作為對照，本文還單獨(dú)使用了兩種傳統(tǒng)算法進(jìn)行了實(shí)驗(yàn)，該實(shí)驗(yàn)使用了完全相同的組合數(shù)遺傳框架。三邊定位法的計算失敗概率過高，無法形成有效的搜索路徑；單純形算法的搜索路徑不光滑，中后段明顯退化成一維搜索（如圖9），逐漸向傳統(tǒng)的單純形算法過渡，且迭代次數(shù)多，溯源成功率約50%。

圖8 混合型平面溯源算法仿真路徑圖及迭代次數(shù)Fig.8 Simulation path of hybrid traceability algorithm(n for number of iterations)

圖9 傳統(tǒng)單純形算法仿真路徑圖（60代）Fig.9 Simulation path diagram of traditional simplex algorithm

5.3 路徑規(guī)劃方案分析

無人車的規(guī)劃路徑以代際為單位，每一次迭代包含6個搜索目標(biāo)點(diǎn)，無先后順序，故整個溯源路徑問題可以分解成為數(shù)十次連續(xù)的多目標(biāo)路徑規(guī)劃問題。而路徑確定之后，根據(jù)小車的運(yùn)動速度和傳感器測量時間，就可以估算得到完成一次溯源任務(wù)的時間成本。選擇不同的路徑規(guī)劃方案與迭代計算結(jié)果無關(guān)。

由于運(yùn)動場地模型中不存在障礙物，可以粗略地用兩點(diǎn)連線的方式代表小車運(yùn)動路徑。對于任意一代目標(biāo)點(diǎn)，共存在720種路徑選取方式，容易選出長度最短的一條作為單個小車的規(guī)劃路徑（如圖10）。這種路徑規(guī)劃方式存在一定的路徑折返，增加了不必要的時間成本，使用一輛小車的無人系統(tǒng)基本無法避免此類問題。

圖10 一輛無人小車溯源規(guī)劃路徑圖（n=26）Fig.10 Trace route of one unmanned vehicle

一種優(yōu)化方式是通過增加無人車的數(shù)量，以及建立多輛車之間的通信系統(tǒng)，合理分配運(yùn)動目標(biāo)點(diǎn)和測量時間，同時減少路徑折返現(xiàn)象的發(fā)生。不同的車之間需要保持同步性，即當(dāng)一代6 個目標(biāo)點(diǎn)全部測量結(jié)束后，再開始次一代計算。實(shí)驗(yàn)中采取了兩輛車的規(guī)劃方案，每輛車在一次迭代中測量3 組坐標(biāo)下的濃度數(shù)據(jù)。仿真路徑如圖11。

圖11 兩輛無人小車溯源規(guī)劃路徑圖（n=35）Fig.11 Trace route of two unmanned vehicles

實(shí)驗(yàn)在8 組不同濃度場條件下，分別使用以上兩種路徑規(guī)劃策略，對平均路徑長度、時間成本進(jìn)行了統(tǒng)計和對比（表1）。算法平均迭代39.89次，兩車路徑規(guī)劃方案比一車規(guī)劃的場內(nèi)迭代時間節(jié)省了47.9%，完成全部溯源過程的時間成本平均下降了43.6%；和改進(jìn)的蟻群算法比較，在同尺度場地、相同定位精度、同樣使用兩輛無人小車的條件下［5］，系統(tǒng)的溯源效率提高了約91.0%。

6 結(jié) 論

本文提出的混合型三點(diǎn)定位算法與傳統(tǒng)算法相比，體現(xiàn)出諸多改良和創(chuàng)新性，在運(yùn)行穩(wěn)定性、結(jié)果可靠性和搜索效率上均有所突破，大大提高了兩種算法的實(shí)用性。三邊定位、單純形算法和組合遺傳策略，這三者對于各自的劣勢形成了互相彌補(bǔ)的結(jié)構(gòu)。三邊定位法通過其定向能力、步長調(diào)節(jié)能力，改善了單純形算法的搜索緩慢、單一化和路徑折返問題；組合遺傳策略，補(bǔ)償了三邊定位法中計算失敗的概率，確保xtr解在逐級迭代中發(fā)揮持續(xù)的作用，也為單純形算法提供了多樣性的選擇，避免搜尋軌跡過早地陷入共線狀態(tài)；單純形算法利用了一部分濃度梯度信息，保證了算法系統(tǒng)的運(yùn)算安全性。

該算法的優(yōu)勢首先在于測量節(jié)點(diǎn)少，效率高，機(jī)動性強(qiáng)，使搜索步長具有了自我調(diào)適能力。在煙羽追溯階段，搜索步長沒有明顯下降，維持了快速移動的能力；在算法趨于收斂的階段，搜索步長逐漸下降，從而獲得高精確性。本算法現(xiàn)階段達(dá)到的效率和搜索場域大小，已經(jīng)基本符合無人小車的移動特征和現(xiàn)實(shí)需求。而現(xiàn)有算法以改進(jìn)的蟻群為例，小車在溯源路徑上逐點(diǎn)探測，搜索步長小于定位精度，在現(xiàn)有的傳感器條件下導(dǎo)致高昂的時間成本，可能花費(fèi)數(shù)個小時才能完成一次定位。這一特點(diǎn)是本算法相較于蟻群等算法的主要優(yōu)勢，也是現(xiàn)有算法無法突破場地大小限制的核心原因。

其次，本算法具有收斂性。使用親代數(shù)據(jù)的定序排列作為判斷溯源結(jié)束的標(biāo)志，保證了數(shù)據(jù)更新的優(yōu)化趨勢，避免了各種群智能算法和加權(quán)質(zhì)心法中，迭代次數(shù)過多導(dǎo)致定位遠(yuǎn)離源點(diǎn)的情況。五代不更新的判斂條件是經(jīng)驗(yàn)結(jié)果，為保證收斂的可靠性，需要避免算法陷入共線陷阱，防止發(fā)生過早收斂。

由于本算法在運(yùn)算中利用的數(shù)據(jù)點(diǎn)較少，數(shù)據(jù)即時性較強(qiáng)，因而使系統(tǒng)的時間敏感性有所降低，提高了計算結(jié)果的可靠性。經(jīng)遺傳結(jié)構(gòu)保存下來的親代數(shù)據(jù)，基本上都是2～3min 以內(nèi)的測量結(jié)果，在變化不太劇烈的濃度場中基本符合靜態(tài)特征。

最后，由于該算法擺脫了對風(fēng)信息的高度依賴，也沒有形成對梯度信息的絕對依賴，故可以認(rèn)為其對于非湍流環(huán)境、湍流主控微弱的環(huán)境和湍流環(huán)境都具有一定的兼容性和適應(yīng)性。這一猜想仍有待實(shí)驗(yàn)驗(yàn)證。

本文在某些細(xì)節(jié)上仍然有待進(jìn)一步改進(jìn)，特別是有關(guān)維護(hù)溯源定位過程不進(jìn)入共線狀態(tài)的方法。當(dāng)算法陷入共線狀態(tài)時，容易失去三邊定位能力，近似退化為單純形算法，對算法的溯源能力形成一定的制約。與傳統(tǒng)算法相比，本算法在克服共線問題上已經(jīng)得到了大幅改善，但實(shí)驗(yàn)中，初始化親代數(shù)據(jù)和參數(shù)的選取方式等可能都對結(jié)果造成一定的影響。亦可以引入禁忌表或斥力因素等，保持親代坐標(biāo)點(diǎn)的離散狀態(tài)，使算法跳出共線陷阱。

表1 一輛小車與兩輛小車路徑規(guī)劃的平均時間成本Table1 Average time cost of one-car path planning and two-car path planning