張榮，王彬

（1.武漢鐵路職業(yè)技術(shù)學(xué)院，湖北武漢， 430200；2.中鐵第四勘察設(shè)計(jì)院集團(tuán)有限公司，湖北武漢， 430063）

0 引言

無(wú)人機(jī)在過(guò)去十年的應(yīng)用越來(lái)越廣泛，其技術(shù)也更加成熟。無(wú)人機(jī)在智能化戰(zhàn)場(chǎng)上的出色發(fā)揮，使得無(wú)人機(jī)多任務(wù)協(xié)同的研究引起了廣泛的關(guān)注。雖然多無(wú)人機(jī)協(xié)同多目標(biāo)分配應(yīng)用廣泛，但對(duì)單無(wú)人機(jī)多任務(wù)規(guī)劃的研究也尤為重要，如RQ-4、MQ-1和MQ-9等無(wú)人機(jī)的生產(chǎn)成本和運(yùn)行維護(hù)成本高，不可能實(shí)現(xiàn)大規(guī)模協(xié)作[1]。單無(wú)人機(jī)多任務(wù)規(guī)劃與多無(wú)人機(jī)協(xié)同多目標(biāo)分配一樣，都是NP難題，需要獲得全局最優(yōu)解。為了解決計(jì)算復(fù)雜度問(wèn)題，數(shù)學(xué)算法、遺傳算法(GA)[2～3]、粒子群優(yōu)化算法(PSO)[4～6]、蟻群優(yōu)化算法（ACO)[7]等諸多智能算法被提出并改進(jìn)。近年來(lái)，差分進(jìn)化（DE）算法[8～9]得到了廣泛的重視和應(yīng)用，尤其是在多目標(biāo)分配和路徑規(guī)劃方面。

本文針對(duì)在復(fù)雜三維地形環(huán)境和多約束條件下，如何使無(wú)人機(jī)在任務(wù)中合理分配目標(biāo)，提出了一種新的自適應(yīng)差分進(jìn)化算法，以解決三維環(huán)境下單無(wú)人機(jī)執(zhí)行多任務(wù)的困難。在解決方案中，使用三維航次成本表達(dá)無(wú)人機(jī)和目標(biāo)之間的分配關(guān)系，將動(dòng)態(tài)自適應(yīng)變異和交叉差分進(jìn)化策略進(jìn)行組合來(lái)調(diào)整在搜索算法中的平衡檢測(cè)和開(kāi)發(fā)從而避免陷入局部最優(yōu)；同時(shí)提高了無(wú)人機(jī)任務(wù)執(zhí)行的精度，適用于求解無(wú)人機(jī)大規(guī)模目標(biāo)任務(wù)分配。首先，在三維環(huán)境下建立單個(gè)無(wú)人機(jī)多任務(wù)規(guī)劃模型及其約束條件；其次，提出了一種基于種群迭代次數(shù)和個(gè)體適應(yīng)度值的自適應(yīng)進(jìn)化算法來(lái)調(diào)整變異因子和交叉因子，以解決當(dāng)前演化過(guò)程中存在的問(wèn)題；第三，通過(guò)不同規(guī)模的仿真實(shí)驗(yàn)，證明了IADE算法的合理性；最后，通過(guò)與其他算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了IADE算法的優(yōu)越性。

1 無(wú)人機(jī)多目標(biāo)分配模型

■1.1 目標(biāo)函數(shù)

無(wú)人機(jī)多任務(wù)規(guī)劃是一個(gè)約束優(yōu)化問(wèn)題。通常，這類問(wèn)題同時(shí)包含了等式約束和不等式約束[10]。根據(jù)優(yōu)化理論，COP的數(shù)學(xué)描述如下：

其中，x∈D表示優(yōu)化問(wèn)題的決策變量，f(x)為目標(biāo)函數(shù)，表示待優(yōu)化目標(biāo)，hi(x)和g j(x)分別表示等式約束和不等式約束。

根據(jù)以上描述，結(jié)合無(wú)人機(jī)多任務(wù)分配的具體問(wèn)題，可以假設(shè)單架無(wú)人機(jī)在任務(wù)空間的不同區(qū)域?qū)Χ嗄繕?biāo)攻擊或執(zhí)行多任務(wù)。解決該問(wèn)題的關(guān)鍵是獲取攻擊和執(zhí)行序列，使無(wú)人機(jī)具有滿足所有約束條件的最短飛行距離和最短飛行時(shí)間。

無(wú)人機(jī)多任務(wù)模型的目標(biāo)函數(shù)描述如下：

式中，dj為無(wú)人機(jī)到目標(biāo)j的飛行距離，wj為j的目標(biāo)權(quán)重，其取值范圍為0～1，值越大優(yōu)先級(jí)越高，tj為無(wú)人機(jī)到目標(biāo)的飛行時(shí)間，ck為違反約束，α和β表示用于平衡目標(biāo)函數(shù)多項(xiàng)式的比例因子，保持航次成本、飛行時(shí)間和違反約束在同一數(shù)量級(jí)，Dj表示決策變量，決定無(wú)人機(jī)的執(zhí)行目標(biāo)。圖1顯示函數(shù)的3D環(huán)境和應(yīng)用場(chǎng)景。

圖1 三維環(huán)境的應(yīng)用場(chǎng)景

■1.2 約束關(guān)系

（1）最大飛行距離約束

最大飛行距離約束反映無(wú)人機(jī)的性能和油耗指標(biāo)，即無(wú)人機(jī)完成所有任務(wù)過(guò)程中的最大飛行距離限制。這個(gè)約束的關(guān)鍵是確保無(wú)人機(jī)能夠完成所有的目標(biāo)。約束函數(shù)表示為：

其中di為估計(jì)航程成本，D為無(wú)人機(jī)最大航程限制。C1viol表示違反約束，無(wú)人機(jī)執(zhí)行第j個(gè)任務(wù)時(shí)超過(guò)最大飛行距離將受到限制。

（2）空速約束

式中，V(j)max、V(j)min分別表示無(wú)人機(jī)的最大航速和最小航速；C2viol限制無(wú)人機(jī)飛行的最小和最大速度范圍。

（3）最大飛行時(shí)間約束

最大飛行時(shí)間約束表示無(wú)人機(jī)完成所有任務(wù)所需的總時(shí)間。該約束的關(guān)鍵是確保無(wú)人機(jī)在規(guī)定的飛行時(shí)間內(nèi)完成所有任務(wù)。

其中C3viol表示如果無(wú)人機(jī)超過(guò)最大飛行時(shí)間限制。

（4）目標(biāo)點(diǎn)之間的時(shí)間約束

時(shí)間約束反映了目標(biāo)點(diǎn)之間的執(zhí)行順序。重要目標(biāo)點(diǎn)的優(yōu)先級(jí)高必須優(yōu)先執(zhí)行，其他目標(biāo)點(diǎn)根據(jù)約束按順序執(zhí)行。

其中：Tj＜T j+τ表示目標(biāo)點(diǎn)j必須晚于目標(biāo)點(diǎn)j+τ執(zhí)行，τ為正整數(shù)，C4viol限制目標(biāo)點(diǎn)j后執(zhí)行。

（5）最大任務(wù)數(shù)的約束

無(wú)人機(jī)執(zhí)行的最大任務(wù)數(shù)由以下約束表示：

其中：Mmax表示無(wú)人機(jī)執(zhí)行的任務(wù)數(shù)不超過(guò)設(shè)定執(zhí)行的任務(wù)數(shù)，C5viol表示無(wú)人機(jī)任務(wù)約束。

2 改進(jìn)的自適應(yīng)差分進(jìn)化

■2.1 標(biāo)準(zhǔn)差分進(jìn)化算法

DE算法首先對(duì)種群進(jìn)行初始化，然后進(jìn)行變異、交叉和選擇操作，不斷迭代更新種群大小[11]。DE算法的步驟如下：

（1）種群初始化

DE算法在解的搜索范圍的維度D內(nèi)隨機(jī)生成NP個(gè)體：

DE算法經(jīng)常使用一些固定的變異策略來(lái)生成變異個(gè)體vi，以保證種群的多樣性。DE算法中的確定性變異策略如下：

其中xbest表示最佳個(gè)體，F(xiàn)為比例因子，r1 r2 r3 r4 r5表示在[1,NP]上的不同隨機(jī)整數(shù)，且不等于i。

（3）交叉操作

交叉運(yùn)算的基本原理是將變異向量與目標(biāo)向量進(jìn)行參數(shù)混合，生成實(shí)驗(yàn)向量。具體表達(dá)式如下：

式中CR為交叉率；jrand表示在[1,D]上的一個(gè)隨機(jī)整數(shù)。（4）選擇操作

DE算法的主要思想是根據(jù)貪婪法則選擇下一代的個(gè)體，即保留優(yōu)秀的個(gè)體，剔除劣等的個(gè)體。對(duì)于優(yōu)化問(wèn)題，優(yōu)秀個(gè)體的適應(yīng)度值較小。

■2.2 JADE算法

DE/current-to-pbest作為一種新的變異策略，構(gòu)成了JADE算法的基礎(chǔ)，JADE是一種具有可選存檔的自適應(yīng)DE算法[12]。

其中Fi為變異因子，與xi,g相關(guān)。的選擇方法是在算法的每次迭代中，從100p%的種群中隨機(jī)選擇一個(gè)個(gè)體作為當(dāng)前最優(yōu)個(gè)體，并將其應(yīng)用到變異策略中。

在JADE中，F(xiàn)表示為：

其中randc為柯西分布，若Fi＞1，則Fi等于1，或者重新生成Fi；若Fi≤0，初始化 為0.5，更新如下：

式中，c為區(qū)間(0,1)內(nèi)的值，SF為所有優(yōu)秀變異因子的集合。

在JADE中，CR是獨(dú)立于正態(tài)分布產(chǎn)生的，正態(tài)分布的均值為uCR，標(biāo)準(zhǔn)差為0.1。

其中CiR屬于[0,1]，初始化uCR為0.5，更新如下：

其中，meanA為平均值，S CR為所有優(yōu)秀因子CRi的集合。

■2.3 PaDE算法

在整個(gè)進(jìn)化過(guò)程中，PaDE算法保持k個(gè)組，并所有個(gè)體在其中進(jìn)化分類。然后，uF可以根據(jù)下式更新：

并根據(jù)以下公式更新選擇概率：

為了適應(yīng)種群規(guī)模的動(dòng)態(tài)變化，本文提出了一種減小拋物線種群規(guī)模的新方案。

同時(shí)提出一種新的帶時(shí)間戳的變異策略，可以在第一階段初始化所有的劣等個(gè)體，然后插入到外部存檔中。

■2.4 RAM-JAPDE算法

RAM-JAPDE算法是將基于秩的變異策略自適應(yīng)(RAM)和基于DE參數(shù)的聯(lián)合自適應(yīng)(JAPDE)相結(jié)合而產(chǎn)生的一種新算法[13]。RAM-JAPDE算法的主要流程及計(jì)算公式如下：

■2.5 改進(jìn)機(jī)制

在眾多的自適應(yīng)DE算法中，變異和交叉操作是DE算法中的兩個(gè)重要步驟[13]。改進(jìn)主要針對(duì)F和CR，它們的值對(duì)于DE算法能否避免陷入局部最優(yōu)，找到全局最優(yōu)解具有重要意義。

F取值在進(jìn)化的前期階段應(yīng)該盡可能大，并快速接近全局最優(yōu)解，避免陷入局部最優(yōu)。后期種群會(huì)聚集在全局最優(yōu)解周圍，因此F值應(yīng)盡可能小，以提高搜索精度，找到全局最優(yōu)解。CR決定了可以進(jìn)入選擇操作的變異個(gè)體的數(shù)量。CR值越大，可繼承的信息就越少，種群更新則主要依賴于變異過(guò)程，進(jìn)而豐富種群的多樣性，提高了全局搜索能力。CR值較小則會(huì)縮小優(yōu)化范圍，但會(huì)提高收斂速度，有利于局部?jī)?yōu)化。

由于許多DE變量的F和CR值是隨機(jī)生成的，不受迭代次數(shù)和個(gè)體適應(yīng)度值的影響，其收斂性不如預(yù)期的好。針對(duì)這些問(wèn)題，本文提出了一種改進(jìn)的自適應(yīng)DE算法(IADE)，同時(shí)為了使變異因子適應(yīng)進(jìn)化程度，提出了一種新的動(dòng)態(tài)自適應(yīng)變異因子。具體表達(dá)式如下：

式中，g表示第g代,G為進(jìn)化的總代，F(xiàn)max和Fmin分別為變異因子的最大值和最小值。

交叉因子CR控制單個(gè)參數(shù)各維度參與交叉步驟的程度，使其隨個(gè)體適應(yīng)度值變化，保證算法收斂的穩(wěn)定性，呈現(xiàn)動(dòng)態(tài)自適應(yīng)交叉因子。具體表達(dá)式如下：

其中，CRu和CR1分別表示CR的最小和最大限制，fi為個(gè)體適應(yīng)度值，fmax為最大值，fbest為最佳值。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證IADE算法應(yīng)用于無(wú)人機(jī)多任務(wù)規(guī)劃的效果，本文進(jìn)行了仿真實(shí)驗(yàn)，并與其他算法進(jìn)行了比較。

■3.1 IADE算法的性能

為了證明算法在不陷入局部最優(yōu)解的情況下找到最優(yōu)解的能力的有效性，本文在不同目標(biāo)數(shù)下進(jìn)行了兩個(gè)實(shí)驗(yàn)：實(shí)驗(yàn)1的目標(biāo)尺度較小，實(shí)驗(yàn)2的目標(biāo)尺度較大。在實(shí)驗(yàn)前，首先建立了三維空間地形圖，并設(shè)置了無(wú)人機(jī)和目標(biāo)點(diǎn)的初始位置，以及無(wú)人機(jī)自身的一些參數(shù)。

表1顯示了初始化無(wú)人機(jī)的參數(shù)，其中Num為無(wú)人機(jī)數(shù)量，Po表示無(wú)人機(jī)的初始位置，D為無(wú)人機(jī)的飛行范圍，V表示無(wú)人機(jī)的最大和最小的飛行速度，N為無(wú)人機(jī)每次飛行執(zhí)行的最大任務(wù)數(shù)。

表1 無(wú)人機(jī)初始化參數(shù)

表2設(shè)置了目標(biāo)點(diǎn)數(shù)量和位置，其中T為目標(biāo)點(diǎn)數(shù)量。

表2 初始化目標(biāo)坐標(biāo)

兩組實(shí)驗(yàn)參數(shù)設(shè)置如表3所示。其中，T為目標(biāo)點(diǎn)，P為種群中的個(gè)體，G為進(jìn)化迭代次數(shù)，Num為程序運(yùn)行次數(shù)。

表3 組進(jìn)化參數(shù)

圖2～圖3為三維環(huán)境下兩組實(shí)驗(yàn)無(wú)人機(jī)攻擊目標(biāo)的最優(yōu)仿真結(jié)果。黃色圓圈表示無(wú)人機(jī)的起始位置，黃色星形表示目標(biāo)點(diǎn)的位置，紅線表示無(wú)人機(jī)執(zhí)行目標(biāo)點(diǎn)任務(wù)的路徑。

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

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

兩組實(shí)驗(yàn)的收斂曲線如圖4～圖5所示?？梢钥闯觯捎趯?shí)驗(yàn)1中目標(biāo)點(diǎn)數(shù)量較少，算法從進(jìn)化開(kāi)始到進(jìn)化結(jié)束都是最優(yōu)解。實(shí)驗(yàn)2在第50代左右收斂到最優(yōu)解，說(shuō)明IADE算法在進(jìn)化初期具有良好的收斂性。從實(shí)驗(yàn)2的收斂曲線可以看出，算法執(zhí)行到一半仍然收斂，這證明了在自適應(yīng)變異因子和自適應(yīng)交叉因子的共同作用下，算法能夠有效地得到最優(yōu)解。

圖4 實(shí)驗(yàn)1的收斂曲線

圖5 實(shí)驗(yàn)2的收斂曲線

表4列出了兩組實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)數(shù)據(jù)。其中Avgtime為算法平均執(zhí)行時(shí)間，Bestcost為最優(yōu)總航程成本，Avgcost為該航程的平均總航程成本，optimal為最優(yōu)解比例，以百分比表示。兩組實(shí)驗(yàn)結(jié)果表明，IADE算法能很好地解決無(wú)人機(jī)多任務(wù)問(wèn)題，并能獲得最優(yōu)解。

表4 結(jié)果統(tǒng)計(jì)

通過(guò)對(duì)比兩個(gè)實(shí)驗(yàn)的結(jié)果，雖然大規(guī)模實(shí)驗(yàn)2增加了無(wú)人機(jī)多任務(wù)問(wèn)題的復(fù)雜性，但I(xiàn)ADE算法仍能在有限的時(shí)間內(nèi)找到最優(yōu)解，最優(yōu)解比例達(dá)到92.5%。實(shí)驗(yàn)1的規(guī)模相對(duì)較小，說(shuō)明該算法能夠快速得到最優(yōu)解，且運(yùn)行時(shí)間短，最優(yōu)解比例達(dá)到97.5%。盡管實(shí)驗(yàn)2中的任務(wù)是實(shí)驗(yàn)1的兩倍，但兩組實(shí)驗(yàn)得到的最優(yōu)解的平均運(yùn)行時(shí)間是在同一數(shù)量級(jí)，這表明該算法適用于高效地解決不同尺度的多任務(wù)處理問(wèn)題，且平均成本Avgcost接近最佳成本Bestcost。表5顯示了兩組實(shí)驗(yàn)的最優(yōu)分配結(jié)果。

表5 分配結(jié)果

■3.2 IADE算法與其他算法的比較

為了進(jìn)一步驗(yàn)證IADE算法的有效性和合理性，本文將該算法與DMDE算法和標(biāo)準(zhǔn)DE算法進(jìn)行了比較。對(duì)比實(shí)驗(yàn)是在完全相同的仿真環(huán)境下進(jìn)行的。實(shí)驗(yàn)結(jié)果見(jiàn)表6。各算法的仿真結(jié)果及收斂曲線分別如圖6～圖11所示。

圖11 DE算法的收斂曲線

表6 結(jié)果統(tǒng)計(jì)

圖6 IADE算法的結(jié)果

圖7 IADE算法的收斂曲線

圖8 DMDE算法的結(jié)果

圖9 DMDE算法的收斂曲線

圖10 DE算法的結(jié)果

通過(guò)對(duì)比實(shí)驗(yàn)可以看出，IADE算法執(zhí)行時(shí)間最短，收斂速度最快，平均飛行成本最低，獲得最優(yōu)解的效率最高。雖然DEDM算法[14]在多無(wú)人機(jī)協(xié)同多目標(biāo)分配方面表現(xiàn)良好，但在在任務(wù)規(guī)模較大時(shí)處理單無(wú)人機(jī)多任務(wù)時(shí)表現(xiàn)較差。DEDM算法運(yùn)行時(shí)間最長(zhǎng)，平均飛行成本最高，獲得最優(yōu)解的效率僅為30%。雖然標(biāo)準(zhǔn)DE算法優(yōu)于DMDE算法，但其執(zhí)行時(shí)間較IADE算法長(zhǎng)，且得到最優(yōu)解的效率為72.5%，比IADE算法低20%。

4 結(jié)論

針對(duì)無(wú)人機(jī)多任務(wù)執(zhí)行過(guò)程中建模困難、計(jì)算復(fù)雜的問(wèn)題，本文提出了一種新的算法。主要結(jié)果如下：

（1）在三維環(huán)境中建立了單個(gè)無(wú)人機(jī)多任務(wù)規(guī)劃模型及其約束條件。

（2）提出了一種基于種群迭代次數(shù)和個(gè)體適應(yīng)度值調(diào)整變異因子和交叉因子的自適應(yīng)進(jìn)化算法，解決了當(dāng)前進(jìn)化過(guò)程中存在的問(wèn)題。

（3）通過(guò)不同尺度的仿真實(shí)驗(yàn)，證明了IADE算法的合理性。

（4）與其他算法的對(duì)比實(shí)驗(yàn)表明了IADE算法的優(yōu)越性。

未來(lái)將致力于IADE算法應(yīng)用于無(wú)人機(jī)的路徑規(guī)劃的研究。