胡宏啟 陳建華

(海軍陸戰(zhàn)學(xué)院 廣州 510431)

基于遺傳算法的海上搜索力量優(yōu)化研究*

胡宏啟 陳建華

(海軍陸戰(zhàn)學(xué)院 廣州 510431)

在實際的海上搜索工作中,海上搜索區(qū)域由若干個分散的子區(qū)域組成,而搜索主體通常也不只是一個,研究多目標(biāo)區(qū)域條件下如何配置搜索力量,以期達(dá)到最優(yōu)的搜索效果,具有較大的實踐意義。從分析搜索力量最優(yōu)化分配的角度入手,基于遺傳算法,構(gòu)建搜索力分配的計算模型,并通過實例,對模型的有效性進(jìn)行檢驗驗證。

搜索; 遺傳算法; 模型

(Naval Marine Academy, Guangzhou 510431)

Class Number TP391

1 引言

隨著中國經(jīng)濟(jì)的發(fā)展,海上活動日益頻繁,海難事故時有發(fā)生,嚴(yán)重威脅著海上人員生命財產(chǎn)安全,對海上遇險船舶、人員實施及時的搜索對于減少生命、財產(chǎn)損失具有十分重要的意義。2014年發(fā)生的馬來西亞航空MH370客機(jī)失聯(lián)事件以及韓國“歲月號”客輪沉沒事件讓公眾更加清楚認(rèn)識到海上搜救的重要性[1]。海上搜索是一項較為復(fù)雜的工作,涉及到很多計算問題,海難事故發(fā)生時,對搜索力量進(jìn)行優(yōu)化分配,增大搜索成功概率,可以為搜索計劃的制定提供科學(xué)的理論依據(jù)。

2 最優(yōu)搜索問題的描述

在海上搜索過程中,參與搜索的人員數(shù)量、觀察器材的效果、耗費的搜索時間(或觀察次數(shù))、搜索航程或搜掃面積等等統(tǒng)稱為搜索力。搜索力在時間、空間上的分配方式,稱為搜索力的配置或搜索計劃。假設(shè)目標(biāo)的位置在搜索區(qū)域內(nèi)的分布是已知的,為了發(fā)現(xiàn)目標(biāo),就必須在目標(biāo)出現(xiàn)概率大的地方,多配置一些搜索力。根據(jù)所知道的目標(biāo)位置的分布律,對所擁有的有限的搜索力,在一定的成本約束下如何分配,才能使發(fā)現(xiàn)目標(biāo)的概率最大,這就是搜索力的最優(yōu)配置問題,也就是最優(yōu)搜索計劃問題[2]。

海上搜索行動能否取得成功主要受兩個因素的影響: 1) 搜索者必須在可能包含目標(biāo)的區(qū)域中搜索, 2) 搜索者在搜索區(qū)域內(nèi)必須具有探測發(fā)現(xiàn)搜索目標(biāo)的能力,即搜索者所配備的探測器能以一定探測概率在搜索區(qū)域內(nèi)探測到該目標(biāo)。搜索成功概率(Probability of Success,POS)是發(fā)現(xiàn)目標(biāo)的可能性,它依賴于兩個概率[3～4]:

1) 搜索區(qū)域包含目標(biāo)的概率,簡稱包含率(Probability of Containing,POC)。

2) 如果搜索目標(biāo)在該搜索區(qū)域內(nèi),搜索者探測到目標(biāo)的概率,簡稱探測率(Probability of Detection,POD)。

POS的計算公式為

POS=POC×POD

與POD相比,POS能真正衡量搜索行動的效率。實際搜索行動中,POS的值處在0～1之間。不同的POC和POD組合產(chǎn)生0～1之間任意的POS值。根據(jù)目標(biāo)位置及其移動路徑的概率分布,可以獲得指定搜索區(qū)域的POC。而探測函數(shù)則給出了搜索者在指定搜索區(qū)域中搜索的POD。因此海上最優(yōu)搜索的目標(biāo)可表示為,在最可能搜索區(qū)域之上最有效地分配有限且昂貴的搜索資源使得搜索行動中POS的值達(dá)到最大。

探測函數(shù)是以搜索力為自變量的探測概率。搜索力可以是搜掃面積、時間、軌跡路徑或者任何適于給定搜索的物理量。定義于J的探測函數(shù)形如b:J×[0,∞)→[0,1],搜索的總區(qū)域為J,b(j,z)表示目標(biāo)位于搜索子區(qū)域j時,把z量的搜索力施加到該區(qū)域而探測到目標(biāo)的條件概率,在這里假定在區(qū)域j的探測概率僅僅取決于施加于該區(qū)域的搜索力總數(shù),而與搜索力施加的方式無關(guān)[5]。

探測函數(shù)給我們提供了一種根據(jù)探測到目標(biāo)的概率來分析搜索效果的方法。設(shè)p為目標(biāo)在J上的概率分布,假定某一搜索計劃把f(j)量的搜索力施加于區(qū)域j,那么目標(biāo)位于區(qū)域j且由搜索力f(j)探測到該目標(biāo)的概率為p(j)b(j,f(j))。探測到目標(biāo)全概率為

所付出的搜索力總數(shù)為∑f(j)。

一般情況下,能夠用于搜索的搜索資源是有限的,總希望在物力范圍內(nèi)(即在費用約束條件下)優(yōu)化探測到目標(biāo)的概率。定義于J的費用函數(shù)形如C:J×[0,∞)→[0,∞)。由此,c(j,z)表示把搜索力z施加于單元j的費用。經(jīng)常地c(j,z)=z(j∈J,z≥0),這意味著搜索費用由搜索力度量。此外,搜索費用也可不由搜索力度量。比如,搜索力可由軌跡路程度量,而費用則由金錢度量,搜索力與費用的度量取決于實際的搜索問題。

對于離散型分布的多區(qū)域目標(biāo),令F為該空間內(nèi)分配函數(shù)的集合,對于f∈F,P[f]是與分配函數(shù)f對應(yīng)的探測到目標(biāo)的概率。C[f]是與f對應(yīng)的搜索費用。假設(shè)K為搜索費用的限定值?；舅阉鲉栴}是找到f*∈F,使得

C[f*]≤K,P[f*]=max{P[f]:f∈F及C[f]≤K}

f*稱為對應(yīng)于費用K的最優(yōu)分配函數(shù)。

3 遺傳算法簡介

遺傳算法是模擬生物進(jìn)化過程的計算模型。遺傳算法作為一種新的全局優(yōu)化搜索算法,以其簡單通用、魯棒性強(qiáng)、適于并行處理以及應(yīng)用范圍廣等顯著特點,奠定了它作為21世紀(jì)關(guān)鍵智能計算之一的地位[6]。

生物的遺傳物質(zhì)的主要載體是染色體,DNA是其中最主要的遺傳物質(zhì),而基因又是控制生物性狀的遺傳物質(zhì)的功能單位和結(jié)構(gòu)單位。復(fù)數(shù)個基因組成染色體,染色體中基因的位置稱作基因座(locus),而基因所取的值又叫做等位基因(alleles)?；蚝突蜃鶝Q定了染色體的特征,也就決定了生物個體的性狀。此外,染色體有兩種相應(yīng)的表示模式,即基因型和表現(xiàn)型。所謂表現(xiàn)型是指生物個體所表現(xiàn)出來的性狀,而基因型指與表現(xiàn)型密切相關(guān)的基因組成。同一種基因型的生物個體在不同的環(huán)境條件下可以有不同的表現(xiàn)型,因此表現(xiàn)型是基因型與環(huán)境條件相互作用的結(jié)果。在遺傳算法中,染色體對應(yīng)的是數(shù)據(jù)或數(shù)組,在標(biāo)準(zhǔn)的遺傳算法中,這通常是由一維的串結(jié)構(gòu)數(shù)據(jù)來表現(xiàn)的。串上各個位置對應(yīng)上述的基因座,而各位置上所取的值對應(yīng)上述的等位基因。遺傳算法處理的是染色體,或者叫基因型個體(individuals)。一定數(shù)量的個體組成了群體(population),也叫集團(tuán)。群體中個體的數(shù)目稱為群體的大小(population size),也叫群體規(guī)模,而各個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)[7]。

遺傳算法是具有“生成+檢測”的迭代過程的搜索算法。它的基本處理流程如圖1所示。

圖1 遺傳算法流程圖

4 算法應(yīng)用

案例假設(shè),某商船海上失事,人員落水,海水溫度20℃,根據(jù)水溫與生存時間的關(guān)系,落水人員在海水中生存的極限時間為10小時,除去搜救船只到達(dá)搜索區(qū)域的時間,搜索的生還者的有限時間為8小時,根據(jù)目標(biāo)分布概率的特點將搜索區(qū)域分為6個矩形子區(qū)域,長、寬分別為(3海里,2海里),(5海里,3海里),(5海里,3海里),(5海里,4海里),(5海里,5海里),(5海里,3海里),根據(jù)目標(biāo)的概率分布,初步確定各個子區(qū)域的概率分布依次為0.05,0.25,0.15,0.2,0.25,0.1,采用搜救船只對搜索區(qū)域進(jìn)行搜索,其搜索行進(jìn)速度為18節(jié),掃視寬度為1海里。

本問題采用符號編碼方式,案例給出的有限的搜索時間為8小時,可將搜索時間做n等分,n值大小取決于計算所需的精度,搜索時間分別分布于6個搜索區(qū)域中,對n等分的時間進(jìn)行編碼,形如α1α2α3α4α5…αn,在此取n=480,即將時間細(xì)化至每一分鐘。

碼串即為遺傳算法中的染色體,αk(1≤k≤n)為染色體上的一個基因,每一碼串均屬于問題解空間的一個解,每一基因αk∈(1,2,3,4,5,6),問題的目標(biāo)使探測到海上落水人員的概率取得最大值,因此可取探測到落水人員的全概率為適應(yīng)度函數(shù)。

用mj,j∈(1,2,3,4,5,6)表示每一個碼串中基因取值為j的基因數(shù)目,那么m1表示屬于第一個搜索區(qū)域的基因數(shù),m1/60即為分配在第一個搜索區(qū)域上的搜索時間,參考文獻(xiàn)[8],計算出探測函數(shù):

b(j,z)=b(j,mj)=1-e-vmjω/60Aj

則算法的適應(yīng)度函數(shù)為

1) 初始化種群

隨機(jī)產(chǎn)生50個碼串作為第一代染色體。

2) 復(fù)制操作

將50個父代染色體全部參與復(fù)制到子代,參與選擇。

3) 交叉操作

設(shè)置交叉概率PC=0.25,取每個碼串的前120位進(jìn)行交叉。

4) 變異操作

設(shè)置變異概率為0.01,在此設(shè)置5位變異數(shù)字,隨機(jī)取5位數(shù)字進(jìn)行變異操作。

5) 遺傳終止條件

遺傳次數(shù)最小為50,最大為500,適應(yīng)度函數(shù)差距小于0.001時可以提前終止。

利用Matlab軟件編寫程序[9～10],進(jìn)行模型檢驗,部分代碼如下:

R=randint(100,480,[1 6]);%初始化種群

RR=R;

for i=1:1:50

RR(51:100,:)=RR(1:50,:); %復(fù)制操作

for i0=1:2:49 %交叉操作,交叉概率0.25

jc=RR(50+i0,1:120);

RR((50+i0),1:120)=RR((51+i0),1:120);

RR((51+i0),1:120)=jc;

end

for i1=1:1:50 %變異操作,變異概率0.01

RR((50+i1),476:480)=randint(1,5,[1 6]);

end

for i2=1:1:100

C(i2)=gl(RR(i2,:)); %計算適應(yīng)度

end

[B,ind]=sort(C,2,'descend');

for i3=1:1:50

RR(i3,:)=RR(ind(i3),:);

end

end

gl(RR(1,:)) %gl為調(diào)用的概率計算函數(shù)

計算出最大概率為0.80。

5 結(jié)語

本文從海上搜索的特點和基本原則出發(fā),給出了最優(yōu)搜索問題的目標(biāo)函數(shù),運用遺傳算法建立了搜索力的優(yōu)化分配模型,使其具有較好的符合性。實例解算證明了該算法簡便、搜索質(zhì)量高、速度快,適于解決復(fù)雜的搜索力量優(yōu)化分配問題。

[1] 吳翔.海上搜救中發(fā)現(xiàn)概率的研究[J].中國安全生產(chǎn)科學(xué)技術(shù),2015,11(1):28-30.

[2] [蘇]B·A阿勃楚克.搜索目標(biāo)法[M].北京:中國系統(tǒng)工程學(xué)會軍事系統(tǒng)工程委員會,1982:303-308.

[3] 李杰.海上搜救輔助決策系統(tǒng)設(shè)計及應(yīng)用[D].哈爾濱:哈爾濱工程大學(xué),2011:14-19.

[4] 肖方兵.海上搜救決策支持系統(tǒng)關(guān)鍵技術(shù)的研究[D].大連:大連海事大學(xué),2011:19-21.

[5] 勞倫斯D.斯通.最優(yōu)搜索理論[M].吳曉峰,譯.北京:海潮出版社,1990:7-23.

[6] 戴軍.基于遺傳算法的水下機(jī)器人模糊控制器設(shè)計[D].哈爾濱:哈爾濱工程大學(xué),2002:23-26.

[7] 蔡自興.人工智能及其應(yīng)用[M].北京:清華大學(xué)出版社,2013:160-169.

[8] 張之駓.搜索論[M].大連:大連艦艇學(xué)院,1988:31-36.

[9] 許麗佳.MATLAB程序設(shè)計及應(yīng)用[M].北京:清華大學(xué)出版社,2011:32-52.

[10] 孫蓬.MATLAB基礎(chǔ)教程[M].北京:清華大學(xué)出版社,2011:79-101.

Maritime Search Power Optimization Research Based on Genetic Algorithm

HU Hongqi CHEN Jianhua

In actual maritime search work, the search area is composed of several scattered sub regions, and usually there is not just one searching unit, researching how to configure the search power when there are some areas to achieve the optimal search effect is of great practical significance. In this text,how to configure the search power is analyzed. Based on the genetic algorithm, a search power distribution calculation model is builded, and the validity of the model is verified through an example.

search, genetic algorithm, model

2016年6月10日,

2016年7月29日

胡宏啟,男,碩士研究生,研究方向:海軍兵種戰(zhàn)術(shù)建模與仿真。陳建華,男,碩士,教授,研究方向:戰(zhàn)術(shù)建模與仿真、人工智能、軟件工程。

TP391

10.3969/j.issn.1672-9730.2016.12.023