改進離散粒子群算法的多無人艇任務分配研究?

趙冬梅 宋 陽 周國軍 崔海峰

（海軍大連艦艇學院基礎部 大連 116018）

1 引言

無人艇（USV）結構簡單，價格低廉，安全性好，適合在危險區域執行搜救、偵察、巡邏、打擊等多種任務［1～2］。2022年6月7日，我國首艘全國產化的百噸級無人艇在舟山海域順利完成首次海上自主航行試驗，標志著我國無人艇自主航行和智能機艙技術取得了新的突破［3］。隨著無人艇技術的發展，在未來戰場上，無人艇將大顯身手，成為海戰的主力。

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

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

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

2 任務分配問題建模

2.1 問題描述

假設在5km×5km 的海域內有m 艘無人艇S={S1，S2，...，Sm}，到達n 個待打擊的目標點T={T1，T2，...，Tn}執行打擊任務，無人艇Si攜帶Wi個載荷，在滿足多項約束條件下，使無人艇完成打擊任務的評價指標最好。

離散粒子群算法對于求解此類非線性整數規劃問題具有參數設置簡單、執行效率高等優點［19］，建立無人艇和打擊目標之間m×n階的決策變量矩陣如式（1）所示。

xij只能取1 或0，xij=1 表示無人艇Si對目標Tj執行打擊任務，xij=0 則不打擊。結合實際約束條件和評價函數求解出將m 艘無人艇的載荷分配給n個目標的最優目標分配方案。

2.2 約束條件

1）時間窗約束

構建模型時，通常要求無人艇在指定的時間段對目標執行打擊任務，時間窗約束如式（2）所示。

其中，Tj.StartTime_t和Tj.EndTime_t為指定的打擊第j 個目標的起始和結束時間，StartTime_o和EndTime_o為實際打擊第j個目標的起始和結束時間。

2）無人艇載荷約束

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

3）目標載荷約束

為避免出現多無人艇打擊目標點過于集中的現象，要求無人艇對某個目標使用的載荷總數有限，即對目標Tj最多可使用Sj個載荷，目標承受載荷約束如式（4）所示。

2.3 任務分配評價函數

評價函數體現無人艇任務分配的優劣程度。本文設計基于完成任務的效益減去航線距離代價和執行任務時間代價的任務分配評價函數，表達式如式（5）。

其中，ωR、ωD和ωT分別為任務效益、距離代價和時間代價的權重系數，體現每項收益或代價的重要程度，可根據實際需求動態調整三項系數以體現任務分配的多原則決策機制。

為減少無人艇暴露時間，提高其執行任務的安全性，以航線距離最長的無人艇行駛距離作為時間代價，v為無人艇航行速度。

上述評價函數兼顧了執行打擊任務的收益、距離和時間代價，能夠引導種群選擇出打擊效益高、航行距離短和執行時間少的分配方案。

3 改進離散粒子群算法

3.1 離散粒子群算法原理

粒子群算法是基于種群和進化的概念，通過個體間的協作和競爭，實現對復雜空間最優解的搜索［20］。粒子通過開發和探索，依據最優信息不斷更新迭代，速度向量νij和位置向量xij的更新規則如式（6）所示。

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

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

式（7）中，r為［0，1］間的均勻隨機數。

利用離散粒子群算法求解任務分配問題時，每個粒子代表一種任務分配方案，根據評價函數計算各個粒子的適應度值，更新個體、全局最優位置和最優值，更新粒子速度和位置，進行邊界條件處理，重復上述步驟，直至迭代結束，得到最優分配方案BestDistribution。

3.2 粒子的編碼與解碼

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

對粒子序列進行解碼時，先依據載荷數Wi依次提取每艘無人艇執行任務的目標序號，根據無人艇Si和目標Tj的對應關系，更新位置變量xij的值，載荷被分配時為1，否則置0。

3.3 混沌初始化粒子

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

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

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

1）隨機產生取值在0～n 之間的N×D維初始粒子群xori，n 為目標數，N 為種群粒子個數，D 為載荷總數；

2）隨機產生一個D 維向量z1=[z11，z12，...，z1D]，根據式（8）得到N個D維向量z1，z2，...，zN；

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

式中，| | 表示取整運算。

3.4 指數型慣性因子

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

其中，l 為迭代次數，NC為最大迭代次數，α為控制慣性因子衰減速度的常系數，設置慣性因子w的取值范圍在［wmin，wmax］區間內。根據上述設計，慣性因子隨迭代次數呈現指數遞減分布，突出了不同時段對粒子全局和局部搜索能力的動態調整，極大提高了算法的效率和準確性。

3.5 自適應學習因子

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

其中，l 為迭代次數，NC為最大迭代次數，σ取值為最大迭代次數的1/4，設置學習因子c1和c2的取值范圍在［Cmin，Cmax］區間內。

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

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

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

3.7 加入罰函數的適應度函數

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

式中，F 為2.3 節式（5）所示的評價函數，該值越大，任務分配的收益越高。β、γ分別為違反時間窗約束和目標載荷約束的懲罰因子，lj為無人艇到達目標j 的時間，bj為目標j 的右時間窗，sj為對目標Tj最多可使用的載荷數。當無人艇到達目標的時間超過右時間窗時，需要給予時間懲罰，且超時越多，懲罰越大；當對目標使用的載荷數超量時，需要給予超限懲罰，且超出數量越多，懲罰越大。適應度函數等于評價函數減去懲罰函數，故適應度函數值越大越好。

4 算法流程

應用改進離散粒子群算法進行多無人艇任務分配的流程如圖1所示。

圖1 改進離散粒子群算法流程圖

5 仿真實驗與結果分析

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

表1 無人艇位置坐標信息

表2 目標位置坐標、威脅值、時間窗信息

表3 無人艇對目標的命中概率

改進離散粒子群算法進行任務分配的結果如圖2所示。

圖2 改進離散粒子群算法任務分配圖

傳統算法和改進算法的任務分配適應度函數值隨迭代次數變化的曲線如圖3所示。

圖3 傳統算法和改進算法適應度函數值對比圖

隨機選取3 次實驗，記錄兩種算法在適應度函數值、迭代次數和運行時間等方面的結果如表4 所示。

表4 傳統算法和改進算法的性能對比

綜上所述，與傳統離散粒子群算法相比，改進后的算法具有較強的收斂性，整體迭代次數更少，規劃的任務分配方案收益更高，這充分說明改進算法的優越性。

6 結語

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