基于免疫遺傳算法的無人艇任務分配研究?

胡紅波 曹 璐

（1.海裝武漢局駐宜昌地區軍事代表室 宜昌 443003）

（2.中國船舶重工集團有限公司第七一〇研究所 宜昌 443003）

1 引言

現代戰爭正朝著透明化、非接觸化、無人化的方向發展，隨著人工智能技術的進步，無人艇在海上巡邏安防、反水雷以及反潛作戰等領域中扮演日益重要的角色［1～2］。無人艇編隊協同作戰是未來戰爭的主要發展趨勢，作為協同控制關鍵技術的任務分配，是無人艇協同作戰的核心和有效保證。任務分配的主要作用是通過整合無人艇各自的特點，形成“1+1＞2”的總體優勢，提高無人艇的戰場動態適應能力以及整體作戰效能［3～4］。

目前在任務分配求解算法方面已取得了較多的成果，例如基于整數規劃模型的算法求解較為簡便，但問題規模增大時，求解的難度也變大［5～6］；遺傳算法（GA）以生物進化為原型，具有很好的收斂性，但搜索過程中的劣質導致效率低下［7～8］；基于合同網的方法通過互相協商和任務競爭在局部最優的基礎上追求全局最優，但問題規模增大導致相互協商次數變多，降低了算法求解的速度［9～10］。

遺傳算法在多目標優化時容易出現“早熟”，即收斂于局部極值［11］，為了克服這一缺陷，以提高其全局搜索能力，本文通過將生物免疫機制和遺傳算法進行結合，構造一種免疫遺傳算法（Immune Ge?netic Algorithm，IGA），用于解決多艘無人艇協同任務分配問題，可以有效地提高尋優速度、改善尋優質量。

2 任務分配問題建模

無人艇任務分配是實現無人艇編隊協調控制和協同航路規劃的前提，主要研究如何從大量目標和無人艇編隊之中找到可以最小的代價獲得最大任務收益的方案。本文以無人艇損耗最小化、目標價值毀傷最大化以及消耗時間最短建立任務分配模型［12］，并通過加權求和轉換為單一目標函數進行求解，各個權值與影響因素的重要程度相關。將各量綱轉化為［0，1］集合內的數值，例如令目標的價值V取0～1之間的數值；令Tut=Dut/Dmax，使Tut為第u艘USV與目標t間的距離（到達時間）相對于USV與目標間最遠（最長到達時間）距離的百分比。因此，USV任務分配模型為

3 基于IGA的任務分配

3.1 IGA算法流程

生物免疫系統能夠進行自我調節，并具有免疫記憶功能，因此抗體多樣性增加。IGA將生物免疫原理應用到遺傳算法中，通過免疫算子來抑制遺傳算法在選擇、交叉、變異過程中，因隨機操作而帶來的個體退化現象，有效地提高上述操作的選擇性、目的性，保證種群的多樣性并防止未成熟收斂陷入局部最優［13］。

IGA中新抗體的產生依然采用遺傳算法中的交叉和變異操作，其結構框圖如下圖所示。

圖1 免疫遺傳算法流程圖

3.2 抗體適應度計算

無人艇任務分配就是求解目標函數值最大時，USV與目標之間的對應關系，因此通過對任務分配的目標函數進行變化，得到抗體v與抗原之間的結合力 Av：

其中：f(v)為目標函數，Cmin為一個適當地相對較小的數。無人艇任務分配的目的尋求目標函數的最大值，當結合力Av的數值越大，抗體與最優解越接近。

3.3 免疫濃度控制

IGA將免疫系統的濃度控制融入到GA的選擇、復制操作中，這樣可以保持抗體的多樣性。在通常GA采取比例選擇的基礎上，增加濃度調節因子改進算法的選擇操作，實現IGA中抗體的促進和抑制。此時，適應度概率Pf和濃度抑制概率Pd共同組成了個體通過選擇之后的再生概率P：

式中，α、β為調節常數，N為抗體總數，ci為抗體濃度?？贵w的適應度與選擇概率正相關，因此，在保留適應度高的個體的同時，豐富了個體的多樣性，有利于早熟現象的改善。

4 仿真驗證及分析

4.1 參數設置

在IGA中，有五個參數：群體中所含抗體的數量N、終止代數M、選擇概率中適應度概率所占的比例α和交叉概率Pc、變異概率Pm對任務分配問題的求解都有一定的影響。根據在實際問題中的作用效果測試，參數設置如下。

表1 IGA相關參數設置

4.2 仿真驗證

仿真場景為3艘無人艇攻擊8個不同的目標，假設各目標被確認的概率已知、不同敵方目標的評估值已知、敵方對USV的損傷概率已知、USV與敵方目標的距離已知、USV對敵方目標的殺傷概率已知。IGA具體參數設置如下：種群規模NIND＝40，最大進化代數MAXGEN=400，α=0.6，交叉概率Pc=0.9，變異概率Pm=0.1，經IGA求解得到的目標函數值隨迭代次數變化的結果如下圖所示。從圖中可知，IGA經迭代2次收斂，使無人艇多目標任務分配問題很好地收斂到全局最優。

圖2 目標函數值隨迭代次數變化圖

由IGA計算結果可知，作戰效能取最大解（3，2，2，1，1，3，2，1）=0.970時，最終得到的最優分配方案為：目標1和目標6分配給第3艘無人艇，目標2、目標3和目標7分配給第2艘無人艇，目標4、目標5和目標8分配給第1艘無人艇。

4.3 算法有效性分析

從上述仿真算例中可以看出，IGA能夠有效地解決USV協同任務分配問題，并反映了無人艇損耗、目標價值毀傷以及消耗時間等因素對任務分配結果的影響。為了分析免疫遺傳算法的性能，以10艘無人艇攻擊10個目標為例進行仿真對比，結果表明遺傳算法與免疫遺傳算法均能夠有效地處理USV協同任務分配的眾多約束條件，解決了USV協同的任務分配問題。從下圖可以看出，作戰效能目標函數隨進化代數變化的曲線均能夠收斂到最優值，但IGA的最優值大于GA的最優值，且IGA的收斂速度更快。

圖3 IGA與GA目標函數隨進化代數變化的曲線

從上圖可以看出，遺傳算法加入免疫算子后，改進后的遺傳算法最優適應度比改進前的最優適應度大，曲線振蕩減弱，表明加入免疫算子后，整體收斂速度加快，種群進化時遺傳策略保持較好，算法更為穩定，IGA能夠快速收斂到全局最優，克服了GA的“早熟現象”缺陷。

5 結語

本文針對無人艇任務分配過程中多參數、多約束條件優化問題，提出了基于免疫遺傳算法的任務分配方法。免疫遺傳算法通過生物學領域的免疫行為對遺傳算法進行改進，很好地保持了種群多樣性，從而使算法快速收斂到全局最優解。通過該方法求解無人艇協同任務分配模型，并與遺傳算法進行了對比分析，結果表明免疫遺傳算法能夠快速對多約束條件下的多目標優化問題進行求解，對解決無人艇任務分配優化問題是有效、可行的。