[發明專利]一種基于蜂群遺傳混合算法的AUV系統任務分配方法

在審

• 申請號: 202210273979.4
• 申請日: 2022-03-20
• 公開（公告）號: CN114861856A
• 公開（公告）日: 2022-08-05
• 發明（設計）人: 王天澤;何軍紅;牛云;廉家偉
• 申請（專利權）人: 西北工業大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06N3/12;G06Q10/04;G06Q10/06
• 代理公司: 西安凱多思知識產權代理事務所(普通合伙) 61290
• 代理人: 高凌君

1.一種基于蜂群遺傳混合算法的AUV系統任務分配方法，其特征在于，包括如下步驟：

步驟1：初始化IABC算法參數與NGA算法參數，設定任務集合；

步驟2：利用IABC算法得到每只蜜蜂滿足約束條件的任務分配矩陣；

步驟2-1：為每只蜜蜂從任務集合中隨機選擇一個任務，然后依據IABC算法的概率公式選擇執行任務的AUV；

定義任務約束為：

式中，N表示AUV數量，M表示任務總數；x_(i,j)表示AUV_i是否執行Task_j，x_(i,j)＝1表示AUV_i執行Task_j，x_(i,j)＝0表示AUV_i不執行Task_j，AUV_i表示第i個AUV，Task_j表示第j個任務；O_i為AUV_i的最大負荷任務數，m表示AUV執行同一任務的次數；(1)式表示任意一個AUV執行任務的個數不超過該AUV最大負荷任務數；(2)式表示同一AUV對某個任務最多執行一次；(3)式表示每個任務至少需要一個AUV執行；(4)式表示所有任務需全部被AUV執行；

當遍歷完所有蜜蜂后，如果能夠同時滿足任務約束式(1)到式(4)就進入步驟2-2，否則重新開始步驟2-1；

步驟2-2：判斷執行任務的AUV是否滿足航程、通信、資源約束：

航程與通信約束為：

d(AUV_i,Task_j)Max(AUV_i) (5)

dis(AUV_i,AUV_g)min[M(AUV_i),M(AUV_g)] (7)

式中，d(AUV_i,Task_j)為AUV_i執行Task_j的航行距離，Max(AUV_i)為AUV_i的最大航行距離；p為AUV_i執行的任務數量，dis(AUV_i,AUV_g)為AUV_i到AUV_g的通信距離，M(AUV_i)為AUV_i的最大通訊距離；(5)式為單個AUV的航行距離約束；(6)式為多AUV系統的航行距離約束；(7)式為AUV_i與AUV_g之間的通訊距離約束；

資源約束為：

式中，r_ai為AUV_i負載的資源種類，r_tj為Task_j所需要的資源種類；為AUV_i負載的資源數量，k為資源種類，為Task_j所需要的資源的數量；(8)式表示對于單個AUV_i負載的資源種類與數量要滿足Task_j所需的資源量；(9)式表示對于多AUV系統的所有資源種類和數量之和應滿足所有任務所需的資源量；

當任務所需要的資源種類大于等于設定閾值時，該任務被定義為復雜任務；當任務所需要的資源種類小于設定閾值時，該任務被定義為簡單任務；

如果執行任務的AUV同時滿足式(5)到式(9)的航程、通信、資源約束，則形成任務與執行該任務的AUV之間的關聯關系，如果不能同時滿足式(5)到式(9)的航程、通信、資源約束，則重新開始步驟2-1；所有任務與執行該任務的AUV之間的關聯關系構成任務分配矩陣；

步驟3：計算步驟2得到的任務分配矩陣的效能函數U_t；

效能函數即完成所有任務的目標函數：

U_t＝α₁*Ben*x_(i,j)-α₂*D*x_(i,j)-α₃*Time*x_(i,j)-α₄*A_k

其中，為完成所有任務所獲效益,f(.)表示單個任務所獲收益，Typ(Task_j)表示任務類型，Sta(Task_j)表示任務狀態；

為AUV執行任務消耗距離代價；其中，M_p與M_q分別表示執行的簡單任務與復雜任務數量，其和為M；N_p表示執行簡單任務的AUV集合，N_q表示執行復雜任務的AUV集合；C_k為執行復雜任務的AUV個數；

為任務完成時間；其中d_(i,j)表示距離，v_i表示速度；

為資源均衡函數；式中，n為AUV的個數，R_i為AUV_i執行任務Task_j后的剩余資源，為剩余資源的平均值，ε為對于資源消耗不公平的厭惡程度，ε值越大，對各AUV消耗的資源越均衡；α₁、α₂、α₃、α₄均表示系數；

步驟4：設定次數S和子群體數T，且S能被T整除；將步驟2和步驟3重復S次，得到S個任務分配矩陣，計算出S個效能函數值；

步驟5：將S個效能函數值按從大到小的順序依次分配為T個子群體；

在T個子群體中隨機選擇兩個子群體，在這兩個子群體之間獨立進行交叉變異；重新在T個子群體中隨機選擇兩個子群體，在這兩個子群體之間獨立進行交叉變異；將此過程重復Z次；

再計算每個子群體的平均效能值，選擇平均效能值最大的子群體，再找到平均效能值最大的子群體中最大效能值對應的任務分配矩陣作為最優分配結果；

步驟6：重復步驟2至步驟5，直到達到設定的終止條件最大迭代次數或者最優分配結果不再變化為止；此時的最優分配結果即為全局最優分配結果。

2.根據權利要求1所述的一種基于蜂群遺傳混合算法的AUV系統任務分配方法，其特征在于，所述α₁＝0.4、α₂＝0.3、α₃＝0.2、α₄＝0.4。