[發(fā)明專利]一種基于聯(lián)合強化學習策略的多目標云工作流調(diào)度方法

有效

• 申請?zhí)枺?/td>: 202110024639.3
• 申請日: 2021-01-08
• 公開（公告）號: CN112685165B
• 公開（公告）日: 2022-08-23
• 發(fā)明（設(shè)計）人: 李慧芳;王彬陽;黃姜杭;王一竹;黃經(jīng)緯;鄒偉東;柴森春;夏元清
• 申請（專利權(quán)）人: 北京理工大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/455;G06N20/00;G06N3/04
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 代麗

本發(fā)明公開了一種基于聯(lián)合強化學習策略的多目標云工作流調(diào)度方法，通過對工作流請求和云資源的屬性和方法進行擴展建立了強化學習agent聯(lián)合策略模型，使調(diào)度模型更加貼合實際的工作流應(yīng)用場景，在行為選擇時綜合考慮調(diào)度進程、各決策子網(wǎng)絡(luò)以及歷史決策信息的影響，使得最終選擇的行為更為合理，進一步提升了算法產(chǎn)生非支配解集的主導性和多樣性，有效提高了方法的實用性。

技術(shù)領(lǐng)域

本發(fā)明屬于云計算技術(shù)領(lǐng)域，具體涉及一種基于強化學習策略的多目標云工作流調(diào)度方法。

背景技術(shù)

作為一種最新的分布式系統(tǒng)計算范例，云計算的按使用付費與彈性資源模式為大規(guī)模科學應(yīng)用的快速部署與分布式高效執(zhí)行提供了易于訪問、可擴展的基礎(chǔ)設(shè)施環(huán)境。越來越多的科學家使用工作流來構(gòu)建他們的復雜應(yīng)用并將這些應(yīng)用部署在云平臺上執(zhí)行。但是，云的按需使用等優(yōu)點也給云環(huán)境下的工作流調(diào)度帶來了很多挑戰(zhàn)。一方面，云的按使用付費模式使得工作流調(diào)度時，需要同時考慮應(yīng)用的執(zhí)行時間與成本等，增加了調(diào)度求解難度。另一方面，其彈性資源模式大大增加了調(diào)度求解空間，進一步使調(diào)度問題復雜化。

目前，多目標優(yōu)化問題的求解主要采用啟發(fā)式、元啟發(fā)式或二者的混合算法。啟發(fā)式算法一般基于特定問題求解場景，通過設(shè)計一定的規(guī)則計算任務(wù)調(diào)度的優(yōu)先級，并根據(jù)優(yōu)先級依次調(diào)度各個任務(wù)。啟發(fā)式方法對簡單的問題模型求解效果好，但當調(diào)度問題變得復雜時，很難找到最優(yōu)解，且泛化能力不足。與啟發(fā)式算法相比，元啟發(fā)式算法的泛化能力有了很大改善，但通常需要多次迭代更新才能找到近似最優(yōu)解，而且當問題規(guī)模變大時，算法尋優(yōu)所需的時間開銷較大，難以滿足用戶對調(diào)度的實時性要求。

隨著強化學習的發(fā)展及其在序列決策方面的突出優(yōu)勢，越來越多的研究者開始嘗試利用強化學習求解調(diào)度問題。例如，有學者提出利用基于模擬退火的Q學習算法解決協(xié)同工作中的任務(wù)調(diào)度問題以及利用基于DQN和策略梯度網(wǎng)絡(luò)的多目標工作流調(diào)度算法解決云環(huán)境下的任務(wù)調(diào)度問題。然而，在面臨大規(guī)模任務(wù)請求時，Q學習算法需要大量的數(shù)據(jù)存儲，其固有的Q值矩陣維數(shù)爆炸問題將導致很高的算法存儲復雜性。基于DQN的算法，采用值函數(shù)逼近解決了Q學習的高維數(shù)據(jù)存儲問題，但是由于采用固定維數(shù)的環(huán)境狀態(tài)向量與單一類型的工作流來訓練強化學習模型，其泛化能力具有較大的局限性，很難適應(yīng)不同大小、不同類型的應(yīng)用調(diào)度需求。基于策略梯度網(wǎng)絡(luò)并結(jié)合時序模型，可以在一定程度上克服DQN算法的不足，但其單策略模型在面對復雜多云場景下的多目標優(yōu)化問題時，顯示出求解能力的不足。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明提供了一種基于聯(lián)合強化學習策略的多目標云工作流調(diào)度方法，在適應(yīng)多種類型工作流調(diào)度問題的情況下，實現(xiàn)執(zhí)行跨度時間和成本的同時最小化的工作流調(diào)度。

本發(fā)明提供的一種基于聯(lián)合強化學習策略的多目標云工作流調(diào)度方法，包括以下步驟：

步驟1、構(gòu)建基于強化學習代理的聯(lián)合策略模型，所述基于強化學習代理的聯(lián)合策略模型包含基于引導策略和進化策略強化學習算法的兩個子代理，每個子代理模型又包含時間優(yōu)化子網(wǎng)和成本優(yōu)化子網(wǎng)兩個部分；

所述基于強化學習代理的聯(lián)合策略模型的狀態(tài)包括工作流執(zhí)行時間狀態(tài)和工作流執(zhí)行成本狀態(tài)；所述工作流執(zhí)行時間狀態(tài)和工作流執(zhí)行成本狀態(tài)均包含任務(wù)狀態(tài)和虛擬機狀態(tài)；

步驟2、所述時間優(yōu)化子網(wǎng)以所述工作流執(zhí)行時間狀態(tài)作為輸入、所述成本優(yōu)化子網(wǎng)以所述工作流執(zhí)行成本狀態(tài)作為輸入與環(huán)境交互，完成一次完整調(diào)度，將調(diào)度過程涉及的所有狀態(tài)轉(zhuǎn)換、動作和回報作為訓練樣本構(gòu)建訓練樣本集，采用所述訓練樣本集訓練所述基于強化學習代理的聯(lián)合策略模型；

步驟3、調(diào)度應(yīng)用時，將由所述步驟1計算得到的待調(diào)度工作流的工作流執(zhí)行時間狀態(tài)和工作流執(zhí)行成本狀態(tài)輸入到所述基于強化學習代理的聯(lián)合策略模型中分別得到時間優(yōu)化工作流調(diào)度方案和成本優(yōu)化工作流調(diào)度方案，從中確定工作流調(diào)度方案。

進一步地，所述步驟1中的所述工作流執(zhí)行時間狀態(tài)包括和