[發明專利]一種基于改進粒子群優化算法的任務調度方法

在審

• 申請號: 202211218829.X
• 申請日: 2022-10-07
• 公開（公告）號: CN115454611A
• 公開（公告）日: 2022-12-09
• 發明（設計）人: 張登銀;季毛毛;趙瑩
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06N3/00
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

1.一種基于改進粒子群優化算法的任務調度方法，其特征是，包括如下步驟，

獲取待調度的任務數據，根據所述任務數據進行粒子編碼；

通過粒子群優化算法對所述粒子進行迭代計算；其中，若所述粒子群優化算法未陷入局部最優解，則直接輸出調度方案；若所述粒子群優化算法陷入局部最優解，則采用粒子群優化算法融合布谷鳥搜索算法的方式，輸出調度方案。

2.根據權利要求1所述的基于改進粒子群優化算法的任務調度方法，其特征是，所述任務數據包括任務的數量和處理節點的數量；

所述粒子的編碼方式如下：

P_i＝{p_i1，p_i2，...，p_ij，...，p_in}，

其中，P_i為第i個粒子的編碼方式，p_ij代表第i個調度方案中第j個任務調度到的處理節點，n為任務的數量，1≤i≤N，N為粒子種群規模；初始化時，p_ij的取值范圍為0≤p_ij≤m，m為處理節點的數量。

3.根據權利要求2所述的基于改進粒子群優化算法的任務調度方法，其特征是，粒子群優化算法陷入局部最優解的判定方式包括：

獲取粒子一次迭代的變化量和平均變化量，得到該次所有粒子變化量的方差值；

將粒子按照迭代變化量的大小升序排序，選取并計算前X個粒子變化量的方差值；

比較所有粒子變化量的方差值和前X個粒子變化量的方差值；其中，若所有粒子變化量的方差值大于前X個粒子變化量的方差值，則判定粒子群優化算法陷入局部最優解，反之則判定粒子群優化算法未陷入局部最優解。

4.根據權利要求3所述的基于改進粒子群優化算法的任務調度方法，其特征是，所述所有粒子變化量的方差值的表達式如下：

其中，為第t次所有粒子變化量的方差值，為第t次粒子迭代的變化量，ΔP^t為第t次粒子迭代的平均變化量。

5.根據權利要求3所述的基于改進粒子群優化算法的任務調度方法，其特征是，所述前X個粒子變化量的方差值的表達式如下：

其中，為第t次前X個粒子變化量的方差值，為第t次粒子迭代的變化量，ΔP^t為第t次粒子迭代的平均變化量。

6.根據權利要求3所述的基于改進粒子群優化算法的任務調度方法，其特征是，所述粒子群優化算法融合布谷鳥搜索算法的方法包括如下步驟：

將前X個粒子中的部分粒子作為布谷鳥搜索算法的初始解，通過布谷鳥搜索算法迭代求解，得到布谷鳥搜索算法的最優調度方案；

在原粒子群優化算法中剔除所述部分粒子，并隨機生成與部分粒子相同數量的粒子，繼續通過粒子群優化算法迭代求解，得到粒子群優化算法的最優調度方案。

7.根據權利要求6所述的基于改進粒子群優化算法的任務調度方法，其特征是，所述粒子群優化算法融合布谷鳥搜索算法的方法還包括：

比較所述布谷鳥搜索算法的最優調度方案和粒子群優化算法的最優調度方案的適應度，輸出的調度方案為適應度更高的最優調度方案。