[發明專利]一種面向云計算任務調度的改進粒子群算法

有效

• 申請號: 202110485843.5
• 申請日: 2021-04-30
• 公開（公告）號: CN113222096B
• 公開（公告）日: 2022-11-11
• 發明（設計）人: 謝曉蘭;張啟明;翟青海;劉亞榮
• 申請（專利權）人: 桂林理工大學
• 主分類號: G06F9/00
• 分類號: G06F9/00;G06N3/00;G06F9/54;G06F9/455
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種面向云計算任務調度的改進粒子群算法，其特征在于，包括以下步驟：

步驟S1.粒子編碼及適應度函數的選擇：將粒子群算法應用于云環境中的任務調度時，由于待分配子任務通常都是離散值，所以需要對粒子進行編碼，粒子包含位置和速度兩個屬性，通過編碼將任務調度與粒子位置和速度相結合，云計算中任務是離散值，因此對粒子采用自然數編碼，設有n個任務，分配給m臺虛擬機，粒子種群規模為NP，每個粒子的位置由向量P表示，則第i個粒子可編碼為式(1)所示的n維向量：

P_i＝{p_i1,p_i2,…,p_ij,...,p_in} (1)

式(1)中1≤p_ij≤m，每一維分量表示分配給此任務的虛擬機，初始化時，p_ij的取值范圍為0到m+1之間的隨機整數，粒子速度則由向量V表示，第i個粒子的速度表示為：

v_i＝{v_i1,v_i2,...,v_ij,...,v_in} (2)

式(2)中，-m≤v_ij≤m，vij初始化時為-m到m之間的隨機數；

定義兩個n*m的矩陣Time和S，如下所示；

相應任務與對應虛擬機之間的關系通過矩陣S中對應行列的取值表示，S_ij表示任務i在虛擬機j上是否執行，若S_ij為0，表示任務i不在虛擬機j上執行，反之為1；

其中Time_ij表示虛擬機j處理完任務i所用時間，Time_ij等于任務i的長度與虛擬機j的執行速度之比，可以得出虛擬機j上的執行時間為：

時間FTime的大小，FTime即每個虛擬機完成任務時間中的最大值，如公式(6)所示；

適應度函數就是FTime；

步驟S2.改進動態慣性權值策略：采用混合了隨機和非線性遞減的慣性權重策略，即在慣性權重非線性遞減的過程中穿插隨機慣性權重，這一隨機性并不是真正的隨機取值，而是通過借鑒模擬退火的思想將隨機取值結果分為急劇加大或縮小慣性權重兩類；

標準粒子群算法由以下兩個公式確定；

式(7)中ω是慣性權重，它的取值大小表示粒子在下一次迭代時的速度對粒子當前速度的參考比重；

在算法迭代過程中，每隔5次迭代，獲取粒子當前的適應度值和前一次適應度值設概率值p，p的取值公式如下：

式(10)中，表示粒子i到t次迭代為止的平均適應度值，表示粒子i到t次迭代為止的最優解的適應度值，每隔5次迭代時慣性權重的取值公式如下：

平時迭代中慣性權重的取值公式如下：

式(11)中random是取值為0到1之間的隨機數，式(12)中t為當前迭代次數，T_max為最大迭代次數，當t＝0時，ω取值為ω_s，當t＝T_max時，ω取值為ω_e，ω_s取0.9，ω_e取0.4，T_max取1000，式(11)和式(12)組成新的動態慣性權值策略，當t取0時，ω取值為ω_s，當t取T_max，ω取值為ω_e；

隨著迭代的進行，慣性權重從整體上看由0.9非線性減至0.4，期間每隔5 次迭代，若粒子當前的適應度值也就是任務完成的時間比上一次迭代的適應度值大時，加大慣性權重，提高搜索范圍，若當前粒子適應度值小于上次迭代時產生的適應度值，則按照一定的概率選擇加大或者減小慣性權重；

步驟S3.更新粒子位置和速度：每一次迭代，粒子的速度按照公式(7)和公式(9)～(12)進行更新，由于任務調度是離散問題，采用的是自然數編碼，按照公式(8)更新后會變為浮點數，某些維度的分量可能超出規定的取值范圍，對浮點數依次取絕對值，向下取整，取余，公式如下：

更新后的粒子速度也可能超出范圍使得粒子飛出可行范圍，因此設定粒子最大飛行速度V_max，若|v_ij|V_max，v_ij＝V_max/2，計算新粒子的適應度函數值，產生新的全局最優解和個人最優解；

步驟S4.加入混沌擾動策略：采用Logistic映射產生的混沌序列，其方程為：

z_k+1＝μz_k(1-z_k) (14)

當粒子種群迭代一定次數后，全局最優值會出現保持不變的情況，這時候對全局最優值對應的粒子采用混沌序列進行擾動，將全局最優粒子的每一維都映射到(0，1)區間，產生一個新的向量A＝(a₁，a₂，…，a_n)，向量A中每一維分量的取值范圍為(0，1)，然后利用向量A作為初始值帶入式(14)產生新的序列z₁，將z₁代入適應度函數計算并與全局最優解的適應度值進行對比，若優于當前最優解，則將z₁更新為全局最優解。