連續時空最優搜索者路徑問題的改進雙鏈遺傳算法

張　獻, 任耀峰, 沈　靜

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

?

連續時空最優搜索者路徑問題的改進雙鏈遺傳算法

張獻, 任耀峰, 沈靜

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

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

關鍵詞：最優搜索者路徑; 連續時空; 馬爾可夫目標; 雙鏈遺傳算法; 自適應變異

0引言

搜索論是主要研究利用探測手段尋找指定目標優化方案的理論和方法,起源于二戰時期美國反潛運籌小組對德國潛艇進行搜索的一系列研究工作。1956～1980年,在眾多學者的努力下[1-3],取得了一批主要針對靜止目標和運動目標最優搜索資源分配問題的理論成果,奠定了搜索論的理論基礎。無論在離散時空還是連續時空,此類問題都要求搜索資源能夠任意細分,同時搜索者的運動能力不受約束,可在搜索空間內任意轉移并分配搜索資源。

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

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

本文研究目標運動為時空連續馬爾可夫過程的OSPP,使問題更為一般化。首先建立了目標和搜索者的運動模型,將搜索者方向和速度均作為決策變量,提出變異幅度自適應控制的方法,給出了IDCGA。最后將算法應用于兩個仿真例子,通過算法對比驗證了IDCGA的有效性。改進的算法具有穩定性好、尋優能力強等優點,適用于求解復雜搜索路徑問題。研究成果對求解OSPP具有一定應用價值。

1連續Markov運動目標模型

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

本文討論的搜索問題屬搜索論中的單向搜索范疇,即目標不能對搜索者的行為做出反應,其運動不受搜索者策略影響。同時，不考慮深度,搜索者和目標在2維空間內運動。

2搜索路徑的表達

實際問題中,目標和搜索者通常在一定時間段內保持穩定的運動方向和速度,每隔一段時間根據情況進行調整(如艦船和潛艇)。

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

圖1　方向的表達

圖2　搜索路徑的表達

3OSPP的規劃模型描述

3.1目標函數

利用累積探測概率(cumulativedetectionprobability,CDP)作為搜索路徑規劃的目標函數,用于評價路徑的搜索效率。在0≤t≤T時,t時刻的CDP記為FCDP(t),定義為時間段[0,T]內至少一次探測到目標的概率:

FCDP(t)=P{在時刻 t 以前至少一次探測到目標}=

P{初次探測到目標的時間≤t }

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

3.2規劃模型

OSPP的規劃模型描述為

maxFCDP(X,t)

(1)

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

4IDCGA

文獻[15-16]將GA應用于連續時空OSPP,并取得不錯的效果。本文提出一種IDCGA求解OSPP。IDCGA采用雙鏈基因實數編碼策略、混沌初始種群策略以及保留、交叉、變異3種遺傳操作。針對OSPP特點,提出變異幅度自適應控制的方法,并通過引入2種自適應因子改進了變異操作。

4.1雙鏈基因實數編碼策略

4.2混沌初始種群策略

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

隨機生成2N個實數y1i(y1i∈(0,1), y1i≠0.5,i=1,2,…,2N),并作為Logistic映射的初始值。通過式(2)得到第j個混沌序列{yj1,yj2,…,yj2N}。

(2)

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

(3)

4.3改進的遺傳操作

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

圖3　IDCGA流程圖

4.3.1保留

將父代一組精英個體直接保留到子代,此操作也稱為穩態選擇[17],其中選取的個體數為PS×M。

4.3.2交叉

采用輪盤賭法從父代中選取一組個體,并兩兩進行單點交叉[17],產生的新個體遺傳到子代。其中交叉點在染色體長度的1/4至3/4處隨機選擇,選取交叉操作的個體數為PC×M。

4.3.3變異及改進

變異操作中,基因的變更通常通過簡單地產生隨機數代替父代基因。針對OSPP特點,本文采用較高的變異概率保證種群的多樣性,避免早熟收斂。為使變異更高效,提出變異幅度自適應控制的方法?，F考慮以下兩個方面的問題:

(1) 不同階段搜索者的方向和速度對搜索路徑的靈敏性。在圖4中,將路徑1分別對不同階段的方向作幅度相同的變異操作得到路徑2和路徑3?？梢钥闯?階段越是靠前的方向變化對路徑的改變越是劇烈,因此階段越靠前的方向對搜索路徑的靈敏性越大。在OSPP中,搜索的前期階段選擇正確的搜索方向尤為關鍵。將路徑3的第1階段速度作幅度相同的變異操作得到路徑4。分析可得,速度相對于方向對搜索路徑的靈敏性較小。變量的次序及類別影響變量的靈敏性,這是OSPP與其他數值優化問題的一個關鍵區別。因此變異幅度應根據變量的次序及類別自適應調整,特別是針對較優個體的變異。

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

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

文獻[16]的變異方法只作用于父代最優個體,本文對保留操作中的精英個體組進行變異操作,其中隨機選取的個體數為PM×M。為提高變異效率、加快算法收斂,本文還提出了自適應變異策略:

(4)

(5)

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

(6)

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

引入基因位自適應因子η后,變異幅度隨基因位次序線性遞增,即在搜索路徑中階段越靠前的方向變異幅度越小,使得對精英個體的變異不易出現無效甚至離譜的反差,保證了變異的高效性。因為速度相比方向對路徑的靈敏性小,未對V基因引入η因子。

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

IDCGA通過自適應控制逐步尋優,保證了多樣性和高效性,實現了全局搜索和局部搜索的動態平衡,使算法收斂速度快、優化結果穩定。

5仿真與分析

在實際中,OSPP的應用領域十分廣泛,例如機器人搜索路徑規劃[6]、無人機偵察[18]、反潛搜索[15-16,19]等方面。本文選擇兩個艦艇搜索潛艇目標的軍事問題作為算例,并通過算法對比驗證IDCGA的有效性。

5.1逃離目標搜索

5.1.1問題描述

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

(1) 目標的仿真

利用目標起始坐標TS、目標目的地坐標TD、速度VT、方向θT、階段時長SteptT共5個要素描述Markov運動目標(下標T表示目標),并利用Monte Carlo方法對目標路徑進行仿真。已知目標起始點坐標為TS=(130,150);目的地TD服從均值為μTDx=μTDy=30(n mile),標準差為σTDx=σTDy=20/3,相關系數為ρXY=0的二維正態分布(見圖5)。

圖5　目標目的地分布及Time=5時刻分布

圖6　目標各階段方向的確定

圖7　最優搜索路徑及逃離目標運動路徑分布

(2) 搜索者的相關參數

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

式中,NumT表示目標仿真的總數;NDetect(t)表示已探測到的目標數。

5.1.2仿真結果與算法比較

(1) 仿真結果

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

(2) 算法對比

標準GA[17]的參數設置:M=130,PC=0.8,PM=0.01。文獻[16]提出的GA*的參數設置:M=128,PS=0.25,PC=0.125,PM=0.625。

將本文IDCGA與標準GA、GA*的運算結果列于表1。

表1　逃離目標搜索的算法對比(50次運算)

表1中,IDCGA種群數量最少但平均FCDP最高,且最優FCDP和最差FCDP相差最小,因此算法穩定性好、尋優能力強、收斂速度快。GA*相對優化結果次之,但算法不夠穩定,容易早熟。標準GA在求解復雜OSPP上效果不理想。IDCGA相比標準GA、GA*,平均FCDP的相對增長幅度為53.7%和10.5%。

圖8和圖9分別展示了GA*和IDCGA 50次運算結果中最優的10條搜索路徑?？梢钥闯鯥DCGA的穩定性好,所得最優路徑接近,可視為收斂。因此相比文獻[16]的算法,IDCGA在求解復雜運動目標OSPP上效果更好。

圖8　GA*的10條最優搜索路徑(逃離目標)

圖9　IDCGA的10條最優搜索路徑(逃離目標)

5.2方向未知目標搜索

5.2.1問題描述

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

圖10　Time=3,Time=8時刻目標分布

5.2.2仿真結果與算法比較

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

表2　方向未知目標搜索的算法對比(50次運算)

圖11　最優搜索路徑及方向未知目標運動路徑分布

圖12　GA*的10條最優搜索路徑(方向未知目標)

圖13　IDCGA的10條最優搜索路徑(方向未知目標)

IDCGA相比標準GA、GA*,平均FCDP的相對增長幅度為42.7%和10.7%。分析可得IDCGA具有穩定性好、尋優能力強、收斂速度快等優點,適用于求解復雜OSPP。

在實際應用中,對一般的探測模型可以利用等效的探測距離進行處理,只要合理地給出目標概率分布,利用本文算法即可求得“最優”的搜索路徑,為決策者提供可行的搜索策略。

6結論

IDCGA引入2種自適應因子,采用變異幅度自適應控制的方法改進了變異操作,具有穩定性好、尋優能力強、收斂速度快等優點,在艦艇搜索潛艇的仿真例子中優化效果理想,適用于求解復雜的連續時空馬爾可夫運動目標OSPP,研究成果對相關搜索問題具有一定啟發意義。進一步工作可以將改進的算法應用于多搜索者問題和3維空間OSPP。

參考文獻：

[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編隊協同應召搜索馬爾可夫運動目標的方法[J]. 系統工程與電子技術, 2012, 34(8): 1630-1634.)

[12] Zhu Q X.Optimalsearchtheoryindiscreteandcontinuousspaces[M]. Beijing: Science Press, 2005. (朱清新. 離散和連續空間中的最優搜索理論[M]. 北京: 科學出版社, 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]. 控制理論與應用, 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. (李敏強,寇紀淞,林丹,等.遺傳算法的基本理論與應用[M].北京:科學出版社,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. (吳文超, 黃長強, 宋磊, 等. 不確定環境下的多無人機協同搜索航路規劃[J]. 兵工學報, 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編隊協同最優擴方應召搜索方法[J].系統工程與電子技術,2013,35(5):987-992.)

張獻(1990-),男,碩士研究生,主要研究方向為軍事系統建模與運籌決策。

E-mail:919453887@qq.com

任耀峰(1959-),男,教授,博士,主要研究方向為軍事系統建模與運籌決策。

E-mail:renyaofeng@sina.com

沈靜(1980-),女,講師,博士,主要研究方向為約束滿足問題模型及其相變現象研究。

E-mail:shendina@hotmail.com

網絡優先出版地址：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

作者簡介：

中圖分類號：O 229

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.18

收稿日期：2014-04-01；修回日期：2014-06-11；網絡優先出版日期：2014-08-20。