[發明專利]一種帶約束云工作流調度的自適應多目標進化方法

有效

• 申請號: 201710046208.0
• 申請日: 2017-01-22
• 公開（公告）號: CN106845642B
• 公開（公告）日: 2019-03-29
• 發明（設計）人: 劉麗;張淼;李慧琦;范琦
• 申請（專利權）人: 北京科技大學;北京理工大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/10
• 代理公司: 北京市廣友專利事務所有限責任公司 11237
• 代理人: 張仲波

本發明提供一種帶約束云工作流調度的自適應多目標進化方法，能夠提高多目標進化方法的全局探測和局部開采能力。所述方法包括：S1、根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態，根據檢測到的種群在進化過程中所處的進化狀態，自適應地利用相應的個體評估策略處理約束條件，并對種群中的個體進行排序，其中，在個體評估策略中，采用約束違反處理方法來處理約束條件；S2、根據個體排序結果，從種群中選擇個體進行遺傳操作，得到子種群，其中，在進行遺傳操作時，根據種群在進化過程中所處的進化狀態自適應地調節進化參數。本發明適用于解決帶約束的多目標優化問題，并可應用于云計算環境中工作流調度技術領域。

技術領域

本發明涉及解決帶約束的多目標優化的問題，并應用于云工作流調度技術領域，特別是指一種帶約束云工作流調度的自適應多目標進化方法。

背景技術

云環境下的工作流調度(簡稱：云工作流調度)是尋找合適的云資源來執行工作流任務，并滿足用戶的服務質量需求。云工作流調度問題是一個帶約束的多目標優化問題，多目標進化算法能有效處理此類問題。但現有技術中，大多是簡單地利用靜態的懲罰函數來處理約束條件，這樣容易導致早熟收斂，甚至進入不可行的搜索空間，例如：

現有技術一，通過利用帕累托(Pareto)熵信息和Pareto差熵信息來評估多目標粒子群算法中種群的多樣性以及進化狀態，并且以此為反饋信息來設計進化策略，使得算法具有更好的收斂性和多樣性。

現有技術二，在NSGA-II算法的基礎上進行了改進，通過離散化整個Pareto最優前沿，找到一些良好分布的參考點，在算法的進化過程中以這些點為搜索方向，找到與提供的參考點集相關聯的Pareto最優解或Pareto最優解附近的解，使得到的解集具有更優的收斂性和多樣性。

現有技術一和現有技術二，雖然可以使算法得到的非支配解集具有更好的收斂性和多樣性，但其針對的是無約束的多目標優化問題。對于云環境下的工作流調度問題是一個帶約束的多目標優化問題，在處理此類問題時，常用的方法是基于多目標進化算法，使用靜態的懲罰函數將帶約束優化問題轉化為無約束優化問題，懲罰函數如果太小，一些非可行解的適應度值將高于大部分可行解，種群很有可能會朝一個非可行的搜索空間進化；但懲罰函數如果太大，許多更優的個體將會被排除，從而導致早熟收斂，綜上，現有的多目標進化算法在使用靜態懲罰函數處理約束條件時容易陷入局部最優。

發明內容

本發明要解決的技術問題是提供一種帶約束云工作流調度的自適應多目標進化方法，以解決現有技術所存在的多目標進化算法在使用靜態懲罰函數處理約束條件時容易陷入局部最優的問題。

為解決上述技術問題，本發明實施例提供一種帶約束云工作流調度的自適應多目標進化方法，包括：

S1、根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態，根據檢測到的種群在進化過程中所處的進化狀態，自適應地利用相應的個體評估策略處理約束條件，并對種群中的個體進行排序，其中，在個體評估策略中，采用約束違反處理方法來處理約束條件；

S2、根據個體排序結果，從種群中選擇個體進行遺傳操作，得到子種群，其中，在進行遺傳操作時，根據種群在進化過程中所處的進化狀態自適應地調節進化參數。

進一步地，所述根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態包括：

若種群中沒有Pareto解，則種群在進化過程中所處的進化狀態為初始狀態。

進一步地，所述根據Pareto解的個數和Pareto熵檢測種群在進化過程中所處的進化狀態包括：

若種群中Pareto解的個數小于種群大小，則種群在進化過程中所處的進化狀態為收斂狀態；或，