[發明專利]云環境下基于強化學習的超啟發式任務調度方法及系統

有效

• 申請號: 202110705390.2
• 申請日: 2021-06-24
• 公開（公告）號: CN113448687B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 周風余;孫倡;尹磊;劉進
• 申請（專利權）人: 山東大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48;G06N3/04;G06N3/08
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 張慶騫

1.一種云環境下基于強化學習的超啟發式任務調度方法，其特征在于，包括：

獲取云環境下任務調度相關信息及虛擬機運行參數，并初始化解集及高級啟發式方法的各項參數；其中，解集中的元素由一系列設定長度的序列值構成，序列值為相應任務在各個虛擬機上運行消耗的時間；

隨機選擇低級啟發式方法，并初始化相應低級啟發式方法參數，直至達到當前低級啟發式方法迭代停止條件，更新候選解解集，得到當前的最優解；

計算當前低級啟發式方法迭代的獎勵值，更新獎勵表；

根據獎勵表繼續選擇低層啟發式方法，遷移候選解，直至得到最優解，以實現最短的時間內完成云環境下任務調度工作；

當前低級啟發式方法迭代所獲獎勵的第一部分由當前迭代結果的makespan和上一次迭代得到的makespan所決定；

當前迭代結果R₁(s，a)為：

R₁(s，a)＝1/1+e^{-σ×makespan}/N_num

其中a表示動作信息，s表示狀態信息，由makespan和UDCS的值區間組成，σ表示常數，N_num表示任務數量，makespan表示任務完成時間，UDCS表示候選解種群多樣性。

2.如權利要求1所述的云環境下基于強化學習的超啟發式任務調度方法，其特征在于，在遷移候選解時，只保留滿足差分條件的最優解和5個次優解。

3.如權利要求1所述的云環境下基于強化學習的超啟發式任務調度方法，其特征在于，50％的候選解將由傳遞解的隨機擾動產生，剩余的候選解決方案將隨機生成。

4.如權利要求1所述的云環境下基于強化學習的超啟發式任務調度方法，其特征在于，獎勵值的更新公式為：

R₁(s，a)＝R₁(s，a)+α[r+λmax_a′R₁'(s，a)-R₁(s，a)]

其中max_S′R′(s′，a′)表示給定新狀態和新狀態s′下所有可能操作的最大期望未來；R₁(s，a)為前迭代結果的makespan；有限狀態state集合，s表示某個特定狀態；有限動作action集合，a表示某個特定動作；r表示固定獎勵值，為設定的常數；λ表示折扣率，也是固定常數，用以控制獎勵項所占比重。

5.如權利要求1所述的云環境下基于強化學習的超啟發式任務調度方法，其特征在于，上一次迭代得到的makespan確定的獎勵值的第一部分：

R₂(s，a)＝udcs_n-udcs_n-1

其中udcs_n表示當前迭代中候選解的單元多樣性，udcs_n-1表示上一次迭代候選解的單元多樣性。