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

有效

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

本發明提出了一種面向云計算任務調度的改進粒子群算法。包括4個步驟：首先對粒子采用自然數編碼，以任務完成總時間作為適應度函數，將粒子與任務調度相關聯，然后改進動態慣性權值策略，平衡全局和局部搜索能力，接著更新粒子位置和速度，規范取值范圍，最后加入混沌擾動策略使算法盡可能尋找更優解，從而提高算法后期收斂精度。與標準粒子群算法相比，本發明所述算法在云計算任務調度中具有很強的全局開發能力，在算法的前期不斷探索全局最優解，且在后期也具有良好的局部探索能力。同時，由于加入了混沌擾動策略，不斷地隨機改變粒子的位置信息，使得算法能夠盡可能跳出局部最優解，從而最終收斂的結果更好。

技術領域

本發明涉及云環境下任務調度策略領域，尤其涉及一種面向云計算任務調度的改進粒子群算法。

背景技術

數據大爆炸之后，與數據相關的計算任務變得十分繁重。云計算的思想便是來源于如何高效地處理這些龐大的數據，在一臺計算機資源不足以在規定時間內完成計算任務的情況下，可以將計算任務交由由大量硬件和軟件資源共同構成的資源池處理，并以服務的方式通過網絡提供給用戶。云計算的基本原理就是利用互聯網將大而難的任務分解成較小的任務，并發送到服務器上進行分布式計算、分析和總結。

如何高效合理地將任務集分配到資源池中的虛擬機上便是任務調度，這是云計算中的關鍵技術之一，許多啟發式算法應運而生，諸如人工蜂群算法，飛蛾優化算法，粒子群算法等。粒子群算法由于可供修改的參數少、早期收斂速度快，已經被許多學者應用于云計算任務調度中。但傳統的標準粒子群算法對粒子在上一次迭代中的速度的依賴程度一直保持不變，缺少靈活性。由于慣性權重保持不變，雖然前期收斂速度快，但后期局部搜索能力不足，導致算法收斂速度慢，求解精度不高，并且容易陷入局部最優解，所以本發明公開一種面向云計算任務調度的改進粒子群算法，以獲得更好的任務調度結果。

發明內容

本發明一種面向云計算任務調度的改進粒子群算法所要解決的問題：針對標準粒子群算法后期收斂速度慢，容易陷入局部最優，收斂精度差的缺陷，本發明在算法中采用混合了隨機和非線性遞減慣性權重的策略，加快算法后期收斂速度，同時借鑒模擬退火中“以一定概率接受較差解”的思想，提高了算法的全局搜索能力，最后加入混沌擾動策略使算法盡可能尋找更優解，從而提高算法后期收斂精度。

本發明的技術方案包括以下步驟：

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

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

式(1)中1≤p_ij≤m，每一維分量表示分配給此任務的虛擬機，比如最優解若為(1,4,2,…,m,…)，則表示虛擬機1接受任務1，虛擬機4接受任務2，虛擬機2接受任務3，初始化時，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，如下所示。