基于遺傳算法的海上搜索力量優化研究*

胡宏啟 陳建華

(海軍陸戰學院 廣州 510431)

基于遺傳算法的海上搜索力量優化研究*

胡宏啟 陳建華

(海軍陸戰學院 廣州 510431)

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

搜索; 遺傳算法; 模型

(Naval Marine Academy, Guangzhou 510431)

Class Number TP391

1 引言

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

2 最優搜索問題的描述

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

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

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

2) 如果搜索目標在該搜索區域內,搜索者探測到目標的概率,簡稱探測率(Probability of Detection,POD)。

POS的計算公式為

POS=POC×POD

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

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

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

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

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

對于離散型分布的多區域目標,令F為該空間內分配函數的集合,對于f∈F,P[f]是與分配函數f對應的探測到目標的概率。C[f]是與f對應的搜索費用。假設K為搜索費用的限定值。基本搜索問題是找到f*∈F,使得

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

f*稱為對應于費用K的最優分配函數。

3 遺傳算法簡介

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

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

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

圖1 遺傳算法流程圖

4 算法應用

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

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

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

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

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

則算法的適應度函數為

1) 初始化種群

隨機產生50個碼串作為第一代染色體。

2) 復制操作

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

3) 交叉操作

設置交叉概率PC=0.25,取每個碼串的前120位進行交叉。

4) 變異操作

設置變異概率為0.01,在此設置5位變異數字,隨機取5位數字進行變異操作。

5) 遺傳終止條件

遺傳次數最小為50,最大為500,適應度函數差距小于0.001時可以提前終止。

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

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

RR=R;

for i=1:1:50

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

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,:)); %計算適應度

end

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

for i3=1:1:50

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

end

end

gl(RR(1,:)) %gl為調用的概率計算函數

計算出最大概率為0.80。

5 結語

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

[1] 吳翔.海上搜救中發現概率的研究[J].中國安全生產科學技術,2015,11(1):28-30.

[2] [蘇]B·A阿勃楚克.搜索目標法[M].北京:中國系統工程學會軍事系統工程委員會,1982:303-308.

[3] 李杰.海上搜救輔助決策系統設計及應用[D].哈爾濱:哈爾濱工程大學,2011:14-19.

[4] 肖方兵.海上搜救決策支持系統關鍵技術的研究[D].大連:大連海事大學,2011:19-21.

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

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

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

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

[9] 許麗佳.MATLAB程序設計及應用[M].北京:清華大學出版社,2011:32-52.

[10] 孫蓬.MATLAB基礎教程[M].北京:清華大學出版社,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日

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

TP391

10.3969/j.issn.1672-9730.2016.12.023