[發明專利]基于蟻獅優化算法的云計算任務調度方法

在審

• 申請號: 201810823408.7
• 申請日: 2018-07-25
• 公開（公告）號: CN109062664A
• 公開（公告）日: 2018-12-21
• 發明（設計）人: 左宗文;劉勝美
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/50;G06N3/00
• 代理公司: 南京蘇科專利代理有限責任公司 32102
• 代理人: 張霞

1.一種基于蟻獅優化算法的云計算任務調度方法，其特征在于，包括以下步驟：

S1、根據用戶提交的任務，確定任務的參數以及適應度函數的權值α；

S2、根據S1中的所述參數，初始化蟻獅算法中螞蟻和蟻獅的位置；

S3、根據S1中的所述權值α建立適應度函數，通過任務與虛擬機的映射關系計算出適應度結果；根據螞蟻的坐標使用適應度函數計算出每只螞蟻的適應度，若螞蟻的適應度函數小于蟻獅的適應度函數，則更新蟻獅的位置，同時選出適應度最小的蟻獅作為精英蟻獅；

S4、根據每只螞蟻的適應度函數結果，使用輪盤法選擇對應的蟻獅，螞蟻的新位置由選擇的蟻獅和唯一的精英蟻獅通過隨機游走獲得；

S5、更新螞蟻位置后，再次使用適應度函數計算螞蟻和蟻獅的適應函數值；

S6、判斷是否大于最大迭代次數；若是，則輸出精英蟻獅的位置，由任務與虛擬機的映射關系表得到最終的任務分配方案；若否，則返回步驟S4。

2.根據權利要求1所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：步驟S1中，用戶提交任務后將n個任務和m臺虛擬機之間的關系被抽象成矩陣M_Task和M_Net，分別為：

其中：M_Task中T_i,j表示第i個虛擬機、第j個任務的長度，單位是百萬條指令；M_Net中N_i,j表示對第i臺虛擬機、接收和提交第j個任務在網絡上消耗的時間，單位是秒。

3.根據權利要求1所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：所述適應度函數的權值α是QoS的權重，且α∈(0,1)。

4.根據權利要求2所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：步驟S2中初始化參數，種群數量為k，螞蟻的位置表示為M_Ant，蟻獅的位置表示為M_Antlion，即：

其中：A_i,j和AL_i,j初始化為A_i,j，AL_i,j＝random*m，random是在[0,1)上隨機均勻分布的隨機值。

5.根據權利要求4所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：步驟S3中，適應度函數表示為：

fitness_k＝α(spanTime)+(1-α)cost； (5)

其中，spanTime表示時間跨度，cost表示功耗消耗。

6.根據權利要求5所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：所述時間跨度spanTime和功能消耗cost通過下述計算得到：

spanTime＝Max(Time_i)； (7)

cost＝(P_run-P_free)∑Time_i+P_free*spanTime*m； (8)

其中，C_i表示第i臺虛擬機的計算能力，單位是Mips；P_run代表虛擬機滿負荷運行時的功耗，P_free代表虛擬機待機時的功耗；螞蟻和蟻獅的適應度函數矩陣由螞蟻和蟻獅的坐標所決定：

7.根據權利要求6所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：步驟S4中，根據M_{Antlionfitness}的結果獲得輪盤法所需數據M_wheel，其對應關系是：

第i只螞蟻選擇蟻獅的過程表示為：

selectAntlion_i＝random*M_wheel[k]； (12)

其中，random是在[0,1)上隨機均勻分布的隨機值。

8.根據權利要求7所述的一種基于蟻獅優化算法的云計算任務調度方法，其特征在于：當選擇第一個大于selectAntlion_i的M_wheel[j]，則j為選擇的蟻獅，隨機游走表示為：

經過t次迭代后，可得隨機游走中的最大值為randomWalk_Max、最小值randomWalk_Min和當前randomWalk(t)，由這三個值歸一化計算得到第t次的隨機步長：

其中，Lbi^t和Ubi^t表示第t次迭代的搜索邊界。