[發明專利]基于改進遺傳算法的云計算任務調度方法

有效

• 申請號: 202011086788.4
• 申請日: 2020-10-12
• 公開（公告）號: CN112181598B
• 公開（公告）日: 2022-12-09
• 發明（設計）人: 付學良;孫揚;李宏慧
• 申請（專利權）人: 內蒙古農業大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06N3/12
• 代理公司: 西安研創天下知識產權代理事務所(普通合伙) 61239
• 代理人: 郭璐

本發明公開了一種基于改進遺傳算法的云計算任務調度方法，針對云環境下的任務調度問題，采用實數直接編碼方式進行編碼，利用競爭交叉的方法初始化種群；將云任務總完成時間作為適應度函數計算種群中每個個體的適應度值；判斷是否滿足終止條件，如果滿足終止條件，則此時種群中適應度值最小的染色體個體的編碼即為最終的云任務調度方案，反之，利用三段式選擇法對種群中的優秀個體進行選擇，對經過選擇操作后的種群進行吞噬操作，對經過吞噬操作后的種群進行變異操作，直至最終種群中個體的適應度值滿足終止條件。本發明中的云計算任務調度方法明顯改善了云任務的總體完成時間，在云計算任務調度方面具有有效性。

技術領域

本發明涉及云技術領域，尤其涉及基于改進遺傳算法的云計算任務調度方法。

背景技術

云計算被定義為一種信息技術源和交付模型，用于實現對可配置計算資源(例如：網絡、服務器、存儲、應用程序和服務)共享池方便、按需的網絡訪問，可以通過最小化的管理工作或者服務提供商的交互被快速的提供和發布。云計算的交付模型分為三大類，即軟件即服務(SaaS)、平臺即服務(PaaS)和基礎設施即服務(IaaS)。隨著云計算的廣泛應用，云用戶數量以及云任務量的增長越來越快，使得云環境面臨著嚴峻的挑戰。如何合理地利用和分配云環境提供的各種資源、如何有效的調度用戶提交的海量任務以及保證云系統的負載均衡已成為云計算研究領域的熱點問題。即使在一些簡單的情況下，實現云任務的最優調度分配由于解空間大，異構資源的動態性，屬于NP完全問題。在這種類型中，我們不能在多項式時間內得到解。在云計算環境中，大量的用戶是同時需要資源的，所以調度方法應該盡快確定。

針對于云環境下的任務調度問題，國內外研究者提出了許多非啟發式和啟發式算法。例如，Max-Min算法、Min-Min算法是一類常見的非啟發式算法，粒子群算法、遺傳算法是一類常見的啟發式算法。Osman和Laporte將元啟發式定義為一個迭代生成過程，該過程整合了不同的概念，以探索和利用搜索空間來指導從屬啟發式，并且使用學習策略來構造信息以有效地找到最優解。隨著云計算環境下的任務調度算法逐步成熟，尤其是啟發式算法，逐步被廣泛應用。繼而出現了各種基于改進優化啟發式智能調度算法，例如，文獻《AnEfficient Approach to Genetic Algorithm for Task Scheduling in Cloud Com-puting Environment》提出了一種改進的單用戶作業遺傳算法，該算法通過建立適應度來鼓勵解的形成，從而使執行時間和執行成本最小化。實驗結果表明，在重載情況下，該算法具有良好的性能；文獻《A novel task scheduling approach based on dynamic queuesand hybrid meta-heuristic algorithms for cloud computing environment》提出了一種基于動態調度隊列和混合元啟發式算法的任務調度優化方案。文獻提出了兩種混合元啟發式算法，第一種是模糊邏輯與粒子群優化算法(FLPSO)，第二種是模擬退火與粒子群優化算法(SAPSO)，這兩種混合元啟發式算法與動態調度隊列混合形成TSDQ-FLPSO算法和TSDQ-SAPSO算法，它們在最小化等待時間以及隊列長度、減少最大完工時間、最大化資源利用率、最小化執行成本和改善負載平衡方面都取得了良好的性能；文獻《Improved HybridSymbiotic Organism Search Task-Scheduling Algorithm for Cloud Com-puting》提出了SA-CLS-SOS算法，該算法對共生生物搜索算法(SOS)進行簡化，將混沌局部搜索(CLS)引入到簡化的SOS中，以提高收斂速度，同時將模擬退火算法(SA)加入到SOS算法在有助于避免陷入局部極小值。文獻《A slave ants based ant colony optimization algorithmfor task scheduling in cloud computing environments》提出了一種基于蟻群優化的云任務調度算法(IACO)，該算法能夠有效地將云用戶的任務分配給云計算環境中的虛擬機。