基于非支配排序遺傳算法的目標分配算法

徐磊 杜思偉

摘要：解決指揮控制領域的目標分配問題，主要使用單目標函數優化分配模型的分配方法。這一類方法的缺點是在當前時間序列上只考慮單一目標對下屬節點的分配，未綜合全局考慮分配任務的效率。本文先描述了單目標函數優化分配算法的使用步驟，后分析了該算法應用于指揮控制系統目標分配研究的優劣。再此基礎上，進一步利用NSGA-II算法提出快速非支配排序機制的多目標分配算法，快速逼近多目標分配問題的Pareto最優解。

關鍵詞：指揮控制 目標分配 非支配排序遺傳算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1007-9416（2016）07-0120-02

1 引言

隨著指揮控制系統的發展，需要其具備同時對20批以上目標的分配能力，指揮控制系統需要根據各下屬節點的能力及目標的綜合態勢確定較優的分配方案。因此，目標優化分配是指揮控制領域最具有研討價值的問題。

目標優化分配是最具有代表性典型的非確定多項式問題。隨著指揮控制系統下屬任務處理節點與目標數目的增加，目標分配的可選方案隨著指控系統下屬任務節點及目標數量的增加而呈幾何式階梯增長。

當指控系統有2個下屬節點，用以應對2批目標時，可行的分配方案有16種；當指控系統有4個下屬節點，用以應對4批目標時，理論可行分配方案數上升到65536種；而當下屬節點和目標數量再次翻倍之后，總分配方案數的數量級已過億，在實際工程應用中不可能通過窮舉的方式獲得最優解。

目前，目標優化分配方法主要有基于單目標函數優化分配模型的分配方法，以及針對該類模型改良的快速分配方法，這兩種分配方法本質上其實是一類方法，這一類方法的缺點是在當前時間序列上只考慮單一目標對下屬節點的分配，完成分配后轉入下一個單一目標的分配任務，此時下屬節點的可分配資源已減少，未綜合全局考慮分配任務的效率，因此該方法不是最優化的分配方法。

2 單目標函數優化分配算法

下面給出單目標函數優化分配模型進行分析，目標函數和限制條件見表達式（1）、（2）：

（1）

（2）

式中：N：指揮控制系統下屬可處理目標的節點數量；

M：參與優化分配的目標數量；

：目標j的任務緊迫度；

：下屬節點i對目標j的分配有利度；

：目標j是否分配給下屬節點i的假定值，=1分配，=0不分配，該假定數受任務分配可行性判斷結果限制。∈D，D= {|滿足資源、時間和空間約束}。

公式（1）的物理含義是把目標分配給處理最有利的下屬處理節點，任務緊迫度高的目標具有優先選擇權。

針對以上單目標優化分配模型，本文根據工程經驗提出以下快速分配方法，該方法結合一系列先行的選優工作，能在較短時間內獲得較優的可行解。步驟如下：

Step1：如指揮控制系統的下屬任務處理節點數量N，從任務列表中選取2N的目標參與分配，任務序列中的目標已進行了時間和空間約束條件判斷，按照任務緊迫度排序。

Step2：任務序列表中排序靠前目標最先參加目標分配，當目標到達分配時空域遠界后，對目標進行資源約束條件判斷，若滿足條件，優選處理節點中分配有利度最高的處理節點進行分配，完成一批目標的分配。

Step3：重復步驟2，直到所有下屬處理節點均有目標。

Step4：等待空閑的處理節點，實施再次分配。

該分配算法的優點是無需疊代，可在較短時間內獲得較優的可行解，分配結果可保證將目標分配給任務最有利的處理單元，且漏分數量最小。缺點是：只考慮了當前單一目標任務有利度對分配結果的影響，未綜合考慮全局處理單元對多目標的分配可能。因此有必要在指揮控制系統目標分配起始時，就考慮全局多目標的優化分配方案，以獲得更優的分配方案。

3 基于非支配排序遺傳算法的多目標分配算法

為了獲得指揮控制系統對于多目標的全局優化分配結果，嘗試將利用解決多目標決策問題的思路來解決時序上的單目標優化分配問題。

多目標分配決策的難點在于，全局的分配有利度與各目標自身的分配結果是可能存在一定矛盾的。理論上不可能存在每個目標的自身的分配結果均是最優的全局最優情況，往往是采用某種確定的分配方案后，會使目標域中的某一批目標的分配有利度變差。但由于該目標的犧牲，提升了全局的分配結果。基于以上的特征，可以規避使所有目標均達到最優分配的情況，轉而在各目標之間進行協調，促使全域的分配結果盡可能的優化。

一般而言，根據各參考文獻，利用解決多目標決策問題的思路來解決時序上的單目標優化分配問題的基本算法有線性加權求和法、密切值法、分層評價法等。以上算法的基本思路均是通過不同的數值計算方法，將多目標的全局有利度歸化成單一值，用以衡量分配方案的優劣。這種做法的優點在于簡單、快速、可實現性強，缺點在于計算效率低、算法魯棒性及適應性差，在實際的工程實現中效果一般。

本文采用非支配排序遺傳算法解決指揮控制系統的多目標分配問題。

3.1 遺傳算法

遺傳算法（Genetic Algorithm）是一類借鑒生物界適者生存、優勝劣汰遺傳機制的進化規律演化而來的隨機化搜索方法，其主要基于群體搜索策略在處理的群體間根據預先設定的模型進行信息的傳遞與交換。與牛頓梯度法等最優化算法的確定性、方向性搜索策略相比，遺傳算法的處理機制是基于概率的，因此，其在處理和搜索最優解的過程中搜索到局部最優解的概率相對較低。另外，該算法的處理方式是非線程的，搜索過程不僅僅局限于單值解，因此，該算法比較適合于結果指控領域中的目標分配問題。

3.2 第二代非支配排序遺傳算法（NSGA-II）描述

第二代非支配排序遺傳算法（NSGA-II）是基于第一代非支配排序遺傳算法NSGA的改進算法。

該算法采用了快速非支配排序（Fast Non-Dominated Sorting），采用了擁擠度及其比較算子，代替了第一代算法中需要使用者指定的共享半徑。當排序過程中出現同級個體時，使用擁擠度及其比較算子作為次級排序的依據，從而保持了種群的多樣性；另外，該算法在原算法的基礎之上引入精英策略。該策略可以使得采樣空間擴大，防止錯失最優解，提高了算法的快速性和魯棒性。

3.3 算法操作

步驟1 初始化：根據指控系統下屬節點數量以及當前目標批數，初始化產生200組原始分配組合種群P0。對初始種群P0實施非支配倒序排序，排序完成后，按排序結果，對每一組分配方案賦一個非支配值R。

步驟2 選擇：對初始化產生200組原始分配組合種群P0進行淘汰賽選擇，即隨機對200組原始分配組合進行兩兩配對，對于一對中的兩組分配組合方式進行非支配值R的比較。假定參與比較的兩對分配組合方式為A和B，其對應的非支配分別為RA和RB。根據預設原則“保留非支配大的那組分配組合方式，淘汰另一組分配方式” ，若RA

步驟3 交叉：選擇后的分配組合種群P1中共有100組分配組合，該分配組合包括了指控下屬任務節點的編號以及目標的批號。將目標的批號設定為單點交叉源，按照步驟2中的配對方式，對100組分配組合進行兩兩配對。對配對后的分配組合的目標批號進行相互交叉，形成交叉后的分配組合種群P2。

步驟4 變異：交叉后的分配組合種群P2中共有100組分配組合，該分配組合包括了指控下屬任務節點的編號以及交叉后的目標批號。對于指控系統的目標分配問題，本文的變異操作采用下屬節點與待分配目標的雙元素變異。即使用一個新的指控下屬節點或新的目標批號去替換原始分配組合中的某個組合，從而形成一個新的分配組合種群P3。具體的變異步驟如下：

（1）根據交叉后分配組合種群P2的規模大小，設定變異概率Pm，并確定變異門限g。隨P2的規模增大或變異概率Pm的增大，變異的分配組合數量也會隨之增大。

（2）對于交叉后分配組合種群P2中的每一組分配組合，產生一個[0，1]之間遵循高斯分布的隨機數，若>g，則該分配組合需要進行變異操作。

（3）隨機在全局可分配組合中挑選可用的指控下屬節點或目標批號，對確定發生變異操作的分配組合的下屬節點或目標批號進行更改。

算法流程如下圖1所示。

4 結語

本文由淺入深，先描述了單目標函數優化分配算法的使用步驟，后分析了該算法應用于指揮控制系統目標分配研究的優劣；再此基礎上，進一步利用NSGA-II算法提出快速非支配排序機制的多目標分配算法，快速逼近多目標分配問題的Pareto最優解，用于指揮控制系統的多目標分配研究。為指揮控制系統的多目標分配研究提供了一種可行、高效的解決方案。

參考文獻

[1]邢清華，王穎龍，劉付顯.多型號武器的目標優化分配問題研究[J].空軍工程大學學報，2003，4（1）：22-25.

[2]王士同，劉征.動態武器目標分配問題的DWTA-GA算法[J].華東船舶工業學院學報，1999，13（5）：17-22.

[3]J.F.Aguilar Madeira，H.Rodrigues，Heitor Pina.Multi—objective optimization of structures topology bygenetic algorithms[J].Advances in Engineering Softwal'e，2005（36）：21-28.

[4]戴耀，汪德虎.艦艇火力分配的多指標模糊優選動態規劃[J].遼寧工程技術大學學報，2001，20（5）：673-675.

[5]劉軍，賈宏慧.基于改進的排列法的目標威脅評估與排序模型[J].計算機工程與設計，2007，28（19）：4750-4751.