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

有效

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

1.一種基于聯(lián)合強(qiáng)化學(xué)習(xí)策略的多目標(biāo)云工作流調(diào)度方法，其特征在于，包括以下步驟：

步驟1、構(gòu)建基于強(qiáng)化學(xué)習(xí)代理的聯(lián)合策略模型，所述基于強(qiáng)化學(xué)習(xí)代理的聯(lián)合策略模型包含基于引導(dǎo)策略和進(jìn)化策略強(qiáng)化學(xué)習(xí)算法的兩個(gè)子代理，每個(gè)子代理模型又包含時(shí)間優(yōu)化子網(wǎng)和成本優(yōu)化子網(wǎng)兩個(gè)部分；構(gòu)建進(jìn)化策略子代理，其主體結(jié)構(gòu)為由多個(gè)指針網(wǎng)絡(luò)作為并行網(wǎng)絡(luò)并聯(lián)構(gòu)成，隨機(jī)選取任意并行網(wǎng)絡(luò)的輸出作為進(jìn)化策略決策子代理的輸出；構(gòu)建引導(dǎo)策略子代理，其主體結(jié)構(gòu)為包括混合時(shí)變線性高斯控制器的前置引導(dǎo)監(jiān)督模塊及策略網(wǎng)絡(luò)，其中，策略網(wǎng)絡(luò)與進(jìn)化策略子代理具有相同的網(wǎng)絡(luò)結(jié)構(gòu)，前置引導(dǎo)監(jiān)督模塊為采用重要性采樣方式重復(fù)利用離線樣本，并通過(guò)微分動(dòng)態(tài)規(guī)劃算法對(duì)離線樣本集進(jìn)行補(bǔ)充，引導(dǎo)算法搜索指向高回報(bào)區(qū)域獲得更高質(zhì)量的解；

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

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

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

所述步驟2中所述時(shí)間優(yōu)化子網(wǎng)以所述工作流執(zhí)行時(shí)間狀態(tài)作為輸入、所述成本優(yōu)化子網(wǎng)以所述工作流執(zhí)行成本狀態(tài)作為輸入與環(huán)境交互，完成一次完整調(diào)度，將調(diào)度過(guò)程涉及的所有狀態(tài)轉(zhuǎn)換、動(dòng)作和回報(bào)作為訓(xùn)練樣本構(gòu)建訓(xùn)練樣本集，包括以下步驟：

步驟5.1、重置環(huán)境為初始狀態(tài)，已調(diào)度任務(wù)列表及虛擬機(jī)運(yùn)行狀態(tài)記錄列表均為空；

步驟5.2、將當(dāng)前時(shí)間步t下兩個(gè)優(yōu)化目標(biāo)下的所述工作流執(zhí)行時(shí)間狀態(tài)和工作流執(zhí)行成本狀態(tài)分別輸入到所述時(shí)間優(yōu)化子網(wǎng)和所述成本優(yōu)化子網(wǎng)中，得到備選方案在兩個(gè)優(yōu)化目標(biāo)下的最終選擇概率；

步驟5.3、根據(jù)所述最終選擇概率，依照Pareto準(zhǔn)則分別選擇所述時(shí)間優(yōu)化子網(wǎng)和所述成本優(yōu)化子網(wǎng)的最終行為并輸出；

步驟5.4、根據(jù)公式1-e^{0.1×ep×nmax}，其中，ep為訓(xùn)練的片段數(shù)，nmax為以回報(bào)為評(píng)價(jià)標(biāo)準(zhǔn)下各子代理交互過(guò)程中累計(jì)的優(yōu)勝次數(shù)，分別計(jì)算所述時(shí)間優(yōu)化子網(wǎng)和所述成本優(yōu)化子網(wǎng)的行為概率，選擇概率較大的子代理的最終行為作為模型最終行為；

步驟5.5、執(zhí)行所述模型最終行為得到新環(huán)境狀態(tài)，更新所述已調(diào)度任務(wù)列表及虛擬機(jī)運(yùn)行狀態(tài)記錄列表；

步驟5.6、計(jì)算并存儲(chǔ)兩個(gè)目標(biāo)在當(dāng)前時(shí)間步t下的回報(bào)值，并將所述回報(bào)值和馬爾科夫過(guò)程e_t、e_t+1添加到所述訓(xùn)練樣本集中；

步驟5.6、判斷工作流調(diào)度過(guò)程是否完成，如果已完成，則結(jié)束本流程；否則，執(zhí)行步驟5.2。

2.根據(jù)權(quán)利要求1所述的多目標(biāo)云工作流調(diào)度方法，其特征在于，所述步驟1中的所述工作流執(zhí)行時(shí)間狀態(tài)包括和

其中，當(dāng)前時(shí)間步t下任務(wù)的狀態(tài)，n為當(dāng)前時(shí)間步t下可調(diào)度的任務(wù)個(gè)數(shù)；θ_i表示當(dāng)前可調(diào)度任務(wù)的計(jì)算量，ns_i為當(dāng)前可調(diào)度任務(wù)的所有子任務(wù)的個(gè)數(shù)，nc_i表示從當(dāng)前可調(diào)度任務(wù)到出口任務(wù)的最大路徑長(zhǎng)度；

為當(dāng)前時(shí)間步t下虛擬機(jī)的狀態(tài)，m為虛擬機(jī)個(gè)數(shù)，為當(dāng)前時(shí)間步t下虛擬機(jī)r_f的預(yù)期租用結(jié)束時(shí)間。