[發明專利]基于集合型離散粒子群優化的云工作流調度方法

在審

• 申請號: 201811200809.3
• 申請日: 2018-10-16
• 公開（公告）號: CN109543875A
• 公開（公告）日: 2019-03-29
• 發明（設計）人: 張軍;詹志輝;陳偉能;余維杰;梁迪
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/00
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

1.一種基于集合型離散粒子群優化的云工作流調度方法，其特征在于，所述的調度方法包括下列步驟：

S1、將待優化的云工作流調度問題建立數學模型，過程如下：

S11、將云工作流調度問題所含有的元素的全集記為E，集合E被分為一個n元組(E¹,E²,…,Eⁿ)，其中E＝E¹∪E²∪…∪Eⁿ；

S12、將云工作流調度問題的一組候選解X∈PS分為一個n元組(X¹,X²,…,Xⁿ),其中X^j，j＝1,2,…,n是一個集合并且PS則是所有可行解的集合；

S13、當且僅當X滿足約束條件Ω，將X作為可行解；

S14、將云工作流調度問題的優化目標當成要找到一個合適的解X^*使得問題的目標函數f得到最優化；

S2、對建立的數學模型基于集合型離散粒子群優化實現云工作流調度，過程如下：

S21、初始化算法的各個參數，并建立第一代粒子群和初始速度，其中，粒子的編碼方式為：

X＝(X¹,X²,…,Xⁿ)

其中Xⁱ∈S_i，S_i表示能用于執行第i個任務T_i的所有云計算服務的集合，由于每個任務只能匹配到一個云計算服務中執行，因此Xⁱ僅僅只含一個元素K_i，表示任務T_i被安排云計算服務上執行，n是工作流中任務的總數量；

速度的編碼方式為：

V＝(V¹,V²,…,Vⁿ)

其中，每一維度是一個帶有可能性的集合V^j＝{e/p(e)|e∈S_j}，表示集合S_j中的每一個元素e都關聯著一個可能性p(e)；

S22、根據粒子當前的位置評估每個粒子的適應度值；

S23、更新每個粒子的個體最優位置；

S24、更新粒子的速度，速度更新公式如下：

其中，下標i表示第i個粒子，上標j表示維度，ω是慣性權重，c是參數，r^j是位于[0,1]區間的隨機數，表示第f_i(j)個粒子的歷史最優位置的第j維，f_i(j)定義如下：首先產生一個處于[0,1]區間的隨機數ran，如果ran比給定的參數Pc大，f_i(j)＝i，否則對兩個隨機選擇的粒子進行錦標賽選擇，適應度值更大的粒子會被選中為f_i(j)；

S25、更新粒子的位置；

S26、如果迭代次數超過規定的最大進化代數或此時得到的最優解達到規定的誤差要求則停止，否則返回步驟S22繼續執行。

2.根據權利要求1所述的基于集合型離散粒子群優化的云工作流調度方法，其特征在于，所述的速度更新公式中相關操作定義如下：

(i)參數×速度：

其中，c是參數，V表示粒子速度，e是該調度問題中所含有的元素，E是元素全集，p(e)表示與e相關聯的可能性，p^l(e)表示更新后的可能性；

(ii)位置-位置：

其中，A和B表示兩個粒子位置，e是該調度問題中所含有的元素；

(iii)參數×(位置-位置)：

其中，c是參數，E^l表示兩個粒子位置之差，e是該調度問題中所含有的元素，E是元素全集，p^l(e)表示更新后的可能性；

(iv)速度+速度：

V₁+V₂＝{e/max(p₁(e),p₂(e))|e∈E}

其中，V₁和V₂表示兩個粒子速度，e是該調度問題中所含有的元素，E是元素全集，p₁(e)和p₂(e)分別表示兩個粒子與元素e相關聯的可能性。