[發明專利]一種基于改進鯨魚優化算法的工作流多目標調度方法

在審

• 申請號: 202211613591.0
• 申請日: 2022-12-15
• 公開（公告）號: CN116305747A
• 公開（公告）日: 2023-06-23
• 發明（設計）人: 袁友偉;黃笑成;高一鳴;姜添;毛婭鈊;王昌鵬;鄢臘梅
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06F9/50;G06N3/006;H04L67/1014;H04L67/1023;H04L67/63;H04L67/61;G06F111/08;G06F111/06
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 朱亞冠

1.一種基于改進鯨魚優化算法的工作流多目標調度方法，其特征在于所述方法包括以下步驟：

步驟(1)：構建任務依賴模型，確定工作流任務的執行順序；

使用有向無環圖DAG表示工作流中各任務之間存在依賴關系，DAG＝{T,E}，其中T＝{t₁,t₂,t₃,...t_i,...,t_n}表示工作流的任務集合，n為任務總數，t_i表示第i個任務,i∈[1,n],E＝{(e_jk,ed_jk)|j,k∈[1,n]}表示各任務之間的依賴關系集合，e_jk為任務t_j與任務t_k的前驅后繼關系，ed_jk為任務t_j傳遞給任務t_k的數據；

步驟(2)：工作流調度方案編碼；

對于每個任務，應確定其對應的服務器編號，已知邊緣環境中的服務器數量為m；在對T中的任務根據依賴關系進行拓撲排序后可用維向量X＝(x_i,x_i+1,...,x_n)表示，X表示調度方案，代表鯨魚個體；

步驟(3)：混沌映射初始化鯨魚種群；

采用Piecewise混沌映射為種群進行初始化，其描述如下：

其中p表示(0，0.5)區間的一個隨機數，是混沌序列的隨機產生參數；x_i表示第i次產生的初始編碼，x_i+1是根據x_i產生的第i+1次初始編碼，由所有初始編碼生成混沌序列，然后將每個初始編碼乘m并向上取整，得到對應的服務器編號，如下所示：

令N為種群數量，則可獲得初始工作流鯨魚種群W，其中每個個體X¹,X²,X³,…,X^N代表一種工作流調度方案：

W＝{X¹,X²,X³,…,X^N}??????式(3)步驟(4)：計算鯨魚個體適應度；

適應度的目標函數f(X)：

其中α是負載的懲罰系數，β是權重因子，AVER_load表示邊緣服務器平均負載量，TD_total表示工作流消耗的總時間，E_total表示工作流消耗的總能耗；

步驟(5)：根據p₁是否小于0.5判斷是否捕食獵物，p₁代表鯨魚隨機行為的選擇概率；若是則進行步驟(7)，若否則進行步驟(6)；

步驟(6)：包圍或搜尋獵物；

在搜索空間中，獵物代表當前最優的工作流調度方案，根據式(16)，若鯨魚種群中的每個鯨魚個體會游向獵物以進行包圍；若每個鯨魚個體會游向另一個隨機鯨魚個體以搜尋獵物，最優工作流調度方案的行為模型如下：

其中表示當前鯨魚第t+1次迭代后的位置，表示當前迭代位置，表示在第t次迭代中最優鯨魚的位置，表示鯨魚種群中隨機一條鯨魚的位置，是表示系數，是距離系數，并分別以式(16)、式(17)計算；通過上述公式向最優工作流調度方案趨近；是由生成的隨機數，是[0,1]中的隨機向量；max_iter是最大迭代次數，t是當前迭代次數，是迭代過程的權重系數，ω是范圍系數；

步驟(7)：螺旋更新位置；

最優工作流調度方案的行為模型如下：

其中b是限定螺旋狀的常數，從當前最優的位置根據搜索路徑不斷迭代至全局最優位置，即獲得最優工作流調度方案，l是[0,1]之間的隨機數；

步驟(8)：改進隨機差分法變異；

為加快尋找最優工作流調度方案，采用隨機差分法變異：

其中r₁，r₂是兩個隨機數，分別代表最優個體距離和隨機個體距離權重占比，代表經過隨機差分法變異后的新個體，若新個體適應度優于原個體，則接受并替換原個體，以此加快最優工作流調度方案的輸出；

若新個體適應度劣于原個體，則以概率接受，其數學表達如下所示：

其中q^r是[0,1]之間的隨機數，q是變化的非線性選擇概率，并由下方公式給出：

其中t表示當前迭代次數；

步驟(9)：輸出最優調度方案；

若迭代次數達到最大，則終止迭代，輸出最優個體，并解碼得到最優工作流調度方案。