婁艷秋，莊 毅，顧晶晶，霍 瑛

(1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210000；2.南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 南京 210000)

協(xié)同干擾環(huán)境下基于IMOABC的任務(wù)調(diào)度方法

婁艷秋1，莊 毅1，顧晶晶1，霍 瑛2

(1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210000；2.南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 南京 210000)

在協(xié)同干擾環(huán)境下，除了需要考慮最大限度地完成干擾任務(wù)，還需要最大程度地減少己方的損失消耗。在這種復(fù)雜的需求下，需要將協(xié)同干擾環(huán)境下的任務(wù)調(diào)度問(wèn)題轉(zhuǎn)化為多目標(biāo)優(yōu)化問(wèn)題。針對(duì)如何最大限度地完成干擾任務(wù)，同時(shí)最大程度地減少無(wú)人作戰(zhàn)飛行器(UCAV)的能量損失消耗問(wèn)題，將干擾貢獻(xiàn)值和損失消耗值作為目標(biāo)函數(shù)，建立了基于多目標(biāo)優(yōu)化的協(xié)同干擾任務(wù)調(diào)度模型(MOTSM)。提出了基于多目標(biāo)優(yōu)化的改進(jìn)人工蜂群算法(IMOABC)的任務(wù)調(diào)度算法來(lái)求解該模型。IMOABC算法首先進(jìn)行染色體的二進(jìn)制編碼，然后隨機(jī)生成一個(gè)滿(mǎn)足MOTSM模型約束條件的初始種群。對(duì)初始種群進(jìn)行非支配快速排序以及擁擠度距離的計(jì)算，通過(guò)雇傭蜂、觀察蜂、偵察蜂三種蜜蜂的配合，完成對(duì)最優(yōu)解的搜索。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該模型與算法的有效性。

協(xié)同干擾；多目標(biāo)優(yōu)化；任務(wù)調(diào)度；人工蜂群算法

0 引 言

在現(xiàn)代化的信息戰(zhàn)中，無(wú)人作戰(zhàn)飛行器(Unmanned Combat Aerial Vehicle,UCAV)憑借其零傷亡率、高靈活性等特點(diǎn)活躍在軍事的各個(gè)領(lǐng)域，比如電子干擾。戰(zhàn)場(chǎng)環(huán)境中如何對(duì)UCAV進(jìn)行合理的任務(wù)調(diào)度成為了無(wú)人機(jī)指揮與控制的關(guān)鍵技術(shù)之一，同時(shí)也受到了國(guó)內(nèi)外專(zhuān)家學(xué)者的關(guān)注與研究。以往的研究大多是將協(xié)同干擾環(huán)境下的任務(wù)調(diào)度問(wèn)題作為單目標(biāo)優(yōu)化問(wèn)題來(lái)考慮，其重點(diǎn)在于如何有效構(gòu)造組合方案使其滿(mǎn)足所有的約束條件并使其適應(yīng)度值達(dá)到全局最優(yōu)。但是在現(xiàn)實(shí)戰(zhàn)場(chǎng)上，除了需要考慮最大限度地完成干擾任務(wù)，也需要最大程度地減少己方的損失消耗。在這種復(fù)雜的需求下，迫切需要將協(xié)同干擾環(huán)境下的任務(wù)調(diào)度問(wèn)題轉(zhuǎn)化為多目標(biāo)優(yōu)化問(wèn)題，通過(guò)相應(yīng)算法求解出一組最優(yōu)非劣解，讓決策者根據(jù)現(xiàn)實(shí)戰(zhàn)場(chǎng)環(huán)境來(lái)進(jìn)行選擇。

針對(duì)上述問(wèn)題，提出了基于多目標(biāo)優(yōu)化的任務(wù)調(diào)度模型。與單目標(biāo)的優(yōu)化模型不同，該模型以最大化干擾貢獻(xiàn)值、最小化損失消耗值為兩個(gè)目標(biāo)進(jìn)行優(yōu)化。其中，干擾貢獻(xiàn)值是對(duì)UCAV的多個(gè)指標(biāo)(除續(xù)航能力外)的綜合評(píng)估。為求解該模型，提出了一種基于多目標(biāo)優(yōu)化的改進(jìn)人工蜂群算法(Improved Multi-Objective Artificial Bee Colony，IMOABC)，用蜜蜂的覓食行為來(lái)模擬對(duì)任務(wù)調(diào)度方案的搜索，并通過(guò)實(shí)驗(yàn)對(duì)該算法進(jìn)行驗(yàn)證。

1 相關(guān)研究

協(xié)同干擾環(huán)境下，基于多目標(biāo)優(yōu)化的任務(wù)調(diào)度問(wèn)題本質(zhì)上是一個(gè)多目標(biāo)、多約束條件、高耦合度的武器目標(biāo)分配問(wèn)題；因此將從多目標(biāo)優(yōu)化的角度，并結(jié)合該領(lǐng)域的研究現(xiàn)狀，對(duì)協(xié)同干擾環(huán)境下基于多目標(biāo)優(yōu)化的任務(wù)調(diào)度問(wèn)題進(jìn)行探索和研究。

武器目標(biāo)分配問(wèn)題屬于NP難問(wèn)題，很難在有限的時(shí)間內(nèi)獲得最優(yōu)的解決方案[1]。因此，研究多目標(biāo)優(yōu)化問(wèn)題，從而能在有效時(shí)間內(nèi)獲取最優(yōu)解決方案，對(duì)提高效率、增強(qiáng)電子干擾效果具有重要的理論和實(shí)踐意義。

對(duì)于武器目標(biāo)分配問(wèn)題，國(guó)內(nèi)外專(zhuān)家和學(xué)者已經(jīng)進(jìn)行了大量研究。例如，Wu Ling等提出了一種基于改進(jìn)遺傳算法的隨時(shí)算法，用以求解武器目標(biāo)分配問(wèn)題，從而使得目標(biāo)生存值最小[2]。該算法約定，在目標(biāo)到達(dá)前對(duì)每個(gè)武器逐一進(jìn)行分配。當(dāng)目標(biāo)被分配到一定數(shù)目的武器之后，這個(gè)目標(biāo)在整個(gè)染色體中被一個(gè)新的目標(biāo)替換，同時(shí)，整個(gè)優(yōu)化過(guò)程不進(jìn)行任何重啟。Chen Jie等提出了一種以四種類(lèi)型的約束為基礎(chǔ)的武器目標(biāo)分配模型，包括能力約束、策略約束、資源約束和參與可行性約束。提出使用一個(gè)通用的“虛擬”決策代表以方便產(chǎn)生可行的決定。為了求解該模型，改進(jìn)了三種進(jìn)化決策算法，包括一種遺傳算法和兩種文化基因算法。實(shí)驗(yàn)表明，基于貪婪局部搜索的文化基因算法能夠得到更好的武器目標(biāo)分配方案，特別是對(duì)大規(guī)模的問(wèn)題，明顯優(yōu)于遺傳算法和基于梯度的局部搜索的文化基因算法[3]。H Naeem等提出一種穩(wěn)定婚姻算法來(lái)討論一種最優(yōu)多空中威脅評(píng)估和武器分配問(wèn)題。采用了一種新的武器調(diào)度算法，允許多主體使用攻擊-搜索-攻擊策略，計(jì)算接近最優(yōu)的解決方案[4]。Xin B等提出了一個(gè)通用的基于資產(chǎn)的武器目標(biāo)分配模型，特別是對(duì)戰(zhàn)爭(zhēng)的武力協(xié)調(diào)問(wèn)題。并提出了一種禁忌搜索算法來(lái)求解該模型[5]。Atif Shahzad等提出了一個(gè)離散事件系統(tǒng)仿真模型，考慮了資源約束、能力約束、戰(zhàn)略約束和參與的可行性約束。采用三種不同的方法：MMR、無(wú)禁忌搜索以及提出的基于人工智能的模擬優(yōu)化的混合框架。生成一組規(guī)則的基礎(chǔ)上的優(yōu)化模塊，然后采用實(shí)時(shí)控制[6]。但是以上研究都基于單目標(biāo)的武器目標(biāo)分配，只有少量研究基于多目標(biāo)的武器目標(biāo)分配。如Zhang Ying等在靜態(tài)武器目標(biāo)分配模型的基礎(chǔ)上,提出了一種武器目標(biāo)分配模型，并設(shè)計(jì)了一種基于分解的多目標(biāo)進(jìn)化算法求解該模型[7]。

目前，國(guó)內(nèi)外的研究人員對(duì)多目標(biāo)優(yōu)化方法的研究大致分為兩個(gè)方向：一個(gè)是傳統(tǒng)的數(shù)學(xué)規(guī)劃法，另一個(gè)則是智能優(yōu)化算法，且主要集中在對(duì)智能優(yōu)化算法的研究上。傳統(tǒng)的數(shù)學(xué)規(guī)劃法采用規(guī)劃的思路，通過(guò)窮舉得到最優(yōu)的分配方案，典型的方法有割平面法、分支定界法等[8]。使用這些方法，通常能得到問(wèn)題的全局最優(yōu)解，但是其計(jì)算效率較低，且隨著問(wèn)題規(guī)模的上升呈指數(shù)增長(zhǎng)，無(wú)法滿(mǎn)足武器目標(biāo)分配的實(shí)時(shí)要求。

智能優(yōu)化算法是一類(lèi)通過(guò)模擬某一自然現(xiàn)象或過(guò)程而建立起來(lái)的優(yōu)化方法，典型的有遺傳算法、粒子群算法、禁忌搜索、人工免疫系統(tǒng)、蟻群算法、人工蜂群算法等。與傳統(tǒng)的數(shù)學(xué)規(guī)劃法相比，使用智能優(yōu)化算法求解多目標(biāo)優(yōu)化問(wèn)題顯得更為合適。首先，大多數(shù)智能優(yōu)化算法能同時(shí)處理一組解，每次運(yùn)行算法，就能獲得多個(gè)有效解。其次，智能優(yōu)化算法對(duì)帕累托最優(yōu)前端的形狀和連續(xù)性不敏感，因此可以很好地逼近非凸或是不連續(xù)的最優(yōu)前端。其中，由于人工蜂群算法的提出時(shí)間較晚，對(duì)于這方面的研究還比較少。但是因其參數(shù)設(shè)置少、收斂速度快、收斂精度高且不易陷入局部最優(yōu)等特點(diǎn)越來(lái)越受到研究者的廣泛關(guān)注。如Xiang Yi等通過(guò)引入精英策略提出了一種新的多目標(biāo)人工蜂群算法。該算法使用一個(gè)固定大小的檔案保持基于擁擠距離來(lái)存儲(chǔ)搜索過(guò)程中的非劣解。在觀察蜂和雇傭蜂階段，檔案中的精英都有可能被選擇和使用,從而在每個(gè)周期產(chǎn)生新的食物源。為了保持多樣性，當(dāng)檔案發(fā)生變化時(shí)，位于最擁擠區(qū)域的成員將被刪除[9]。Huo Ying等在原始ABC算法中加入多目標(biāo)優(yōu)化策略，提出基于精英的多目標(biāo)人工蜂群算法，并在隨機(jī)服務(wù)集和真實(shí)服務(wù)集驗(yàn)證了該算法的有效性[10]。趙輝等針對(duì)多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題經(jīng)過(guò)單目標(biāo)簡(jiǎn)化后對(duì)決策處理存在的片面性和主觀性等問(wèn)題，提出了一種利用多目標(biāo)自適應(yīng)快速人工蜂群算法對(duì)其進(jìn)行處理的方法。首先，建立多目標(biāo)無(wú)人機(jī)協(xié)同任務(wù)分配模型；其次通過(guò)建立外部種群的約束處理技術(shù)及重置Harmonic平均距離循環(huán)策略對(duì)自適應(yīng)快速人工蜂群算法進(jìn)行改進(jìn)，另外通過(guò)定義自主決策準(zhǔn)則引導(dǎo)多目標(biāo)任務(wù)分配的方案選取[11]。

綜上，目前對(duì)多目標(biāo)的武器目標(biāo)分配問(wèn)題的研究還存在一些不足。首先，對(duì)多目標(biāo)的武器目標(biāo)分配問(wèn)題的模型缺少深入研究，不少模型都是在靜態(tài)武器目標(biāo)分配模型或是單目標(biāo)武器目標(biāo)分配模型的基礎(chǔ)上進(jìn)行一個(gè)簡(jiǎn)單的重復(fù)；其次，在目前已有的對(duì)武器目標(biāo)分配問(wèn)題的研究中，大部分沒(méi)有考慮到協(xié)同作戰(zhàn)的問(wèn)題；最后，缺乏多目標(biāo)的武器目標(biāo)分配問(wèn)題求解算法，只有找到高效實(shí)時(shí)的求解算法，才能為軍事指揮與控制決策提供有力的支持。因此，對(duì)多目標(biāo)武器目標(biāo)分配問(wèn)題展開(kāi)研究具有實(shí)際意義。

2 多目標(biāo)任務(wù)調(diào)度問(wèn)題建模

2.1決策變量描述

假設(shè)我方提供一支擁有n架UCAV的電子干擾遠(yuǎn)程支援編隊(duì)(U={U1,U2,···,Un}，其中Ui表示第i架UCAV)，需要對(duì)敵方的m部分布離散的地面雷達(dá)(D={D1,D2,…,Dm}，其中Dj表示第j部雷達(dá))進(jìn)行干擾作戰(zhàn)，并且規(guī)定每部地面雷達(dá)最多分配lmax架UCAV，同時(shí)每架UCAV只能選擇一部雷達(dá)進(jìn)行干擾。則編隊(duì)方案集合可以表示為UD={UD1,UD2,…,UDn}，其中UDi(i=1,2,…,n)表示將第i架UCAV分配給干擾目標(biāo)雷達(dá)的設(shè)備號(hào)，并且1≤UDi≤m,UDi∈N。多目標(biāo)任務(wù)調(diào)度就是從所有滿(mǎn)足約束條件的編隊(duì)方案中選取一個(gè)使目標(biāo)最優(yōu)的方案。因此該問(wèn)題的決策變量即為編隊(duì)方案，可以用一個(gè)一維數(shù)組表示。其中數(shù)組下標(biāo)表示UCAV編號(hào)，數(shù)組內(nèi)容表示干擾目標(biāo)編號(hào)。

2.2優(yōu)化目標(biāo)1：最大化干擾貢獻(xiàn)值

干擾效果評(píng)估模型是評(píng)價(jià)編隊(duì)方案質(zhì)量的重要標(biāo)準(zhǔn)，由多個(gè)維度構(gòu)成，從不同方面對(duì)編隊(duì)方案的質(zhì)量進(jìn)行評(píng)價(jià)。文中參考文獻(xiàn)[12]，可以得到任務(wù)調(diào)度評(píng)估指標(biāo)集q(eji,j)={qjp(eji,j),qjs(eji,j),qjf(eji,j),qjt(eji,j)}，具體含義如表1所示。

在真實(shí)戰(zhàn)場(chǎng)上，當(dāng)面對(duì)的敵方雷達(dá)較強(qiáng)時(shí)，單架UCAV的功能是有限的。為了滿(mǎn)足戰(zhàn)場(chǎng)日益復(fù)雜的攻擊、防守需求，需要將多架UCAV進(jìn)行組合來(lái)提供復(fù)雜的功能；同時(shí)，也需要將任務(wù)進(jìn)行合理分配，運(yùn)用合適的武器組合來(lái)實(shí)現(xiàn)任務(wù)調(diào)度利益最大化。任務(wù)調(diào)度的指標(biāo)集用Q(ej)={Q1,Q2,…,Qr}，其中Qk表示任務(wù)的第k維指標(biāo)的聚合值，是由各候選武器裝備的指標(biāo)值qk(eji,j)聚合得到[13]。

表2給出了各指標(biāo)的聚合函數(shù)。

表1 任務(wù)調(diào)度評(píng)估指標(biāo)描述

表2 聚合函數(shù)

采用簡(jiǎn)單加權(quán)和法(Simple Additive Weighting,SAW)，對(duì)各指標(biāo)按照重要程度賦予不同的權(quán)重，再通過(guò)加權(quán)和計(jì)算得到綜合評(píng)價(jià)值。但由于指標(biāo)評(píng)價(jià)時(shí)采用了不同的方法且量綱也不同，因此首先必須將指標(biāo)進(jìn)行歸一化。

在歸一化階段，將指標(biāo)分為積極指標(biāo)和消極指標(biāo)。歸一化時(shí)要分別處理，參考文獻(xiàn)[14]，方法如下:

(1)

其中，maxQk(minQk)表示所有任務(wù)調(diào)度方案中第k維指標(biāo)的最大值(最小值)，如果兩者相等，則指標(biāo)的歸一化值為1。

任務(wù)調(diào)度的干擾貢獻(xiàn)度值的計(jì)算函數(shù)feva如下：

(2)

2.3優(yōu)化目標(biāo)2：最小化損失消耗值

協(xié)同電子干擾中，為了減少UCAV的耗損，需要考慮其續(xù)航能力，盡可能最小化損失消耗值，使其在完成任務(wù)之后能夠順利返回。可以用qea(eji,j)來(lái)表示編號(hào)為i的UCAV對(duì)目標(biāo)j進(jìn)行干擾后的損失消耗值。其聚合函數(shù)如式(3)所示。

(3)

為便于后續(xù)優(yōu)化過(guò)程中的計(jì)算，損失消耗值的計(jì)算函數(shù)felo同樣通過(guò)歸一化值來(lái)表示，計(jì)算公式如式(4)所示。

(4)

2.4多目標(biāo)優(yōu)化模型

為了滿(mǎn)足決策者在進(jìn)行有限損失消耗的基礎(chǔ)上制定干擾效果最優(yōu)的編隊(duì)方案的需求，設(shè)定任務(wù)調(diào)度的干擾貢獻(xiàn)值最大化maxfeva，損失消耗值最小化minfelo為兩個(gè)優(yōu)化目標(biāo)，設(shè)計(jì)基于多目標(biāo)優(yōu)化的任務(wù)調(diào)度模型MOTSM。為便于求解，將minfelo轉(zhuǎn)化為max(-felo)，轉(zhuǎn)化后模型如下：

(5)

式(5)表明模型的目的是用來(lái)尋找使目標(biāo)函數(shù)最大化的調(diào)度方案。其中，ωk為第k維指標(biāo)的權(quán)重；UniQk為第k維指標(biāo)的歸一化值。約束條件是用來(lái)保證算法所求的調(diào)度方案中每個(gè)UCAV對(duì)目標(biāo)雷達(dá)進(jìn)行干擾時(shí)，滿(mǎn)足干擾頻率、干擾樣式等要求。其中， UD={UD1,UD2,…,UDn},UDi(i=1,2,…,n)表示將第i架UCAV分配給干擾目標(biāo)雷達(dá)的設(shè)備號(hào)；VAj(j=1,2,…,m)表示對(duì)第j部目標(biāo)雷達(dá)進(jìn)行干擾的價(jià)值量；duij表示第i架UCAV是否對(duì)第j部目標(biāo)雷達(dá)進(jìn)行干擾，若為0則表示不進(jìn)行干擾，否則就進(jìn)行干擾；lmax表示每部目標(biāo)雷達(dá)最多分配UCAV的架數(shù)。

3 基于IMOABC的任務(wù)調(diào)度算法設(shè)計(jì)

為求解協(xié)同干擾環(huán)境下的多目標(biāo)優(yōu)化問(wèn)題，設(shè)計(jì)基于IMOABC的任務(wù)調(diào)度算法。設(shè)計(jì)染色體編碼方式來(lái)對(duì)協(xié)同干擾環(huán)境下的任務(wù)調(diào)度方案進(jìn)行編碼，并描述快速支配選擇，種群選擇、交叉及變異操作，以及多目標(biāo)適應(yīng)度計(jì)算等多目標(biāo)優(yōu)化策略。

3.1編碼方式

U表示UCAV編隊(duì)，D表示地面雷達(dá)組，UD表示協(xié)同干擾環(huán)境下的任務(wù)調(diào)度方案。當(dāng)有9架UCAV需要對(duì)3部目標(biāo)雷達(dá)進(jìn)行干擾時(shí)，即U={1,2,3,4,5,6,7,8,9}，D={1,2,3}。如果分配編號(hào)為1,2,3的UCAV對(duì)1號(hào)雷達(dá)進(jìn)行干擾，分配編號(hào)為4,5,6,7的UCAV對(duì)2號(hào)雷達(dá)進(jìn)行干擾，分配編號(hào)為8,9的UCAV對(duì)3號(hào)雷達(dá)進(jìn)行干擾。文獻(xiàn)[16]采用的是分組染色體編碼方式，即UD={{1<->1,2,3},{2<->4,5,6,7},{3<->8,9}}；文中對(duì)文獻(xiàn)[16]的編碼方式進(jìn)行改進(jìn)，用一維數(shù)組進(jìn)行表示：數(shù)組下標(biāo)表示UCAV編號(hào)，數(shù)組內(nèi)容表示干擾目標(biāo)編號(hào)，即UD=[1,1,1,2,2,2,2,3,3]。

3.2算法描述

3.2.1 初始種群確定

(6)

其中，duij∈{0,1}。

這樣每一個(gè)種群可以轉(zhuǎn)換成二進(jìn)制的編碼方式，而相較于十進(jìn)制編碼方式，二進(jìn)制編碼方式的搜索效率更高，對(duì)變異概率和交叉概率的魯棒性更好。

3.2.2 快速非支配排序

IMOABC算法在選擇運(yùn)算之前需要對(duì)種群中的個(gè)體的優(yōu)劣程度進(jìn)行分級(jí)，而快速非支配排序方法就是目前多數(shù)多目標(biāo)優(yōu)化問(wèn)題中判斷個(gè)體優(yōu)劣程度的方法。基本思想是根據(jù)可行解之間的支配關(guān)系對(duì)種群中的個(gè)體目標(biāo)函數(shù)值進(jìn)行排序，從而為后續(xù)的選擇、進(jìn)化提供依據(jù)。

快速非支配排序算法需要記錄兩個(gè)變量的值：支配個(gè)數(shù)np，記錄可支配可行解UD的所有個(gè)體的數(shù)量；被支配集Sp，是可被可行解UD支配的解的集合。

對(duì)于可支配可行解UD中的每個(gè)個(gè)體ud，令np=0。如果存在ud'，使得ud支配ud'，則把ud'添加到Sp列表中，否則ud被ud'支配，則np=np+1。如果np=0，則該個(gè)體ud為第一級(jí)，即ud.rank=1。同時(shí)遍歷被支配集Sp，使集合中每個(gè)個(gè)體的支配個(gè)數(shù)都減1。如果此時(shí)該個(gè)體的支配個(gè)數(shù)為0，則該個(gè)體是非支配個(gè)體，將該個(gè)體級(jí)別記為當(dāng)前最高級(jí)別加1，同時(shí)將該個(gè)體存入新列表Sq。針對(duì)Sq重復(fù)以上步驟，可得到ud.rank=3的解。重復(fù)以上步驟，直到Sq為空集。

3.2.3 種群選擇、交叉和變異操作

(1)種群選擇策略。

選擇策略是為了在進(jìn)行交叉和變異操作前提供一種策略，能夠選擇優(yōu)越性較大的個(gè)體作為父代種群。非支配排序完成后，通過(guò)計(jì)算每個(gè)解的擁擠度距離，能夠得到兩個(gè)重要屬性，即非支配排名ud.rank和擁擠度距離ud.distance。文中采用輪賽制選擇算子，根據(jù)這兩個(gè)屬性設(shè)計(jì)的種群選擇策略如下：

①在種群完成非支配排序之后，從種群中隨機(jī)選擇兩個(gè)個(gè)體，記為udi和udj。如果udi.rankudj.distance，則選擇udi遺傳到下一代新種群。

②對(duì)需進(jìn)行選擇策略的種群重復(fù)步驟①SN次，就可以得到下一代種群中的SN個(gè)個(gè)體。

使用輪賽制選擇算子，可以保證淘汰最差的個(gè)體，同時(shí)最大限度地保留最優(yōu)個(gè)體。而選擇較小的非支配排名可以使解向質(zhì)量更好的方向進(jìn)化，選擇較大的擁擠度距離則可以使種群中可行解的分布更加均勻，從而提高解的多樣性。

(2)種群交叉和變異操作。

遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的搜索算法。自然界中生物的進(jìn)化是通過(guò)染色體交叉、變異、重組來(lái)生成新的染色體，因此遺傳算法中的交叉也是通過(guò)交換個(gè)體的基因來(lái)生成新的個(gè)體。通常使用的適用于二進(jìn)制編碼方式的交叉算子有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉以及均勻交叉等。遺傳算法中的變異算子則是通過(guò)改變個(gè)體內(nèi)部的基因來(lái)保持種群中個(gè)體的多樣性。

文中將遺傳算法與ABC算法相結(jié)合，在雇傭蜂和觀察蜂進(jìn)行鄰域搜索時(shí)，對(duì)于新產(chǎn)生的鄰域解，采用多點(diǎn)交叉算子進(jìn)行交叉操作，采用二進(jìn)制位取反變異算子進(jìn)行變異操作。多點(diǎn)交叉算子是指在選擇的兩個(gè)個(gè)體中隨機(jī)設(shè)置多個(gè)交叉點(diǎn)，然后基于這些交叉點(diǎn)將位于兩交叉點(diǎn)之間的基因互相交換。二進(jìn)制位取反變異算子則是以一定的概率將所選的個(gè)體中的某些位置按位取反。

3.2.4 多目標(biāo)適應(yīng)度值計(jì)算方法

在ABC算法中，可行解的適應(yīng)度值是通過(guò)單目標(biāo)函數(shù)值來(lái)確定的。但是在文中所述的多目標(biāo)優(yōu)化問(wèn)題中，由于目標(biāo)函數(shù)不止一個(gè)，目標(biāo)函數(shù)值也有多個(gè)，因此原有的計(jì)算方法不再適用，需要對(duì)適應(yīng)度值計(jì)算方法進(jìn)行更新。

文中優(yōu)化的目標(biāo)數(shù)為2，maxf(x)=[f1(x),f2(x)]=[feva,-felo]，即f1(x)=feva，f2(x)=-felo。由于兩個(gè)目標(biāo)所衡量的對(duì)象不一樣，在計(jì)算適應(yīng)度值前，需要將目標(biāo)函數(shù)值進(jìn)行歸一化處理，如式(7)所示。

(7)

其中，maxfk=max{fk(x1),fk(x2),…,fk(xSN)}，minfk=min{fk(x1),fk(x2),…,fk(xSN)},k=[1,2]。

可行解的適應(yīng)度值計(jì)算公式如式(8)所示。

(8)

3.2.5 基于IMOABC的任務(wù)調(diào)度算法流程

基于IMOABC的任務(wù)調(diào)度算法，首先進(jìn)行染色體的二進(jìn)制編碼，然后隨機(jī)生成一個(gè)滿(mǎn)足MOTSM模型約束條件的初始種群，對(duì)初始種群進(jìn)行非支配快速排序以及擁擠度距離的計(jì)算，然后分別進(jìn)行雇傭蜂、觀察蜂、偵察蜂的行為，直到迭代次數(shù)結(jié)束或者滿(mǎn)足條件生成最后的最優(yōu)解。

算法步驟如下：

Step1：參數(shù)初始化，根據(jù)MOTSM模型對(duì)種群初始化，并計(jì)算目標(biāo)函數(shù)-feva和felo的值，對(duì)生成的SN組食物源進(jìn)行非支配排序，計(jì)算其擁擠度距離；

Step2：對(duì)于每只雇傭蜂，在其所依附的食物源的鄰域內(nèi)進(jìn)行局部搜索，并將新生成的鄰域解進(jìn)行交叉、變異操作，得到一個(gè)新的食物源，并計(jì)算新食物源的目標(biāo)函數(shù)-feva和felo的值。對(duì)現(xiàn)有的所有食物源進(jìn)行非支配排序，計(jì)算其擁擠度距離，根據(jù)選擇策略選擇前SN組作為新的食物源集合；

Step3：對(duì)于每只觀察蜂，根據(jù)輪盤(pán)賭法選擇食物源，在其所依附的食物源的鄰域內(nèi)進(jìn)行局部搜索，并將新生成的鄰域解進(jìn)行交叉、變異操作，得到一個(gè)新的食物源，并計(jì)算新食物源的目標(biāo)函數(shù)-feva和felo的值。對(duì)現(xiàn)有的所有食物源進(jìn)行非支配排序，計(jì)算其擁擠度距離，根據(jù)選擇策略選擇前SN組作為新的食物源集合；

Step4：當(dāng)食物源進(jìn)行l(wèi)imit次進(jìn)化仍保持原樣時(shí)，雇傭蜂變成偵察蜂，隨機(jī)產(chǎn)生一個(gè)新的食物源位置重新進(jìn)行搜索；

Step5：判斷迭代次數(shù)是否達(dá)到最大循環(huán)次數(shù)MCN，如果沒(méi)有達(dá)到，則跳至Step2，否則退出循環(huán)，并輸出當(dāng)前的食物源位置信息作為最優(yōu)解。

4 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證MOTSM模型和基于IMOABC的任務(wù)調(diào)度算法的可行性，以最大化干擾貢獻(xiàn)值和最小化損失消耗值為目標(biāo)進(jìn)行了兩組實(shí)驗(yàn)。實(shí)驗(yàn)1用來(lái)驗(yàn)證文中設(shè)計(jì)的基于IMOABC的任務(wù)調(diào)度算法是否可以較好地解決協(xié)同電子干擾環(huán)境下的任務(wù)調(diào)度問(wèn)題；實(shí)驗(yàn)2用來(lái)驗(yàn)證基于IMOABC的任務(wù)調(diào)度算法與現(xiàn)有的一些多目標(biāo)優(yōu)化算法相比，能否給出更優(yōu)的解。

實(shí)驗(yàn)1的參數(shù)具體設(shè)置如下：種群規(guī)模為20，迭代限制次數(shù)為50，最大循環(huán)次數(shù)為2 500。圖1為實(shí)驗(yàn)1的仿真結(jié)果圖。

圖1 實(shí)驗(yàn)1的仿真結(jié)果

從圖1可以看出，基于IMOABC的任務(wù)調(diào)度算法較好地求出了協(xié)同電子干擾環(huán)境下任務(wù)調(diào)度問(wèn)題的最優(yōu)解，使得干擾貢獻(xiàn)值最大，損失消耗值最小。

實(shí)驗(yàn)2是與多目標(biāo)優(yōu)化算法EMOABC[10]進(jìn)行對(duì)比。參數(shù)設(shè)置同實(shí)驗(yàn)1。實(shí)驗(yàn)結(jié)果和執(zhí)行時(shí)間對(duì)比分別如圖2和圖3所示。

圖2 不同算法對(duì)比

圖3 時(shí)間對(duì)比

從圖2和圖3中可以看出，基于IMOABC的任務(wù)調(diào)度算法在實(shí)驗(yàn)結(jié)果和執(zhí)行時(shí)間上都優(yōu)于EMOABC算法，能更好地解決協(xié)同電子干擾環(huán)境下的任務(wù)調(diào)度問(wèn)題，進(jìn)行更優(yōu)的任務(wù)調(diào)度。

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

在綜合考慮UCAV在協(xié)同干擾環(huán)境下的干擾貢獻(xiàn)值和損失消耗值的前提下，提出了一種基于多目標(biāo)優(yōu)化的協(xié)同干擾任務(wù)調(diào)度算法。將協(xié)同干擾環(huán)境中的任務(wù)調(diào)度問(wèn)題建模為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，將干擾貢獻(xiàn)值和損失消耗值作為目標(biāo)函數(shù)，建立了基于多目標(biāo)優(yōu)化的任務(wù)調(diào)度模型IMOTSM，并設(shè)計(jì)了基于IMOABC的任務(wù)調(diào)度算法來(lái)求解該模型。實(shí)驗(yàn)結(jié)果表明，IMOABC算法能夠?qū)f(xié)同干擾任務(wù)進(jìn)行有效的調(diào)度與管理，且能在減少損失消耗值的同時(shí)獲得更高的干擾貢獻(xiàn)值。

[1] 翟曉峰.資源調(diào)度機(jī)制的研究及其在電子對(duì)抗中的應(yīng)用[D].南京:南京航空航天大學(xué),2010.

[2] Wu L,Wang H Y,Lu F X,et al.An anytime algorithm based on modified GA for dynamic weapon-target allocation problem[C]//IEEE congress on evolutionary computation.[s.l.]:IEEE,2008:2020-2025.

[3] Chen Jie,Xin Bin,Peng Zhihong,et al.Evolutionary decision-makings for the dynamic weapon-target assignment problem[J].Science in China,2009,52(11):2006-2018.

[4] Naeem H,Masood A.An optimal dynamic threat evaluation and weapon scheduling technique[M].[s.l.]:[s.n.],2010.

[5] Xin B,Chen J,Zhang J,et al.Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics[J].IEEE Transactions on Systems Man & Cybernetics Part C,2010,40(6):649-662.

[6] Shahzad A,Ur-Rehman R.An artificial intelligence based novel approach for real-time allocation of armament to hostile targets[C]//International Bhurban conference on applied sciences and technology.Bhurban:IEEE,2013:141-146.

[7] Zhang Y,Yang R,Zuo J,et al.Improved MOEA/D for dynamic weapon-target assignment problem[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào):英文版,2015(6):121-128.

[8] 王 邑,孫金標(biāo),肖明清,等.基于類(lèi)型2區(qū)間模糊K近鄰分類(lèi)器的動(dòng)態(tài)武器-目標(biāo)分配方法研究[J].系統(tǒng)工程與電子技術(shù),2016,38(6):1314-1319.

[9] Xiang Y,Zhou Y,Liu H.An elitism based multi-objective artificial bee colony algorithm[J].European Journal of Operational Research,2015,245(1):168-193.

[10] Huo Y,Zhuang Y,Gu J,et al.Elite-guided multi-objective artificial bee colony algorithm[J].Applied Soft Computing,2015,32(C):199-210.

[11] 趙 輝,李牧東,韓 統(tǒng),等.基于多目標(biāo)MQABC算法的無(wú)人機(jī)協(xié)同任務(wù)分配[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2016,44(3):121-126.

[12] 薛 羽,莊 毅,張友益,等.基于啟發(fā)式自適應(yīng)離散差分進(jìn)化算法的多UCAV協(xié)同干擾空戰(zhàn)決策[J].航空學(xué)報(bào),2013,34(2):343-351.

[13] Huo Y,Yi Z,Gu J,et al.Discrete gbest-guided artificial bee colony algorithm for cloud service composition[J].Applied Intelligence,2015,42(4):661-678.

[14] Ardagna D,Pernici B.Adaptive service composition in flexible processes[J].IEEE Transactions on Software Engineering,2007,33(6):369-384.

[15] Saaty T L.How to make a decision: the analytic hierarchy process[J].European Journal of Operational Research,1990,48(1):9-26.

[16] Xu J,Fortes J A B.Multi-objective virtual machine placement in virtualized data center environments[C]//IEEE/ACM international conference on green computing and communications & 2010 IEEE/ACM international conference on cyber,physical and social computing.[s.l.]:IEEE,2010:179-188.

ATaskSchedulingMethodBasedonIMOABCinCollaborationInterferenceEnvironment

LOU Yan-qiu1，ZHUANG Yi1，GU Jing-jing1，HUO Ying2

(1.School of Computer Science and Technology,Nanjing University of Aeronautics &Astronautics,Nanjing 210000,China；2.School of Computer Engineering,Nanjing Institute of Technology,Nanjing 210000,China)

Not only the maximization of interference tasks but the minimization of energy loss itself is needed to be considered in the collaborative interference environment.In this complex requirements,it is necessary to convert task scheduling into multi-objective optimization in the collaborative interference environment.Aiming at the problem of how to maximize the interference tasks and minimize the energy loss of Unmanned Combat Aerial Vehicle (UCAV) simultaneously,the Multi-Objective based Task Scheduling Model of collaborative interference (MOTSM) is established which takes contribution value and loss consumption as the objective functions.A task scheduling algorithm based on Improved Multi-Objective Artificial Bee Colony (IMOABC) is developed to solve the proposed model.First,it carries out the binary coding of chromosomes.Then an initial population that satisfies the MOTSM constraints is generated randomly,and performed in rapid non-dominated sorting and calculation of crowding distances.Through the cooperation of the three bees including the employed bees,onlookers and the scouts,the search for the optimal solution is finished.Finally,the effectiveness of the proposed model and algorithm is verified by simulation experiments.

collaboration interference;multi-objective optimization;task scheduling;artificial bee colony

2016-11-21

2017-03-21 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

國(guó)家自然科學(xué)基金面上項(xiàng)目(61572253);國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61202351);國(guó)家博士后基金項(xiàng)目(一等)(2011M500124)

婁艷秋(1991-),女,碩士生,研究方向?yàn)橹悄軆?yōu)化算法；莊 毅,教授,研究方向?yàn)榫W(wǎng)絡(luò)與分布式計(jì)算、信息安全、可信計(jì)算。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1550.032.html

TP301

A

1673-629X(2017)11-0046-06

10.3969/j.issn.1673-629X.2017.11.010