基于遺傳粒子群算法的無人船集群目標(biāo)分配

翟澤宇，許志遠(yuǎn)，邱文軒，曲勝，張曉鵬，許航

（大連海洋大學(xué)航海與船舶工程學(xué)院，遼寧 大連116023 ）

隨著海上通信、協(xié)同控制和人工智能等技術(shù)的不斷發(fā)展，多智能體在海上協(xié)同作業(yè)變?yōu)榭赡躘1]。無人船因具有獨(dú)立性高、靈活性強(qiáng)和成本低等優(yōu)勢(shì)，在救助搜查、水底探測(cè)和環(huán)境監(jiān)控等領(lǐng)域得到了廣泛應(yīng)用。無人船集群在執(zhí)行海面各項(xiàng)任務(wù)中，會(huì)更加關(guān)注于各個(gè)成員之間的協(xié)作與分工。不同的任務(wù)需要不同的集群隊(duì)形來完成，因此對(duì)無人船集群目標(biāo)分配路徑、時(shí)間和效率都提出了更高要求。

關(guān)于多無人船集群的目標(biāo)任務(wù)分配問題，朱曉軍等[2]使編隊(duì)的部署能力用遺傳算法進(jìn)行優(yōu)化；Wei等[3]提出了基于粒子群算法的雙級(jí)任務(wù)分配法，使任務(wù)完成精度和可靠性得到提升；牛曉博等[4]采用帶精英策略的快速非支配遺傳算法，較好完成編隊(duì)分配問題，又解決了單目標(biāo)分配優(yōu)化的局限性。Chopra等[5]通過改進(jìn)匈牙利算法，解決并行分配任務(wù)的問題；呂光顥等[6]提出最大迭代次數(shù)的拍賣終止機(jī)制，解決改進(jìn)傳統(tǒng)拍賣算法在重構(gòu)分配中存在無可行解的問題；馬碩等[7]采用分層聚類拍賣算法，解決多任務(wù)分組的問題；李磊等[8]提出采用布谷鳥優(yōu)化方法，為目標(biāo)點(diǎn)附近的過程規(guī)劃能耗最優(yōu)的運(yùn)動(dòng)方案。解決目標(biāo)分配的算法，都會(huì)涉及到提高計(jì)算效率、空間內(nèi)全面搜索、并行運(yùn)行、提升分配精準(zhǔn)度等問題。

為解決上述問題提出基于遺傳粒子群算法的無人船集群目標(biāo)分配方法，以粒子群算法為基礎(chǔ)與遺傳算法相結(jié)合，通過對(duì)無人船分配到的劣勢(shì)目標(biāo)點(diǎn)進(jìn)行不斷地替換，尋找到更具有優(yōu)勢(shì)的目標(biāo)點(diǎn)，完成無人船集群目標(biāo)分配任務(wù)。

1 算法原理

1.1 目標(biāo)分配原理

目標(biāo)分配是指將多個(gè)目標(biāo)點(diǎn)分配給多艘無人船，使其分別到達(dá)指定目標(biāo)點(diǎn)的分配問題。無人船作為抵達(dá)目標(biāo)點(diǎn)的主體，用表示，n為無人船數(shù)量。無人船的初始位置表示為；目標(biāo)點(diǎn)表示為；n 為目標(biāo)點(diǎn)數(shù)目，與無人船數(shù)目相同。目標(biāo)點(diǎn)的位置為；無人船與目標(biāo)點(diǎn)為一一對(duì)應(yīng)關(guān)系，如式1；其中：xij為目標(biāo)點(diǎn)分配的結(jié)果，無人船ui的目標(biāo)點(diǎn)分配是目標(biāo)點(diǎn)pj；如果xij=1，無人船ui和目標(biāo)點(diǎn)pj配對(duì)成功。C 為無人船和目標(biāo)點(diǎn)一一對(duì)應(yīng)的所有集合。

目標(biāo)分配的優(yōu)劣影響整個(gè)集群構(gòu)建隊(duì)形的效率，并且直接關(guān)系到集群中各艘無人船是否能盡快到達(dá)目標(biāo)點(diǎn)，避免占用更多的資源。

1.2 粒子群算法

粒子群算法在無人船集群目標(biāo)分配中，每艘無人船尋找目標(biāo)點(diǎn)的最終方向受三個(gè)影響因素，如圖1 所示。

圖1 粒子所受的影響因素

如果設(shè)無人船當(dāng)前時(shí)刻的速度向量為vid，當(dāng)前位置為xid，用式2 和式3 表示；其中，為慣性因子，取值為1；C1為個(gè)體影響因子；C2為整體影響因子；id為粒子自身最優(yōu)點(diǎn)；gd 為群體最優(yōu)點(diǎn)；r1和r2為[0,1]之間的隨機(jī)值。

粒子群算法的本質(zhì)是利用2 個(gè)最優(yōu)點(diǎn)來指導(dǎo)粒子下一步位置。當(dāng)有無人船找到目標(biāo)點(diǎn)后，未找到目標(biāo)點(diǎn)的無人船，受已找到目標(biāo)點(diǎn)無人船的位置影響，其位置和速度會(huì)發(fā)生改變，會(huì)造成無人船無效行程和分配時(shí)間的增加。

1.3 遺傳算法

遺傳算法在無人船集群目標(biāo)分配操作如下：第一步確定無人船集群數(shù)量，設(shè)置最大進(jìn)化代數(shù)并根據(jù)無人船初始位置和當(dāng)前分配到的目標(biāo)點(diǎn)位置進(jìn)行編碼；第二步確定適應(yīng)度函數(shù)，并計(jì)算每艘無人船初始位置和目標(biāo)點(diǎn)對(duì)應(yīng)組合的適應(yīng)度值，根據(jù)適應(yīng)度值選擇進(jìn)入下一代的組合，對(duì)未被選擇的組合進(jìn)行交叉和變異操作；第三步對(duì)產(chǎn)生新的無人船初始位置和目標(biāo)點(diǎn)的對(duì)應(yīng)組合計(jì)算，不斷迭代，直到所有無人船得到對(duì)應(yīng)目標(biāo)點(diǎn)后，算法停止。

遺傳算法采用群體搜索提高尋找目標(biāo)點(diǎn)的效率。但在操作時(shí)無人船缺乏指導(dǎo)方向，導(dǎo)致算法收斂慢。因此將粒子群算法和遺傳算法相結(jié)合[9]，減少最優(yōu)點(diǎn)對(duì)粒子的影響，使無人船尋找目標(biāo)點(diǎn)的效率提升。

2 基于遺傳粒子群算法的無人船集群目標(biāo)分配

2.1 遺傳粒子群算法

通過粒子群算法得到無人船當(dāng)前分配的目標(biāo)點(diǎn)，并進(jìn)行編碼；再對(duì)無人船和目標(biāo)點(diǎn)的組合進(jìn)行自適應(yīng)函數(shù)計(jì)算，自適應(yīng)函數(shù)如式4。對(duì)適應(yīng)度值由高到低排序，選擇算子采用精英保留算法將排名在前的組合保留，不繼續(xù)后面的操作。

2.2 交叉算法

遺傳算法的交叉操作在粒子群算法的具體步驟是讓兩個(gè)最優(yōu)點(diǎn)進(jìn)行交叉操作，產(chǎn)生的解為新的粒子速度，也就是先將式2 中的項(xiàng)中的項(xiàng)C1，C2定義為一個(gè)概率組合。pc1和pc2分別代表個(gè)體最優(yōu)點(diǎn)和群體最優(yōu)點(diǎn)交叉操作的概率，通常情況下pc1=pc2=pc；其次，從種群中沒有進(jìn)入下一代的隨機(jī)選擇兩個(gè)，進(jìn)行個(gè)體配對(duì)；最后，在個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)進(jìn)行單點(diǎn)交叉操作。根據(jù)給定的交叉概率從而得到兩個(gè)新個(gè)體；通過交叉算子處理后的式2 更新為式5。

2.3 變異算法

通過遺傳操作之后，位置更新式3 表中速度項(xiàng)就是一個(gè)交換序列無人船迭代前后位置變化就是該交換序列作用于無人船迭代前位置的結(jié)果。由此得到第k 次迭代后位置x（k+1）和迭代前位置x（k）與這個(gè)速度交換序列v（k）之間的關(guān)系表示為式7；將得出的較優(yōu)目標(biāo)點(diǎn)的編碼替換原目標(biāo)點(diǎn)編碼。

3 實(shí)驗(yàn)結(jié)果及分析

通過MATLAB 對(duì)隨機(jī)分布的無人船集群進(jìn)行隊(duì)形構(gòu)建，并比較兩種算法所用時(shí)間和路程。

實(shí)驗(yàn)假設(shè)某一海域內(nèi)存在需要預(yù)設(shè)成DHD 隊(duì)形，構(gòu)建編隊(duì)是由48 艘隨機(jī)分布的無人船組成，對(duì)此分配問題進(jìn)行仿真。無人船的初始位置及目標(biāo)點(diǎn)位置，如圖2 所示。粒子群算法的分配結(jié)果如圖3 所示；遺傳粒子群算法的分配結(jié)果如圖4 所示；兩種算法的實(shí)驗(yàn)仿真數(shù)據(jù)，如表1 所示。

表1 兩種算法仿真結(jié)果對(duì)比

圖2 DHD 隊(duì)形中無人船與目標(biāo)點(diǎn)分布圖

圖3 粒子群算法實(shí)驗(yàn)結(jié)果

圖4 遺傳粒子群算法實(shí)驗(yàn)結(jié)果

目標(biāo)分配結(jié)果可得，遺傳粒子群算法對(duì)無人船分配得目標(biāo)點(diǎn)會(huì)更為合理化，無人船之間相交的路線明顯減少；遺傳粒子群算法的分配時(shí)間減少約27.4%，所行使的路徑長(zhǎng)度也縮短了約10.9%；對(duì)于粒子群算法無法保證目標(biāo)分配的成功率，而遺傳粒子群算法可以維持100%的分配成功率。

4 結(jié)論

以粒子群算法為基礎(chǔ)，結(jié)合遺傳算法對(duì)無人船集群的目標(biāo)分配問題進(jìn)行優(yōu)化，結(jié)合后的算法具有搜索面積廣和靈活性高的特點(diǎn)，對(duì)目標(biāo)點(diǎn)的搜索和確認(rèn)速度明顯加快。與粒子群算法相比，遺傳粒子群算法得到目標(biāo)點(diǎn)的分配時(shí)間和路徑長(zhǎng)度有明顯減少，也使到達(dá)分配目標(biāo)的路徑更加合理，目標(biāo)分配的成功率也有很好的保證，對(duì)于無人船集群隊(duì)形構(gòu)建起到了較好的輔助作用。