基于改進(jìn)DE 算法的目標(biāo)分配問(wèn)題研究*

李 靜，魯濟(jì)帥，翟凱玥

（西安工業(yè)大學(xué)電子信息工程學(xué)院，西安 710021）

0 引言

在巡飛彈協(xié)同攻擊決策中，目標(biāo)分配是協(xié)同戰(zhàn)役指揮決策中最重要的問(wèn)題之一，但其本質(zhì)仍屬于武器分配（weapon target assignment，WTA）問(wèn)題，WTA是指根據(jù)目標(biāo)威脅、武器和目標(biāo)的特性等相關(guān)約束條件，結(jié)合已獲得的戰(zhàn)場(chǎng)態(tài)勢(shì)信息，對(duì)武器和目標(biāo)進(jìn)行有效合理分配，從而達(dá)到最優(yōu)攻擊效果［1］。

WTA 問(wèn)題是NP（non-deterministic polynomial）問(wèn)題，問(wèn)題求解的難度隨目標(biāo)數(shù)量的增大呈指數(shù)型增加，而傳統(tǒng)的啟發(fā)式算法，目標(biāo)規(guī)劃方法等，難以適應(yīng)對(duì)大規(guī)模WTA 問(wèn)題的求解［2-3］。相比之下，智能算法如PSO 算法［4］、SA 算法［5］、GA 算法［6］和DE算法［7］等，憑借其自身收斂速度較快、尋優(yōu)性能較強(qiáng)等優(yōu)點(diǎn)被廣泛用于求解此類問(wèn)題。雖然上述智能算法最終都能得到較為滿意的結(jié)果，但在求解大規(guī)模WTA 問(wèn)題中，收斂性和尋優(yōu)能力仍有改進(jìn)的空間。

DE 算法是基于群體性差異的智能算法，因其魯棒性好、優(yōu)化能力強(qiáng)等優(yōu)點(diǎn)被廣泛應(yīng)用［8］。近幾年來(lái)，很多研究者借助DE 算法來(lái)解決WTA 問(wèn)題，歐嶠等提出一種改進(jìn)的離散DE 算法，改進(jìn)了自適應(yīng)差分變異、隨機(jī)均勻交叉等操作，提高了求解WTA 問(wèn)題的時(shí)效性［9］；MENG 等提出了一種基于歷史種群的突變策略且具有參數(shù)自適應(yīng)機(jī)制的DE 算法［10］；徐英杰等提出一種基于小波基函數(shù)的差分進(jìn)化改進(jìn)算法，通過(guò)小波基函數(shù)對(duì)DE 的縮放因子進(jìn)行改進(jìn)，提高了算法性能［11］。

本文提出了一種改進(jìn)的DE 算法，通過(guò)引導(dǎo)“探索性”種群協(xié)作進(jìn)化、自適應(yīng)選擇變異率、變異策略及交叉率來(lái)進(jìn)行改進(jìn)，然后將改進(jìn)的DE 算法應(yīng)用到目標(biāo)分配模型中進(jìn)行最優(yōu)求解，進(jìn)而提高協(xié)同攻擊作戰(zhàn)決策中目標(biāo)分配問(wèn)題的效率。

1 WTA 問(wèn)題的描述

在某次協(xié)同攻擊作戰(zhàn)中，有m 枚巡飛彈和n 個(gè)待攻擊目標(biāo)，對(duì)我方巡飛彈和待攻擊目標(biāo)進(jìn)行分配。假設(shè)每枚巡飛彈攜帶多個(gè)武器，可對(duì)多個(gè)地面目標(biāo)進(jìn)行連續(xù)打擊；假設(shè)在巡飛彈集群有效的作用時(shí)間和作用區(qū)域內(nèi)，某時(shí)刻這m 枚巡飛彈同時(shí)到達(dá)攻擊區(qū)域，且某枚巡飛彈在這一時(shí)刻可分配多個(gè)武器攻擊同一目標(biāo)。則巡飛彈協(xié)同攻擊目標(biāo)分配決策矩陣為：

式中，i=1，2，…，m，j=1，2，3，…，n，xij∈（0，mi）（mi為第i 枚巡飛彈的可用武器總數(shù)量）；xij=d 為第i 枚巡飛彈分配給第j 個(gè)目標(biāo)d 個(gè)武器。

假設(shè)同一枚巡飛彈上攜帶的武器對(duì)同一目標(biāo)的毀傷概率相同，且分配前已獲得每枚巡飛彈的武器對(duì)攻擊目標(biāo)的毀傷概率，對(duì)應(yīng)的毀傷矩陣如下：

式中，i=1，2，…，m，j=1，2，3，…，n，pij＞0，pij為第i 枚巡飛彈的武器攻擊第j 個(gè)目標(biāo)的毀傷概率。

第j 個(gè)目標(biāo)總的毀傷概率可以表示為：

那么毀傷所有目標(biāo)的數(shù)學(xué)期望Z 為：

結(jié)合戰(zhàn)場(chǎng)中敵方目標(biāo)的綜合價(jià)值，則可建立目標(biāo)毀傷綜合價(jià)值最大的數(shù)學(xué)模型f（x）為：

其中，vj為第j 個(gè)敵方目標(biāo)的綜合價(jià)值，目標(biāo)綜合價(jià)值vj大小主要取決于目標(biāo)的綜合威脅程度Thi、目標(biāo)造價(jià)Mei和目標(biāo)任務(wù)價(jià)值A(chǔ)ti三者的綜合加權(quán)，具體計(jì)算如下：

約束條件1：

該式表示對(duì)xij進(jìn)行整數(shù)約束，其值必須為大于等于0 的整數(shù)。

約束條件2：

式中，mi表示第i 枚巡飛彈可用武器數(shù)量。上式表明某時(shí)刻某枚巡飛彈分配給目標(biāo)的武器數(shù)量不超過(guò)該枚巡飛彈攜帶武器的總數(shù)。

約束條件3：

式中，sj表示某時(shí)刻目標(biāo)j 受到攻擊的最大閾值。該式表明分配給每個(gè)目標(biāo)至少一個(gè)武器，且對(duì)綜合價(jià)值較大的目標(biāo)可分配多個(gè)武器同時(shí)攻擊，但不能超過(guò)最大閾值，以免造成彈藥浪費(fèi)，一般取sj=5。

2 DE 算法基本原理

2.1 種群初始化

種群初始化方法，一般如式（10）所示：

2.2 種群變異

父代個(gè)體xiG進(jìn)行變異操作，產(chǎn)生變異體viG；以下的7 種變異策略較為常用：

DE/rand/1：

DE/rand/2：

DE/current to rand/2：

DE/best/1：

DE/best/2：

DE/pbest/1：

DE/current to pbest/2：

2.3 種群交叉

變異體viG與父代個(gè)體xiG進(jìn)行交叉，產(chǎn)生試驗(yàn)體u。試驗(yàn)體由式（18）計(jì)算得到：

式中，CR 為交叉率，xiG為第G 代種群的個(gè)體（或稱為目標(biāo)體）；uiG+1為第G+1 代的試驗(yàn)個(gè)體。條件j=jr是為了保證試驗(yàn)中必有部分基因來(lái)源于變異體，jr為［1，D］之間的隨機(jī)整數(shù)。

2.4 種群選擇

采用“貪婪策略”，試驗(yàn)體uiG與父代個(gè)體xiG執(zhí)行選擇操作，產(chǎn)生下一代個(gè)體u。如式（19）所示：

式中，f（·）為適應(yīng)度函數(shù)。

3 DE 算法的改進(jìn)

3.1 編碼

針對(duì)復(fù)雜的目標(biāo)分配問(wèn)題，使用DE 算法求解時(shí)，首先需對(duì)待解決問(wèn)題的性質(zhì)進(jìn)行全方面的考慮，其次對(duì)編碼方案進(jìn)行合適化的選擇，其所選方案既要滿足所建數(shù)學(xué)模型的約束條件，還要能對(duì)問(wèn)題的解進(jìn)行表示［12］。

基于上述考慮，本文選用十進(jìn)制整數(shù)編碼方案，每個(gè)個(gè)體都代表一個(gè)可行的解，其具體的編碼方式，如圖1 所示。

圖1 改進(jìn)的DE 算法求解目標(biāo)分配問(wèn)題的編碼Fig.1 Encoding of improved DE algorithm for the solution of target allocation problem

編碼塊由各枚巡飛彈所攜帶武器預(yù)分配的目標(biāo)編號(hào)組成，編碼塊按各枚巡飛彈順序排列構(gòu)成一個(gè)種群個(gè)體的編碼，每種排列代表了一種分配方案。各枚巡飛彈所攜帶的武器總數(shù)決定了個(gè)體編碼的長(zhǎng)度。例如，某次巡飛彈協(xié)同攻擊作戰(zhàn)，第i 枚巡飛彈的所攜帶武器數(shù)為ki，則與該枚巡飛彈對(duì)應(yīng)的編碼塊長(zhǎng)度為ki，編碼個(gè)體的長(zhǎng)度（即編碼維度）為D=ki；編碼塊里的數(shù)字代表該編碼塊所對(duì)應(yīng)巡飛彈的武器預(yù)分配的目標(biāo)編號(hào)，且數(shù)字須為（1-n）內(nèi)的整數(shù)；如個(gè)體的k1段數(shù)字為3，4，6，2，表示第1枚巡飛彈有4 個(gè)可用武器，第1，2，3，4 個(gè)武器分配給3，4，6，2 號(hào)目標(biāo)。

3.2 多種群協(xié)作進(jìn)化

多種群協(xié)作進(jìn)化是指多個(gè)種群?jiǎn)为?dú)進(jìn)行交叉變異操作和定期共享信息，從而實(shí)現(xiàn)協(xié)作進(jìn)化，提高算法的優(yōu)化能力［13］。具體步驟如下：1）計(jì)算初始種群適應(yīng)度值；2）排列初始種群的個(gè)體（按適應(yīng)值從大到小順序）；3）將排名在前Q%的個(gè)體存入“特定種群”中（為了方便，這里稱“特定種群”為精英種群）；4）將（1-Q）%的種群重新劃分為3 個(gè)“同等規(guī)模的種群”（為了方便，這里將“同等規(guī)模的種群”命名為探索種群）；5）每迭代1 次，探索種群和精英種群更新一次；6）當(dāng)?shù)螖?shù)超過(guò)設(shè)定總迭代次數(shù)的1/2 時(shí)，精英種群的優(yōu)秀個(gè)體參與每個(gè)探索種群的變異。

多種群協(xié)作進(jìn)化中，精英種群的任務(wù)是保留存在歷史進(jìn)化過(guò)程中探索種群的優(yōu)秀個(gè)體，適時(shí)引導(dǎo)探索種群向最優(yōu)搜索方向發(fā)展，探索種群的任務(wù)是探索更大的解空間，從而使整個(gè)種群朝著全局最優(yōu)的方向發(fā)展。在進(jìn)化的早期階段，為了保持種群的多樣性，探索種群需要不斷地進(jìn)行積極的變異操作，而精英種群僅對(duì)其內(nèi)部的優(yōu)秀個(gè)體進(jìn)行更新，不干涉探索種群，其目的是避免提前“干預(yù)”導(dǎo)致局部?jī)?yōu)化和收斂。在進(jìn)化的后期，以精英種群的優(yōu)秀個(gè)體為基本變量，引導(dǎo)種群加速搜索全局最優(yōu)解，進(jìn)行種群變異。多次迭代進(jìn)化之后，精英群體中的優(yōu)秀個(gè)體逐漸逼近全局最優(yōu)，從而可通過(guò)利用精英群體中的優(yōu)秀個(gè)體引導(dǎo)算法向全局最優(yōu)方向發(fā)展。如下頁(yè)圖2 所示。

圖2 種群協(xié)作進(jìn)化Fig.2 Population collaborative evolution

更新種群的思路為：探索種群每次迭代后，取出前20%的個(gè)體組成一個(gè)集合（該集合為本次更新產(chǎn)生的精英種群的最佳候選個(gè)體）；每次迭代進(jìn)化后，將集合中個(gè)體的適應(yīng)值與原精英群體中的個(gè)體進(jìn)行比較和替換，如此直至算法迭代完成，最優(yōu)解即為最后精英種群中適應(yīng)度值排名第1 的個(gè)體。

本文改進(jìn)的DE 算法中，精英種群規(guī)模為10%NP，探索種群自適應(yīng)選擇變異策略、變異率和交叉率。

值得注意的是，精英種群參與進(jìn)化過(guò)程（即引導(dǎo)探索種群的交叉變異），但自身不進(jìn)化，只更新。

3.3 變異策略的多種選擇

在DE 算法中，變異策略不同，起到的效果便會(huì)有差異。變異策略的適應(yīng)性選擇是指在種群每次進(jìn)化中，其內(nèi)部的個(gè)體根據(jù)能生成優(yōu)秀變異體的歷史統(tǒng)計(jì)信息，對(duì)最適用于本代進(jìn)化的變異策略進(jìn)行選擇［14］。本文改進(jìn)的DE 算法，探索種群將對(duì)DE/rand/1、DE/rand/2、DE/current to rand/2 和DE/current to pbest/2 這4 種變異策略進(jìn)行適應(yīng)性選擇。變異策略自適應(yīng)選擇和更新步驟，如圖3 所示。

圖3 變異策略選擇與更新Fig.3 Mutation strategy selection and update

其中，步驟1 中選擇概率記為P1、P2、P3和P4，步驟4 中選擇次數(shù)記為num1、num2、num3 和num4，步驟5 中選擇次數(shù)記為num_best1、num_best2、num_best3和num_best4，其中，步驟1 變異策略的更新方式和步驟6 中選擇概率需歸一化處理，如式（20）、式（21）所示：

其中，k∈{1，2，3，4}。

在算法中后期階段（即G＞1/2Gmax時(shí)），這一階段的DE/current to pbest/2 的計(jì)算方法需進(jìn)行變更，計(jì)算方法如下：

3.4 自適應(yīng)變異率F 和交叉率CR

DE 算法進(jìn)化過(guò)程中，變異率F 和交叉率CR 的取值常常很難把握［15］，F(xiàn) 取值偏大或者偏小，都會(huì)對(duì)算法產(chǎn)生不良影響［16］。為了防止上述情況的出現(xiàn)，本文將變異率F 和交叉率CR 調(diào)整為自適應(yīng)變化。

3.4.1 自適應(yīng)調(diào)整變異率F

設(shè)計(jì)關(guān)于迭代次數(shù)的非線性變化函數(shù)來(lái)調(diào)整F，設(shè)計(jì)公式如下式：

式中，G 為迭代次數(shù)；Gmax為最大迭代次數(shù)；F0為變異率初值。

3.4.2 自適應(yīng)調(diào)整交叉率CR

設(shè)計(jì)關(guān)于迭代次數(shù)的非線性變化函數(shù)來(lái)調(diào)整交叉率CR，設(shè)計(jì)公式如下式：

式中，CRmin、CRmax分別為最小和最大交叉率。

3.5 算法的流程

1）算法的基本實(shí)現(xiàn)流程，如下頁(yè)圖4 所示。

圖4 改進(jìn)DE 算法流程圖Fig.4 Flow chart of improved DE algorithm

2）算法步驟。

Step 1 種群初始化，包括種群規(guī)模NP、最大迭代次數(shù)Gmax，變異率初值F0，最小和最大交叉率CRmax、CRmin等。

Step 2 探索種群獨(dú)自進(jìn)行自適應(yīng)變異率F 如式（23）所示的選擇和變異操作，并進(jìn)行基因檢測(cè)和處理。

Step 3 探索性種群獨(dú)自進(jìn)行自適應(yīng)交叉率CR的選擇如式（24）所示、交叉操作如式（18）所示和選擇操作如式（19）所示。

Step 4 更新變異策略的選擇概率如式（20）所示。

Step 5 更新精英種群。

Step 6 判斷G 是否等于Gmax。若是，則取出精英種群適應(yīng)度值最大的個(gè)體即為最優(yōu)解；若否，返回Step 2，繼續(xù)迭代。

4 仿真實(shí)驗(yàn)分析

假設(shè)我方發(fā)射4 枚巡飛彈對(duì)敵方陣地的防空導(dǎo)彈車（M1）、坦克（M2）、步兵戰(zhàn)車（M3）、指揮車（M4）、雷達(dá)車（M5）和裝甲運(yùn)輸車（M6）這6 種目標(biāo)進(jìn)行協(xié)同攻擊，4 枚巡飛彈可記為W=（W1，W2，W3，W4），其對(duì)攜帶的武器數(shù)量為［4，4，4，3］，目標(biāo)綜合威脅程度為Thi=（0.43，0.25，0.17，0.04，0.05，0.06），權(quán)重為0.30，目標(biāo)造價(jià)為Mei=（0.3，0.25，010，0.10，0.15，0.10），權(quán)重為0.25；目標(biāo)任務(wù)價(jià)值為Ati=（0.25，0.10，0.10，0.30，0.15，0.10），權(quán)重為0.45，則目標(biāo)綜合價(jià)值Cvi為（0.31，0.18，0.12，0.17，0.12，0.09），目標(biāo)毀傷概率和目標(biāo)綜合價(jià)值如表1 所示（其中目標(biāo)綜合威脅程度、目標(biāo)造價(jià)、目標(biāo)任務(wù)價(jià)值及其權(quán)重、武器的價(jià)值和目標(biāo)毀傷概率由C3I 專家提供）。

表1 巡飛彈上的武器對(duì)目標(biāo)的毀傷概率Table 1 Probability of damage to targets by weapons on loitering munition

算法仿真實(shí)驗(yàn)在Matlab 9.1，AMD R5—4600H CPU 3.0 GHz，16 GB 內(nèi)存的PC 上運(yùn)行。設(shè)置實(shí)驗(yàn)參數(shù)：種群規(guī)模NP=100，最大迭代次數(shù)Gmax=1 000，變異率初值F0=0.65，交叉率：CRmin=0.60，CRmax=0.9。

通過(guò)仿真可得到最優(yōu)個(gè)體的編碼：［（11 2 2）、（1 1 2 6）、（34 4 4）、（35 5）］，最優(yōu)適應(yīng)度值即目標(biāo)分配最優(yōu)函數(shù)值為f（x）=0.994 0，對(duì)應(yīng)的目標(biāo)分配決策矩陣為：

適應(yīng)度值和種群適應(yīng)度均值變化，如圖5 所示。

圖5 改進(jìn)DE 算法的適應(yīng)度值和適應(yīng)度均值變化曲線Fig.5 The fitness value and fitness mean change curve of the improved DE algorithm

4.1 改進(jìn)DE 算法與標(biāo)準(zhǔn)DE 算法的比較

標(biāo)準(zhǔn)DE 算法與本文改進(jìn)的算法都采用同樣的變異、交叉和選擇機(jī)制，不同的是標(biāo)準(zhǔn)DE 算法中的交叉、變異率是不變值，且其采用單一的變異策略，而改進(jìn)的DE 算法采用變異策略、變異率和交叉率是自適應(yīng)的。經(jīng)過(guò)仿真得到改進(jìn)的DE 算法與標(biāo)準(zhǔn)的DE 算法采用DE/rand/1、DE/rand/2、DE/current to rand/2 和DE/current to pbest/2 模式對(duì)比的適應(yīng)度值變化曲線，如下頁(yè)圖6 所示。

圖6 改進(jìn)DE 算法與各模式的適應(yīng)度值曲線Fig.6 Improved DE algorithm and fitness value curves for each mode

從圖5 和圖6 可以看出，本文改進(jìn)的DE 算法與分別采用4 種變異策略的標(biāo)準(zhǔn)DE 算法相比，具有更好的適應(yīng)度值（即最優(yōu)解）和收斂性，即該算法在迭代278 次時(shí)，就求解出了最優(yōu)解且高達(dá)0.994 0。

4.2 改進(jìn)DE 算法與不同算法的比較

分別采用SA-PSO 算法［5］、AI 算法［17］和改進(jìn)的DE 算法進(jìn)行求解，進(jìn)行600 次迭代進(jìn)化后，得到了3 種算法的適應(yīng)度變化對(duì)比曲線及算法對(duì)比，如圖7 所示和表2 所示。

表2 3 種算法最優(yōu)解和迭代次數(shù)對(duì)比Table 2 Comparison of optimal solutions and iteration times of three kinds of algorithms

圖7 3 種算法的對(duì)比曲線Fig.7 Comparison curves of three kinds of algorithms

由圖7 和表2 可知，隨著不斷的迭代進(jìn)化，這3種算法的適應(yīng)度值不斷增加，且最后趨于穩(wěn)定；AI算法能夠在較短時(shí)間內(nèi)找到最優(yōu)解，但找到的最優(yōu)解較差；與AI 算法相比，改進(jìn)的PSO 算法找到的最優(yōu)解較好，但需要多次迭代進(jìn)化，其收斂性能較差；本文改進(jìn)的DE 算法相比改進(jìn)的PSO 算法和AI 算法而言，能在較少的迭代次數(shù)下找到更好的最優(yōu)解，說(shuō)明本文改進(jìn)的DE 算法具有很好的收斂性和全局尋優(yōu)性。

5 結(jié)論

為了使協(xié)同作戰(zhàn)指揮決策系統(tǒng)能更快、更合理進(jìn)行目標(biāo)分配，提出一種改進(jìn)的DE 算法，采用精英種群引導(dǎo)“探索性”種群協(xié)作進(jìn)化，以提高算法全局搜索和開發(fā)性能；采用變異策略自適應(yīng)選擇，以提高算法收斂性和全局尋優(yōu)能力；采用自適應(yīng)調(diào)整變異率F 和交叉率CR，以滿足進(jìn)化過(guò)程中種群對(duì)控制參數(shù)的要求。本文改進(jìn)的DE 算法，提高了局部尋優(yōu)精度、收斂性以及全局尋優(yōu)性，該算法可用于解決大規(guī)模的目標(biāo)分配問(wèn)題，并且能快速、有效地求解出符合多巡飛彈-多目標(biāo)分配模型要求的最優(yōu)解。