謝 鋒,姚 堯,張曉霜

(江蘇自動(dòng)化研究所,江蘇 連云港 222061)

自主水下機(jī)器人(Autonomous Underwater Vehicle, AUV) 航行噪聲低、機(jī)動(dòng)靈活、無人員傷亡等優(yōu)點(diǎn)非常適用于各種水下作業(yè),如探測、搜索、追蹤、圍堵等[1]。

目前多數(shù)AUV受續(xù)航能力限制,航速有限,面向水下有人平臺(tái)搜索任務(wù)難以在任務(wù)約束時(shí)間內(nèi)完成任務(wù)區(qū)域覆蓋搜索[2-4]。因此如何有效規(guī)劃AUV的搜索路徑,使得有限時(shí)間內(nèi)搜索到目標(biāo)的概率最大,成為亟待解決的關(guān)鍵問題。AUV動(dòng)態(tài)目標(biāo)搜索過程實(shí)質(zhì)上是連續(xù)時(shí)間和空間上的優(yōu)化搜索問題,較多研究者在研究搜索作業(yè)時(shí)都進(jìn)行了一定的簡化處理,如將區(qū)域網(wǎng)格化等[5],但這種方法使得搜索過程離散化,與實(shí)際情況有著較大的差異。

遺傳算法作為一種搜索啟發(fā)式算法,廣泛應(yīng)用于解決最優(yōu)化問題[6],因此其適用于上述有限時(shí)間內(nèi)動(dòng)態(tài)目標(biāo)搜索問題,但它也存在一定的不足,如各種算子的參數(shù)選擇大多依靠經(jīng)驗(yàn),存在著一定的隨機(jī)性,算法在大規(guī)模計(jì)算問題中容易陷入“早熟”,即過早陷入局部極值,除此之外,既保留優(yōu)秀個(gè)體又維持種群多樣性同樣也是該方法的一個(gè)難點(diǎn)。因此在解著決上述問題時(shí)需要對(duì)遺傳算法進(jìn)行優(yōu)化。

1 問題描述

由于敵方目標(biāo)在一定時(shí)間內(nèi)航行深度較為穩(wěn)定,本文重點(diǎn)研究二維平面內(nèi)的搜索規(guī)劃方法。假設(shè)某一時(shí)刻一艘AUV接收到岸基總臺(tái)發(fā)送的敵目標(biāo)指示信息,目標(biāo)位置記為Pt0,記岸基位置為坐標(biāo)原點(diǎn),以正東方向?yàn)閄軸,正北方向?yàn)閅軸建立平面直角坐標(biāo)系,則目標(biāo)位置可表示為Pt0=(xt0,yt0)。當(dāng)AUV到達(dá)Pt0位置,開始執(zhí)行搜索任務(wù),記為0時(shí)刻。

AUV在前往Pt0位置過程中,水下目標(biāo)也處于動(dòng)態(tài)運(yùn)動(dòng)中,但水下目標(biāo)的運(yùn)動(dòng)具有很強(qiáng)的隨機(jī)性,AUV無法事先知道,故假設(shè)當(dāng)AUV到達(dá)Pt0位置時(shí),水下目標(biāo)運(yùn)動(dòng)起始位置Pt1=(xt1,yt1)服從二維正態(tài)分布,即

(1)

其中,σ為導(dǎo)航誤差。

在一段較長的固定時(shí)間[0,Tend]的搜索任務(wù)中, AUV和水下目標(biāo)的轉(zhuǎn)向時(shí)間可忽略不計(jì)。AUV為確保探測聲吶的穩(wěn)定性,搜索行進(jìn)時(shí)采用勻速航行,期間可多次調(diào)整方向,直至搜索時(shí)間結(jié)束。相比之下,水下運(yùn)動(dòng)目標(biāo)具有更多的不確定性,可以多次進(jìn)行改向和變速操作,但水下目標(biāo)在轉(zhuǎn)向時(shí)由于結(jié)構(gòu)和體型等原因,無法像AUV一樣進(jìn)行較大幅度的轉(zhuǎn)向,目標(biāo)在轉(zhuǎn)向前的航向角αn和轉(zhuǎn)向后的航向角αn+1,應(yīng)滿足公式(2)和(3),其中f(α1)為其開始任務(wù)時(shí)的航向角α1的概率密度函數(shù)。

(2)

(3)

目標(biāo)各段速度v的取值服從 [Vmin,Vmax] 之間的均勻分布,各段航行時(shí)間t服從參數(shù)為λ的指數(shù)分布。它們的概率密度函數(shù)如下所示:

(4)

(5)

式(4)中Vmax和Vmin分別為水下動(dòng)目標(biāo)的最大和最小運(yùn)行速度。

根據(jù)上述模型構(gòu)建,所能得到的目標(biāo)運(yùn)動(dòng)軌跡數(shù)目是無限的,無法通過列舉等常規(guī)方法得出運(yùn)動(dòng)軌跡,但借用蒙特卡羅(Monte Carlo)方法,可以通過計(jì)算機(jī)輔助生成大量目標(biāo)運(yùn)動(dòng)軌跡作為水下目標(biāo)實(shí)際運(yùn)動(dòng)軌跡的模擬。蒙特卡羅目標(biāo)運(yùn)動(dòng)模型由大量的目標(biāo)軌跡組成,軌跡路線可以源自于歷史數(shù)據(jù)分析,也可能源自于先驗(yàn)地圖的仿真,也可以像前文所描述的采用隨機(jī)數(shù)生成的方法,產(chǎn)生大量目標(biāo)運(yùn)動(dòng)軌跡,抑或是多種數(shù)據(jù)的融合。以50束目標(biāo)運(yùn)動(dòng)軌跡為一簇作為基礎(chǔ),可以將這些軌跡整合為多簇,通過計(jì)算機(jī)模擬仿真生成的一簇軌跡如圖1所示。

圖1 計(jì)算機(jī)模擬生成的50條目標(biāo)運(yùn)動(dòng)軌跡Fig.1 The 50 target trajectories generated by computer simulation

受水中因素的影響,AUV在搜索過程中常采用的工具是聲吶,包括主動(dòng)聲吶和被動(dòng)聲吶,在本文中為擴(kuò)大探索范圍,可采用被動(dòng)聲吶進(jìn)行探測,根據(jù)AUV與水下動(dòng)目標(biāo)的距離D(單位:海里)進(jìn)行瞬時(shí)探測,瞬時(shí)探測P(D)可描述為下式

(6)

與其他搜索過程所注重的完成全覆蓋搜索所用時(shí)間等完成度指標(biāo)不同的是,本文將目標(biāo)函數(shù)設(shè)為在一定時(shí)間內(nèi)的最大探測概率,又稱為累積探測概率(Cumulative Detection Probability,CDP)[7]。在0≤t≤T時(shí),t時(shí)刻的累積探測概率(CDP)記為Fd(t),定義為[0,T]時(shí)間段內(nèi)至少發(fā)生一次探測的概率,即

Fd(t)=Pr{在時(shí)刻t以前至少發(fā)生一次探測}=Pr{ 初始探測時(shí)間≤t}

2 基于改進(jìn)遺傳算法的目標(biāo)搜索策略

遺傳算法(Genetic Algorithm,簡稱GA)作為一種隨機(jī)全局搜索優(yōu)化方法,概念來源于生物系統(tǒng)的遺傳與進(jìn)化,通過模擬自然界基因?qū)用嫔系膹?fù)制、交叉(crossover)和變異(mutation)等現(xiàn)象以及自然界中的物競天擇現(xiàn)象,在一代又一代種群的繁衍進(jìn)化中,得到最適應(yīng)環(huán)境的個(gè)體,即求得問題的最優(yōu)解[6]。但它也存在著易“早熟”,過早陷入極值等問題。

本文采用改進(jìn)遺傳算法進(jìn)行搜索路徑優(yōu)化,并采用蒙特卡羅統(tǒng)計(jì)方法建立評(píng)價(jià)度指標(biāo),在種群的選擇上將災(zāi)變思想與精英主義相結(jié)合,既保留優(yōu)秀個(gè)體,同時(shí)也給予種群產(chǎn)生更優(yōu)秀基因片段的機(jī)會(huì),避免過早陷入局部極值。交叉和變異操作基于橢圓約束遺傳算子,并采用混沌序列對(duì)交叉或變異點(diǎn)的選取進(jìn)行改進(jìn),再對(duì)交叉概率與變異概率進(jìn)行動(dòng)態(tài)自適應(yīng),減少對(duì)經(jīng)驗(yàn)的依賴,同時(shí)盡量在后期也維持種群的多樣性,具體流程圖如圖2所示。

圖2 改進(jìn)遺傳算法流程圖Fig.2 Flow chart of improved genetic algorithm

遺傳算法最重要的幾個(gè)部分為遺傳算法編碼的描述,適應(yīng)度函數(shù)的設(shè)計(jì),初始種群的產(chǎn)生,遺傳過程中選擇、交叉、變異的操作和最后的迭代終止條件的設(shè)定[8]。

2.1 編碼

編碼作為遺傳算法的首要和關(guān)鍵步驟,會(huì)對(duì)交叉算子、變異算子等運(yùn)算方法產(chǎn)生重要影響,進(jìn)而影響遺傳算法的效率[9]。

在此問題中,AUV的搜索過程實(shí)質(zhì)上是連續(xù)時(shí)間和空間上的優(yōu)化搜索問題,因此AUV的編碼形式采用變長實(shí)數(shù)編碼。設(shè)P為種群的總體,種群大小為N,種群內(nèi)的個(gè)體記為pi(i=1,2,3,…,N),表示一條搜索路徑,每一個(gè)個(gè)體由多個(gè)基因組成,即pi=(gi1,gi2,…,gij,…),gij代表第i個(gè)個(gè)體上的第j個(gè)基因,而gij=(xij,yij,tij),其中xij,yij,tij分別代表第i個(gè)個(gè)體運(yùn)行至節(jié)點(diǎn)j時(shí)的橫坐標(biāo),縱坐標(biāo)和時(shí)間點(diǎn)。

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

由于此搜索過程是連續(xù)時(shí)間和空間上的[10-12],航路實(shí)際上是無限條的,需要設(shè)計(jì)一個(gè)目標(biāo)函數(shù)(適應(yīng)度函數(shù))作為評(píng)價(jià)指標(biāo),即后續(xù)選擇操作的依據(jù)。

本文采用 CDP 作為適應(yīng)度函數(shù),可根據(jù)水聲模型及離散探測概率公式,由蒙特卡羅法完成適應(yīng)度函數(shù)的計(jì)算。假設(shè)根據(jù)蒙特卡羅法生成了S條目標(biāo)路線,其中第j條路線記為Sj,而在種群某代中某一個(gè)體pi有M個(gè)基因(即M個(gè)坐標(biāo)點(diǎn)),則其路線共有M-1段,每一段均分為10個(gè)點(diǎn)作為這一段的采樣點(diǎn),分別計(jì)算個(gè)體pi和路線Sj在這10個(gè)采樣點(diǎn)時(shí)刻的距離差值,代入公式(6)計(jì)算得到這10個(gè)點(diǎn)的瞬時(shí)探測概率,取其中的最大值代表個(gè)體pi在第k段的瞬時(shí)探測概率,記為Pins(k) (k=1,2,3,…,M-1),則pi對(duì)Sj的探測概率可描述為

Pij=F(Pins(1),Pins(2),…,Pins(M-1))

(7)

根據(jù)文獻(xiàn)[7]和實(shí)驗(yàn)總結(jié),可設(shè)計(jì)得到如下CDP的計(jì)算公式

(8)

式中,α=1-e-λΔk,Δk為個(gè)體pi中第k段路線的用時(shí),Pimax為Pins(k)中的最大值。

2.3 種群的產(chǎn)生

初始種群按照一定的隨機(jī)性生成初始群體。按照編碼規(guī)則隨機(jī)生成初始群體。初始種群可采用隨機(jī)生成的方式,隨機(jī)生成的個(gè)體可提供更豐富的基因片段,通過交叉和選擇可留下更優(yōu)秀的個(gè)體。

2.4 遺傳過程的選擇

遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取優(yōu)秀個(gè)體,以便遺傳到下一代群體。選擇操作用來確定重組或交叉?zhèn)€體,以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。

現(xiàn)在大多數(shù)遺傳算法的選擇過程采用的都是輪盤賭的方式,但也會(huì)帶來早期高適應(yīng)度個(gè)體迅速占據(jù)種群和后期的種群中因個(gè)體適應(yīng)度不大而導(dǎo)致的種群停止進(jìn)化問題[6]。

為避免此類問題,提出災(zāi)變思想與精英主義相結(jié)合的思想。災(zāi)變思想[13]是指消滅最優(yōu)秀的一部分個(gè)體,才有可能誕生更優(yōu)秀的個(gè)體,而精英主義思想是指在每一次產(chǎn)生新一代時(shí),保留上一代最優(yōu)秀的一部分個(gè)體到下一代。看似沖突的兩者卻可以相結(jié)合。在每一代進(jìn)行交叉運(yùn)算時(shí),直接將最優(yōu)秀的個(gè)體復(fù)制到下一代,但當(dāng)連續(xù)多代的最優(yōu)秀個(gè)體沒有變化時(shí),則認(rèn)為算法可能已經(jīng)陷入了局部極值,此時(shí)進(jìn)行災(zāi)變操作,將最優(yōu)秀的部分個(gè)體消滅(包括直接保留的最優(yōu)秀個(gè)體),再進(jìn)行交叉變異等操作,在經(jīng)歷過若干次災(zāi)變后產(chǎn)生個(gè)體的適應(yīng)度與災(zāi)變前一樣時(shí),則停止災(zāi)變,同時(shí)認(rèn)為算法已經(jīng)跳出局部極值,表明進(jìn)化完成。

2.5 遺傳過程的交叉

本文采用基于橢圓約束的單點(diǎn)交叉策略[14-15],交叉概率設(shè)為Pc。如圖3所示,若選擇種群內(nèi)的兩個(gè)個(gè)體(即兩條染色體)p1和p2進(jìn)行交叉操作,A、B、C三點(diǎn)位于染色體p1上,坐標(biāo)分別為XA,XB,XC,在時(shí)間軸上所代表的時(shí)間分別為tA,tB,tC,D、E、F三點(diǎn)位于染色體p2上,坐標(biāo)分別為XD,XE,XF,在時(shí)間軸上所代表的時(shí)間分別為tD,tE,tF,而T1和T2分別位于染色體p1和p2上,但它們在時(shí)間軸上都代表同一時(shí)刻tc,由于AUV一直保持勻速運(yùn)動(dòng),染色體的交叉過程應(yīng)滿足橢圓約束。在此設(shè)d(Xi,Xj)代表Xi和Xj兩點(diǎn)間的歐氏距離,而Xi可表示為Xi=(xi,yi),因此有

(9)

以圖3為例,分別選取染色體p1和p2上的B、E兩點(diǎn)作為交叉點(diǎn),很明顯,B、E兩點(diǎn)需要滿足

d(B,E)≤V0×|tB-tE|

(10)

其中V0為AUV的勻速速度。

但線段BE不可能每次都恰好滿足AUV運(yùn)動(dòng)時(shí)的空間和時(shí)間上的連續(xù)性,即d(B,E)=V0×|tB-tE|不是對(duì)所有的交叉點(diǎn)B和E都成立, 因此,需要找一個(gè)點(diǎn)G,使得E、G間距離與B、G間距離之和等于E到T2的距離與T1到B的距離之和,即:

d(B,G)+d(E,G)=V0×|tT2-tE|+V0×|tT1-tB|=

V0×|tc-tE|+V0×|tc-tB|=V0×|tB-tE|

(11)

而V0×|tB-tE|對(duì)于任意兩個(gè)確定的交叉點(diǎn)B和E,其值都為一個(gè)常數(shù),因此可看出G點(diǎn)位于以B、E為焦點(diǎn)的橢圓上,但由于時(shí)間上的不可逆性,通過基于橢圓約束的交叉方法只能生成1條子染色體,如圖3中只能生成DEGBC這條子染色體。

圖3 基于橢圓約束的交叉節(jié)點(diǎn)示意圖Fig.3 Schematic diagram of crossover diagram based on elliptic constraints

例子中的交叉點(diǎn)B、E可按照Logistic混沌序列[16]方式進(jìn)行選取,具體步驟如下:若被選擇染色體p1共有20個(gè)節(jié)點(diǎn)(包括起點(diǎn)和終點(diǎn)),編號(hào)為1-20,因此可選取的交叉節(jié)點(diǎn)只有2-19號(hào)。先取一個(gè)(0,1)的隨機(jī)初始值,再利用混沌序列x(n+1)=4x(n)(1-x(n))迭代多次(即多次代入x(n))產(chǎn)生一個(gè)新值,再把這個(gè)值乘以18再加2,最后取整數(shù)部分即可。假如這個(gè)數(shù)為14,則表示這條染色體的14號(hào)節(jié)點(diǎn)作為交叉點(diǎn)。同理可選取出p2的交叉點(diǎn),再按時(shí)間先后順序生成了染色體。這種選取方式對(duì)原來的解改動(dòng)較小,可以削弱遺傳算法在組合優(yōu)化算法中產(chǎn)生的尋優(yōu)抖振問題,可以提高算法收斂精度[16]。

由于交叉過程中G點(diǎn)的選擇具有較強(qiáng)的隨機(jī)性,為做出一定的規(guī)范,取其橢圓短軸的頂點(diǎn),頂點(diǎn)的選取應(yīng)使EG的方向與DE的方向夾角不超過90°。

2.6 遺傳過程的變異

變異操作是實(shí)現(xiàn)全局最優(yōu)解的關(guān)鍵環(huán)節(jié),增加變異運(yùn)算可以防止過早陷入局部最優(yōu)解。在此模型中,變異概率設(shè)為Pm,可采用的合適的變異操作有替換節(jié)點(diǎn)或消除節(jié)點(diǎn)兩種方案,采用替換和消除操作的概率相等,都為50%。被替換節(jié)點(diǎn)Ni同樣按照Logistic混沌序列方式進(jìn)行選取。

替換節(jié)點(diǎn)和交叉一樣,也受到橢圓約束,如圖4所示。p為一條染色體,替換節(jié)點(diǎn)選擇Ni,Ni的前一個(gè)節(jié)點(diǎn)為Ni-1,Ni的后一個(gè)節(jié)點(diǎn)為Ni+1,為保持AUV運(yùn)動(dòng)時(shí)在空間和時(shí)間上的連續(xù)性,將節(jié)點(diǎn)Ni替換為N′i時(shí),應(yīng)滿足

d(Ni-1,N′i)+d(N′i,Ni+1)=d(Ni-1,Ni)+d(Ni,Ni+1)

(12)

對(duì)每一條確定的染色體p,d(Ni-1,Ni)+d(Ni,Ni+1)都為一個(gè)常數(shù),因此,更改的節(jié)點(diǎn)N′i也位于以Ni-1和Ni+1為焦點(diǎn)的橢圓上。

消除節(jié)點(diǎn)操作是指刪去染色體中的某一節(jié)點(diǎn)Nj,將Nj的前一個(gè)節(jié)點(diǎn)Nj-1以及Nj的后一個(gè)節(jié)點(diǎn)Nj+1連起來,并且將從Nj+1及以后的節(jié)點(diǎn)的對(duì)應(yīng)時(shí)間都進(jìn)行改正,并在最后的節(jié)點(diǎn)末尾加上一段運(yùn)動(dòng)軌跡,以彌補(bǔ)因?yàn)閯h除節(jié)點(diǎn)而缺少的時(shí)間,使AUV能在Tend時(shí)刻結(jié)束搜索。

圖4 基于橢圓約束的替換節(jié)點(diǎn)示意圖Fig.4 Schematic diagram of replacement node based on elliptic constraint

2.7 自適應(yīng)的交叉與變異概率

遺傳算法中的交叉概率Pc和變異概率Pm對(duì)算法的行為和性能影響非常大,Pc過大會(huì)導(dǎo)致遺傳模式出現(xiàn)問題,高適應(yīng)度的個(gè)體很難存活,Pc過小會(huì)導(dǎo)致搜索速度慢,種群停滯不前。Pm過大則偏向于隨機(jī)搜索,Pm過小則不易產(chǎn)生新的個(gè)體,且算法各時(shí)期對(duì)交叉和變異的需求都不同,因此,Pc和Pm應(yīng)隨著適應(yīng)度自動(dòng)變化。本文采用任子武[17]等提出的自適應(yīng)公式。

(13)

(14)

其中,變量Pc和Pm為自適應(yīng)后的交叉概率和變異概率,fmax為每代種群中最大的適應(yīng)度值,favg為每代種群中平均適應(yīng)度值,f′為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值,f為要變異個(gè)體的適應(yīng)度值。Pc1、Pc2、Pm1、Pm2都有規(guī)范的取值。

3 實(shí)驗(yàn)與仿真

本次實(shí)驗(yàn)仿真平臺(tái)為Matlab,實(shí)驗(yàn)參數(shù)設(shè)置:水下動(dòng)目標(biāo)最小航速為0節(jié),代表靜止,最大航速為20節(jié);被發(fā)現(xiàn)初始位置點(diǎn)Pt0為(50,50) ,單位為海里,其運(yùn)行路線為折線;AUV行進(jìn)勻速速度為10節(jié),兩者水平面間距離為2 海里,搜索任務(wù)總時(shí)長為3 h。為使結(jié)果更具有適用性和可靠性,在初始生成的路線數(shù)量設(shè)定上應(yīng)盡可能多一些,因此設(shè)定初始種群的數(shù)量為100,進(jìn)化最大代數(shù)為100,采用蒙特卡羅法仿真的水下動(dòng)目標(biāo)路線為2 000條。選擇操作中直接保留優(yōu)秀個(gè)體中的適應(yīng)度值前2%的個(gè)體,而災(zāi)變操作中直接刪除的個(gè)體占總數(shù)的5%,交叉算子和變異算子中的Pc1、Pc2、Pm1、Pm2取值采用經(jīng)典取值,分別為0.9、0.6、0.1、0.001。

先采用外螺旋式傳統(tǒng)算法進(jìn)行實(shí)驗(yàn),可得到其行進(jìn)路線,如圖5所示,并與用蒙特卡羅法生成的2 000條水下目標(biāo)運(yùn)動(dòng)路線進(jìn)行仿真計(jì)算,可得出其探測概率為0.429。

圖5 外螺旋式搜索路徑Fig.5 External spiral search path

傳統(tǒng)遺傳算法在同樣的仿真環(huán)境,問題模型以及種群數(shù)目、目標(biāo)數(shù)目和種群迭代數(shù)目等參數(shù)相同的條件下,得到的最優(yōu)路徑路線如圖6所示,其各代最優(yōu)適應(yīng)度函數(shù)曲線如圖7所示,各代探測概率中的最大值為56.1%。從這個(gè)最大值可以看出,經(jīng)典遺傳算法相比外螺旋式傳統(tǒng)算法,路徑整體也呈現(xiàn)外螺旋式結(jié)構(gòu),但不規(guī)則,且各代最優(yōu)適應(yīng)度函數(shù)曲線整體先逐漸上升后趨于穩(wěn)定。因?yàn)榻?jīng)典遺傳算法未引入精英主義策略,所以該函數(shù)曲線不是每代的最大探測概率都能保證比上一代大,即呈現(xiàn)波動(dòng)上升的趨勢,且遺傳算法由于自身的局限性,非常容易陷入局部極值,像該曲線一樣,從44代開始最大探測概率就在53%上下波動(dòng)。

圖6 經(jīng)典遺傳算法最大適應(yīng)度個(gè)體搜索路徑Fig.6 Classical genetic algorithm maximum fitness individual search path

圖7 經(jīng)典遺傳算法最大探測概率進(jìn)化曲線Fig.7 Evolution curve of maximum detection probability of classical genetic algorithm

由改進(jìn)遺傳算法得到的最優(yōu)路徑路線如圖8所示,此路線和傳統(tǒng)遺傳算法一樣,呈不規(guī)則的外螺旋狀。改進(jìn)遺傳算法各代最優(yōu)適應(yīng)度函數(shù)曲線如圖9所示,各代探測概率中的最大值為63.3%,從此值的對(duì)比可看出改進(jìn)遺傳算法累積探測概率明顯優(yōu)于外螺旋式傳統(tǒng)算法,也優(yōu)于經(jīng)典遺傳算法。由于引進(jìn)了精英主義思想,保留最優(yōu)秀個(gè)體,除了災(zāi)變發(fā)生時(shí)曲線基本不會(huì)下降。當(dāng)多次最優(yōu)適應(yīng)度基本不變時(shí),會(huì)進(jìn)行災(zāi)變操作,去除最優(yōu)的部分個(gè)體,此時(shí)曲線會(huì)降低,后逐步上升。改進(jìn)遺傳算法和經(jīng)典遺傳算法由于計(jì)算量基本相同,所用時(shí)間都較長,經(jīng)典遺傳算法收斂速度更快,但它更容易陷入極值,改進(jìn)遺傳算法在搜索概率上更具優(yōu)勢。

圖8 改進(jìn)遺傳算法最大適應(yīng)度個(gè)體搜索路徑Fig.8 Improved genetic algorithm for maximum fitness individual search path

圖9 改進(jìn)遺傳算法最大探測概率進(jìn)化曲線Fig.9 Evolution curve of maximum detection probability of improved genetic algorithm

4 結(jié)束語

針對(duì)未知區(qū)域的動(dòng)態(tài)目標(biāo)搜索問題,本文提出采用災(zāi)變思想與精英主義相結(jié)合的改進(jìn)遺傳算法,采用蒙特卡羅統(tǒng)計(jì)方法生成大量目標(biāo)運(yùn)動(dòng)軌跡,作為計(jì)算種群個(gè)體適應(yīng)度依據(jù)。同時(shí)在適應(yīng)度函數(shù)的設(shè)計(jì)上結(jié)合水聲模型提出一種新型的累積探測概率算法,使其具有更明顯的區(qū)分性。種群選擇方法上將災(zāi)變思想與精英主義相結(jié)合,在保留優(yōu)秀個(gè)體的同時(shí)也給予種群產(chǎn)生更優(yōu)秀基因片段的機(jī)會(huì),有效跳出局部極值。交叉和變異操作基于橢圓約束遺傳算子,并采用混沌序列對(duì)交叉或變異點(diǎn)的選取進(jìn)行改進(jìn),提高隨機(jī)性帶來的差距,加速跳出局部極值。交叉概率與變異概率采用動(dòng)態(tài)自適應(yīng)策略,減少對(duì)經(jīng)驗(yàn)的依賴,并在后期維持種群的多樣性。本算法相較于外螺旋式傳統(tǒng)算法和經(jīng)典遺傳算法,能有效跳出局部極值,提高搜索到動(dòng)態(tài)目標(biāo)的概率。

盡管此方法得到了較高的搜索概率,但適用場景有限,接下來會(huì)考慮AUV與目標(biāo)的縱向運(yùn)動(dòng),將此方法擴(kuò)展到三維仿真環(huán)境中,同時(shí)根據(jù)實(shí)際環(huán)境增加障礙物,進(jìn)一步優(yōu)化算法的適應(yīng)度函數(shù)設(shè)計(jì),提高算法泛用性與可靠性。