張獻，任耀峰，王潤芃（海軍工程大學理學院，湖北武漢430033）

基于自適應遺傳算法的連續(xù)時空最優(yōu)搜索路徑規(guī)劃研究

張獻，任耀峰，王潤芃
（海軍工程大學理學院，湖北武漢430033）

針對連續(xù)時空最優(yōu)搜索者路徑問題，利用隨機微分方程描述Markov運動目標，建立了同時優(yōu)化搜索者方向和速度的規(guī)劃模型，并考慮了搜索速度對探測能力的影響。設計了一種新穎的自適應變異遺傳算法，算法采用較高的變異概率作用于父代精英個體組，通過引入3種控制因子對變異方向和幅度進行自適應控制，動態(tài)調(diào)節(jié)局部搜索和全局搜索的平衡。在對方向未知的逃離目標搜索算例中，得到了近似對數(shù)螺旋曲線的搜索路徑；在直升機搜索多目標的路徑規(guī)劃中，提供了合理有效的搜索方案。算法對比表明所給出的算法在全局優(yōu)化能力和穩(wěn)定性上有明顯的優(yōu)勢，適用于求解連續(xù)搜索路徑規(guī)劃問題。

運籌學；最優(yōu)搜索；連續(xù)時空；Markovian目標；自適應變異遺傳算法；反潛搜索

0　引言

最優(yōu)搜索者路徑問題（OSPP）是搜索論中搜索者運動受到約束的一類復雜優(yōu)化問題，要求搜索者在有限資源約束下，構造一個搜索路徑使得搜索效益最大，目前在海上救援、無人機偵查、反潛搜索[1-3]等諸多領域有廣泛的應用。

根據(jù)是否對時間和空間進行了離散化處理，OSPP可大致分為離散時空OSPP和連續(xù)時空OSPP兩類[4]。1986年Trummel和Weisinger已經(jīng)證明了在離散時間和空間下，對于靜止目標OSPP的復雜度至少是NP-hard[5].目前無論對于哪類問題，許多學者都將算法的設計與優(yōu)化作為問題研究的一個重要方向。在離散時空OSPP方面，已有較多的方法被采用，例如動態(tài)規(guī)劃技術[6]、分支定界法[7-9]、割平面法[10]、啟發(fā)式算法[3，11-12]。但由于離散化處理的需要，使得模型在目標和搜索者運動過程的表達上與實際情況相差較大。

為了使模型更貼近實際，部分文獻對更為復雜的連續(xù)時空OSPP展開了討論。Ohsumi[13]和朱清新等[14]利用最優(yōu)控制理論研究了此類問題，但是目標和搜索者的運動需要滿足嚴格的微分方程，這一要求局限了模型的應用范圍。在寬泛的問題描述下，Kierstead等[15]首次將遺傳算法（GA）應用于連續(xù)時空OSPP，針對一些探測環(huán)境復雜的搜索問題，提出了一種基于路徑幾何關系進行遺傳操作的GA，得到了令人滿意的搜索方案。Cho等[16-17]設計了一種基于搜索者方向編碼的高變異率GA，討論了靜止目標和簡單定向運動目標的搜索問題，相比Kierstead的算法優(yōu)化效果有所提高，體現(xiàn)出GA在求解此類搜索問題方面的優(yōu)勢。然而這兩種模型的不足之處是均假定目標為靜止或作簡單的勻速運動，搜索者的速度也為固定的，不利于實際應用。并且所給算法的優(yōu)化效果受初始種群的影響較大。

本文研究更為一般的連續(xù)時空Markov運動目標的搜索問題。首先利用隨機微分方程表達目標運動模型，同時考慮搜索速度對探測能力的影響，建立了搜索者模型，對搜索者方向和速度同時進行優(yōu)化。然后針對OSPP的特點，設計了一種自適應變異遺傳算法（AMGA）.該算法采用較高的變異概率作用于父代精英個體組，豐富了種群的多樣性；通過引入3種控制因子，對變異方向和幅度進行自適應控制，動態(tài)調(diào)節(jié)局部搜索和全局搜索的平衡，增強了算法的尋優(yōu)能力和穩(wěn)定性。最后通過仿真分析、實例應用及算法對比驗證了AMGA的有效性。

1　目標模型

文獻[15-17]在連續(xù)時空下討論了靜止目標和簡單定向運動目標的OSPP.為使模型更一般化，考慮一個R2空間中的連續(xù)時間Markov運動目標｛X（t），t≥0｝.利用隨機微分方程理論[18]對目標的運動過程進行描述：

式中：X（t）∈R2；b（t，x）：[0，+∞）×R2→R2，b（t，x）為漂移系數(shù)；α（t，x）：[0，+∞）×R2→R2×2，α（t，x）為擴散系數(shù)；B（t）是二維布朗運動；X0為初始位置。對（1）式的詳細表達為

在搜索問題中，X（t）表示目標的運動位置，b（t，X（t））表示目標的速度矢量，B（t）代表環(huán)境等因素的干擾，α（t，X（t））則表示干擾的幅度大小。這種隨機微分方程描述方法同時考慮了目標的運動參數(shù)以及環(huán)境等因素的影響，能夠較好地描述目標的運動狀態(tài)。

本文假定目標的運動不受搜索者策略的影響，即目標不會對搜索者的行為做出反應，所討論的問題屬于單向搜索范疇。

2　搜索者模型

2.1搜索者運動模型

在實際中，搜索雙方通常在一定時間段內(nèi)保持穩(wěn)定的運動方向和速度，每隔一段時間根據(jù)情況進行調(diào)整（如艦船和潛艇）?，F(xiàn)將方向、速度穩(wěn)定不變的運動過程視為一個階段（Step）.搜索路徑的表達包括以下幾個要素：搜索者起始坐標SS、搜索時間Ts、階段時長Stepts、方向θs和速度vs（下標s表示搜索者），其中θs∈[0，2π），vs∈[vmin，vmax].需要指出的是，本文模型忽略各階段在方向調(diào)整上所消耗的時間以及由此引起的路徑偏差。

在搜索路徑的優(yōu)化過程中，文獻[15-17]都將vs固定考慮，只將θs視為變量。為了更準確地描述實際問題，本文在階段時長Stepts視為常數(shù)的前提下，將方向θs和速度vs同時作為問題的決策變量進行優(yōu)化（見圖1）。

圖1　搜索路徑的表達Fig.1　Search path

圖1展示了一條簡單的搜索路徑：搜索者的搜索時間Ts=4 h，各階段時長Stepts=1 h，各階段的速度及方向如圖所示。由于考慮了搜索速度的變化，這里所討論的“搜索路徑”不只表示搜索者的運動軌跡，而且還包涵了路徑上的速度信息，實際上是一種搜索方案。為了便于敘述，本文仍使用“搜索路徑”一詞。

2.2探測模型

探測過程中，搜索者一般利用傳感器采集目標信息。聲納是艦艇搜索水下目標常用的設備之一，其探測概率是一個受物理環(huán)境、信號功率等多種因素影響的復雜函數(shù)。本文選用理想的探測模型，即當目標與搜索者的距離小于等于聲納作用距離L時，探測到目標的概率為1，否則為0.

實際問題中，搜索者速度往往會對探測能力產(chǎn)生影響，例如L會受到艦船自身噪聲的影響：通常當艦船速度低于某臨界值時，自身噪聲保持不變；當速度高于臨界值時，自身噪音會隨速度的加快而增強[19]。因此L與搜索速度有著一定關系，然而這種關系在實際中往往十分復雜。（2）式給出了一個簡單函數(shù)，表征路徑各階段的聲納作用距離與搜索速度間的關系，如圖2所示。

圖2　聲納作用距離與搜索速度的關系曲線Fig.2　Relation between detection rang and search velocity

3　自適應變異遺傳算法

本節(jié)針對連續(xù)時空OSPP，設計一種AMGA.

3.1問題描述

OSPP要求搜索者按照構造的物理路徑實施搜索，通過合理配置資源使得搜索效益最大。本文利用累積探測概率（CDP）[19]評價路徑的搜索效率，并作為搜索路徑規(guī)劃的目標函數(shù)和AMGA的適應度函數(shù)。在0≤t≤T時，對于任意一個可行的搜索方案ξ，t時刻的CDP記為FCDP（ξ，t），定義為時間段[0，t]內(nèi)至少一次探測到目標的概率

對于一般的搜索路徑，精確地求得FCDP的解析表達式是很困難的，可采用Monte Carlo方法近似計算[15-17]。

針對問題的特點，建立對搜索者方向和速度同時優(yōu)化的搜索路徑規(guī)劃模型如下：

式中：決策變量X=（x1，x2，…，x2N）T表示一種搜索路徑規(guī)劃方案，N表示搜索路徑階段總數(shù)，（x1，x2，…，xN）T和（xN+1，xN+2，…，x2N）T分別表示搜索路徑各階段的方向θS和速度vs；FCDP（X，t）表示t時刻沿搜索路徑X的累積探測概率，由于FCDP是t的單調(diào)遞增函數(shù)，一般 t取 Ts；變量的約束條件 Ψ=｛X|xi∈[ai，bi]｝，ai＜bi為實常數(shù)，i=1，2，…，2N，具體到問題中，Ψ=｛X|xi∈[0，2π]，1≤i≤N；xi∈[vmin，vmax]，N+1≤i≤2N｝.

3.2個體編碼方案

AMGA采用雙鏈實數(shù)編碼方案：每條染色體代表一條搜索路徑，由兩條并列的基因鏈組成，分別表示經(jīng)過實數(shù)編碼的搜索路徑的方向和速度。將遺傳種群記為，其中一條雙鏈染色體表示為

i=1，2，…，N；j=1，2，…，M；k=1，2，…，Gmax.

需要指出的是，在進化過程中雙鏈染色體上同基因位的基因θi、vi一同進行遺傳運算。

3.3遺傳操作

在遺傳操作方面，AMGA采用改進的交叉和變異算子引導種群進化。在詳細討論之前，需要強調(diào)一些重要參數(shù)的定義。

變異算子針對父代精英個體組實施變異操作，其中精英個體組為種群中適應度最高的一部分個體，將精英個體占種群的比例稱為精英個體比率，記為PE.在每代進化過程中，兩種遺傳算子是獨立運算的，得到的兩組新個體組成子代種群。分別將這兩組新個體占子代種群的比例稱為交叉概率和變異概率，記為PC和PM（PC+PM=1）.需要指出的是，這里對交叉概率和變異概率的定義與其他GA中的定義不完全相同。通過大量的實驗和參數(shù)對比，本文選取PE=0.15，PC=0.25，PM=0.75.

3.3.1交叉操作

交叉操作采用輪盤賭法[20]從父代中選取一組個體，通過兩兩單點交叉得到新個體，起到豐富種群多樣性的作用。其中交叉點在染色體長度的1/4～3/4處隨機選擇，選取交叉操作的個體數(shù)為PC×M.

3.3.2變異操作的改進思路

變異的方向和幅度直接影響算法的效率和收斂速度，但在一般GA的變異操作中，基因的變更常常只通過簡單地產(chǎn)生隨機數(shù)替換父代基因，顯然這種變異方式過于盲目。下面針對OSPP特點，從3個角度分析改進變異操作的措施：

1）利用父代最優(yōu)個體自適應控制變異方向。由于進化過程中父代最優(yōu)個體具有最高的適應度值，在種群中往往最接近全局最優(yōu)解。因此可以利用其信息控制變異方向，使被操作的個體向接近父代最優(yōu)個體的方向變異，引導種群進化。類似的思想在量子進化算法的旋轉(zhuǎn)門操作和粒子群算法的速度更新方程中都有所體現(xiàn)，但這些算法大都選取當前最優(yōu)個體來引導種群演化，而本文選取的是父代最優(yōu)個體，這樣可增強算法的全局搜索能力。

2）在搜索路徑的不同階段自適應控制變異幅度。在圖3中，將路徑1分別對不同階段的方向作幅度相同的變異操作得到路徑2和路徑3.從圖3中可以看出，階段越靠前，方向的變化對搜索路徑的改變越劇烈，即影響程度越大。將路徑3第一階段的速度作幅度相同的變異操作得到路徑4.從中可以看出速度對路徑的影響較小。變量類別與其變異時所處的階段對路徑的影響差異較大是OSPP與其他數(shù)值優(yōu)化問題的一個關鍵區(qū)別。因此變異幅度應根據(jù)變量的類別與其所處的階段自適應調(diào)整。

圖3　不同搜索階段方向和速度對搜索路徑的影響Fig.3　Effects of direction and velocity on search path in different search steps

3）根據(jù)不同進化階段自適應控制變異幅度。在進化前期變異有助于增加種群的多樣性，而在進化后期，優(yōu)秀個體逐漸接近最優(yōu)解，應避免劇烈變異（例如方向的180o旋轉(zhuǎn)）。因此變異幅度應隨進化代數(shù)的增加自適應減小。

文獻[16-17]給出了5種選取變異位置和變異基因個數(shù)的方法，并將其作用于父代最優(yōu)解。AMGA則從父代精英個體組中隨機選取PM×M個個體進行變異操作，進一步豐富種群的多樣性。

3.3.3自適應變異策略

基于上述思路，本文對變異操作進行改進，提出下面的自適應變異策略：

通過大量的實驗和參數(shù)對比，本文選取的常數(shù)值和控制因子由（6）式～（8）式給出。在這些參數(shù)選擇下，算法能夠發(fā)揮出最佳的優(yōu)化性能，得到穩(wěn)定的運算結(jié)果。

在變異方向控制因子Sgn（·）的設計上，利用父代最優(yōu)個體的引導作用，將被操作個體向逼近父代最優(yōu)個體的方向?qū)嵤┳儺?。首先將父代最?yōu)個體記為式中兩類方向控制因子Sgn（·）分別由（7）式、（8）式確定：

式中：R3和R4為區(qū)間[0，1]上的隨機數(shù)；R0為一個算法參數(shù)（0≤R0≤1），用于調(diào)節(jié)算法在局部搜索和全局搜索間的平衡，本文選取R0=0.8.

通過Sgn（·）得到的基因自適應變異方向，可以使被操作的搜索路徑不斷向父代最優(yōu)路徑靠近。（7）式的原理為：當π）且R3≤R0時，變異方向取 +1；當[-π，0）∪[π，2π）且R3≤R0時，變異方向取-1；當R3＞R0或時，變異方向取±1均可。因此基因θ的方向控制因子Sgn1（·）可簡化為（7）式。（8）式的原理更為簡單，在此不作贅述。

3.3.4自適應控制因子的分析

依據(jù)3.3.2節(jié)的3點改進思路，AMGA引入了3個控制因子Sgn、β和γ，設計了自適應變異策略。由（4）式可知，變異操作的方向由Sgn控制，幅度由D、R、β和γ共同控制。

引入方向控制因子Sgn后，算法利用父代最優(yōu)個體的信息自適應控制變異方向，加快了收斂速度。引入基因位控制因子β后，變異幅度隨著基因位的次序線性遞增，即在路徑中，階段越靠前，變異幅度越小，保證變異的高效性。引入進化代數(shù)控制因子γ后，在進化前期變異幅度大，可以廣泛搜索解空間，避免陷入局部最優(yōu)。在進化后期變異幅度自適應減小，通過對精英個體的微調(diào)，提高了變異效率。

總的來說，AMGA的主要優(yōu)點有：1）通過對變異方向和幅度的自適應控制，提高了變異效率，增強了尋優(yōu)能力；2）針對父代精英個體組實施變異操作，充分保留了父代有用的遺傳信息；3）采用較高的變異概率保證了種群的多樣性，有效避免了早熟收斂。因此AMGA在優(yōu)化過程中由“求泛”到“求精”自適應搜索，兼顧了多樣性和高效性，動態(tài)調(diào)節(jié)局部搜索和全局搜索的平衡，使算法收斂速度快、優(yōu)化結(jié)果穩(wěn)定。

3.4AMGA流程

步驟1 采用雙鏈實數(shù)編碼方案對染色體進行編碼，并初始化種群得到Pop（1），此時進化代數(shù)k=1.

步驟3 對算法終止條件的判斷。若進化代數(shù)k達到最大限制Gmax，終止運算，否則繼續(xù)進行。

步驟4 按照3.3節(jié)的方法對種群Pop（k）進行交叉和變異操作。

步驟5 遺傳操作得到的兩組新個體組成子代，同時進化代數(shù)k←k+1.轉(zhuǎn)至步驟2.

4　仿真驗證

4.1算例描述

假設T=0 h時刻，在某海域探測到敵潛艇目標在TS點出水，隨后潛入水下，并迅速逃離出水點。我方艦艇獲悉情報后，趕往敵情區(qū)域展開反潛搜索。依據(jù)此背景，分別對目標和搜索者進行具體描述。

首先，討論目標的運動規(guī)則。根據(jù)（1）式利用目標起始坐標 TS、速度 vT、方向 θT和階段時長SteptT（下標T表示目標）對目標加以表達，并利用Monte Carlo方法對目標運動路徑進行仿真，其運動規(guī)則見圖4.（1）式中，速度矢量b（t，X）的方向為θT，其模值為vT.對于表征干擾因素的α（t，X（t））d B（t），仿真中利用一種二維正態(tài)噪聲Φ代替并作用于目標運動的各個階段。圖4中，目標在第二階段按照初始航向航速應運動到位置X′（t），由于受到干擾實際運動到位置X（t）.

接下來，對目標運動路徑進行仿真。已知目標起始坐標為TS=（120 nmile，120 nmile），假定目標的速度vT服從μvT=10 kn，σvT=1 kn的正態(tài)分布；階段時長SteptT服從[1/3 h，1 h]的均勻分布；目標第一階段方向θ1服從[0 rad，2πrad]的均勻分布，其余階段方向θi=θ1（i＞1）.二維正態(tài)噪聲Φ的均值μΦ1= μΦ2=0nmile，標準差σΦ1=σΦ2= 0.2 n mile，相關系數(shù)ρΦ1，Φ2=0.目標路徑的仿真次數(shù)NT=10 000次，目標分布見圖5.

圖4　Markovian目標的運動規(guī)則Fig.4　Movement rules of Markovian target

圖5　T=3 h和T=10 h時刻目標分布圖Fig.5　The distribution of targets at T=3 h and T=10 h

最后，給出搜索者的相關參數(shù)。搜索者在T= 0 h時刻展開搜索，起始位置坐標SS=（100 n mile，100 n mile），給定搜索時間Ts=10 h，取各階段時長Stepts=0.5 h，則階段總數(shù)NStep=20.各階段方向θs∈[0 rad，2πrad），速度vs∈[10 kn，25 kn]，則變量總數(shù)為40.在探測方面，聲納作用距離隨速度變化的函數(shù) L（vs）見（2）式，探測時間間隔ΔtD= 0.1 h.每條搜索路徑CDP的計算公式為

式中：NT為目標仿真的總數(shù)；ND（t）為已探測到的目標個數(shù)。

4.2算法實現(xiàn)與結(jié)果分析

首先，針對仿真算例，給出一個簡單的種群初始化方法：初始搜索方案為勻速直線運動，路徑方向在SS與TS連線左右各60°的扇面內(nèi)等間隔選取，初始搜索路徑的速度在[10 kn，25 kn]內(nèi)隨機選取，路徑分布見圖6.

圖6　初始搜索方案的路徑分布Fig.6　The distribution of initial search paths

然后，利用AMGA求解本算例。設定算法參數(shù)為：種群規(guī)模M=100，染色體長度N=20，最大遺傳代數(shù)Gmax=100，精英個體比率PE=0.15，交叉概率PC=0.25，變異概率PM=0.75.在100次獨立的仿真實驗中，AMGA按照上述初始搜索方案進行運算，最終得到的“最優(yōu)”搜索路徑如圖7所示，其累積探測概率FCDP（10）=48.53%，平均速度各階段速度由（9）式給出（為便于分析已將速度取整）：

圖7　所得最優(yōu)搜索路徑與對數(shù)螺旋曲線搜索路徑Fig.7　Optimal search path found by AMGA and logarithmic spiral search path

下面對仿真結(jié)果進行分析。從AMGA的運算結(jié)果可以看出“最優(yōu)”搜索路徑有如下兩個特點：

1）搜索速度自動優(yōu)化調(diào)節(jié)。算例中，搜索者各階段速度vs的取值范圍為[10 kn，25 kn]，速度與探測能力的函數(shù)關系由（2）式給出。經(jīng)AMGA逐步優(yōu)化，求得的“最優(yōu)”搜索者路徑具有一定的“智能”性：路徑各階段大都沒有選擇速度最快時的25 kn，也沒有選擇聲吶作用距離L最大時的0～15 kn，而是基本選取了20 kn左右的速度，兼顧了探測能力與速度的大小，反映出AMGA對求解OSPP有較強的優(yōu)化能力。

2）搜索路徑接近于對數(shù)螺旋線。在搜索速度固定不變的條件下，對向四周作勻速直線運動的逃離目標這一簡單搜索問題，理論上證明了搜索者應采用螺旋搜索方法[21]，即搜索路徑是一條光滑的對數(shù)螺旋線。

式中：r為螺旋半徑；φ為極角；（r0，φ0）為螺旋線開始點；系數(shù)k=tan[arcsin（vT0/vs0）]，vT0為目標固定的速度，vs0為搜索者固定的速度。本文討論的是向四周作Markov運動的逃離目標搜索問題，且搜索速度對探測能力有一定的影響，相比上述問題更為復雜，但有相似之處。由AMGA得到的“最優(yōu)”搜索路徑與對數(shù)螺旋線比較吻合（見圖7），一定程度上表明該算法在求解OSPP上具有較高的有效性。在本例中，（10）式的參數(shù)為vT0==10 kn，vs0== 20.3 kn，（r0，φ0）=（10 n mile，-π/2 rad），即方程r（φ）=10exp[0.566·（φ+π/2）].

在實際的搜索問題中，目標的運動復雜多變，搜索者需要根據(jù)環(huán)境的變化實施靈活的機動。解析方法通常需要利用嚴格的方程描述問題，應用范圍受限。相比而言，AMGA對問題的約束更為寬松，特別是在對搜索雙方運動的表達上。因此AMGA在求解連續(xù)時空OSPP方面有較大的應用范圍和潛力。

4.3算法對比與性能驗證

利用AMGA、Cho等[16]提出的GA*和Kierstead等[15]提出的GA#分別求解仿真算例，為使對比效果的可信度更高，3種算法采用相同的種群初始化方法（見4.2節(jié)），最大遺傳代數(shù)Gmax均為100.GA*的參數(shù)設置[16]：M=128，PS=0.25，PC=0.125，PM= 0.625.GA#的參數(shù)設置[15]：M=120，PS=0.05，PC=0.95×0.9，PClone=0.95×0.1，PM=0.05.以上參數(shù)的具體意義請參見相關文獻。運算結(jié)果見表1.

表1　不同算法的結(jié)果對比（100次運算）Tab.1　Calculated results of different algorithms （100 calculations）

表1中的種群規(guī)模表示算法種群中的個體總數(shù)，其值越大，算法往往越易獲得更優(yōu)的結(jié)果；最劣值表示算法100次運算結(jié)果中最差的累積探測概率FCDP；最優(yōu)值表示算法100次運算結(jié)果中最佳的FCDP；方差值表示算法100次運算結(jié)果的方差，其往往能反應出算法的穩(wěn)定性；平均值表示算法100次運算結(jié)果的均值，其可以反映出算法的全局優(yōu)化能力；相對增幅是指AMGA的平均值指標對于其他算法平均值指標的相對增長幅度。

由表1不難看出，在相同的種群初始化方法下，AMGA種群的數(shù)量最少但FCDP的平均值最高，最優(yōu)值和最劣值相差最小，且FCDP的方差值最小，體現(xiàn)出AMGA較強的全局優(yōu)化能力和穩(wěn)定性。在平均值指標上，AMGA相比 GA*、GA#的相對增長幅度為18.8%和10.3%，體現(xiàn)出AMGA顯著的性能優(yōu)勢。

圖8、圖9分別展示了 AMGA、GA*和 GA#100次運算結(jié)果中最優(yōu)的10條搜索路徑。由于目標時空分布的對稱性，最優(yōu)的搜索者路徑存在兩種情況，即搜索方向為順時針和逆時針。從圖8中可以直觀地看出，作為一種隨機優(yōu)化算法，AMGA求得了這兩種最優(yōu)路徑。同時AMGA的穩(wěn)定性好，所得路徑相似度高，可視為收斂。而圖9中，GA*和GA#所得的路徑差異相對較大，體現(xiàn)出算法都不夠穩(wěn)定，容易早熟。

圖8　AMGA求得的10條最優(yōu)搜索者路徑Fig.8　10 optimal search paths obtained by AMGA

圖9　GA*和GA#求得的10條最優(yōu)搜索者路徑Fig.9　10 optimal search paths obtained by GA*and GA#

因而，AMGA相比GA*和GA#在求解復雜OSPP上，優(yōu)化效果有明顯提高。

5　實例應用

2000年美國科爾號驅(qū)逐艦在也門亞丁港遭遇了基地組織的小艇襲擊，損失慘重。隨后不久，美國海軍開始組織多艘小艇攻擊艦艇的演習科目[22]。2008年，我國海軍開始在亞丁灣索馬里海域執(zhí)行護航任務，護航編隊常常需要搜索海盜的快速小艇[23-24]。從上述事件中不難看出，有效地保護一個高價值單元，例如航母、主艦或商船，免受小艇的襲擊，是各國海軍所面臨的一個重要問題[22]。針對這一類問題，F(xiàn)oraker等利用最優(yōu)控制模型討論了連續(xù)時空多目標搜索問題[25-26]，給出了問題的離散化形式及數(shù)值求解算法和實例計算結(jié)果。本節(jié)選用文獻[26]中的部分實例，進一步驗證AMGA的有效性。

已知在70 n mile×70 n mile的海域上，一艘主艦在t∈[0 h，1 h]內(nèi)由初始位置（35 nmile，0 nmile）以25 kn的速度沿正北方向勻速航行[22，26]。在此期間，敵方10艘快速小艇間隔1.5 n mile由東側(cè)（70 n mile，6 n mile）～（70 n mile，51.5 n mile）區(qū)域進入該海域，并以最短的時間攻擊主艦。其中敵目標群進入該海域的初始時間和初始位置服從均勻分布，在駛?cè)肭澳繕俗鲃蛩僦本€運動。為保護主艦安全，直升機由初始位置（23.8 n mile，27.4 n mile）出發(fā)，開始執(zhí)行目標搜索任務（見圖10）.

圖10　AMGA求得的最優(yōu)搜索路徑Fig.10　The optimal search path found by AMGA

文獻[25]建立了最優(yōu)控制模型，以最小化未發(fā)現(xiàn)任何一個目標的概率（記作FP（t））作為目標函數(shù)，對搜索路徑進行規(guī)劃，并討論了計算FP（t）的離散化形式。按照文獻[26]建立的目標模型和求解方法[27-28]，通過離散化參數(shù)空間，實現(xiàn)了不同初始條件的目標仿真（圖10展示了部分目標路徑），其中目標群進入此海域的初始時間和初始位置的離散化規(guī)模均為25，記作δ=（25，25）.

下面利用AMGA算法，對搜索路徑進行規(guī)劃。其中搜索時間Ts=1 h，搜索路徑的階段總數(shù)NStep= 15，各階段時長Stepts=1/15 h，搜索速度為120 kn，探測時間間隔為0.01 h.算法的最大遺傳代數(shù)Gmax=120，其余參數(shù)設置與第4節(jié)的相同。經(jīng)50次獨立運算，AMGA求得的目標函數(shù)均值= 0.023 9，方差為2.8×10-8，其中最佳路徑的FP（t）= 0.023 6，即 10艘小艇均未被探測到的概率為0.023 6，最優(yōu)的搜索路徑如圖10所示。

由圖10可以看出，按照最優(yōu)搜索策略，直升機先沿直線迅速駛向敵情區(qū)域的偏南部分，然后向北搜索，最后在目標可能出現(xiàn)區(qū)域的中央反復巡邏，執(zhí)行搜索和警戒任務，兼顧了不同區(qū)域目標的探測。

Foraker等在文獻[26]中給出了不同離散化規(guī)模δ對應的最優(yōu)結(jié)果FP（t）.利用AMGA經(jīng)10次獨立運算求得最優(yōu)結(jié)果，對比如表2所示。

表2　算法對比Tab.2　Comparison between algorithms

需要指出的是，目標路徑受初始參數(shù)的影響較大，離散化規(guī)模的不同會使仿真計算發(fā)生變化。通過表2的縱向?qū)Ρ炔浑y看出，在6種不同δ規(guī)模下，本文算法有5種結(jié)果優(yōu)于Foraker等[26]求得的最優(yōu)值，說明了AMGA擁有更好地尋優(yōu)能力，也適用于求解直升機搜索水面目標的搜索路徑規(guī)劃問題。同時AMGA所得結(jié)果方差較小，表明了算法優(yōu)化能力穩(wěn)定。

6　結(jié)論

本文針對連續(xù)時空Markov運動目標的OSPP進行了研究，建立了同時優(yōu)化搜索者方向和速度的搜索路徑規(guī)劃模型。針對問題特點，設計了一種新穎的AMGA.該算法主要利用對方向和幅度自適應控制的方法改進了變異操作，增強了算法的尋優(yōu)能力和穩(wěn)定性，在仿真實驗及實例應用中得到了滿意的搜索方案，對求解連續(xù)時空OSPP具有一定啟發(fā)意義與應用價值。

（References）

[1]Lavis B，F(xiàn)urukawa T，Durrant-Whyte H F.Dynamic space reconflguration for Bayesian search and tracking with moving targets [J].Autonomous Robots，2008，24（4）：387-399.

[2]吳文超，黃長強，宋磊，等.不確定環(huán)境下的多無人機協(xié)同搜索航路規(guī)劃[J].兵工學報，2011，32（11）：1337-1342. WUWen-chao，HUANGChang-qiang，SONG Lei，et al.Cooperative search and path planning ofmulti-unmanned air vehicles in uncertain environment[J].Acta Armamentarii，2011，32（11）：1337-1342.（in Chinese）

[3]Hong SP，Cho S J，Park M J.A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search[J].European Journal of Operational Research，2009，193（2）：351-364.

[4]Stone L D.What's happened in search theory since the1975 Lanchester prize？[J].Operations Research，1989，37（3）：501-506.

[5]Trummel K E，Weisinger J R.The complexity of the optimal searcher path problem[J].Operations Research，1986，34（2）：324-327.

[6]Eagle JN.The optimal search for amoving targetwhen the search path is constrained[J].Operations Research，1984，32（5）：1107-1115.

[7]Eagle JN，Yee JR.An optimal Branch-and-Bound procedure for the constrained path，moving target search problem[J].Operations Research，1990，38（1）：110-114.

[8]Lau H，Huang S，Dissanayake G.Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times [J].European Journal of Operational Research，2008，190（2）：383-397.

[9]Sato H，Royset JO.Path optimization for the resource-constrained searcher[J].Naval Research Logistics，2010，57（5）：422-440.

[10]Royset J O，Sato H.Route optimization for multiple searchers [J].Naval Research Logistics，2010，57（8）：701-717.

[11]Hong SP，Cho S J，Park M J，et al.Optimal search-relocation trade-off in Markovian-target searching[J].Computers&Operations Research，2009，36（6）：2097-2104.

[12]楊日杰，吳芳，徐俊艷，等.基于馬爾可夫過程的水下運動目標啟發(fā)式搜索[J].兵工學報，2010，31（5）：586-591. YANG Ri-jie，WU Fang，XU Jun-yan，et al.Heuristic search formoving underwater targets based on Markov process[J].Acta Armamentarii，2010，31（5）：586-591.（in Chinese）

[13]Ohsumi A.Optimal searching for a Markovian-target[J].Naval Research Logistics，1991，38（4）：531-554.

[14]朱清新，卿利，彭博.隨機運動目標搜索問題的最優(yōu)控制模型[J].控制理論與應用，2007，24（5）：841-845. ZHU Qing-xin，QING Li，PENG Bo.Optimal control model of search problem for randomly moving targets[J].Control Theory &Applications，2007，24（5）：841-845.（in Chinese）

[15]Kierstead D P，DelBalzo D R.A genetic algorithm applied to planning search paths in complicated environments[J].Military Operations Research，2003，8（2）：45-59.

[16]Cho JH，Kim JS，Lim JS，et al.Optimal acoustic search path planning for sonar system based on genetic algorithm[J].International Journal of Offshore and Polar Engineering，2007，17 （3）：218-224.

[17]Cho JH，Kim JS.Benchmarking of optimal acoustic search path planning[C]//Proceedings of the 19th International Offshore and Polar Engineering Conference.Osaka，Japan：International Society of Offshore and Polar Engineers，2009：620-626.

[18]厄克森達爾B.隨機微分方程導論與應用[M].第6版.劉金山，吳付科，譯.北京：科學出版社，2012. Oksendal B.Stochastic differential equations[M].6th ed.LIU Jinshan，WU Fu-ke，translated.Beijing：Science Press，2012.（in Chinese）

[19]瓦格納D H，邁蘭德W，森德T J.海軍運籌分析[M].第3版.姜青山，鄭保華，譯.北京：國防工業(yè)出版社，2008：207-212. Wagner D H，Charles Mylander W，Sanders T J.Naval operations analysis[M].3rd ed.JIANGQing-shan，ZHENG Bao-hua，translated.Beijing：National Defense Industry Press，2008：207-212.（in Chinese）

[20]李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].北京：科學出版社，2002. LIMin-qiang，KOU Ji-song，LIN Dan，et al.The basic theory and applications of genetic algorithm[M].Beijing：Science Press，2002.（in Chinese）

[21]李乃奎，崔同生.軍事運籌學基礎理論教程[M].北京：國防大學出版社，2005. LINai-kui，CUI Tong-sheng.Basic theory of military operation research[M].Beijing：National Defense University Press，2005. （in Chinese）

[22]Foraker J.Optimal search for moving targets in continuous time and space using consistent approximations[D].Monterey，California：Naval Postgraduate School，2011.

[23]肖洋，柳思思.索馬里海盜的“恐怖主義化”及對策[J].當代世界，2010（1）：57-59. XIAO Yang，LIU Si-si.“Terrorism”of Somalipirates and countermeasures[J].The Contemporary World，2010（1）：57-59. （in Chinese）

[24]邵哲平，潘家財.亞丁灣水域交通特征分析及防海盜策略研究[J].中國航海，2011，34（4）：119-122. SHAO Zhe-ping，PAN Jia-cai.Analysis of the Gulf of Aden's traffic characteristics and study of anti-piracy strategy[J].Navigation of China，2011，34（4）：119-122.（in Chinese）

[25]Foraker J，Royset J O，Kaminer I.Search-trajectory optimization：part I，formulation and theory[J/OL].Journal of Optimization Theory and Applications，2015.doi：10.1007/s10957-015-0768-y.

[26]Foraker J，Royset J O，Kaminer I.Search-trajectory optimization：part II，algorithms and computations[J/OL].Journal of Optimization Theory and Applications，2015.doi：10.1007/ s10957-015-0770-4.

[27]Yakimenko O.Directmethod for rapid prototyping of near-optimal aircraft trajectories[J].Journal of Guidance，Control，and Dynamics，2000，23（5）：865-875.

[28]Ghabcheloo R，Kaminer I，Aguiar A，et al.A general framework formultiple vehicle time-coordinated path following control[C]∥American Control Conference.St Louis，Missouri，US：the American Automatic Control Council，2009：3071-3076.

Research on Optimal Search Path Programm ing in Continuous Time and Space Based on an Adaptive Genetic Algorithm

ZHANG Xian，REN Yao-feng，WANG Run-peng
（College of Science，Naval University of Engineering，Wuhan 430033，Hubei，China）

A Markovian-targetmodel based on stochastic differential equations and a path programming modelwith both searcher's direction and velocity treated as decision variables are presented for optimal searcher path problem in continuous time and space，and the effectof searcher's velocity on the detection ability is considered.A genetic algorithm with adaptivemutation is designed by introducing three kinds of control factors，which fulfills the adaptive control of the direction and range ofmutation and dynamically regulates the balance between local search and global search.In an example of searching a targetwith a random escaping direction，an approximate logarithmic spiral path is found.Moreover，the algorithm provides a reasonable and effective search scheme in a path programming problem for a helicopter searching multiple targets.The results indicate that the proposed algorithm has the significantadvantages of stability and global optimizing ability in comparison with othermethods，and is well suitable for the search path programming problem in continuous time and space.

operations research；optimal search；continuous time and space；Markovian target；genetic algorithm with adaptivemutation；anti-submarine search

O229；E917

A

1000-1093（2015）12-2386-10

10.3969/j.issn.1000-1093.2015.12.024

2014-09-03

全軍軍事學研究生課題（2011JY002-423）

張獻（1990—），男，博士研究生。E-mail：919453887@qq.com；任耀峰（1959—），男，教授，博士生導師。E-mail：renyaofeng@sina.com