[發明專利]一種基于多目標優化的云工作流調度方法及裝置

有效

• 申請號: 201710607203.0
• 申請日: 2017-07-24
• 公開（公告）號: CN109298930B
• 公開（公告）日: 2022-12-13
• 發明（設計）人: 馬玉新;于聚省;郭浩東;戚玉濤;鮑亮
• 申請（專利權）人: 西安電子科技大學昆山創新研究院;馬玉新;戚玉濤;鮑亮;于聚省;郭浩東
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06N3/00;G06Q10/04
• 代理公司: 北京匯思誠業知識產權代理有限公司 11444
• 代理人: 王剛;龔敏

本發明實施例提供了一種基于多目標優化的云工作流調度方法及裝置，涉及高性能計算技術領域，能夠基于局部搜索和權向量調整進行多目標優化，在獲得較快的收斂速度同時得到多樣性更好的個體。該方法包括建立仿真的云計算資源模型及云工作流任務模型；然后初始化種群并計算每個個體的適應值；進一步對每個個體進化處理；然后進行局部搜索，獲取每個子問題鄰居中的兩個最優個體，計算得到新個體，以再次更新個體；并且當更新后的個體滿足收斂條件時，對進化后種群進行權向量調整操作；包括刪除擁擠區域的子問題以及向稀疏區域增加新的子問題；最后輸出最優個體。本發明實施例提供的技術方案適用云工作流調度過程中。

【技術領域】

本發明涉及高性能計算技術領域，尤其涉及一種基于多目標優化的云工作流調度方法及裝置。

【背景技術】

隨著高性能計算技術的發展，越來越多的研究者逐漸在云工作流調度問題中應用多目標優化技術。多目標優化技術使得用戶從多個優化解中進行偏好決策成為可能。對于多目標優化的云工作流調度，不存在某個決策可以同時優化所有目標，但可以獲得多個沖突目標的一組折中的Pareto決策，云工作流調度的真實Pareto決策集合很難獲取，往往也沒有必要獲取真實的Pareto決策集合，通常獲取的是一組在目標空間上均勻分布的Pareto漸進最優決策。

目前，有基于Pareto支配的啟發式列表調度算法，可以同時優化任務完成時間和任務執行用戶花費，為用戶提供了一組可供選擇的優化調度方案。并且，還有研究者采用進化多目標優化算法來解決基礎設施即服務層次上同時優化任務完成時間和任務執行代價的云工作流調度問題，提出了針對問題的編碼方式、種群初始化、適應度評估和遺傳算子操作的新方案。

在實現本發明過程中，發明人發現現有技術中至少存在如下問題：

現有技術中，基于Pareto支配的云工作流調度方法及基于進化多目標優化算法的云工作流調度方法所求得解的多樣性較差，且基于Pareto支配的云工作流調度方法計算量較大并收斂性較差。

【發明內容】

有鑒于此，本發明實施例提供了一種基于多目標優化的云工作流調度方法及裝置，通過鄰居局部搜索和權向量調整進行多目標優化，可以在獲得較快的收斂速度上得到多樣性更好的個體。

第一方面，本發明實施例提供一種基于多目標優化的云工作流調度方法，所述方法包括：

根據參數配置數據，建立仿真的云計算資源模型，并根據工作流拓撲數據，建立云工作流任務模型；

隨機初始化包含N個個體的種群，其中，每個個體指的是云工作流任務模型中若干個工作流子任務到云計算資源模型中若干個虛擬機的一種映射方式；

根據若干個目標，獲取每個個體的若干個目標函數；

根據若干個目標函數，初始化理想點；

將多目標優化問題分解成N個子問題，根據理想點計算每個子問題，以獲取每個個體的適應值；

根據每個個體適應值的權值，獲取每個子問題的鄰居子問題，并計算每個個體的目標函數值，以初始化外部種群；

對每個個體進行進化處理；

根據所述進化處理，更新每個個體、理想點、每個子問題的鄰居子問題的個體以及外部種群；

獲取更新后的每個個體及每個子問題鄰居中的兩個最優個體；

當更新后的個體與鄰居中的兩個最優個體滿足指定條件時，通過更新后的個體及鄰居中的兩個最優個體計算得到新個體；

當得到的新個體優于更新后的個體時，再次更新每個個體；

輸出最優個體。

第二方面，本發明實施例提供一種基于多目標優化的云工作流調度方法，所述方法包括：