胡宏啟 陳建華

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

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

胡宏啟 陳建華

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

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

搜索; 遺傳算法; 模型

(Naval Marine Academy, Guangzhou 510431)

Class Number TP391

1 引言

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

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

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

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

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

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

POS的計(jì)算公式為

POS=POC×POD

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

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

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

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

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

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

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

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

3 遺傳算法簡(jiǎn)介

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

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

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

圖1 遺傳算法流程圖

4 算法應(yīng)用

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

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

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

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

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

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

1) 初始化種群

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

2) 復(fù)制操作

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

3) 交叉操作

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

4) 變異操作

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

5) 遺傳終止條件

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

利用Matlab軟件編寫程序[9～10],進(jìn)行模型檢驗(yà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,:)); %計(jì)算適應(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)用的概率計(jì)算函數(shù)

計(jì)算出最大概率為0.80。

5 結(jié)語(yǔ)

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

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

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

[3] 李杰.海上搜救輔助決策系統(tǒng)設(shè)計(jì)及應(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è)計(jì)[D].哈爾濱:哈爾濱工程大學(xué),2002:23-26.

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

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

[9] 許麗佳.MATLAB程序設(shè)計(jì)及應(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