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

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

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

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

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

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

1 算法原理

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

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

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

1.2 粒子群算法

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

圖1 粒子所受的影響因素

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

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

1.3 遺傳算法

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

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

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

2.1 遺傳粒子群算法

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

2.2 交叉算法

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

2.3 變異算法

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

3 實驗結(jié)果及分析

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

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

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

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

圖3 粒子群算法實驗結(jié)果

圖4 遺傳粒子群算法實驗結(jié)果

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

4 結(jié)論

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