基于非支配排序遺傳算法的目標(biāo)分配算法

徐磊 杜思偉

摘要：解決指揮控制領(lǐng)域的目標(biāo)分配問題，主要使用單目標(biāo)函數(shù)優(yōu)化分配模型的分配方法。這一類方法的缺點(diǎn)是在當(dāng)前時(shí)間序列上只考慮單一目標(biāo)對(duì)下屬節(jié)點(diǎn)的分配，未綜合全局考慮分配任務(wù)的效率。本文先描述了單目標(biāo)函數(shù)優(yōu)化分配算法的使用步驟，后分析了該算法應(yīng)用于指揮控制系統(tǒng)目標(biāo)分配研究的優(yōu)劣。再此基礎(chǔ)上，進(jìn)一步利用NSGA-II算法提出快速非支配排序機(jī)制的多目標(biāo)分配算法，快速逼近多目標(biāo)分配問題的Pareto最優(yōu)解。

關(guān)鍵詞：指揮控制 目標(biāo)分配 非支配排序遺傳算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）07-0120-02

1 引言

隨著指揮控制系統(tǒng)的發(fā)展，需要其具備同時(shí)對(duì)20批以上目標(biāo)的分配能力，指揮控制系統(tǒng)需要根據(jù)各下屬節(jié)點(diǎn)的能力及目標(biāo)的綜合態(tài)勢(shì)確定較優(yōu)的分配方案。因此，目標(biāo)優(yōu)化分配是指揮控制領(lǐng)域最具有研討價(jià)值的問題。

目標(biāo)優(yōu)化分配是最具有代表性典型的非確定多項(xiàng)式問題。隨著指揮控制系統(tǒng)下屬任務(wù)處理節(jié)點(diǎn)與目標(biāo)數(shù)目的增加，目標(biāo)分配的可選方案隨著指控系統(tǒng)下屬任務(wù)節(jié)點(diǎn)及目標(biāo)數(shù)量的增加而呈幾何式階梯增長(zhǎng)。

當(dāng)指控系統(tǒng)有2個(gè)下屬節(jié)點(diǎn)，用以應(yīng)對(duì)2批目標(biāo)時(shí)，可行的分配方案有16種；當(dāng)指控系統(tǒng)有4個(gè)下屬節(jié)點(diǎn)，用以應(yīng)對(duì)4批目標(biāo)時(shí)，理論可行分配方案數(shù)上升到65536種；而當(dāng)下屬節(jié)點(diǎn)和目標(biāo)數(shù)量再次翻倍之后，總分配方案數(shù)的數(shù)量級(jí)已過億，在實(shí)際工程應(yīng)用中不可能通過窮舉的方式獲得最優(yōu)解。

目前，目標(biāo)優(yōu)化分配方法主要有基于單目標(biāo)函數(shù)優(yōu)化分配模型的分配方法，以及針對(duì)該類模型改良的快速分配方法，這兩種分配方法本質(zhì)上其實(shí)是一類方法，這一類方法的缺點(diǎn)是在當(dāng)前時(shí)間序列上只考慮單一目標(biāo)對(duì)下屬節(jié)點(diǎn)的分配，完成分配后轉(zhuǎn)入下一個(gè)單一目標(biāo)的分配任務(wù)，此時(shí)下屬節(jié)點(diǎn)的可分配資源已減少，未綜合全局考慮分配任務(wù)的效率，因此該方法不是最優(yōu)化的分配方法。

2 單目標(biāo)函數(shù)優(yōu)化分配算法

下面給出單目標(biāo)函數(shù)優(yōu)化分配模型進(jìn)行分析，目標(biāo)函數(shù)和限制條件見表達(dá)式（1）、（2）：

（1）

（2）

式中：N：指揮控制系統(tǒng)下屬可處理目標(biāo)的節(jié)點(diǎn)數(shù)量；

M：參與優(yōu)化分配的目標(biāo)數(shù)量；

：目標(biāo)j的任務(wù)緊迫度；

：下屬節(jié)點(diǎn)i對(duì)目標(biāo)j的分配有利度；

：目標(biāo)j是否分配給下屬節(jié)點(diǎn)i的假定值，=1分配，=0不分配，該假定數(shù)受任務(wù)分配可行性判斷結(jié)果限制?！蔇，D= {|滿足資源、時(shí)間和空間約束}。

公式（1）的物理含義是把目標(biāo)分配給處理最有利的下屬處理節(jié)點(diǎn)，任務(wù)緊迫度高的目標(biāo)具有優(yōu)先選擇權(quán)。

針對(duì)以上單目標(biāo)優(yōu)化分配模型，本文根據(jù)工程經(jīng)驗(yàn)提出以下快速分配方法，該方法結(jié)合一系列先行的選優(yōu)工作，能在較短時(shí)間內(nèi)獲得較優(yōu)的可行解。步驟如下：

Step1：如指揮控制系統(tǒng)的下屬任務(wù)處理節(jié)點(diǎn)數(shù)量N，從任務(wù)列表中選取2N的目標(biāo)參與分配，任務(wù)序列中的目標(biāo)已進(jìn)行了時(shí)間和空間約束條件判斷，按照任務(wù)緊迫度排序。

Step2：任務(wù)序列表中排序靠前目標(biāo)最先參加目標(biāo)分配，當(dāng)目標(biāo)到達(dá)分配時(shí)空域遠(yuǎn)界后，對(duì)目標(biāo)進(jìn)行資源約束條件判斷，若滿足條件，優(yōu)選處理節(jié)點(diǎn)中分配有利度最高的處理節(jié)點(diǎn)進(jìn)行分配，完成一批目標(biāo)的分配。

Step3：重復(fù)步驟2，直到所有下屬處理節(jié)點(diǎn)均有目標(biāo)。

Step4：等待空閑的處理節(jié)點(diǎn)，實(shí)施再次分配。

該分配算法的優(yōu)點(diǎn)是無(wú)需疊代，可在較短時(shí)間內(nèi)獲得較優(yōu)的可行解，分配結(jié)果可保證將目標(biāo)分配給任務(wù)最有利的處理單元，且漏分?jǐn)?shù)量最小。缺點(diǎn)是：只考慮了當(dāng)前單一目標(biāo)任務(wù)有利度對(duì)分配結(jié)果的影響，未綜合考慮全局處理單元對(duì)多目標(biāo)的分配可能。因此有必要在指揮控制系統(tǒng)目標(biāo)分配起始時(shí)，就考慮全局多目標(biāo)的優(yōu)化分配方案，以獲得更優(yōu)的分配方案。

3 基于非支配排序遺傳算法的多目標(biāo)分配算法

為了獲得指揮控制系統(tǒng)對(duì)于多目標(biāo)的全局優(yōu)化分配結(jié)果，嘗試將利用解決多目標(biāo)決策問題的思路來(lái)解決時(shí)序上的單目標(biāo)優(yōu)化分配問題。

多目標(biāo)分配決策的難點(diǎn)在于，全局的分配有利度與各目標(biāo)自身的分配結(jié)果是可能存在一定矛盾的。理論上不可能存在每個(gè)目標(biāo)的自身的分配結(jié)果均是最優(yōu)的全局最優(yōu)情況，往往是采用某種確定的分配方案后，會(huì)使目標(biāo)域中的某一批目標(biāo)的分配有利度變差。但由于該目標(biāo)的犧牲，提升了全局的分配結(jié)果?；谝陨系奶卣?，可以規(guī)避使所有目標(biāo)均達(dá)到最優(yōu)分配的情況，轉(zhuǎn)而在各目標(biāo)之間進(jìn)行協(xié)調(diào)，促使全域的分配結(jié)果盡可能的優(yōu)化。

一般而言，根據(jù)各參考文獻(xiàn)，利用解決多目標(biāo)決策問題的思路來(lái)解決時(shí)序上的單目標(biāo)優(yōu)化分配問題的基本算法有線性加權(quán)求和法、密切值法、分層評(píng)價(jià)法等。以上算法的基本思路均是通過不同的數(shù)值計(jì)算方法，將多目標(biāo)的全局有利度歸化成單一值，用以衡量分配方案的優(yōu)劣。這種做法的優(yōu)點(diǎn)在于簡(jiǎn)單、快速、可實(shí)現(xiàn)性強(qiáng)，缺點(diǎn)在于計(jì)算效率低、算法魯棒性及適應(yīng)性差，在實(shí)際的工程實(shí)現(xiàn)中效果一般。

本文采用非支配排序遺傳算法解決指揮控制系統(tǒng)的多目標(biāo)分配問題。

3.1 遺傳算法

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

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

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

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

3.3 算法操作

步驟1 初始化：根據(jù)指控系統(tǒng)下屬節(jié)點(diǎn)數(shù)量以及當(dāng)前目標(biāo)批數(shù)，初始化產(chǎn)生200組原始分配組合種群P0。對(duì)初始種群P0實(shí)施非支配倒序排序，排序完成后，按排序結(jié)果，對(duì)每一組分配方案賦一個(gè)非支配值R。

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

步驟3 交叉：選擇后的分配組合種群P1中共有100組分配組合，該分配組合包括了指控下屬任務(wù)節(jié)點(diǎn)的編號(hào)以及目標(biāo)的批號(hào)。將目標(biāo)的批號(hào)設(shè)定為單點(diǎn)交叉源，按照步驟2中的配對(duì)方式，對(duì)100組分配組合進(jìn)行兩兩配對(duì)。對(duì)配對(duì)后的分配組合的目標(biāo)批號(hào)進(jìn)行相互交叉，形成交叉后的分配組合種群P2。

步驟4 變異：交叉后的分配組合種群P2中共有100組分配組合，該分配組合包括了指控下屬任務(wù)節(jié)點(diǎn)的編號(hào)以及交叉后的目標(biāo)批號(hào)。對(duì)于指控系統(tǒng)的目標(biāo)分配問題，本文的變異操作采用下屬節(jié)點(diǎn)與待分配目標(biāo)的雙元素變異。即使用一個(gè)新的指控下屬節(jié)點(diǎn)或新的目標(biāo)批號(hào)去替換原始分配組合中的某個(gè)組合，從而形成一個(gè)新的分配組合種群P3。具體的變異步驟如下：

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

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

（3）隨機(jī)在全局可分配組合中挑選可用的指控下屬節(jié)點(diǎn)或目標(biāo)批號(hào)，對(duì)確定發(fā)生變異操作的分配組合的下屬節(jié)點(diǎn)或目標(biāo)批號(hào)進(jìn)行更改。

算法流程如下圖1所示。

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

[1]邢清華，王穎龍，劉付顯.多型號(hào)武器的目標(biāo)優(yōu)化分配問題研究[J].空軍工程大學(xué)學(xué)報(bào)，2003，4（1）：22-25.

[2]王士同，劉征.動(dòng)態(tài)武器目標(biāo)分配問題的DWTA-GA算法[J].華東船舶工業(yè)學(xué)院學(xué)報(bào)，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]戴耀，汪德虎.艦艇火力分配的多指標(biāo)模糊優(yōu)選動(dòng)態(tài)規(guī)劃[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2001，20（5）：673-675.

[5]劉軍，賈宏慧.基于改進(jìn)的排列法的目標(biāo)威脅評(píng)估與排序模型[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（19）：4750-4751.