[發明專利]一種帶約束云工作流調度的自適應多目標進化方法

有效

• 申請號: 201710046208.0
• 申請日: 2017-01-22
• 公開（公告）號: CN106845642B
• 公開（公告）日: 2019-03-29
• 發明（設計）人: 劉麗;張淼;李慧琦;范琦
• 申請（專利權）人: 北京科技大學;北京理工大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/10
• 代理公司: 北京市廣友專利事務所有限責任公司 11237
• 代理人: 張仲波

1.一種帶約束云工作流調度的自適應多目標進化方法，其特征在于，包括：

S1、建立帶約束云工作流調度模型：

Minimize:TEC

DI

Subject to:TET≤d_w

其中，Minimize表示優化目標，TEC表示總執行成本，DI表示不平衡度，TEC和DI是2個優化目標，Subject to表示約束條件，TET表示總執行時間，d_w表示時限，|VM|表示虛擬機的個數，表示執行任務i的虛擬機，是虛擬機單位時間成本，是執行任務i的實際運行時間，t_i表示任務i，τ是虛擬機單位處理能力，表示任務i和任務j之間的傳輸時間，下標e_i,j表示任務i和任務j是相連的，是的數據轉換成本，i∈T,j∈T中的T指所有的任務下標，T_max和T_min分別表示所有虛擬機的最大運行時間和最小運行時間，T_avg是虛擬機的平均運行時間，V是任務集合，表示任務i的結束時間；

利用Pareto解與優化目標的值之間的對應關系，根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態，根據檢測到的種群在進化過程中所處的進化狀態，自適應地利用相應的個體評估策略處理約束條件，并對種群中的個體進行排序，其中，在個體評估策略中，采用約束違反處理方法來處理約束條件；

S2、根據個體排序結果，從種群中選擇個體進行遺傳操作，得到子種群，其中，在進行遺傳操作時，根據種群在進化過程中所處的進化狀態自適應地調節進化參數，直至迭代次數等于預設的最大迭代次數。

2.根據權利要求1所述的帶約束云工作流調度的自適應多目標進化方法，其特征在于，所述根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態包括：

若種群中沒有Pareto解，則種群在進化過程中所處的進化狀態為初始狀態。

3.根據權利要求1所述的帶約束云工作流調度的自適應多目標進化方法，其特征在于，所述根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態包括：

若種群中Pareto解的個數小于種群大小，則種群在進化過程中所處的進化狀態為收斂狀態；或，

若種群中Pareto解的個數等于種群大小，且種群在t+1次迭代中，Pareto解的個數發生了變化，則種群在進化過程中所處的進化狀態為收斂狀態；或，

若種群中Pareto解的個數等于種群大小，種群在t+1次迭代中，Pareto解的個數沒有發生變化，且則種群在進化過程中所處的進化狀態為收斂狀態；

其中，ΔEntropy(t+1)表示第t+1次迭代和第t次迭代的差熵，M表示優化目標的個數，ΔEntropy_max-diver表示最大差熵值。

4.根據權利要求1所述的帶約束云工作流調度的自適應多目標進化方法，其特征在于，所述根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態包括：

若種群中Pareto解的個數等于種群大小，種群在t+1次迭代中，Pareto解的個數沒有發生變化，且則種群在進化過程中所處的進化狀態為多樣化狀態；或，

若種群中Pareto解的個數等于種群大小，種群在t+1次迭代中，Pareto解的個數沒有發生變化，Pareto熵也沒變化，則種群在進化過程中所處的進化狀態為成熟狀態；

其中，ΔEntropy(t+1)表示第t+1次迭代和第t次迭代的差熵，M表示優化目標的個數，ΔEntropy_max-diver表示最大差熵值。