[發(fā)明專利]基于改進遺傳算法的云計算任務(wù)調(diào)度方法

有效

• 申請?zhí)枺?/td>: 202011086788.4
• 申請日: 2020-10-12
• 公開（公告）號: CN112181598B
• 公開（公告）日: 2022-12-09
• 發(fā)明（設(shè)計）人: 付學(xué)良;孫揚;李宏慧
• 申請（專利權(quán)）人: 內(nèi)蒙古農(nóng)業(yè)大學(xué)
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06N3/12
• 代理公司: 西安研創(chuàng)天下知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 61239
• 代理人: 郭璐

1.基于改進遺傳算法的云計算任務(wù)調(diào)度方法，其特征在于，包括以下步驟：

S1、確定云計算任務(wù)問題：將N個長度不同的云任務(wù)分配給M個性能不同的虛擬機，使N個云任務(wù)的總完成時間最短；

S2、編碼：采用實數(shù)直接編碼方式，種群中的每一個染色體個體表示一種調(diào)度方案，染色體的長度等于任務(wù)的數(shù)量；

S3、初始化種群：利用競爭交叉的方法初始化種群；

S4、適應(yīng)度計算：將云任務(wù)總完成時間作為適應(yīng)度函數(shù)計算種群中每個染色體個體的適應(yīng)度值；

S5：根據(jù)適應(yīng)度計算結(jié)果或迭代次數(shù)，判斷是否滿足終止條件，如果滿足終止條件，則此時種群中適應(yīng)度值最小的染色體個體的編碼即為最終的云任務(wù)調(diào)度方案；

S6、若適應(yīng)度計算結(jié)果或迭代次數(shù)不滿足終止條件，則繼續(xù)對種群依次進行選擇、吞噬和變異操作；

S7：計算變異操作后的種群中每個染色體個體的適應(yīng)度值，重復(fù)步驟S5-S6；

步驟S3利用競爭交叉的方法初始化種群的具體操作包括以下步驟，

S31：利用隨機生成函數(shù)生成一個個體數(shù)量為POPSIZE的種群A，種群A中每個染色體的維度為N，染色體上基因值的范圍為[0,M-1]；

S32：將種群A中的個體按順序每次選取兩個作為母體進行競爭，比較兩者的進化適應(yīng)性；

S33：對步驟S32中進化適應(yīng)性強的個體與Min-Min算法生成的個體進行雙點交叉操作，交叉后產(chǎn)生兩個新的子代個體，比較兩個子代個體進化適應(yīng)性，保留個體進化適應(yīng)性強的個體作為種群B的個體成員；

S34：隨機生成一個新的染色體個體與步驟S32中進化適應(yīng)性弱的個體進行雙點交叉操作，交叉后產(chǎn)生兩個新的子代個體，比較兩個子代個體進化適應(yīng)性，保留個體進化適應(yīng)性強的個體作為種群B的個體成員；

S35：判斷種群A中的個體是否全部參與競爭交叉，如果是，則選擇種群B作為初始種群，反之重復(fù)步驟S32-S34。

2.根據(jù)權(quán)利要求1所述的基于改進遺傳算法的云計算任務(wù)調(diào)度方法，其特征在于，利用適應(yīng)度函數(shù)計算個體的進化適應(yīng)性，所述適應(yīng)度函數(shù)為fitness＝max(time_i)，i∈(0，1，2，3，……M-1，式中，time_i表示虛擬機i上所有云任務(wù)完成所用的時間，M為虛擬機的數(shù)量。

3.根據(jù)權(quán)利要求1所述的基于改進遺傳算法的云計算任務(wù)調(diào)度方法，其特征在于，所述雙點交叉操作的具體操作包括以下步驟，

S341：對參與雙點交叉操作的兩個染色體，利用隨機函數(shù)生成左右兩個交叉位置，如果生成的兩個位置相同，則舍棄該位置，重新生成新的交叉位置；

S342：將左右交叉位置之間的區(qū)域稱之為交叉域；

S343：交叉兩個染色體的交叉域，形成兩個新的染色體個體。

4.根據(jù)權(quán)利要求1所述的基于改進遺傳算法的云計算任務(wù)調(diào)度方法，其特征在于，步驟S4中的適應(yīng)度函數(shù)為fitness＝max(time_i)，i∈(0，1，2，3，……M-1)，式中，time_i表示虛擬機i上所有云任務(wù)完成所用的時間，M為虛擬機的數(shù)量。