張　獻(xiàn), 任耀峰, 沈　靜

(海軍工程大學(xué)理學(xué)院, 湖北 武漢 430033)

?

連續(xù)時(shí)空最優(yōu)搜索者路徑問題的改進(jìn)雙鏈遺傳算法

張獻(xiàn), 任耀峰, 沈靜

(海軍工程大學(xué)理學(xué)院, 湖北 武漢 430033)

摘要：針對(duì)連續(xù)時(shí)空馬爾可夫運(yùn)動(dòng)目標(biāo)的最優(yōu)搜索者路徑問題(optimal searcher path problem,OSPP),建立了搜索者方向和速度均作為決策變量的搜索路徑規(guī)劃模型,給出了一種改進(jìn)的雙鏈遺傳算法(improved double chains genetic algorithm,IDCGA)。算法采用雙鏈實(shí)數(shù)編碼策略表達(dá)搜索路徑,利用混沌初始化方法產(chǎn)生初始種群,提出了變異幅度自適應(yīng)控制的方法,通過引入基因位自適應(yīng)因子η和進(jìn)化代數(shù)自適應(yīng)因子λ對(duì)變異操作進(jìn)行了改進(jìn)。以反潛搜索問題為例進(jìn)行的仿真實(shí)驗(yàn)表明,所提出的算法具有穩(wěn)定性好、尋優(yōu)能力強(qiáng)、收斂速度快等優(yōu)點(diǎn),適用于求解復(fù)雜搜索路徑問題。

關(guān)鍵詞：最優(yōu)搜索者路徑; 連續(xù)時(shí)空; 馬爾可夫目標(biāo); 雙鏈遺傳算法; 自適應(yīng)變異

0引言

搜索論是主要研究利用探測(cè)手段尋找指定目標(biāo)優(yōu)化方案的理論和方法,起源于二戰(zhàn)時(shí)期美國反潛運(yùn)籌小組對(duì)德國潛艇進(jìn)行搜索的一系列研究工作。1956～1980年,在眾多學(xué)者的努力下[1-3],取得了一批主要針對(duì)靜止目標(biāo)和運(yùn)動(dòng)目標(biāo)最優(yōu)搜索資源分配問題的理論成果,奠定了搜索論的理論基礎(chǔ)。無論在離散時(shí)空還是連續(xù)時(shí)空,此類問題都要求搜索資源能夠任意細(xì)分,同時(shí)搜索者的運(yùn)動(dòng)能力不受約束,可在搜索空間內(nèi)任意轉(zhuǎn)移并分配搜索資源。

OSPP是搜索論中搜索者運(yùn)動(dòng)受到約束的一類復(fù)雜優(yōu)化問題,要求搜索者在有限資源約束下,構(gòu)造一個(gè)搜索路徑使得搜索效益最大。1986年,Trummel已經(jīng)證明OSPP是一個(gè)NP完備性問題[4]。許多學(xué)者采用分支定界法[5-7]、割平面法[8]、啟發(fā)式算法[9-10]、貪婪算法[11]等方法進(jìn)行了研究。這些方法都需要進(jìn)行離散化,先將搜索空間分割成許多單元格,目標(biāo)被限制在單元格中,大多被假定為靜止或作離散狀態(tài)的Markov運(yùn)動(dòng),搜索者在單元格中進(jìn)行搜索,探測(cè)僅作用于搜索者所處的單元格內(nèi)。由于問題的復(fù)雜性,算法的設(shè)計(jì)常在優(yōu)化效果與計(jì)算時(shí)間上折中。目前，尚未找到一種具有一般性的有效算法來解決該問題[12]。

為使模型更貼近實(shí)際,部分文獻(xiàn)討論了更為復(fù)雜的連續(xù)時(shí)空OSPP。其中文獻(xiàn)[13-14]利用了最優(yōu)控制理論,但要求目標(biāo)和搜索者的運(yùn)動(dòng)滿足嚴(yán)格的微分方程。文獻(xiàn)[15]首次將遺傳算法(genetic algorithm,GA)應(yīng)用于連續(xù)時(shí)空OSPP,所得效果令人鼓舞,體現(xiàn)出GA求解復(fù)雜路徑規(guī)劃的優(yōu)勢(shì)。文獻(xiàn)[16]提出一種對(duì)搜索者方向編碼的高變異率GA,討論了靜止目標(biāo)和簡(jiǎn)單定向運(yùn)動(dòng)目標(biāo)的搜索問題,算例結(jié)果表明該算法相比文獻(xiàn)[15]的算法對(duì)求解OSPP的效果有明顯提高。

本文研究目標(biāo)運(yùn)動(dòng)為時(shí)空連續(xù)馬爾可夫過程的OSPP,使問題更為一般化。首先建立了目標(biāo)和搜索者的運(yùn)動(dòng)模型,將搜索者方向和速度均作為決策變量,提出變異幅度自適應(yīng)控制的方法,給出了IDCGA。最后將算法應(yīng)用于兩個(gè)仿真例子,通過算法對(duì)比驗(yàn)證了IDCGA的有效性。改進(jìn)的算法具有穩(wěn)定性好、尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn),適用于求解復(fù)雜搜索路徑問題。研究成果對(duì)求解OSPP具有一定應(yīng)用價(jià)值。

1連續(xù)Markov運(yùn)動(dòng)目標(biāo)模型

連續(xù)時(shí)空下,文獻(xiàn)[15-16]討論了靜止目標(biāo)和簡(jiǎn)單定向運(yùn)動(dòng)目標(biāo)的OSPP,本文考慮更為復(fù)雜的馬爾可夫運(yùn)動(dòng)目標(biāo)。假定目標(biāo)位置是一個(gè)狀態(tài)空間為R2,時(shí)間集為[0,+∞)的二維馬爾可夫過程{X(t),t≥0},即目標(biāo)的位置具有無后效性:如果已知目標(biāo)現(xiàn)在時(shí)刻t′所處的狀態(tài),則目標(biāo)將來時(shí)刻t(t>t′)所處位置的概率分布只與目標(biāo)現(xiàn)在所處的位置有關(guān),而與目標(biāo)過去的位置無關(guān)。對(duì)于一般馬爾可夫運(yùn)動(dòng)目標(biāo)的轉(zhuǎn)移概率分布函數(shù)F(X,t|X′,t′)的解析表達(dá)式不易求出,可通過蒙特卡羅方法及概率統(tǒng)計(jì)近似計(jì)算。

本文討論的搜索問題屬搜索論中的單向搜索范疇,即目標(biāo)不能對(duì)搜索者的行為做出反應(yīng),其運(yùn)動(dòng)不受搜索者策略影響。同時(shí)，不考慮深度,搜索者和目標(biāo)在2維空間內(nèi)運(yùn)動(dòng)。

2搜索路徑的表達(dá)

實(shí)際問題中,目標(biāo)和搜索者通常在一定時(shí)間段內(nèi)保持穩(wěn)定的運(yùn)動(dòng)方向和速度,每隔一段時(shí)間根據(jù)情況進(jìn)行調(diào)整(如艦船和潛艇)。

現(xiàn)把方向、速度穩(wěn)定不變的運(yùn)動(dòng)過程視為一個(gè)階段(Step)。利用搜索者起始坐標(biāo)SS、搜索時(shí)間Tsearch、階段時(shí)長(zhǎng)SteptS、各階段方向θS和速度VS共5個(gè)要素表達(dá)搜索路徑(下標(biāo)S表示搜索者),其中θS∈[0,2π),VS∈[Vmin,Vmax]。文獻(xiàn)[16]固定SteptS和VS,將θS視為變量。本文進(jìn)一步深入,將方向θS和速度VS同時(shí)作為決策變量(見圖1和圖2),使模型更一般化。

圖1　方向的表達(dá)

圖2　搜索路徑的表達(dá)

3OSPP的規(guī)劃模型描述

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

利用累積探測(cè)概率(cumulativedetectionprobability,CDP)作為搜索路徑規(guī)劃的目標(biāo)函數(shù),用于評(píng)價(jià)路徑的搜索效率。在0≤t≤T時(shí),t時(shí)刻的CDP記為FCDP(t),定義為時(shí)間段[0,T]內(nèi)至少一次探測(cè)到目標(biāo)的概率:

FCDP(t)=P{在時(shí)刻 t 以前至少一次探測(cè)到目標(biāo)}=

P{初次探測(cè)到目標(biāo)的時(shí)間≤t }

對(duì)一般搜索路徑,通過解析方法求得精確的FCDP是很困難的,可采用蒙特卡羅方法近似計(jì)算[15-16]。本文在仿真中討論搜索者利用聲納搜索水下目標(biāo)的問題,其中聲納的探測(cè)方程為理想模型,即當(dāng)目標(biāo)位于聲納作用距離(Lsonar)內(nèi)探測(cè)到目標(biāo)的概率為1,否則為0。

3.2規(guī)劃模型

OSPP的規(guī)劃模型描述為

maxFCDP(X,t)

(1)

式中,決策變量X=(x1,x2,…,x2N)T表示一種搜索路徑規(guī)劃方案,N表示搜索路徑階段總數(shù),(x1,x2,…,xN)T表示搜索路徑各階段的方向θS;(xN+1,xN+2,…,x2N)T表示各階段的速度VS。約束條件φ={X|xi∈[ai,bi],ai

4IDCGA

文獻(xiàn)[15-16]將GA應(yīng)用于連續(xù)時(shí)空OSPP,并取得不錯(cuò)的效果。本文提出一種IDCGA求解OSPP。IDCGA采用雙鏈基因?qū)崝?shù)編碼策略、混沌初始種群策略以及保留、交叉、變異3種遺傳操作。針對(duì)OSPP特點(diǎn),提出變異幅度自適應(yīng)控制的方法,并通過引入2種自適應(yīng)因子改進(jìn)了變異操作。

4.1雙鏈基因?qū)崝?shù)編碼策略

4.2混沌初始種群策略

為使初始種群具有較好的多樣性,利用混沌現(xiàn)象的隨機(jī)性、不重復(fù)遍歷等特性,IDCGA采用Logistic映射的混沌初始化方法。

隨機(jī)生成2N個(gè)實(shí)數(shù)y1i(y1i∈(0,1), y1i≠0.5,i=1,2,…,2N),并作為L(zhǎng)ogistic映射的初始值。通過式(2)得到第j個(gè)混沌序列{yj1,yj2,…,yj2N}。

(2)

式中,j=2,3,…,M。由式(3)進(jìn)行解空間變換,得到M組決策變量X。

(3)

4.3改進(jìn)的遺傳操作

IDCGA的遺傳操作包括保留、交叉、變異3種獨(dú)立的遺傳算子,算法流程圖見圖3。在遺傳操作方面,IDCGA與普通GA相比,主要不同點(diǎn)有:一是采用提出的自適應(yīng)變異策略;二是雙鏈染色體同基因位的基因θi,Vi一同進(jìn)行遺傳操作;三是3種遺傳算子獨(dú)立運(yùn)算,得到的3組新個(gè)體組成子代種群;四是分別將3組新個(gè)體占子代的比例記為保留概率PS、交叉概率PC、變異概率PM(PS+PC+PM=1)。

圖3　IDCGA流程圖

4.3.1保留

將父代一組精英個(gè)體直接保留到子代,此操作也稱為穩(wěn)態(tài)選擇[17],其中選取的個(gè)體數(shù)為PS×M。

4.3.2交叉

采用輪盤賭法從父代中選取一組個(gè)體,并兩兩進(jìn)行單點(diǎn)交叉[17],產(chǎn)生的新個(gè)體遺傳到子代。其中交叉點(diǎn)在染色體長(zhǎng)度的1/4至3/4處隨機(jī)選擇,選取交叉操作的個(gè)體數(shù)為PC×M。

4.3.3變異及改進(jìn)

變異操作中,基因的變更通常通過簡(jiǎn)單地產(chǎn)生隨機(jī)數(shù)代替父代基因。針對(duì)OSPP特點(diǎn),本文采用較高的變異概率保證種群的多樣性,避免早熟收斂。為使變異更高效,提出變異幅度自適應(yīng)控制的方法。現(xiàn)考慮以下兩個(gè)方面的問題:

(1) 不同階段搜索者的方向和速度對(duì)搜索路徑的靈敏性。在圖4中,將路徑1分別對(duì)不同階段的方向作幅度相同的變異操作得到路徑2和路徑3?？梢钥闯?階段越是靠前的方向變化對(duì)路徑的改變?cè)绞莿×?因此階段越靠前的方向?qū)λ阉髀窂降撵`敏性越大。在OSPP中,搜索的前期階段選擇正確的搜索方向尤為關(guān)鍵。將路徑3的第1階段速度作幅度相同的變異操作得到路徑4。分析可得,速度相對(duì)于方向?qū)λ阉髀窂降撵`敏性較小。變量的次序及類別影響變量的靈敏性,這是OSPP與其他數(shù)值優(yōu)化問題的一個(gè)關(guān)鍵區(qū)別。因此變異幅度應(yīng)根據(jù)變量的次序及類別自適應(yīng)調(diào)整,特別是針對(duì)較優(yōu)個(gè)體的變異。

圖4　搜索者方向和速度對(duì)搜索路徑的靈敏性分析

(2) 不同進(jìn)化階段變異幅度對(duì)進(jìn)化的影響。在進(jìn)化前期變異有助于增加種群的多樣性。在進(jìn)化后期,優(yōu)秀個(gè)體接近最優(yōu)解,應(yīng)該避免劇烈變異。如果變異劇烈(例如方向的180°旋轉(zhuǎn)),將使變異效率低,甚至牽制進(jìn)化。為了使變異更高效,變異幅度應(yīng)隨進(jìn)化代數(shù)的增加自適應(yīng)減小。

文獻(xiàn)[16]的變異方法只作用于父代最優(yōu)個(gè)體,本文對(duì)保留操作中的精英個(gè)體組進(jìn)行變異操作,其中隨機(jī)選取的個(gè)體數(shù)為PM×M。為提高變異效率、加快算法收斂,本文還提出了自適應(yīng)變異策略:

(4)

(5)

若變異后基因值超出可行解空間φ,通過式(6)調(diào)整:

(6)

在式(4)中,變異幅度由C、Rand、λ和η共同控制。如果不引入自適應(yīng)因子λ和η,變異幅度僅由C、Rand控制,式(4)的變異與普通變異沒有本質(zhì)區(qū)別。

引入基因位自適應(yīng)因子η后,變異幅度隨基因位次序線性遞增,即在搜索路徑中階段越靠前的方向變異幅度越小,使得對(duì)精英個(gè)體的變異不易出現(xiàn)無效甚至離譜的反差,保證了變異的高效性。因?yàn)樗俣认啾确较驅(qū)β窂降撵`敏性小,未對(duì)V基因引入η因子。

引入進(jìn)化代數(shù)自適應(yīng)因子λ后,算法在進(jìn)化前期變異幅度大,可以廣泛搜索解空間,避免早熟收斂。進(jìn)化后期變異幅度自適應(yīng)減小,通過對(duì)精英個(gè)體的微調(diào),提高變異效率。因此λ起到由“求泛”到“求精”的自適應(yīng)搜索作用。

IDCGA通過自適應(yīng)控制逐步尋優(yōu),保證了多樣性和高效性,實(shí)現(xiàn)了全局搜索和局部搜索的動(dòng)態(tài)平衡,使算法收斂速度快、優(yōu)化結(jié)果穩(wěn)定。

5仿真與分析

在實(shí)際中,OSPP的應(yīng)用領(lǐng)域十分廣泛,例如機(jī)器人搜索路徑規(guī)劃[6]、無人機(jī)偵察[18]、反潛搜索[15-16,19]等方面。本文選擇兩個(gè)艦艇搜索潛艇目標(biāo)的軍事問題作為算例,并通過算法對(duì)比驗(yàn)證IDCGA的有效性。

5.1逃離目標(biāo)搜索

5.1.1問題描述

假設(shè)在某海域Time=0時(shí)刻,我方兵力探測(cè)到敵潛艇目標(biāo)在TS點(diǎn)出水,隨后潛入水下。已知潛艇入水后逃離出水點(diǎn),并前往TD點(diǎn)附近區(qū)域執(zhí)行任務(wù)。我方艦艇迅速趕往敵情區(qū)域,并制定搜索策略展開搜索。文獻(xiàn)[9-10]在離散時(shí)空下討論了類似逃離目標(biāo)的搜索問題。

(1) 目標(biāo)的仿真

利用目標(biāo)起始坐標(biāo)TS、目標(biāo)目的地坐標(biāo)TD、速度VT、方向θT、階段時(shí)長(zhǎng)SteptT共5個(gè)要素描述Markov運(yùn)動(dòng)目標(biāo)(下標(biāo)T表示目標(biāo)),并利用Monte Carlo方法對(duì)目標(biāo)路徑進(jìn)行仿真。已知目標(biāo)起始點(diǎn)坐標(biāo)為TS=(130,150);目的地TD服從均值為μTDx=μTDy=30(n mile),標(biāo)準(zhǔn)差為σTDx=σTDy=20/3,相關(guān)系數(shù)為ρXY=0的二維正態(tài)分布(見圖5)。

圖5　目標(biāo)目的地分布及Time=5時(shí)刻分布

圖6　目標(biāo)各階段方向的確定

圖7　最優(yōu)搜索路徑及逃離目標(biāo)運(yùn)動(dòng)路徑分布

(2) 搜索者的相關(guān)參數(shù)

搜索者展開搜索的時(shí)刻Time=1,起始位置坐標(biāo)為SS=(160,130),搜索時(shí)間為Tsearch=6 h,各階段時(shí)長(zhǎng)為SteptS=0.5 h,則階段總數(shù)為NStep=Tsearch/SteptS=12。各階段方向θS∈[0,2π)和速度VS∈[10 kn,25 kn],則變量總數(shù)為24。聲納作用距離Lsonar=3n mile,探測(cè)間隔時(shí)間Δtsonar=0.1 h。CDP的計(jì)算公式為

式中,NumT表示目標(biāo)仿真的總數(shù);NDetect(t)表示已探測(cè)到的目標(biāo)數(shù)。

5.1.2仿真結(jié)果與算法比較

(1) 仿真結(jié)果

經(jīng)50次獨(dú)立運(yùn)算,IDCGA得到的“最優(yōu)”路徑的FCDP(6)=79.33%(見圖7),可以看出搜索者先后經(jīng)歷了“接近”、“攔截”、“追逐”、“攔截”、“回溯”幾個(gè)主要階段。其中算法參數(shù)為:種群規(guī)模M=120,染色體長(zhǎng)度N=NStep=12,最大遺傳代數(shù)Gmax=100,保留概率PS=0.2,交叉概率PC=0.2,變異概率PM=0.6。

(2) 算法對(duì)比

標(biāo)準(zhǔn)GA[17]的參數(shù)設(shè)置:M=130,PC=0.8,PM=0.01。文獻(xiàn)[16]提出的GA*的參數(shù)設(shè)置:M=128,PS=0.25,PC=0.125,PM=0.625。

將本文IDCGA與標(biāo)準(zhǔn)GA、GA*的運(yùn)算結(jié)果列于表1。

表1　逃離目標(biāo)搜索的算法對(duì)比(50次運(yùn)算)

表1中,IDCGA種群數(shù)量最少但平均FCDP最高,且最優(yōu)FCDP和最差FCDP相差最小,因此算法穩(wěn)定性好、尋優(yōu)能力強(qiáng)、收斂速度快。GA*相對(duì)優(yōu)化結(jié)果次之,但算法不夠穩(wěn)定,容易早熟。標(biāo)準(zhǔn)GA在求解復(fù)雜OSPP上效果不理想。IDCGA相比標(biāo)準(zhǔn)GA、GA*,平均FCDP的相對(duì)增長(zhǎng)幅度為53.7%和10.5%。

圖8和圖9分別展示了GA*和IDCGA 50次運(yùn)算結(jié)果中最優(yōu)的10條搜索路徑。可以看出IDCGA的穩(wěn)定性好,所得最優(yōu)路徑接近,可視為收斂。因此相比文獻(xiàn)[16]的算法,IDCGA在求解復(fù)雜運(yùn)動(dòng)目標(biāo)OSPP上效果更好。

圖8　GA*的10條最優(yōu)搜索路徑(逃離目標(biāo))

圖9　IDCGA的10條最優(yōu)搜索路徑(逃離目標(biāo))

5.2方向未知目標(biāo)搜索

5.2.1問題描述

假設(shè)Time=0時(shí)刻敵潛艇在TS=(90,160)出水,隨后潛入水下(與第5.1節(jié)相同的問題描述不作贅述)。對(duì)于目標(biāo)方向未知的情形,需要根據(jù)目標(biāo)的某些信息合理地給出目標(biāo)方向的概率分布。在本文中,假設(shè)目標(biāo)沿主航向Φ航行,Φ服從μΦ=3π/2,σΦ=π/10的正態(tài)分布,路徑各階段的方向θT服從μθT=Φ,σθT=π/8的正態(tài)分布。目標(biāo)的時(shí)空分布見圖10和圖11。時(shí)刻Time=1.5搜索者展開搜索,起始點(diǎn)SS=(40,150),搜索時(shí)間Tsearch=8h,則變量總數(shù)為32。

圖10　Time=3,Time=8時(shí)刻目標(biāo)分布

5.2.2仿真結(jié)果與算法比較

50次獨(dú)立運(yùn)算,IDCGA得到的“最優(yōu)”路徑的FCDP(8)=51.27%(見圖11),算法對(duì)比結(jié)果見表2。圖12和圖13展示了GA*和IDCGA50次運(yùn)算結(jié)果中最優(yōu)的10條搜索路徑。

表2　方向未知目標(biāo)搜索的算法對(duì)比(50次運(yùn)算)

圖11　最優(yōu)搜索路徑及方向未知目標(biāo)運(yùn)動(dòng)路徑分布

圖12　GA*的10條最優(yōu)搜索路徑(方向未知目標(biāo))

圖13　IDCGA的10條最優(yōu)搜索路徑(方向未知目標(biāo))

IDCGA相比標(biāo)準(zhǔn)GA、GA*,平均FCDP的相對(duì)增長(zhǎng)幅度為42.7%和10.7%。分析可得IDCGA具有穩(wěn)定性好、尋優(yōu)能力強(qiáng)、收斂速度快等優(yōu)點(diǎn),適用于求解復(fù)雜OSPP。

在實(shí)際應(yīng)用中,對(duì)一般的探測(cè)模型可以利用等效的探測(cè)距離進(jìn)行處理,只要合理地給出目標(biāo)概率分布,利用本文算法即可求得“最優(yōu)”的搜索路徑,為決策者提供可行的搜索策略。

6結(jié)論

IDCGA引入2種自適應(yīng)因子,采用變異幅度自適應(yīng)控制的方法改進(jìn)了變異操作,具有穩(wěn)定性好、尋優(yōu)能力強(qiáng)、收斂速度快等優(yōu)點(diǎn),在艦艇搜索潛艇的仿真例子中優(yōu)化效果理想,適用于求解復(fù)雜的連續(xù)時(shí)空馬爾可夫運(yùn)動(dòng)目標(biāo)OSPP,研究成果對(duì)相關(guān)搜索問題具有一定啟發(fā)意義。進(jìn)一步工作可以將改進(jìn)的算法應(yīng)用于多搜索者問題和3維空間OSPP。

參考文獻(xiàn)：

[1] Koopman B O. The theory of search[J].OperationResearch, 1956, 4(3): 324-346.

[2] Stone L D.Theoryofoptimalsearch[M]. New York: Academic Press, 1975.

[3] Brown S S. Optimal search for moving target in discrete time and space[J].OperationsResearch, 1980, 28(6):1275-1289.

[4] Trummel K E, Weisinger J R. The complexity of the optimal searcher path problem[J].OperationsResearch, 1986, 34(2):324-327.

[5] Eagle J N, Yee J R. An optimal branch-and-bound procedure for the constrained path, moving target search problem[J].OperationsResearch, 1990, 38(1): 110-114.

[6] Lau H, Huang S, Dissanayake G. Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times[J].EuropeanJournalofOperationalResearch,2008,190(2):383-397.

[7] Sato H, Royset J O. Path optimization for the resource-constrained searcher[J].NavalResearchLogistics,2010,57(5):422-440.

[8] Royset J O, Sato H. Route optimization for multiple searchers[J].NavalResearchLogistics, 2010, 57(8): 701-717.

[9] Hong S P, Cho S J, Park M J. A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search[J].EuropeanJournalofOperationalResearch, 2009, 193(2): 351-364.

[10] Hong S P, Cho S J, Park M J, et al. Optimal search-relocation trade-off in Markovian-target searching[J].Computers&OperationsResearch, 2009, 36(6): 2097-2104.

[11] Chen P, Wu X F, Chen Y. Method of call-search for Markovian motion targets using UUV cooperation[J].SystemsEngineeringandElectronics, 2012, 34(8): 1630-1634. (陳盼, 吳曉鋒, 陳云. UUV編隊(duì)協(xié)同應(yīng)召搜索馬爾可夫運(yùn)動(dòng)目標(biāo)的方法[J]. 系統(tǒng)工程與電子技術(shù), 2012, 34(8): 1630-1634.)

[12] Zhu Q X.Optimalsearchtheoryindiscreteandcontinuousspaces[M]. Beijing: Science Press, 2005. (朱清新. 離散和連續(xù)空間中的最優(yōu)搜索理論[M]. 北京: 科學(xué)出版社, 2005.)

[13] Ohsumi A. Optimal searching for a Markovian-target[J].NavalResearchLogistics, 1991, 38(4): 531-554.

[14] Zhu Q X, Qing L, Peng B. Optimal control model of search problem for randomly moving targets[J].ControlTheory&Applications, 2007, 24(5): 841-845. (朱清新, 卿利, 彭博. 隨機(jī)運(yùn)動(dòng)目標(biāo)搜索問題的最優(yōu)控制模型[J]. 控制理論與應(yīng)用, 2007, 24(5): 841-845.)

[15] Kierstead D P, DelBalzo D R. A genetic algorithm applied to planning search paths in complicated environments[J].MilitaryOperationsResearch, 2003, 8(2): 45-59.

[16] Cho J H, Kim J S, Lim J S, et al. Optimal acoustic search path planning for sonar system based on genetic algorithm[J].InternationalJournalofOffshoreandPolarEngineering, 2007, 17(3): 218-224.

[17] Li M Q, Kou J S, Lin D, et al.Thebasictheoryandapplicationsofgeneticalgorithm[M].Beijing: Science Press, 2002. (李敏強(qiáng),寇紀(jì)淞,林丹,等.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社,2002.)

[18] Wu W C, Huang C Q, Song L, et al. Cooperative search and path planning of multi-unmanned air vehicles in uncertain environment[J].ActaArmamentarii, 2011, 32(11): 1337-1342. (吳文超, 黃長(zhǎng)強(qiáng), 宋磊, 等. 不確定環(huán)境下的多無人機(jī)協(xié)同搜索航路規(guī)劃[J]. 兵工學(xué)報(bào), 2011, 32(11): 1337-1342.)

[19] Chen P, Wu X F. Optimal extended position call-search method for UUVs’ formation[J].SystemsEngineeringandElectronics,2013,35(5):987-992. (陳盼,吳曉鋒,陳云.UUV編隊(duì)協(xié)同最優(yōu)擴(kuò)方應(yīng)召搜索方法[J].系統(tǒng)工程與電子技術(shù),2013,35(5):987-992.)

張獻(xiàn)(1990-),男,碩士研究生,主要研究方向?yàn)檐娛孪到y(tǒng)建模與運(yùn)籌決策。

E-mail:919453887@qq.com

任耀峰(1959-),男,教授,博士,主要研究方向?yàn)檐娛孪到y(tǒng)建模與運(yùn)籌決策。

E-mail:renyaofeng@sina.com

沈靜(1980-),女,講師,博士,主要研究方向?yàn)榧s束滿足問題模型及其相變現(xiàn)象研究。

E-mail:shendina@hotmail.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20140820.1731.003.html

Improved double chains genetic algorithm for optimal searcher path

problem in continuous time and space

ZHANG Xian, REN Yao-feng, SHEN Jing

(CollegeofScience,NavalUniversityofEngineering,Wuhan430033,China)

Abstract:An improved double chains genetic algorithm (IDCGA) for optimal searcher path problem (OSPP) with Markovian-target in continuous time and space is proposed,and both the searcher’s direction and speed are considered as decision variables in the programming model of the search path. The algorithm uses a double-chains real-coded strategy to express the search path, generating initial population by the chaotic initialization method. An adaptive control method for the extent of mutation is proposed to improve the mutation operation by using locus adaptive factor η and generation adaptive factor λ.In the simulations of the anti-submarine searches, the results indicate that the proposed algorithm has the advantages of better stability, more powerful optimizing ability,faster convergence speed, and it is well suitable for solving the complex search path problem.

Keywords:optimal searcher path problem (OSPP); continuous time and space; Markovian-target; double chains genetic algorithm; adaptive mutation

作者簡(jiǎn)介：

中圖分類號(hào)：O 229

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.18

收稿日期：2014-04-01；修回日期：2014-06-11；網(wǎng)絡(luò)優(yōu)先出版日期：2014-08-20。