[發明專利]基于動態目標策略的云計算資源調度優化方法及應用

在審

• 申請號: 202011095662.3
• 申請日: 2020-10-14
• 公開（公告）號: CN112379996A
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 詹志輝;王子佳;陳宗淦;張軍
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F30/20;G06N3/12;G06F111/04
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

1.一種基于動態目標策略的云計算資源調度優化方法，其特征在于，包括下述步驟：

初始化種群：對種群中的每一個染色體，隨機生成一個資源調度序列；

適應值評估：采用任務流執行成本的倒數評價適應值；

動態目標策略：若第一代初始化時沒有滿足最終截止時間需求的可行解，則將任務流執行時間作為優化目標，將任務流執行時間倒數評價染色體的適應值，每次迭代選擇TET更小而適應值更高的染色體，直至種群中出現染色體得出的解滿足最終截止時間需求，再重新采用任務流執行成本的倒數評價適應值；

選擇算子：根據染色體的適應值，通過輪盤賭選擇進入下一代的染色體個體；

染色體的交叉和變異：每個染色體都設有一個交叉概率和一個變異概率，對每個資源調度序列生成一個隨機數，若隨機數小于交叉概率，則選擇該資源調度序列作為交叉的父本之一；

對每個資源調度序列的每個任務，生成一個隨機數，若隨機數小于變異概率，則該任務所占資源編號發生變異；

最優個體保留策略：每一代中，若當代中有染色體的適應值高于當前最優染色體，則將當代中所述染色體作為新的最優染色體；否則，采用當前最優染色體個體替換掉當代中適應值最小的染色體；

當找到一個可行解后，執行到指定代數后無法找到可行解的時，輸出產生的最優染色體的解。

2.根據權利要求1所述的基于動態目標策略的云計算資源調度優化方法，其特征在于，所述對種群中的每一個染色體，隨機生成一個資源調度序列，具體步驟包括：

采用資源和任務的編號表示相應的資源和任務，每一個染色體第i位基因表示任務t_i所在執行的資源，對于染色體x，x_i＝j表示任務t_i在資源r_j上執行。

3.根據權利要求1所述的基于動態目標策略的云計算資源調度優化方法，其特征在于，所述通過輪盤賭選擇進入下一代的染色體個體，資源調度序列被選擇的概率為：

fitness_i＝1/TEC_i

其中，TEC表示任務流執行成本，fitness_i表示適應值，i表示染色體基因第i位。

4.根據權利要求1所述的基于動態目標策略的云計算資源調度優化方法，其特征在于，所述染色體的交叉和變異的步驟中，每當選擇到2個染色體時，生成一個隨機數n∈[1,N-1],n∈Z，對應交換兩個資源調度序列的前n個任務的資源編號。

5.一種基于動態目標策略的云計算資源調度優化系統，其特征在于，包括：種群初始化模塊、適應值評估模塊、動態目標策略構建模塊、選擇算子模塊、染色體交叉和變異模塊、最優個體保留策略構建模塊和輸出模塊；

所述種群初始化模塊用于初始化種群，對種群中的每一個染色體，隨機生成一個資源調度序列；

所述適應值評估模塊用于采用任務流執行成本的倒數評價適應值；

所述動態目標策略構建模塊用于構建動態目標策略，具體為：若第一代初始化時沒有滿足最終截止時間需求的可行解，則將任務流執行時間作為優化目標，將任務流執行時間倒數評價染色體的適應值，每次迭代選擇TET更小而適應值更高的染色體，直至種群中出現染色體得出的解滿足最終截止時間需求，再重新采用任務流執行成本的倒數評價適應值；

所述選擇算子模塊用于根據染色體的適應值，通過輪盤賭選擇進入下一代的染色體個體；

所述染色體交叉和變異模塊用于完成染色體的交叉和變異，每個染色體都設有一個交叉概率和一個變異概率，對每個資源調度序列生成一個隨機數，若隨機數小于交叉概率，則選擇該資源調度序列作為交叉的父本之一；

對每個資源調度序列的每個任務，生成一個隨機數，若隨機數小于變異概率，則該任務所占資源編號發生變異；

所述最優個體保留策略構建模塊用于構建最優個體保留策略，具體為：每一代中，若當代中有染色體的適應值高于當前最優染色體，則將當代中所述染色體作為新的最優染色體；否則，采用當前最優染色體個體替換掉當代中適應值最小的染色體；

所述輸出模塊用于輸出最優解，在找到一個可行解后，執行到指定代數后無法找到可行解的時，輸出產生的最優染色體的解。