多節(jié)點(diǎn)協(xié)同任務(wù)分配問題的解決和驗(yàn)證

張家良 王迎磊 李復(fù)名 周濤

摘要

針對(duì)多節(jié)點(diǎn)協(xié)同任務(wù)分配問題，將多節(jié)點(diǎn)執(zhí)行任務(wù)的目標(biāo)價(jià)值毀傷函數(shù)和代價(jià)函數(shù)作為目標(biāo)函數(shù)，多節(jié)點(diǎn)協(xié)同任務(wù)分配問題等效為多目標(biāo)函數(shù)優(yōu)化問題，并建立多節(jié)點(diǎn)協(xié)同任務(wù)分配模型。在粒子群算法的基礎(chǔ)上，通過結(jié)合遺傳算法的交又和變異操作，提高了算法的局部搜索能力。對(duì)多節(jié)點(diǎn)協(xié)同任務(wù)分配問題進(jìn)行求解得到非劣解集，為指揮決策者提供更多的信息依據(jù)，提高了多節(jié)點(diǎn)協(xié)同作戰(zhàn)能力。最后通過仿真計(jì)算對(duì)算法的有效性和收斂性進(jìn)行了驗(yàn)證。

【關(guān)鍵詞】多節(jié)點(diǎn) 任務(wù)分配問題 粒子群算法遺傳算法

1 引言

隨著以信息技術(shù)為核心的軍事科學(xué)技術(shù)迅速發(fā)展，軍事領(lǐng)域的各個(gè)方面發(fā)生了根本性的變革，這些變革推動(dòng)了軍事領(lǐng)域通信速度、反應(yīng)速度和作戰(zhàn)效率的極大提升。國(guó)外研究機(jī)構(gòu)提出了一種全新的作戰(zhàn)理論——網(wǎng)絡(luò)中心戰(zhàn)。通常來說，連入網(wǎng)絡(luò)中心的各作戰(zhàn)單元稱為節(jié)點(diǎn)，網(wǎng)絡(luò)中心戰(zhàn)為各節(jié)點(diǎn)提供以信息利用和共享為顯著特征的優(yōu)勢(shì)。而隨著作戰(zhàn)任務(wù)的日益復(fù)雜，傳統(tǒng)的作戰(zhàn)單元往往都是單獨(dú)對(duì)抗，難以滿足現(xiàn)代戰(zhàn)爭(zhēng)的需求。因此，多節(jié)點(diǎn)協(xié)同作戰(zhàn)是未來戰(zhàn)爭(zhēng)體系中的重要組成部分。但由于戰(zhàn)場(chǎng)環(huán)境，若多節(jié)點(diǎn)協(xié)同作戰(zhàn)時(shí)沒有對(duì)任務(wù)的預(yù)分配，不僅會(huì)使整個(gè)作戰(zhàn)效率低下，也會(huì)浪費(fèi)作戰(zhàn)系統(tǒng)的資源。多節(jié)點(diǎn)協(xié)同作戰(zhàn)有以下的優(yōu)勢(shì)：

（1）多節(jié)點(diǎn)協(xié)同作戰(zhàn)時(shí)，不再只是關(guān)注于單個(gè)節(jié)點(diǎn)的能力，而是通過節(jié)點(diǎn)的協(xié)同運(yùn)用，充分利用各個(gè)節(jié)點(diǎn)的優(yōu)勢(shì)，實(shí)現(xiàn)作戰(zhàn)效能的整體提升。

（2）多節(jié)點(diǎn)協(xié)同作戰(zhàn)時(shí)，若出現(xiàn)某些節(jié)點(diǎn)損傷或無(wú)法繼續(xù)執(zhí)行任務(wù)的情況，其執(zhí)行的任務(wù)可由其余尚有能力的節(jié)點(diǎn)執(zhí)行。充分利用了協(xié)同作戰(zhàn)的優(yōu)勢(shì)，具有一定的自我調(diào)節(jié)能力。

（3）多節(jié)點(diǎn)協(xié)同作戰(zhàn)時(shí)，對(duì)于在功能上以及時(shí)間上都有要求的復(fù)雜任務(wù)，多節(jié)點(diǎn)協(xié)同作戰(zhàn)能利用自身各個(gè)節(jié)點(diǎn)的功能性不同，完成不同的任務(wù)，并得到較高的效能。

因此，多節(jié)點(diǎn)協(xié)同作戰(zhàn)是未來戰(zhàn)爭(zhēng)的主要形式，而多節(jié)點(diǎn)協(xié)同任務(wù)分配問題直接影響作戰(zhàn)效能。為了滿足現(xiàn)代戰(zhàn)爭(zhēng)的需求，如何在各種約束條件下，給出任務(wù)分配方案，已經(jīng)是當(dāng)前重要的研究方向。

目前，國(guó)內(nèi)外學(xué)者已經(jīng)運(yùn)用整數(shù)規(guī)劃、遺傳算法、粒子群算法、蟻群算法等對(duì)多節(jié)點(diǎn)任務(wù)分配問題進(jìn)行了求解。文獻(xiàn)[7]基于整數(shù)規(guī)劃對(duì)多無(wú)人機(jī)任務(wù)分配問題進(jìn)行建模，能有效處理復(fù)雜的約束條件。文獻(xiàn)[12]綜合考慮無(wú)人機(jī)的偵察、攻擊、隱身和武器掛載能力，通過將各因素加權(quán)求和的方式構(gòu)建單目標(biāo)優(yōu)化模型，對(duì)任務(wù)分配問題進(jìn)行求解。文獻(xiàn)[13]對(duì)編碼方式和約束滿足進(jìn)行了改進(jìn)，成功應(yīng)用在任務(wù)分配問題的求解中。本文將多節(jié)點(diǎn)執(zhí)行任務(wù)的目標(biāo)價(jià)值毀傷和代價(jià)兩個(gè)關(guān)鍵指標(biāo)作為目標(biāo)函數(shù)，建立多目標(biāo)優(yōu)化模型，采用混合粒子群算法求解任務(wù)分配方案集。

2 多節(jié)點(diǎn)協(xié)同任務(wù)分配問題

為了直觀地描述多節(jié)點(diǎn)協(xié)同任務(wù)分配問題，本文假設(shè)多節(jié)點(diǎn)執(zhí)行對(duì)目標(biāo)的打擊任務(wù)。通過引入多節(jié)點(diǎn)執(zhí)行任務(wù)的目標(biāo)價(jià)值毀傷和代價(jià)兩個(gè)目標(biāo)函數(shù)，將多節(jié)點(diǎn)協(xié)同任務(wù)分配問題等效為多目標(biāo)函數(shù)優(yōu)化問題。多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)之間彼此制約，目標(biāo)函數(shù)不能被同時(shí)優(yōu)化到極值。因此，本文引入非劣解和非劣解集概念。在多目標(biāo)優(yōu)化問題中，存在一個(gè)解，在解集中，已找不到每個(gè)目標(biāo)函數(shù)都更優(yōu)的其他解，那么該解稱為非劣解。包含非劣解的解集就是非劣解集。

2.1 多節(jié)點(diǎn)協(xié)同任務(wù)分配模型

假設(shè)由N個(gè)節(jié)點(diǎn)對(duì)M個(gè)目標(biāo)執(zhí)行打擊任務(wù)。定義分配矩陣X^N×M，其中各個(gè)元素的定義為x_i，j^k∈{0，1}，具體定義如下：多節(jié)點(diǎn)協(xié)同任務(wù)分配數(shù)學(xué)模型為：

其中J₁（x）為目標(biāo)價(jià)值毀傷函數(shù)，J₂（X）為代價(jià)函數(shù)，由損耗代價(jià)函數(shù)和航程代價(jià)函數(shù)構(gòu)成。具體定義如下：

以上公式中S_ij為第i個(gè)節(jié)點(diǎn)對(duì)目標(biāo)j的殺傷概率，K_j表示第i個(gè)節(jié)點(diǎn)對(duì)目標(biāo)j執(zhí)行任務(wù)后的存活概率，Z_ij表示目標(biāo)j的自身價(jià)值，L_ij表示執(zhí)行任務(wù)的路程，L_ijmax表示執(zhí)行任務(wù)的最大路程。ω₁和ω₂是損耗代價(jià)函數(shù)和航程代價(jià)函數(shù)的權(quán)重比值。

根據(jù)多節(jié)點(diǎn)協(xié)同任務(wù)分配模型，應(yīng)當(dāng)滿足以下約束條件：

約束條件分別表達(dá)了：

（5）決策變量x_ij為0時(shí)代表不打擊，x_ij為1時(shí)代表打擊;

（6）每個(gè)目標(biāo)只能被攻擊一次;

（7）每個(gè)節(jié)點(diǎn)執(zhí)行兩次打擊任務(wù);

（8）執(zhí)行任務(wù)后的目標(biāo)價(jià)值毀傷不應(yīng)大于目標(biāo)的總價(jià)值;

3 混合粒子群算法

粒子群算法起源于對(duì)鳥群捕食行為的觀察和研究。粒子群算法用沒有質(zhì)量和體積的粒子來模擬捕食的鳥，每個(gè)粒子通過速度以及位置更新從而使得粒子貼近個(gè)體極值和群體極值，從而使得整個(gè)群體達(dá)到最優(yōu)，盡管操作相對(duì)容易，可以迅速求解問題，但在算法進(jìn)行過程中，各個(gè)粒子會(huì)變得類似，可能導(dǎo)致算法只得到局部最優(yōu)解。因此，本文采用混合粒子群算法，結(jié)合遺傳算法的優(yōu)點(diǎn)，通過粒子與粒子極值兩兩交叉以及粒子自身變異的方式使其能探索到新的搜索空間，從而使得算法的局部搜索能力增強(qiáng)。

3.1 編碼方式

在混合粒子群算法中，尋求一個(gè)合適的表達(dá)方式，將粒子和任務(wù)分配方案對(duì)應(yīng)是多節(jié)點(diǎn)任務(wù)分配中的關(guān)鍵。本文采用整數(shù)編碼方式來表達(dá)，每個(gè)粒子即是任務(wù)分配問題的一個(gè)方案，粒子的編碼長(zhǎng)度即為目標(biāo)數(shù)量，粒子編碼即為多節(jié)點(diǎn)序列對(duì)應(yīng)的目標(biāo)序列，表示一個(gè)任務(wù)分配方案。例如節(jié)點(diǎn)數(shù)目為4個(gè)，目標(biāo)數(shù)量為8個(gè)。如表1所示，第1個(gè)節(jié)點(diǎn)對(duì)應(yīng)目標(biāo)4和目標(biāo)1，第2個(gè)節(jié)點(diǎn)對(duì)應(yīng)目標(biāo)3和目標(biāo)7，第三個(gè)節(jié)點(diǎn)對(duì)應(yīng)目標(biāo)5和目標(biāo)6，第四個(gè)節(jié)點(diǎn)對(duì)應(yīng)目標(biāo)2和目標(biāo)8。個(gè)體編碼即為[43521768]。

3.2 篩選非劣解集

篩選非劣解集分成兩類。第一類是在初始化后得到非劣解集，種群初始化后，計(jì)算各個(gè)粒子的兩個(gè)目標(biāo)函數(shù)值。若對(duì)于某個(gè)解，在解集中，不存在目標(biāo)函數(shù)值都更優(yōu)的其他解，則將這個(gè)解篩選進(jìn)非劣解集中。第二類是在算法每次迭代后更新非劣解集。

3.3 交又操作

交叉方法采用整數(shù)交叉法，個(gè)體與極值粒子兩兩交叉搜索得到新個(gè)體。具體方法是首先隨機(jī)選取兩個(gè)整數(shù)作為交叉位置，假設(shè)選取的交叉位置為1和4，個(gè)體編碼為[35712658]，極值粒子編碼為[41526783]，然后用極值粒子交叉位置中間的整數(shù)替換個(gè)體交叉位置中間的整數(shù)，其他位置保持不變，得到新個(gè)體編碼為[41522658]。產(chǎn)生的新個(gè)體若存在相同整數(shù)，則用新個(gè)體中未出現(xiàn)的整數(shù)進(jìn)行替換，替換后的新個(gè)體編碼為[41523678]。最后計(jì)算新個(gè)體的兩個(gè)目標(biāo)函數(shù)值，如果新個(gè)體的目標(biāo)函數(shù)值均優(yōu)于舊個(gè)體，則用新個(gè)體替換舊個(gè)體進(jìn)行之后的操作。若得到的新個(gè)體目標(biāo)函數(shù)值中只有一個(gè)目標(biāo)函數(shù)值優(yōu)于舊個(gè)體，則隨機(jī)選擇其中一個(gè)作為之后操作的粒子個(gè)體。

3.4 變異操作

變異方法采用整數(shù)替換法，個(gè)體自身變異從而得到新個(gè)體。具體方法是首先隨機(jī)選取兩個(gè)整數(shù)作為變異位置，假設(shè)選取的變異位置為4和6，個(gè)體編碼為[35712658]，然后互相交換位置，得到的新個(gè)體編碼為[35762158]。最后計(jì)算新個(gè)體的兩個(gè)目標(biāo)函數(shù)值，如果新個(gè)體的目標(biāo)函數(shù)值均優(yōu)于舊個(gè)體，則用新個(gè)體替換舊個(gè)體進(jìn)行之后的操作。若得到的新個(gè)體目標(biāo)函數(shù)值中只有一個(gè)目標(biāo)函數(shù)值優(yōu)于舊個(gè)體，則隨機(jī)選擇其中一個(gè)作為之后操作的粒子個(gè)體。

3.5 算法流程

基于混合粒子群算法的多節(jié)點(diǎn)協(xié)同任務(wù)分配流程圖如圖1所示。

其步驟可總結(jié)如下：

（1）確定算法的各種初始參數(shù)，如算法的初始種群數(shù)量，迭代次數(shù)等參數(shù);

（2）隨機(jī)生成種群中的粒子，產(chǎn)生的粒子為個(gè)體編碼序列隨機(jī)排列得到。

（3）計(jì)算各粒子的兩個(gè)目標(biāo)函數(shù)值，兩個(gè)目標(biāo)函數(shù)分別為執(zhí)行任務(wù)后目標(biāo)毀傷價(jià)值和代價(jià)。

（4）根據(jù)目標(biāo)函數(shù)值，更新種群的粒子和非劣解集，并得到種群的個(gè)體極值粒子和群體極值粒子。

（5）種群中每個(gè)粒子進(jìn)行交叉、變異操作，若得到的新個(gè)體目標(biāo)函數(shù)值均優(yōu)于舊個(gè)體，則用新個(gè)體替換舊個(gè)體進(jìn)行之后的操作。若得到的新個(gè)體目標(biāo)函數(shù)值中只有一個(gè)目標(biāo)函數(shù)值優(yōu)于舊個(gè)體，則隨機(jī)選擇其中一個(gè)作為之后操作的粒子個(gè)體。

（6）更新種群的粒子和非劣解集。當(dāng)執(zhí)行步驟5，更新種群的粒子從而進(jìn)行之后的操作。并更新當(dāng)前的非劣解集。

（7）判斷算法是否結(jié)束。如果未結(jié)束，即迭代次數(shù)未達(dá)到最大，則重復(fù)步驟3到步驟6之間的過程。如果迭代次數(shù)達(dá)到最大，則算法結(jié)束，執(zhí)行步驟8。

（8）得到種群的非劣解集。當(dāng)算法結(jié)束后，得到最終的非劣解集。4仿真計(jì)算實(shí)例

為驗(yàn)證所研究的多節(jié)點(diǎn)協(xié)同任務(wù)分配算法的有效性和收斂性，進(jìn)行仿真計(jì)算。在仿真計(jì)算中，假設(shè)節(jié)點(diǎn)數(shù)目為4個(gè)，目標(biāo)數(shù)目為8個(gè)?；旌狭Ｗ尤核惴ǖ闹饕獏?shù)設(shè)定：初始種群有100個(gè)粒子，迭代次數(shù)最大為200次，ω₁=0.8，ω₂=0.2。其中節(jié)點(diǎn)位置如表2所示。節(jié)點(diǎn)對(duì)目標(biāo)的殺傷概率如表3所示。目標(biāo)自身位置和價(jià)值以及節(jié)點(diǎn)對(duì)目標(biāo)執(zhí)行任務(wù)后的存活概率如表4所示。

經(jīng)過200次的仿真計(jì)算表明，在上述條件下得到的結(jié)果具有穩(wěn)定性?；谏鲜鰲l件，首先驗(yàn)證算法的收斂性。圖2給出了非劣解集中的每代最優(yōu)的兩個(gè)目標(biāo)函數(shù)值隨迭代次數(shù)的收斂曲線。在整個(gè)算法迭代過程中，兩個(gè)目標(biāo)函數(shù)均收斂。其次驗(yàn)證算法的有效性，多節(jié)點(diǎn)任務(wù)分配的非劣解集如圖3所示。與單目標(biāo)優(yōu)化模型只能得到一個(gè)方案相比，本文構(gòu)建的模型能得到非劣解集，給決策者提供更多信息依據(jù)，證明了該算法的有效性。

表5給出了非劣解集中的幾個(gè)非劣解中執(zhí)行任務(wù)的目標(biāo)價(jià)值毀傷和代價(jià)以及任務(wù)集。由表5可知，方案1中，各節(jié)點(diǎn)執(zhí)行任務(wù)集分別為（7，8）、（4，1）、（3，5）和（6，2），執(zhí)行任務(wù)后的目標(biāo)價(jià)值毀傷為3.4464，代價(jià)為2.4125。方案2中，各節(jié)點(diǎn)執(zhí)行任務(wù)集分別為（7，6）、（4，2）、（8，1）和（3，5），執(zhí)行任務(wù)后的目標(biāo)價(jià)值毀傷為2.6695，代價(jià)為1.9382?？梢钥闯觯凑辗桨?執(zhí)行任務(wù)后的目標(biāo)價(jià)值毀傷雖然比方案2執(zhí)行任務(wù)后的目標(biāo)價(jià)值毀傷高，但方案1付出的代價(jià)同樣比方案2高。因此，在非劣解集中具體選擇哪一個(gè)非劣解作為任務(wù)分配方案，由進(jìn)一步需求決定。

5 結(jié)束語(yǔ)

針對(duì)多節(jié)點(diǎn)協(xié)同任務(wù)分配問題，本文將多節(jié)點(diǎn)執(zhí)行打擊任務(wù)的目標(biāo)價(jià)值毀傷和代價(jià)作為目標(biāo)函數(shù)，建立多節(jié)點(diǎn)協(xié)同任務(wù)分配模型。利用混合粒子群算法對(duì)多節(jié)點(diǎn)協(xié)同任務(wù)分配問題進(jìn)行求解，得到非劣解集。仿真計(jì)算結(jié)果驗(yàn)證了此算法的有效性和收斂性。算法操作相對(duì)容易，能快速對(duì)問題進(jìn)行求解。決策者可以根據(jù)進(jìn)一步需求在非劣解集中進(jìn)行選擇。

參考文獻(xiàn)

[1]龔秀成，蔣曉源，陳華.網(wǎng)絡(luò)中心戰(zhàn)體系中的指揮控制[J].火力與指揮控制，2010，35（03）：347-354.

[2]Alberts，D.S.，Garstka，J.J.，Stein，F(xiàn).P.，Network Centric Warfare：Developing and Leveraging InformationSuperiority[M].Washington，DC：CCRPPublications，Aug 1999.

[3]Andrew S.Tanenbaum，ComputerNetwork[M].Tsinghua UniversityPress，2007.

[4]Rabbath CA，Gagnon E，Lauzon M.On theCooperative Control of MultipleUnmanned Aerial Vehicles[J].IEEECanadian Review，2004（46）：15-19.

[5]姜長(zhǎng)生，丁全心，王建剛等.多機(jī)協(xié)同空戰(zhàn)中的威脅評(píng)估與目標(biāo)分配[J].火力與指揮控制，2008，33（11）：8-12.

[6]Thomas H.Cormen，Charles E.Leiserson，Ronald L.Introductionto Algorithms[M].McGrawHill：MITPress，2001.

[7]葉媛媛，閔春平，朱華勇等.基于整數(shù)規(guī)劃的多UCAV任務(wù)分配問題研究[J].信息與控制，2005，34（05）：548-552.

[8]Goldberg，David E.Genetic Algorithms：Search，Optimization and MachineLearning[M].Boston：Kluwer AcademicPublishers，1989.

[9]Kennedy J.Eberhart R.Particle swarmoptimization[J].IEEE，1995，4：1942-1948.

[10]Curz J B，Jr C，Chen G.Particle SwarmOptimization for Resource Allocationin UAV Cooperative Control [A].AIAAGuidance，Navigation，and ControlConference and Exhibit，Rhode Island，Aug.16-19，2004.

[11]DORIGO M.GAMBARDELLA L M.AntColonies for the TravelingSalesman Problem[J].BioSystems，1997，43（02）：73-81.

[12]戚澤旸，王強(qiáng)，黃英杰.多無(wú)人機(jī)偵察打擊任務(wù)分配建模仿真[J].計(jì)算機(jī)仿真，2015，32（09）：142-146.

[13]國(guó)博，王社偉，陶軍.基于改進(jìn)粒子群算法的多無(wú)人機(jī)任務(wù)分配研究[J].計(jì)算機(jī)仿真，2009，26（07）：62-64.

[14]申曉寧，胡維禮.一種多目標(biāo)優(yōu)化合作性協(xié)同進(jìn)化算法[J].計(jì)算機(jī)仿真，2007，24（02）：157-161.

[15]葉秉如，余里紅.多目標(biāo)二次規(guī)劃非劣解集的理論生成及應(yīng)用[J].水電能源科學(xué)，1991，9（02）：102-110.

[16]霍霄華，陳巖，朱華勇等.多UCAV協(xié)同控制中的任務(wù)分配模型及算法[J].國(guó)防科技大學(xué)學(xué)報(bào)，2006，28（03）：83-88.

[17]Dorigo M，Birattari M.AntColony Optimization：a new meta-heuristic[A].in proceedings of theIEEE International Conference onEvolutionary Computation（ICEC99）[C].Piscataway，USA：IEEEPress，1999：1470-1477.

[18]王偉.混合粒子群算法及其優(yōu)化效率評(píng)價(jià)[J].中國(guó)水運(yùn)，2007，7（06）：100-101.

[19]汪定偉，王俊偉，王洪峰等.智能優(yōu)化方法[M].北京：高等教育出版社，2007.