多約束條件下多目標(biāo)函數(shù)無人水下航行器航跡規(guī)劃

邱千鈞,郝翎鈞,張福興,李 梁

(1.海軍駐北京地區(qū)軍事代表局,北京 100854;2.海軍工程大學(xué),湖北 武漢 430033; 3.海軍研究院,北京 100161)

隨著自主導(dǎo)航、無人控制、人工智能等技術(shù)的迅速發(fā)展,無人水下航行器(Unmanned Undersea Vehicle,UUV)作為無人系統(tǒng)的重要組成部分,在民用和軍事領(lǐng)域,展現(xiàn)出了越來越重要的作用[1-2]。在民用領(lǐng)域,UUV可以用于開展水下環(huán)境數(shù)據(jù)采集、海洋資源勘探、海底電纜檢測(cè)等任務(wù)[3];在軍事領(lǐng)域,UUV的使用不僅可以降低戰(zhàn)場(chǎng)的傷亡率,而且其本身具有使用靈活、用途廣泛、隱蔽性強(qiáng)的特點(diǎn),使其被譽(yù)為“海上力量倍增器”[4]。UUV要完成上述一系列任務(wù),并充分發(fā)揮其優(yōu)勢(shì),最為基礎(chǔ)、最為關(guān)鍵的技術(shù)之一就是UUV航跡規(guī)劃問題。

航跡規(guī)劃問題,在國(guó)內(nèi)外已有大量研究,且解決方法也已相當(dāng)成熟,比較常見的有A*算法、Dijkstra最短路徑算法、遺傳或蟻群算法等仿生智能算法,以及基于深度學(xué)習(xí)的人工智能算法等[5]。但是,眾多的文獻(xiàn)中,航跡規(guī)劃針對(duì)的主要問題是最短路徑、航行避碰、算法優(yōu)化,對(duì)于UUV航跡規(guī)劃問題,不僅需要解決如何尋求最短路徑,更為重要的是,要解決航行過程中的定位誤差校正。在海洋復(fù)雜環(huán)境下,由于水下通信困難,系統(tǒng)結(jié)構(gòu)限制等問題,UUV的定位系統(tǒng)難以進(jìn)行精確定位,導(dǎo)致定位誤差累積,以至于最后無法完成既定的任務(wù)。因此,在航行過程中進(jìn)行定位誤差校正也是UUV航跡規(guī)劃問題中的一項(xiàng)重要任務(wù)。

1 問題描述

本文研究的目標(biāo)是在復(fù)雜海洋環(huán)境中的眾多約束條件下找出一條滿足以下兩個(gè)條件的最優(yōu)航跡:

1)UUV的航跡長(zhǎng)度盡可能小;

2)經(jīng)過校正點(diǎn)的個(gè)數(shù)盡可能少。

約束條件需要滿足的定位誤差為:

1)UUV按照規(guī)劃的航跡從起點(diǎn)到終點(diǎn)的路徑上,每航行一段距離就會(huì)在水平垂直方向上產(chǎn)生一段誤差,因此,在可能路徑上,會(huì)有眾多的定位校正點(diǎn),每當(dāng)航行器到達(dá)定位校正點(diǎn)附近時(shí),如果水平、垂直誤差不大于δ個(gè)誤差精度,那么,系統(tǒng)就能夠?qū)叫衅鬟M(jìn)行誤差校正,使其誤差為0。

2)UUV按照規(guī)劃的航跡到達(dá)終點(diǎn)之后,會(huì)產(chǎn)生累計(jì)誤差,要求累計(jì)誤差也不能大于ε個(gè)誤差精度,否則,視為該航跡不可靠,即UUV按照該航跡無法達(dá)到終點(diǎn)。

該問題即為多約束條件下的多目標(biāo)函數(shù)航跡規(guī)劃問題[6],設(shè)目標(biāo)函數(shù)分別為f1(x),f2(x),…,ft(x)(t≥2),問題中的約束條件分別為gi(x)≥0(i=1,2,…,m)和hj(x)=0(j=1,2,…,l),那么該問題就是在滿足多種約束的前提下,使得目標(biāo)函數(shù)的值達(dá)到最小,用數(shù)學(xué)形式表示為

(1)

2 模型構(gòu)建與求解

針對(duì)多約束條件下的多目標(biāo)函數(shù)航跡規(guī)劃問題,采用層次分析法對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行無量綱化處理,加權(quán)得到新的單目標(biāo)函數(shù),將多目標(biāo)函數(shù)問題轉(zhuǎn)換降維為單目標(biāo)函數(shù)問題,再使用遺傳算法對(duì)模型進(jìn)行求解,模型求解思路如圖1所示。

圖1 模型求解思路

2.1 層次分析法求解

層次分析法(AHP法)是將許多復(fù)雜且關(guān)系模糊不清的元素和相互關(guān)系轉(zhuǎn)化為定量分析的一種決策分析方法,是定量和定性分析相結(jié)合的方法。

1)指標(biāo)體系建立

將最終得到的單目標(biāo)函數(shù)作為航跡評(píng)價(jià),那么，由問題描述可知,影響航跡評(píng)價(jià)的因素有兩點(diǎn),分別是: UUV的航跡長(zhǎng)度盡可能小和經(jīng)過校正點(diǎn)的個(gè)數(shù)盡可能少。因此,建立指標(biāo)體系如圖2所示。

圖2 航跡評(píng)價(jià)的指標(biāo)體系

2)歸一化處理

由于航跡評(píng)價(jià)中的指標(biāo)值不在一個(gè)數(shù)量級(jí)上,因此，權(quán)重w1,w2值的大小對(duì)于目標(biāo)函數(shù)的影響并不敏感,所以,必須要進(jìn)行歸一化處理。歸一化處理的數(shù)學(xué)表達(dá)式如下,x為決策變量。

(2)

3)構(gòu)造判斷矩陣

判斷矩陣是層次分析法的關(guān)鍵,是進(jìn)行權(quán)重計(jì)算的基礎(chǔ)。構(gòu)造判斷矩陣的方法是將影響因素x進(jìn)行兩兩比對(duì),通常采用1-9標(biāo)度法,在這里不做贅述。

4)一致性檢驗(yàn)

由于指標(biāo)的復(fù)雜性以及人們對(duì)事物認(rèn)識(shí)的模糊性和多樣性,同時(shí),評(píng)價(jià)影響因素的指標(biāo)值是估計(jì)值,這種估計(jì)就會(huì)不可避免地存在一些誤差,因此，有必要進(jìn)行一致性檢驗(yàn),即相容性檢驗(yàn)。

通過一致性檢驗(yàn)之后,得出影響航跡評(píng)價(jià)因素的權(quán)重w1和w2,那么可以得到最終的目標(biāo)函數(shù)minV為

minV={f1(x),f2(x)}=w1·f1(x)+w2·f2(x)

(3)

2.2 遺傳算法求解

遺傳算法是基于生物自然選擇規(guī)律和基因遺傳學(xué)機(jī)理,通過數(shù)學(xué)模式來模擬“物競(jìng)天擇,適者生存”的一種隨機(jī)搜索方法,其基本思路是把問題的決策變量編碼為染色體,再利用迭代的方式進(jìn)行選擇、交叉以及變異等運(yùn)算來不斷更新染色體信息,直到生成符合優(yōu)化目標(biāo)的染色體[7]。

1)基因編碼方式

編碼是應(yīng)用遺傳算法時(shí)要解決的首要問題,以此反映需要解決的問題,是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵步驟。編碼方式除了決定個(gè)體基因染色體排列方式外,還決定了個(gè)體從搜索空間基因型變換到解空間表現(xiàn)型時(shí)的解碼方法,編碼方法影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法,很大程度上決定了遺傳進(jìn)化的效率。

航跡規(guī)劃中,基因編碼通常采用參數(shù)方程法、直角坐標(biāo)系法和經(jīng)緯度坐標(biāo)系法等。參數(shù)方程和直角坐標(biāo)系法對(duì)航行器狀態(tài)掌控要求高,不利于構(gòu)造航行器空間模型;單純的經(jīng)緯度坐標(biāo)系法不能全面反映航行器當(dāng)前狀態(tài),因此,模型中設(shè)計(jì)了一種航跡結(jié)構(gòu)體的編碼方案,能夠減少航跡規(guī)劃時(shí)重復(fù)的計(jì)算量,提高計(jì)算內(nèi)存的利用效率,其結(jié)構(gòu)體格式如圖3所示。

圖3 航跡結(jié)構(gòu)體格式

其中，Ni表示航跡節(jié)點(diǎn)校正點(diǎn),由5個(gè)基本特征組成。Nik表示航跡節(jié)點(diǎn)基因,其特征如表1所示。

表1 基因編碼在航跡中對(duì)應(yīng)的物理量

①x,y,z表示航行器在航跡校正點(diǎn)所處的空間位置;

②Index是對(duì)航行器的航跡校正點(diǎn)進(jìn)行排序,生成完整航跡;

③Ti表示航行器完成的航跡序列;

④Type表示校正點(diǎn)類型,Type=0代表水平校正點(diǎn),Type=1代表垂直校正點(diǎn);

⑤r表示航行器的最小轉(zhuǎn)彎半徑,大于最小轉(zhuǎn)彎半徑rmin,則航跡可行。

這種基因編碼方式的優(yōu)點(diǎn)是減少了重復(fù)的計(jì)算量,同時(shí)能夠?qū)崟r(shí)提取出航行器航跡的相關(guān)信息,在不用解碼的情況下就能直接計(jì)算參考航跡的代價(jià)函數(shù)值,使得表達(dá)式更有效,能生成更好的解,缺點(diǎn)是增加了計(jì)算機(jī)的物理內(nèi)存。

2)遺傳操作算子

遺傳算子是遺傳算法具有強(qiáng)大搜索能力的核心,是模擬自然選擇過程中的繁殖和基因遺傳過程中發(fā)生的基因交叉、變異的主要載體。為解決該航跡規(guī)劃問題,本文采用了以下六種遺傳算子[8-9]:

①交叉算子:其主要思想是將兩條父代航跡進(jìn)行重新組合,得到兩條具有父代航跡基因的新的子代航跡。

如圖4a)所示,首先將兩條父代航跡隨機(jī)分為兩個(gè)部分,將航跡a的前半部分與航跡b的后半部分組合,航跡a的后半部分與航跡b的前半部分組合,得到兩條新的子代航跡c和d。新的航跡既可以是可行解,也可以是不可行解,并且,航跡的節(jié)點(diǎn)數(shù)可以是不相同的。

②擾動(dòng)算子:其主要思想是對(duì)發(fā)生變異的航跡的一個(gè)節(jié)點(diǎn)坐標(biāo)進(jìn)行隨機(jī)改變。

如圖4b)所示,當(dāng)原始航跡為可行解時(shí)進(jìn)行小范圍擾動(dòng),將其控制在可行區(qū)域內(nèi),以航跡上發(fā)生變異的點(diǎn)為圓心,設(shè)該變異點(diǎn)與距離該變異點(diǎn)最近的點(diǎn)之間的距離為rmin,k擾動(dòng)為小范圍擾動(dòng)系數(shù)(k擾動(dòng)>1),則擾動(dòng)半徑為

r擾動(dòng)=k擾動(dòng)·rmin

(4)

在擾動(dòng)半徑內(nèi)剔除掉原始航跡上的點(diǎn)后,隨機(jī)選擇一個(gè)點(diǎn)的坐標(biāo)替換掉原始航跡上發(fā)生變異的點(diǎn)的坐標(biāo)。

當(dāng)原始航跡為不可行解時(shí),進(jìn)行大范圍擾動(dòng),盡可能跳出限定的范圍,以期望獲得的新航跡為可行解,仍然以原航跡上發(fā)生變異的點(diǎn)為圓心,設(shè)該變異點(diǎn)與距離該變異點(diǎn)最遠(yuǎn)的點(diǎn)之間的距離為rmax,k′擾動(dòng)為大范圍擾動(dòng)系數(shù)(k′擾動(dòng)<1),則擾動(dòng)半徑為

r′擾動(dòng)=k′擾動(dòng)·rmax

(5)

③插入算子:其主要思想是在發(fā)生變異的航跡中隨機(jī)選擇兩個(gè)相鄰航跡節(jié)點(diǎn),在這兩個(gè)節(jié)點(diǎn)中插入一個(gè)新的航跡節(jié)點(diǎn),如圖4c)所示。

④刪除算子:其主要思想是在發(fā)生變異的航跡中隨機(jī)刪除一個(gè)航跡節(jié)點(diǎn)(其中,起點(diǎn)和終點(diǎn)不可刪除),如圖4d)所示。

⑤交換算子:其主要思想是在發(fā)生變異的航跡中隨機(jī)交換兩個(gè)相鄰航跡節(jié)點(diǎn)的先后順序,如圖4e)所示。交換算子只作用于不可行解的航跡,如果相鄰航跡節(jié)點(diǎn)處的轉(zhuǎn)角越大,那么,進(jìn)行交換變異的概率也就越大,目的是盡可能地減小轉(zhuǎn)彎角。

⑥平滑算子:如圖4f)所示,其主要思想是將發(fā)生變異的航跡中轉(zhuǎn)彎角大的“部位”進(jìn)行平滑處理,在相鄰的兩個(gè)航跡段上插入一個(gè)新的航跡節(jié)點(diǎn),并且刪除原來的航跡節(jié)點(diǎn),即切除轉(zhuǎn)彎角大的“部位”,使航跡中的尖角平滑。與交換算子類似,平滑算子只作用于不可行解的航跡,如果相鄰航跡節(jié)點(diǎn)處的轉(zhuǎn)角越大,那么,進(jìn)行平滑變異的概率也就越大。

圖4 遺傳操作算子

3)適應(yīng)度函數(shù)

該問題是一個(gè)多約束的優(yōu)化問題,其難點(diǎn)在于如何有效合理地處理約束條件,罰函數(shù)是一種解決約束優(yōu)化問題常用的方法,所謂罰函數(shù),就是基于優(yōu)化目標(biāo)和約束條件構(gòu)造的有懲罰效果的函數(shù),一般可表示為

Fitness(x)=F(x)+χ(g)P(x)

(6)

式中,F(x)為原約束化問題的適應(yīng)度函數(shù),χ(g)為懲罰因子，P(x)為懲罰項(xiàng)。懲罰因子和懲罰項(xiàng)的設(shè)置是罰函數(shù)設(shè)計(jì)的難點(diǎn),設(shè)置為零,導(dǎo)致種群多樣性降低,算法易陷入局部最優(yōu);設(shè)置得太小,罰函數(shù)失效,造成誤差種群中不可行解的數(shù)量變多,算法難以快速收斂;設(shè)置太大,會(huì)導(dǎo)致懲罰過度,算法陷入早熟。因此，本文根據(jù)種群當(dāng)前狀態(tài)設(shè)計(jì)了能自適應(yīng)調(diào)整的動(dòng)態(tài)罰函數(shù),其原理如圖5所示。

圖5 動(dòng)態(tài)罰函數(shù)機(jī)制示意圖

動(dòng)態(tài)罰函數(shù)的具體形式如下：

(7)

式中,g為當(dāng)前的進(jìn)化代數(shù);θ(eu(x))為分層次的懲罰函數(shù);τ為懲罰強(qiáng)度;eu(x)為種群中個(gè)體x違反第u個(gè)約束條件的程度函數(shù),其表達(dá)式為

(8)

因此,經(jīng)過罰函數(shù)轉(zhuǎn)化后個(gè)體xi的適應(yīng)度函數(shù)可表示為

(9)

2.3 模型求解基本流程

通過對(duì)上述目標(biāo)函數(shù)和約束條件的處理,按照層次分析法和遺傳算法處理步驟,總結(jié)出該問題模型求解的基本流程。

Step1.確定目標(biāo)函數(shù)以及約束條件。

Step2.用層次分析法將問題轉(zhuǎn)化為單目標(biāo)函數(shù)問題。

Step3.選擇合適的基因編碼方式對(duì)問題集進(jìn)行編碼。

Step4.依據(jù)可行航跡初始化種群,種群是進(jìn)行遺傳算法操作的空間。

Step5.定義適應(yīng)度函數(shù),評(píng)價(jià)種群中個(gè)體的適應(yīng)度。

Step6.找出適應(yīng)度較好的個(gè)體放入繁殖池。

Step7.判斷是否滿足終止條件,如果滿足,則程序結(jié)束;如果不滿足,則繼續(xù)下一步。

Step8.設(shè)計(jì)遺傳算子,確定遺傳參數(shù)如交叉概率pc和變異概率pm,對(duì)繁殖池內(nèi)的個(gè)體進(jìn)行選擇、交叉、變異等遺傳操作。

Step9.對(duì)生成的新的子代個(gè)體用適應(yīng)度函數(shù)進(jìn)行評(píng)價(jià),即跳轉(zhuǎn)到Step5。

模型求解基本工作流程如圖6所示。

圖6 模型求解基本流程圖

3 仿真驗(yàn)證

為了驗(yàn)證多約束條件下多目標(biāo)函數(shù)無人水下航行器航跡規(guī)劃問題解決方法的可行性,對(duì)復(fù)雜海洋環(huán)境下的校正點(diǎn)區(qū)域數(shù)據(jù)集進(jìn)行仿真驗(yàn)證,設(shè)定初始參數(shù)δ=30，ε=20,隨機(jī)生成500個(gè)校正點(diǎn)數(shù)據(jù)集，得到遺傳算法的進(jìn)化過程如圖7所示。

圖7 遺傳算法進(jìn)化過程

由圖7可知,藍(lán)色線段代表的是航行器的航跡,遺傳算法的代數(shù)、航跡評(píng)價(jià)的值、航跡最短距離、校正點(diǎn)個(gè)數(shù)和航跡是否可行都顯示在圖中。圖7a)表示的是初始種群的航跡,可以看出,初始解的航行軌跡雜亂無章,經(jīng)過遺傳算法的不斷迭代,由圖7b)、7c)可以看出,到第20代左右的時(shí)候,航行器的航跡出現(xiàn)較為明顯的改善,到第50代左右的時(shí)候,航行軌跡出現(xiàn)較為優(yōu)化的結(jié)果,從圖7d)中可知,到第100代左右的時(shí)候,航行軌跡基本上已經(jīng)收斂,但尚未達(dá)到最優(yōu)可行解。

圖8表示數(shù)據(jù)集1的種群進(jìn)化到第123代時(shí),算法所得到的結(jié)果已經(jīng)完全收斂,并且，已經(jīng)得到最優(yōu)可行路徑,經(jīng)過的校正點(diǎn)個(gè)數(shù)為10。

由圖8算法搜索過程和最優(yōu)可行航跡可知,本文

所采用的改進(jìn)遺傳算法能夠解決多約束條件下的多目標(biāo)函數(shù)的航跡規(guī)劃問題,且可以找到最優(yōu)可行航跡,驗(yàn)證了算法的有效性。

4 結(jié)束語

本文針對(duì)復(fù)雜海洋環(huán)境誤差定位校正的約束條件下,以最短路徑和經(jīng)過最少校正點(diǎn)為目標(biāo)的UUV航跡規(guī)劃問題,采用基于層次分析法和動(dòng)態(tài)罰函數(shù)法的遺傳算法對(duì)該問題進(jìn)行建模分析,最后的仿真結(jié)果表明，所建立的模型和使用的算法能夠有效解決多約束條件下多目標(biāo)函數(shù)的無人水下航行器航跡規(guī)劃問題,可以找出一條既滿足最短距離又滿足經(jīng)過最少校正點(diǎn)的最優(yōu)路徑。

圖8 算法搜索過程和最優(yōu)化可行航跡