基于改進差分進化算法的無人機任務規劃研究

張榮，王彬

（1.武漢鐵路職業技術學院，湖北武漢， 430200；2.中鐵第四勘察設計院集團有限公司，湖北武漢， 430063）

0 引言

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

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

1 無人機多目標分配模型

■1.1 目標函數

無人機多任務規劃是一個約束優化問題。通常，這類問題同時包含了等式約束和不等式約束[10]。根據優化理論，COP的數學描述如下：

其中，x∈D表示優化問題的決策變量，f(x)為目標函數，表示待優化目標，hi(x)和g j(x)分別表示等式約束和不等式約束。

根據以上描述，結合無人機多任務分配的具體問題，可以假設單架無人機在任務空間的不同區域對多目標攻擊或執行多任務。解決該問題的關鍵是獲取攻擊和執行序列，使無人機具有滿足所有約束條件的最短飛行距離和最短飛行時間。

無人機多任務模型的目標函數描述如下：

式中，dj為無人機到目標j的飛行距離，wj為j的目標權重，其取值范圍為0～1，值越大優先級越高，tj為無人機到目標的飛行時間，ck為違反約束，α和β表示用于平衡目標函數多項式的比例因子，保持航次成本、飛行時間和違反約束在同一數量級，Dj表示決策變量，決定無人機的執行目標。圖1顯示函數的3D環境和應用場景。

圖1 三維環境的應用場景

■1.2 約束關系

（1）最大飛行距離約束

最大飛行距離約束反映無人機的性能和油耗指標，即無人機完成所有任務過程中的最大飛行距離限制。這個約束的關鍵是確保無人機能夠完成所有的目標。約束函數表示為：

其中di為估計航程成本，D為無人機最大航程限制。C1viol表示違反約束，無人機執行第j個任務時超過最大飛行距離將受到限制。

（2）空速約束

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

（3）最大飛行時間約束

最大飛行時間約束表示無人機完成所有任務所需的總時間。該約束的關鍵是確保無人機在規定的飛行時間內完成所有任務。

其中C3viol表示如果無人機超過最大飛行時間限制。

（4）目標點之間的時間約束

時間約束反映了目標點之間的執行順序。重要目標點的優先級高必須優先執行，其他目標點根據約束按順序執行。

其中：Tj＜T j+τ表示目標點j必須晚于目標點j+τ執行，τ為正整數，C4viol限制目標點j后執行。

（5）最大任務數的約束

無人機執行的最大任務數由以下約束表示：

其中：Mmax表示無人機執行的任務數不超過設定執行的任務數，C5viol表示無人機任務約束。

2 改進的自適應差分進化

■2.1 標準差分進化算法

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

（1）種群初始化

DE算法在解的搜索范圍的維度D內隨機生成NP個體：

DE算法經常使用一些固定的變異策略來生成變異個體vi，以保證種群的多樣性。DE算法中的確定性變異策略如下：

其中xbest表示最佳個體，F為比例因子，r1 r2 r3 r4 r5表示在[1,NP]上的不同隨機整數，且不等于i。

（3）交叉操作

交叉運算的基本原理是將變異向量與目標向量進行參數混合，生成實驗向量。具體表達式如下：

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

DE算法的主要思想是根據貪婪法則選擇下一代的個體，即保留優秀的個體，剔除劣等的個體。對于優化問題，優秀個體的適應度值較小。

■2.2 JADE算法

DE/current-to-pbest作為一種新的變異策略，構成了JADE算法的基礎，JADE是一種具有可選存檔的自適應DE算法[12]。

其中Fi為變異因子，與xi,g相關。的選擇方法是在算法的每次迭代中，從100p%的種群中隨機選擇一個個體作為當前最優個體，并將其應用到變異策略中。

在JADE中，F表示為：

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

式中，c為區間(0,1)內的值，SF為所有優秀變異因子的集合。

在JADE中，CR是獨立于正態分布產生的，正態分布的均值為uCR，標準差為0.1。

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

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

■2.3 PaDE算法

在整個進化過程中，PaDE算法保持k個組，并所有個體在其中進化分類。然后，uF可以根據下式更新：

并根據以下公式更新選擇概率：

為了適應種群規模的動態變化，本文提出了一種減小拋物線種群規模的新方案。

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

■2.4 RAM-JAPDE算法

RAM-JAPDE算法是將基于秩的變異策略自適應(RAM)和基于DE參數的聯合自適應(JAPDE)相結合而產生的一種新算法[13]。RAM-JAPDE算法的主要流程及計算公式如下：

■2.5 改進機制

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

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

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

式中，g表示第g代,G為進化的總代，Fmax和Fmin分別為變異因子的最大值和最小值。

交叉因子CR控制單個參數各維度參與交叉步驟的程度，使其隨個體適應度值變化，保證算法收斂的穩定性，呈現動態自適應交叉因子。具體表達式如下：

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

3 實驗與分析

為了驗證IADE算法應用于無人機多任務規劃的效果，本文進行了仿真實驗，并與其他算法進行了比較。

■3.1 IADE算法的性能

為了證明算法在不陷入局部最優解的情況下找到最優解的能力的有效性，本文在不同目標數下進行了兩個實驗：實驗1的目標尺度較小，實驗2的目標尺度較大。在實驗前，首先建立了三維空間地形圖，并設置了無人機和目標點的初始位置，以及無人機自身的一些參數。

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

表1 無人機初始化參數

表2設置了目標點數量和位置，其中T為目標點數量。

表2 初始化目標坐標

兩組實驗參數設置如表3所示。其中，T為目標點，P為種群中的個體，G為進化迭代次數，Num為程序運行次數。

表3 組進化參數

圖2～圖3為三維環境下兩組實驗無人機攻擊目標的最優仿真結果。黃色圓圈表示無人機的起始位置，黃色星形表示目標點的位置，紅線表示無人機執行目標點任務的路徑。

圖2 實驗1的仿真結果

圖3 實驗2的仿真結果

兩組實驗的收斂曲線如圖4～圖5所示。可以看出，由于實驗1中目標點數量較少，算法從進化開始到進化結束都是最優解。實驗2在第50代左右收斂到最優解，說明IADE算法在進化初期具有良好的收斂性。從實驗2的收斂曲線可以看出，算法執行到一半仍然收斂，這證明了在自適應變異因子和自適應交叉因子的共同作用下，算法能夠有效地得到最優解。

圖4 實驗1的收斂曲線

圖5 實驗2的收斂曲線

表4列出了兩組實驗結果的統計數據。其中Avgtime為算法平均執行時間，Bestcost為最優總航程成本，Avgcost為該航程的平均總航程成本，optimal為最優解比例，以百分比表示。兩組實驗結果表明，IADE算法能很好地解決無人機多任務問題，并能獲得最優解。

表4 結果統計

通過對比兩個實驗的結果，雖然大規模實驗2增加了無人機多任務問題的復雜性，但IADE算法仍能在有限的時間內找到最優解，最優解比例達到92.5%。實驗1的規模相對較小，說明該算法能夠快速得到最優解，且運行時間短，最優解比例達到97.5%。盡管實驗2中的任務是實驗1的兩倍，但兩組實驗得到的最優解的平均運行時間是在同一數量級，這表明該算法適用于高效地解決不同尺度的多任務處理問題，且平均成本Avgcost接近最佳成本Bestcost。表5顯示了兩組實驗的最優分配結果。

表5 分配結果

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

為了進一步驗證IADE算法的有效性和合理性，本文將該算法與DMDE算法和標準DE算法進行了比較。對比實驗是在完全相同的仿真環境下進行的。實驗結果見表6。各算法的仿真結果及收斂曲線分別如圖6～圖11所示。

圖11 DE算法的收斂曲線

表6 結果統計

圖6 IADE算法的結果

圖7 IADE算法的收斂曲線

圖8 DMDE算法的結果

圖9 DMDE算法的收斂曲線

圖10 DE算法的結果

通過對比實驗可以看出，IADE算法執行時間最短，收斂速度最快，平均飛行成本最低，獲得最優解的效率最高。雖然DEDM算法[14]在多無人機協同多目標分配方面表現良好，但在在任務規模較大時處理單無人機多任務時表現較差。DEDM算法運行時間最長，平均飛行成本最高，獲得最優解的效率僅為30%。雖然標準DE算法優于DMDE算法，但其執行時間較IADE算法長，且得到最優解的效率為72.5%，比IADE算法低20%。

4 結論

針對無人機多任務執行過程中建模困難、計算復雜的問題，本文提出了一種新的算法。主要結果如下：

（1）在三維環境中建立了單個無人機多任務規劃模型及其約束條件。

（2）提出了一種基于種群迭代次數和個體適應度值調整變異因子和交叉因子的自適應進化算法，解決了當前進化過程中存在的問題。

（3）通過不同尺度的仿真實驗，證明了IADE算法的合理性。

（4）與其他算法的對比實驗表明了IADE算法的優越性。

未來將致力于IADE算法應用于無人機的路徑規劃的研究。