[發明專利]一種改進螢火蟲算法的多無人機協同耦合任務分配方法

有效

• 申請號: 201710281909.2
• 申請日: 2017-04-26
• 公開（公告）號: CN107219858B
• 公開（公告）日: 2020-04-03
• 發明（設計）人: 張耀中;謝松巖;胡波;張建東;史國慶;李飛龍
• 申請（專利權）人: 西北工業大學
• 主分類號: G05D1/10
• 分類號: G05D1/10;G06N3/00
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 金鳳

1.一種改進螢火蟲算法的多無人機協同耦合任務分配方法，其特征在于包括下述步驟：

步驟1：構建特殊耦合下的任務分配模型

在該步驟中，存在如下定義：

定義1：U＝{U₁,U₂,…,U_i,…,U_M}為無人機集合，其中U_i表示第i架無人機，M表示無人機總數；

定義2：T＝{T₁,T₂,…,T_j,…,T_N}為目標集合，其中T_j表示第j個目標，N為目標總數；

定義3：Task_jh為目標T_j的第h種任務，h＝1,2,3，當h＝1為確認，h＝2為打擊，h＝3為毀傷評估；

定義4：U^jh為能夠執行任務Task_jh的無人機集合；

定義5：TaskSequence_i＝{task1＞task2＞task3＞…＞taskn_i}為無人機U_i的任務序列；其中n_i表示分配給無人機Ui的任務數量，taskn_i表示無人機U_i需要執行的任務；

定義6：Route_i＝{UP_i,taskP₁,taskP₂,…,taskP_ni,B}為無人機U_i的路徑序列，taskP_ni表示無人機U_i執行任務n時所在的位置，UP_i表示無人機i的初始位置，B表示無人機返回基地的位置；

定義7：Voy_i為無人機U_i的航程，其中i＝1,2,…,M；

定義8：Voymax_i為無人機U_i的最大航程；

定義9：R_i為無人機U_i的武器載荷數量；

定義10：t_ijh為無人機U_i執行任務Task_jh消耗的執行時間；

定義11：sT_k為任務k的開始被執行時刻；

定義12：eT_k為任務k的完成時刻；

定義13：Inter_min為打擊任務和毀傷評估任務間的最小時間間隔；

定義14：Inter_max為打擊任務和毀傷評估任務間的最大時間間隔；

定義15：決策變量：

確認目標函數：選擇無人機最大航程最短作為任務規劃指標，該任務規劃指標是將各無人機中的最大航程最小化，即目標函數為：

確認特殊耦合約束：特殊耦合約束指在任務執行過程中的某一時刻，有兩個目標需要同時被打擊，則特殊耦合約束如下式(2)所示，同時在任務執行時有兩個目標具有被處理的優先級關系，則特殊耦合約束如下式(3)所示：

(1)任務同時執行約束：目標T_i和目標T_j必須同時打擊，則有約束：

式(2)中，和inter分別表示目標T_i的開始打擊時刻、目標T_j的開始打擊時刻和打擊目標T_i和T_j的時間間隔；

(2)任務優先級約束：目標T_k必須在T_l被確認之前被毀傷評估，則有約束：

式中，分別表示目標T_k的毀傷評估結束時刻和目標T_l的確認開始時刻；

具有復雜耦合約束下的多無人機任務分配數學模型：

步驟2：螢火蟲編碼

將螢火蟲表示為1×2N_t維數組，N_t為所有任務數量，N_t＝3×N，采用整數編碼的形式，每個螢火蟲分為兩部分，前N_t維表示任務分配部分，從左至右分別表示第i個目標的確認、打擊和毀傷評估任務，即第1、2、3維代表第1個目標的確認、打擊和毀傷評估任務，第4、5、6維代表第2個目標的確認、打擊和毀傷任務，并以此類推，i＝1,2,…,N，每一維的取值由數組中每一維所對應任務的可執行無人機集合中的元素數量決定決定；后N_t維表示任務排序部分，由3組所有目標的編號組成，從左至右，目標T_j第h次出現分別對應該目標的確認、打擊和毀壞評估任務，即目標T_j第1次出現表示無人機i的確認，目標T_j第2次出現表示無人機i的打擊，目標T_j第3次出現表示無人機i的毀傷評估；

步驟3：種群初始化

比較螢火蟲之間的余弦相似度，當任意兩只螢火蟲余弦相似度超過設定的閾值ξ，則對其中一個螢火蟲重新初始化，即對該螢火蟲的數值隨機化，其中閾值ξ取值在0.6-0.7之間，余弦相似度公式為：

其中，X_i和X_j分別指螢火蟲i和螢火蟲j所對應的向量；

步驟4：螢火蟲位置更新

1)螢火蟲位置進行β更新，具體步驟如下：

Setp1：計算螢火蟲X_i和X_j的海明距離H_ij，海明距離為兩個螢火蟲個體的位置向量中互相對應的數不相等的對數，并找到X_i和X_j中對應相等的元素；

Setp2：計算X_i對X_j相對吸引度β_ij，其中H_ij為螢火蟲i與螢火蟲j的海明距離，γ是移動步長，β₀表示在γ＝0處螢火蟲的初始吸引力；

Setp3：對于X_i和X_j中每一個不對應相等的元素ta，取隨機數r，若r＜β_ij，則ta取X_i和X_j中對應元素的值，若r≥β_ij，則取X_i和X_j中本身對應元素的值；

2)在進行β更新后，螢火蟲個體X_j的任務排序部分TS_j存在非法解，對螢火蟲個體進行修正，具體修正步驟為：

a)令S₁＝TS_j、S₂＝TS_i、L＝length(S₁)、p＝1、q＝1，TS_i為螢火蟲X_i的任務排序部分，TS_j為螢火蟲X_j的任務排序部分，L取螢火蟲個體任務排序部分的長度，即任務總數；

b)找出S₂中第一個等于S₁(p)的元素的索引值p₁，令S₁(p)＝0，S₂(p₁)＝0，其中S₁(p)為p值對應的S₁；

c)令p＝p+1，若p≤L，則返回執行步驟b)，否則執行步驟d)；

d)若S₁(q)不等于0，則在S₂找到第一個非零元素的位置索引值p₂，令S₁(q)＝S₂(p₂)，S₂(p₂)＝0，其中S₁(q)為q值對應的S₁；

e)令q＝q+1，若q≤L，則執行步驟d)，否則結束；

3)進行α更新

在螢火蟲算法中，α為步長因子，其公式為：

ta_i＝int(ta_i+α(rand-1/2)) (5)

式(5)中，ta_i表示螢火蟲任務分配部分某個元素的值，int是對參數取整操作，rand為隨機因子；

4)對α更新后的編碼進行非法修正，非法修正即為對每一位元素進行可行性判斷：若元素的值在元素的取值范圍內，則不用修正，若元素的值超出取值范圍，則以距離邊界值最近的點代替元素值；

步驟5：螢火蟲個體重構

1)對于螢火蟲個體的TS部分，采用基于鄰域搜索的變異方法，其操作步驟如下：Step1：在個體的任務排序部分隨機選擇r個位，并生成其排序的所有鄰域；

Step2：計算所有鄰域的目標函數，選出目標函數值最高的個體作為最佳個體，并代替原來的個體；

2)交叉操作

采用隨迭代次數指數遞增的交叉概率因子：

Cr＝Cr_min+(Cr_max-Cr_min)×exp(-a×(1-t/T)^b) (6)

式(6)中，Cr為交叉概率因子，Cr_min和Cr_max分別為最小交叉率和最大交叉率，且Cr_min＝0.4，Cr_max＝0.6；a＝40，b＝4，T為設定的最大迭代次數，t為當前迭代次數，交叉操作得到的新個體的取值為：

其中，為交叉操作得到的新個體，是需要交叉操作的個體，為不需要進行交叉操作的個體，j_rand為隨機數；

3)選擇操作

在原始個體和經交叉操作后得到的新個體之間選擇目標函數值大的個體保留到下一代，選擇操作為：

其中，X^t_i是第t代的第i個個體，U^t_i是第t代經交叉后得到的個體，fitness為目標函數；

步驟6：特殊耦合約束的處理

用矩陣T^s∈R^3N×3N表示目標或任務間存在的特殊耦合約束關系，表示任務i與任務j的特殊耦合約束，其取值規則為：

步驟7：螢火蟲個體解碼與目標函數的計算

具體的解碼步驟如下：

Step1：對任務分配部分進行解碼

(1)初始化各無人機的任務集合為空集，即

(2)從左至右依次讀取螢火蟲個體第k位上的值i，k＝1,2,…,2N，通過j＝fix(i/2)+1和h＝mod(i/2)分別得到j和h的值，將Task_jh加入到TaskSequence_i中；

Step2：對任務排序部分進行解碼

(1)從左至右依次讀取螢火蟲個體第k位上的值j，k＝1,2,…,2N，每個j為目標T_j上的一個任務，若j是第h次出現，則表示Task_jh，當k＝2N得到所有任務的排列順序TaskS；

(2)將TaskSequence_i根據TaskS重新排列任務順序，當Task_jh和Task_kl均在TaskSequence_i中時，則以從左到右的順序，若Task_jh在TaskS中的位置在Task_kl前面，則y_ijhkl＝1，若Task_jh在TaskS中的位置在Task_kl后面，則y_ijhkl＝-1；否則y_ijhkl＝0；

至此，解碼結束，得到各無人機的任務執行序列TaskSequence_i。