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

張獻(xiàn)，任耀峰，王潤(rùn)芃（海軍工程大學(xué)理學(xué)院，湖北武漢430033）

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

張獻(xiàn)，任耀峰，王潤(rùn)芃
（海軍工程大學(xué)理學(xué)院，湖北武漢430033）

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

運(yùn)籌學(xué)；最優(yōu)搜索；連續(xù)時(shí)空；Markovian目標(biāo)；自適應(yīng)變異遺傳算法；反潛搜索

0　引言

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

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

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

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

1　目標(biāo)模型

文獻(xiàn)[15-17]在連續(xù)時(shí)空下討論了靜止目標(biāo)和簡(jiǎn)單定向運(yùn)動(dòng)目標(biāo)的OSPP.為使模型更一般化，考慮一個(gè)R2空間中的連續(xù)時(shí)間Markov運(yùn)動(dòng)目標(biāo)｛X（t），t≥0｝.利用隨機(jī)微分方程理論[18]對(duì)目標(biāo)的運(yùn)動(dòng)過(guò)程進(jìn)行描述：

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

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

本文假定目標(biāo)的運(yùn)動(dòng)不受搜索者策略的影響，即目標(biāo)不會(huì)對(duì)搜索者的行為做出反應(yīng)，所討論的問(wèn)題屬于單向搜索范疇。

2　搜索者模型

2.1搜索者運(yùn)動(dòng)模型

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

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

圖1　搜索路徑的表達(dá)Fig.1　Search path

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

2.2探測(cè)模型

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

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

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

3　自適應(yīng)變異遺傳算法

本節(jié)針對(duì)連續(xù)時(shí)空OSPP，設(shè)計(jì)一種AMGA.

3.1問(wèn)題描述

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

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

針對(duì)問(wèn)題的特點(diǎn)，建立對(duì)搜索者方向和速度同時(shí)優(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時(shí)刻沿搜索路徑X的累積探測(cè)概率，由于FCDP是t的單調(diào)遞增函數(shù)，一般 t取 Ts；變量的約束條件 Ψ=｛X|xi∈[ai，bi]｝，ai＜bi為實(shí)常數(shù)，i=1，2，…，2N，具體到問(wèn)題中，Ψ=｛X|xi∈[0，2π]，1≤i≤N；xi∈[vmin，vmax]，N+1≤i≤2N｝.

3.2個(gè)體編碼方案

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

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

需要指出的是，在進(jìn)化過(guò)程中雙鏈染色體上同基因位的基因θi、vi一同進(jìn)行遺傳運(yùn)算。

3.3遺傳操作

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

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

3.3.1交叉操作

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

3.3.2變異操作的改進(jìn)思路

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

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

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

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

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

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

3.3.3自適應(yīng)變異策略

基于上述思路，本文對(duì)變異操作進(jìn)行改進(jìn)，提出下面的自適應(yīng)變異策略：

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

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

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

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

3.3.4自適應(yīng)控制因子的分析

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

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

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

3.4AMGA流程

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

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

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

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

4　仿真驗(yàn)證

4.1算例描述

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

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

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

圖4　Markovian目標(biāo)的運(yùn)動(dòng)規(guī)則Fig.4　Movement rules of Markovian target

圖5　T=3 h和T=10 h時(shí)刻目標(biāo)分布圖Fig.5　The distribution of targets at T=3 h and T=10 h

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

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

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

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

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

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

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

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

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

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

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

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

4.3算法對(duì)比與性能驗(yàn)證

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

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

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

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

圖8、圖9分別展示了 AMGA、GA*和 GA#100次運(yùn)算結(jié)果中最優(yōu)的10條搜索路徑。由于目標(biāo)時(shí)空分布的對(duì)稱性，最優(yōu)的搜索者路徑存在兩種情況，即搜索方向?yàn)轫槙r(shí)針和逆時(shí)針。從圖8中可以直觀地看出，作為一種隨機(jī)優(yōu)化算法，AMGA求得了這兩種最優(yōu)路徑。同時(shí)AMGA的穩(wěn)定性好，所得路徑相似度高，可視為收斂。而圖9中，GA*和GA#所得的路徑差異相對(duì)較大，體現(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#在求解復(fù)雜OSPP上，優(yōu)化效果有明顯提高。

5　實(shí)例應(yīng)用

2000年美國(guó)科爾號(hào)驅(qū)逐艦在也門亞丁港遭遇了基地組織的小艇襲擊，損失慘重。隨后不久，美國(guó)海軍開始組織多艘小艇攻擊艦艇的演習(xí)科目[22]。2008年，我國(guó)海軍開始在亞丁灣索馬里海域執(zhí)行護(hù)航任務(wù)，護(hù)航編隊(duì)常常需要搜索海盜的快速小艇[23-24]。從上述事件中不難看出，有效地保護(hù)一個(gè)高價(jià)值單元，例如航母、主艦或商船，免受小艇的襲擊，是各國(guó)海軍所面臨的一個(gè)重要問(wèn)題[22]。針對(duì)這一類問(wèn)題，F(xiàn)oraker等利用最優(yōu)控制模型討論了連續(xù)時(shí)空多目標(biāo)搜索問(wèn)題[25-26]，給出了問(wèn)題的離散化形式及數(shù)值求解算法和實(shí)例計(jì)算結(jié)果。本節(jié)選用文獻(xiàn)[26]中的部分實(shí)例，進(jìn)一步驗(yàn)證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ū)域進(jìn)入該海域，并以最短的時(shí)間攻擊主艦。其中敵目標(biāo)群進(jìn)入該海域的初始時(shí)間和初始位置服從均勻分布，在駛?cè)肭澳繕?biāo)作勻速直線運(yùn)動(dòng)。為保護(hù)主艦安全，直升機(jī)由初始位置（23.8 n mile，27.4 n mile）出發(fā)，開始執(zhí)行目標(biāo)搜索任務(wù)（見(jiàn)圖10）.

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

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

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

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

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

表2　算法對(duì)比Tab.2　Comparison between algorithms

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

6　結(jié)論

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

（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]吳文超，黃長(zhǎng)強(qiáng)，宋磊，等.不確定環(huán)境下的多無(wú)人機(jī)協(xié)同搜索航路規(guī)劃[J].兵工學(xué)報(bào)，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]楊日杰，吳芳，徐俊艷，等.基于馬爾可夫過(guò)程的水下運(yùn)動(dòng)目標(biāo)啟發(fā)式搜索[J].兵工學(xué)報(bào)，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]朱清新，卿利，彭博.隨機(jī)運(yùn)動(dòng)目標(biāo)搜索問(wèn)題的最優(yōu)控制模型[J].控制理論與應(yīng)用，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]厄克森達(dá)爾B.隨機(jī)微分方程導(dǎo)論與應(yīng)用[M].第6版.劉金山，吳付科，譯.北京：科學(xué)出版社，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.海軍運(yùn)籌分析[M].第3版.姜青山，鄭保華，譯.北京：國(guó)防工業(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]李敏強(qiáng)，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，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]李乃奎，崔同生.軍事運(yùn)籌學(xué)基礎(chǔ)理論教程[M].北京：國(guó)防大學(xué)出版社，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]肖洋，柳思思.索馬里海盜的“恐怖主義化”及對(duì)策[J].當(dāng)代世界，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]邵哲平，潘家財(cái).亞丁灣水域交通特征分析及防海盜策略研究[J].中國(guó)航海，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

全軍軍事學(xué)研究生課題（2011JY002-423）

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