改進(jìn)離散粒子群算法的多無人艇任務(wù)分配研究?

趙冬梅 宋 陽(yáng) 周國(guó)軍 崔海峰

（海軍大連艦艇學(xué)院基礎(chǔ)部 大連 116018）

1 引言

無人艇（USV）結(jié)構(gòu)簡(jiǎn)單，價(jià)格低廉，安全性好，適合在危險(xiǎn)區(qū)域執(zhí)行搜救、偵察、巡邏、打擊等多種任務(wù)［1～2］。2022年6月7日，我國(guó)首艘全國(guó)產(chǎn)化的百噸級(jí)無人艇在舟山海域順利完成首次海上自主航行試驗(yàn)，標(biāo)志著我國(guó)無人艇自主航行和智能機(jī)艙技術(shù)取得了新的突破［3］。隨著無人艇技術(shù)的發(fā)展，在未來戰(zhàn)場(chǎng)上，無人艇將大顯身手，成為海戰(zhàn)的主力。

任務(wù)分配是多無人艇協(xié)同控制技術(shù)研究的關(guān)鍵環(huán)節(jié)，是在復(fù)雜的戰(zhàn)場(chǎng)環(huán)境中，在滿足一定的約束條件下，為各無人艇分配任務(wù)并確定任務(wù)時(shí)序［4］。任務(wù)分配模型可分為集中式、分布式和混合式三種，相較于分布式和混合式模型，當(dāng)執(zhí)行的任務(wù)間具有強(qiáng)約束時(shí)，集中式模型的全局求解能力更強(qiáng)，任務(wù)分配質(zhì)量更好［5］。集中式任務(wù)分配模型的典型求解算法包括匈牙利法［6］、混合整數(shù)規(guī)劃算法［7］等最優(yōu)方法和聚類算法、智能算法［8～12］等啟發(fā)式求解方法。

相比于其他算法，智能優(yōu)化算法以其概念簡(jiǎn)明、實(shí)現(xiàn)方便、參數(shù)設(shè)置少、魯棒性強(qiáng)［13］等優(yōu)點(diǎn)越來越受到研究學(xué)者的青睞。文獻(xiàn)［14］將約束融入到算法的粒子矩陣編碼和粒子更新策略中，有效解決了多類復(fù)雜約束條件下的任務(wù)分配問題；文獻(xiàn)［15］設(shè)計(jì)了雙層粒子群編碼方法，基于啟發(fā)信息和沖突消解策略改進(jìn)粒子群算法，提高了算法的收斂性和全局搜索能力；文獻(xiàn)［16］將粒子速度和坐標(biāo)離散化，改善基本粒子群不易處理離散問題的缺陷，實(shí)現(xiàn)了對(duì)艦載機(jī)彈藥的合理調(diào)度，但沒有對(duì)粒子的位置和速度更新公式加以改進(jìn)，算法的收斂性和靈活度不高；文獻(xiàn)［17］應(yīng)用離散粒子群算法解決消防救援隊(duì)伍在現(xiàn)場(chǎng)使用無人機(jī)時(shí)存在的多任務(wù)分配難題，提出引入逆轉(zhuǎn)算子對(duì)算法進(jìn)行優(yōu)化，提高了分配結(jié)果的可靠性和科學(xué)性，但沒有解決算法易陷入局部最優(yōu)問題；文獻(xiàn)［18］整合離散粒子群算法和Logistic 混沌算法，避免算法陷入局部最優(yōu)，但沒有改善算法的收斂性。

本文針對(duì)多無人艇打擊多目標(biāo)的任務(wù)分配問題，考慮時(shí)間窗約束和載荷約束，建立問題模型，確定評(píng)價(jià)函數(shù)。綜合上述文獻(xiàn)對(duì)離散粒子群算法改進(jìn)的優(yōu)缺點(diǎn)，提出一種新的改進(jìn)思路：初始化粒子群時(shí)利用Logistic 方程融入混沌優(yōu)化，以增加種群搜素初期的多樣性；為提高搜索效率，改進(jìn)慣性因子，設(shè)置其隨迭代次數(shù)呈指數(shù)遞減分布，以適應(yīng)不同時(shí)段的算法要求；設(shè)計(jì)隨迭代次數(shù)分別遞增和遞減的學(xué)習(xí)因子c1和c2，以平衡算法的局部搜索能力和全局搜索能力；完善粒子速度和位置更新機(jī)制，融入交叉和變異操作，以解決算法陷入局部最優(yōu)和收斂速度之間的矛盾。最后通過仿真實(shí)驗(yàn)驗(yàn)證改進(jìn)算法的優(yōu)越性。

2 任務(wù)分配問題建模

2.1 問題描述

假設(shè)在5km×5km 的海域內(nèi)有m 艘無人艇S={S1，S2，...，Sm}，到達(dá)n 個(gè)待打擊的目標(biāo)點(diǎn)T={T1，T2，...，Tn}執(zhí)行打擊任務(wù)，無人艇Si攜帶Wi個(gè)載荷，在滿足多項(xiàng)約束條件下，使無人艇完成打擊任務(wù)的評(píng)價(jià)指標(biāo)最好。

離散粒子群算法對(duì)于求解此類非線性整數(shù)規(guī)劃問題具有參數(shù)設(shè)置簡(jiǎn)單、執(zhí)行效率高等優(yōu)點(diǎn)［19］，建立無人艇和打擊目標(biāo)之間m×n階的決策變量矩陣如式（1）所示。

xij只能取1 或0，xij=1 表示無人艇Si對(duì)目標(biāo)Tj執(zhí)行打擊任務(wù)，xij=0 則不打擊。結(jié)合實(shí)際約束條件和評(píng)價(jià)函數(shù)求解出將m 艘無人艇的載荷分配給n個(gè)目標(biāo)的最優(yōu)目標(biāo)分配方案。

2.2 約束條件

1）時(shí)間窗約束

構(gòu)建模型時(shí)，通常要求無人艇在指定的時(shí)間段對(duì)目標(biāo)執(zhí)行打擊任務(wù)，時(shí)間窗約束如式（2）所示。

其中，Tj.StartTime_t和Tj.EndTime_t為指定的打擊第j 個(gè)目標(biāo)的起始和結(jié)束時(shí)間，StartTime_o和EndTime_o為實(shí)際打擊第j個(gè)目標(biāo)的起始和結(jié)束時(shí)間。

2）無人艇載荷約束

無人艇攜帶載荷數(shù)目有限，即執(zhí)行打擊任務(wù)的次數(shù)受限，若無人艇Si最多可攜帶Wi個(gè)載荷，無人艇使用載荷約束如式（3）所示。

3）目標(biāo)載荷約束

為避免出現(xiàn)多無人艇打擊目標(biāo)點(diǎn)過于集中的現(xiàn)象，要求無人艇對(duì)某個(gè)目標(biāo)使用的載荷總數(shù)有限，即對(duì)目標(biāo)Tj最多可使用Sj個(gè)載荷，目標(biāo)承受載荷約束如式（4）所示。

2.3 任務(wù)分配評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)體現(xiàn)無人艇任務(wù)分配的優(yōu)劣程度。本文設(shè)計(jì)基于完成任務(wù)的效益減去航線距離代價(jià)和執(zhí)行任務(wù)時(shí)間代價(jià)的任務(wù)分配評(píng)價(jià)函數(shù)，表達(dá)式如式（5）。

其中，ωR、ωD和ωT分別為任務(wù)效益、距離代價(jià)和時(shí)間代價(jià)的權(quán)重系數(shù)，體現(xiàn)每項(xiàng)收益或代價(jià)的重要程度，可根據(jù)實(shí)際需求動(dòng)態(tài)調(diào)整三項(xiàng)系數(shù)以體現(xiàn)任務(wù)分配的多原則決策機(jī)制。

為減少無人艇暴露時(shí)間，提高其執(zhí)行任務(wù)的安全性，以航線距離最長(zhǎng)的無人艇行駛距離作為時(shí)間代價(jià)，v為無人艇航行速度。

上述評(píng)價(jià)函數(shù)兼顧了執(zhí)行打擊任務(wù)的收益、距離和時(shí)間代價(jià)，能夠引導(dǎo)種群選擇出打擊效益高、航行距離短和執(zhí)行時(shí)間少的分配方案。

3 改進(jìn)離散粒子群算法

3.1 離散粒子群算法原理

粒子群算法是基于種群和進(jìn)化的概念，通過個(gè)體間的協(xié)作和競(jìng)爭(zhēng)，實(shí)現(xiàn)對(duì)復(fù)雜空間最優(yōu)解的搜索［20］。粒子通過開發(fā)和探索，依據(jù)最優(yōu)信息不斷更新迭代，速度向量νij和位置向量xij的更新規(guī)則如式（6）所示。

式（6）中，νij和xij分別表征第i 個(gè)粒子在第j 維空間的速度向量和位置向量；pij表征第i個(gè)粒子在第j維空間的個(gè)體最優(yōu)位置；pgj表征粒子群迄今為止在第j 維空間的全局最優(yōu)位置；w為慣性因子，表征粒子保持原有速度的能力；c1和c2為學(xué)習(xí)因子，表征粒子對(duì)自身的思考；r1和r2為［0，1］間的均勻隨機(jī)數(shù)，以增加粒子飛行的隨機(jī)性，保證種群的多樣性。由上述公式可以看出，粒子群算法的更新規(guī)則兼顧運(yùn)動(dòng)“習(xí)慣”、自身“認(rèn)知”和“社會(huì)”經(jīng)驗(yàn)，以便更快更準(zhǔn)確地搜索出最優(yōu)解。為避免粒子群的膨脹和發(fā)散，通常利用邊界約束將粒子速度和位置限制在可行搜索范圍內(nèi)，一般設(shè)置最大值和最小值，當(dāng)超出二者范圍時(shí)，產(chǎn)生取值范圍內(nèi)的一個(gè)隨機(jī)數(shù)代替當(dāng)前速度和位置值。

離散粒子群算法的思想是將基本粒子群算法中連續(xù)域的位置、速度向量離散化，粒子在狀態(tài)空間的取值只能為0 或1，每一維速度νij代表每一維位置xij取1 的可能性，所以個(gè)體最優(yōu)位置pij和全局最優(yōu)位置pgj只能在［0，1］內(nèi)取值，速度更新公式保持不變，而位置更新公式如式（7）所示。

式（7）中，r為［0，1］間的均勻隨機(jī)數(shù)。

利用離散粒子群算法求解任務(wù)分配問題時(shí)，每個(gè)粒子代表一種任務(wù)分配方案，根據(jù)評(píng)價(jià)函數(shù)計(jì)算各個(gè)粒子的適應(yīng)度值，更新個(gè)體、全局最優(yōu)位置和最優(yōu)值，更新粒子速度和位置，進(jìn)行邊界條件處理，重復(fù)上述步驟，直至迭代結(jié)束，得到最優(yōu)分配方案BestDistribution。

3.2 粒子的編碼與解碼

綜合考慮無人艇任務(wù)分配的載荷約束條件和一般粒子編碼規(guī)則，設(shè)置粒子的維度為所有無人艇攜帶載荷的總數(shù)D，，Wi為第i 艘無人艇攜帶的載荷數(shù)。為體現(xiàn)任務(wù)分配方案，設(shè)置每一維粒子代表相應(yīng)無人艇各個(gè)載荷執(zhí)行任務(wù)的目標(biāo)編號(hào)，例如無人艇S1、S2、S3、S4分別攜帶2、3、2、3 枚載荷，計(jì)劃攻擊6 個(gè)目標(biāo)，如果粒子編碼為［1，3，6，4，5，1，0，2，3，5］，說明S1打擊1 號(hào)和3 號(hào)目標(biāo)，S2打擊6 號(hào)、4 號(hào)和5 號(hào)目標(biāo)，S3打擊1 號(hào)目標(biāo)，S4打擊2 號(hào)、3 號(hào)和5 號(hào)目標(biāo)，故粒子編碼的取值范圍為0 至目標(biāo)數(shù)n之間的整數(shù)，0表示不分配該載荷執(zhí)行任務(wù)，當(dāng)算法迭代出現(xiàn)非整數(shù)時(shí)，需要對(duì)其進(jìn)行取整處理。

對(duì)粒子序列進(jìn)行解碼時(shí)，先依據(jù)載荷數(shù)Wi依次提取每艘無人艇執(zhí)行任務(wù)的目標(biāo)序號(hào)，根據(jù)無人艇Si和目標(biāo)Tj的對(duì)應(yīng)關(guān)系，更新位置變量xij的值，載荷被分配時(shí)為1，否則置0。

3.3 混沌初始化粒子

混沌優(yōu)化算法具有隨機(jī)性、遍歷性和敏感性［21］，為提高離散粒子群算法的全局搜索能力，采用Logistic 方程在粒子的初始化時(shí)融入混沌優(yōu)化。一維混沌系統(tǒng)的Logistic映射方程如式（8）所示。

xl+1=μ?xl?(1-xl)l=1，2...;μ?[0，4] （8）其中，l 為迭代次數(shù)，μ為混沌系統(tǒng)的控制參數(shù)，當(dāng)μ=4，x1?(0，1)且x1≠{0.25，0.5，0.75}時(shí)，該系統(tǒng)處于混沌狀態(tài)。

混沌初始化粒子的步驟如下：

1）隨機(jī)產(chǎn)生取值在0～n 之間的N×D維初始粒子群xori，n 為目標(biāo)數(shù)，N 為種群粒子個(gè)數(shù)，D 為載荷總數(shù)；

2）隨機(jī)產(chǎn)生一個(gè)D 維向量z1=[z11，z12，...，z1D]，根據(jù)式（8）得到N個(gè)D維向量z1，z2，...，zN；

3）通過初始粒子群xori和z向量相乘再取整的運(yùn)算規(guī)則將混沌的z向量映射到粒子的位置向量，如式（9）所示。

式中，| | 表示取整運(yùn)算。

3.4 指數(shù)型慣性因子

慣性因子是影響算法搜索能力的主要因素之一，是平衡局部搜索和全局搜索能力的重要參數(shù)，合理設(shè)置慣性因子的更新方法是離散粒子群算法有效實(shí)現(xiàn)的重要保證。傳統(tǒng)離散粒子群算法設(shè)置固定的慣性因子，其值較小時(shí)，算法不易收斂，其值較大時(shí)，算法易陷入局部最優(yōu)。為兼顧全局和局部搜索能力，采用較多的是隨時(shí)間線性遞減的動(dòng)態(tài)慣性因子，為進(jìn)一步提高算法的收斂速度，參考文獻(xiàn)［22］，設(shè)置如式（10）所示的非線性變化的指數(shù)形式的慣性因子。

其中，l 為迭代次數(shù)，NC為最大迭代次數(shù)，α為控制慣性因子衰減速度的常系數(shù)，設(shè)置慣性因子w的取值范圍在［wmin，wmax］區(qū)間內(nèi)。根據(jù)上述設(shè)計(jì)，慣性因子隨迭代次數(shù)呈現(xiàn)指數(shù)遞減分布，突出了不同時(shí)段對(duì)粒子全局和局部搜索能力的動(dòng)態(tài)調(diào)整，極大提高了算法的效率和準(zhǔn)確性。

3.5 自適應(yīng)學(xué)習(xí)因子

學(xué)習(xí)因子是反映粒子群信息交流的重要參數(shù)，決定粒子個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對(duì)粒子飛行的影響。為提升算法的全局搜索能力，改變傳統(tǒng)離散粒子群算法學(xué)習(xí)因子c1和c2固定不變的機(jī)制，以算法迭代次數(shù)為變量控制c1和c2的取值。在搜索初期，設(shè)置較大的c1和較小的c2，加強(qiáng)粒子對(duì)個(gè)體最優(yōu)值的追隨有助于提高搜索效率；在算法后期，粒子已基本找到最優(yōu)分配方案，設(shè)置較小的c1和較大的c2，使粒子加強(qiáng)對(duì)全局最優(yōu)值的追隨以加快算法的收斂。因此，設(shè)計(jì)學(xué)習(xí)因子c1和c2隨迭代次數(shù)服從半高斯分布，表達(dá)式分別如式（11）和式（12）所示。

其中，l 為迭代次數(shù)，NC為最大迭代次數(shù)，σ取值為最大迭代次數(shù)的1/4，設(shè)置學(xué)習(xí)因子c1和c2的取值范圍在［Cmin，Cmax］區(qū)間內(nèi)。

3.6 融入交叉和變異的粒子更新策略

為提高種群的多樣性，避免算法陷入局部最優(yōu)，在粒子迭代更新時(shí)，融入遺傳算法的交叉和變異操作［23］。

在每次迭代計(jì)算出全局最優(yōu)位置后，將其與隨機(jī)粒子采用整數(shù)交叉法進(jìn)行交叉操作［24］。首先選擇兩個(gè)交叉位置pos1 和pos2，將隨機(jī)粒子pos1 和pos2 之間的片段用全局最優(yōu)粒子pos1 和pos2 之間的片段替換，產(chǎn)生交叉粒子；對(duì)交叉粒子隨機(jī)選擇兩個(gè)變異位置pos3和pos4，交換變異位置的粒子基因，即得到交叉變異后的新粒子；用新粒子隨機(jī)替換群體中一個(gè)粒子。

3.7 加入罰函數(shù)的適應(yīng)度函數(shù)

按照3.2 節(jié)所述的編碼方式可自動(dòng)滿足2.2 節(jié)所述的約束條件2，但不一定滿足約束條件1 和3，因此需要加入懲罰函數(shù)。算法的適應(yīng)度函數(shù)如式（13）所示。

式中，F(xiàn) 為2.3 節(jié)式（5）所示的評(píng)價(jià)函數(shù)，該值越大，任務(wù)分配的收益越高。β、γ分別為違反時(shí)間窗約束和目標(biāo)載荷約束的懲罰因子，lj為無人艇到達(dá)目標(biāo)j 的時(shí)間，bj為目標(biāo)j 的右時(shí)間窗，sj為對(duì)目標(biāo)Tj最多可使用的載荷數(shù)。當(dāng)無人艇到達(dá)目標(biāo)的時(shí)間超過右時(shí)間窗時(shí)，需要給予時(shí)間懲罰，且超時(shí)越多，懲罰越大；當(dāng)對(duì)目標(biāo)使用的載荷數(shù)超量時(shí)，需要給予超限懲罰，且超出數(shù)量越多，懲罰越大。適應(yīng)度函數(shù)等于評(píng)價(jià)函數(shù)減去懲罰函數(shù)，故適應(yīng)度函數(shù)值越大越好。

4 算法流程

應(yīng)用改進(jìn)離散粒子群算法進(jìn)行多無人艇任務(wù)分配的流程如圖1所示。

圖1 改進(jìn)離散粒子群算法流程圖

5 仿真實(shí)驗(yàn)與結(jié)果分析

為檢驗(yàn)本文提出的改進(jìn)離散粒子群算法的有效性，進(jìn)行如下仿真實(shí)驗(yàn)。設(shè)置粒子數(shù)量N 為40，最大迭代次數(shù)NC=200，權(quán)重因子最小值和最大值分別為0.4和0.8，學(xué)習(xí)因子最小值和最大值分別為1.2和1.5，無人艇數(shù)量為4，待打擊目標(biāo)數(shù)量為6，每艘無人艇搭載的載荷數(shù)量為2，無人艇航行速度為20km/h，根據(jù)適應(yīng)度函數(shù)各組成部分的重要程度，同時(shí)均衡各參數(shù)的數(shù)值量級(jí)，設(shè)置ωR、ωD、ωT、β和γ分別為100、1、10、5、10，無人艇位置坐標(biāo)如表1 所示，目標(biāo)點(diǎn)位置坐標(biāo)、威脅值、左時(shí)間窗和右時(shí)間窗如表2所示。無人艇對(duì)目標(biāo)的命中概率如表3所示。

表1 無人艇位置坐標(biāo)信息

表2 目標(biāo)位置坐標(biāo)、威脅值、時(shí)間窗信息

表3 無人艇對(duì)目標(biāo)的命中概率

改進(jìn)離散粒子群算法進(jìn)行任務(wù)分配的結(jié)果如圖2所示。

圖2 改進(jìn)離散粒子群算法任務(wù)分配圖

傳統(tǒng)算法和改進(jìn)算法的任務(wù)分配適應(yīng)度函數(shù)值隨迭代次數(shù)變化的曲線如圖3所示。

圖3 傳統(tǒng)算法和改進(jìn)算法適應(yīng)度函數(shù)值對(duì)比圖

隨機(jī)選取3 次實(shí)驗(yàn)，記錄兩種算法在適應(yīng)度函數(shù)值、迭代次數(shù)和運(yùn)行時(shí)間等方面的結(jié)果如表4 所示。

表4 傳統(tǒng)算法和改進(jìn)算法的性能對(duì)比

綜上所述，與傳統(tǒng)離散粒子群算法相比，改進(jìn)后的算法具有較強(qiáng)的收斂性，整體迭代次數(shù)更少，規(guī)劃的任務(wù)分配方案收益更高，這充分說明改進(jìn)算法的優(yōu)越性。

6 結(jié)語

本文采用改進(jìn)的離散粒子群算法進(jìn)行無人艇任務(wù)分配。為增強(qiáng)初代粒子群的多樣性，提高算法的全局搜索能力，初始化粒子編碼時(shí)融入混沌優(yōu)化策略；設(shè)計(jì)隨迭代次數(shù)呈指數(shù)遞減變化的慣性因子，進(jìn)一步提升搜索效率；設(shè)置服從半高斯分布的自適應(yīng)學(xué)習(xí)因子c1和c2，以兼顧算法收斂速度快和全局搜索能力；融入交叉和變異的粒子更新機(jī)制，有效提高算法的全局搜索能力。仿真實(shí)驗(yàn)表明：改進(jìn)后的算法具有較強(qiáng)的全局搜索能力，有效減小了迭代次數(shù)，較大程度提高了任務(wù)分配的質(zhì)量。