[發明專利]一種混合多目標進化方法

在審

• 申請號: 201710205652.2
• 申請日: 2017-03-31
• 公開（公告）號: CN107016461A
• 公開（公告）日: 2017-08-04
• 發明（設計）人: 劉麗;劉濤;谷淑賢;范琦
• 申請（專利權）人: 北京科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京市廣友專利事務所有限責任公司11237
• 代理人: 張仲波

技術領域

本發明涉及互聯云計算環境中的服務組合領域，特別是指一種混合多目標進化方法。

背景技術

互聯云環境下的服務組合(簡稱：互聯云服務組合)，是要在不同地理位置的云提供商中尋找多個服務實例組合在一起，以完成用戶提交的任務，并滿足用戶多個服務質量(QoS)指標的需求，因此是一個多目標優化問題。多目標進化算法能有效處理此類問題。但現有的算法大多沒有自適應動態調整參數，并從局部進一步改善帕累托(Pareto)解的分布性，這樣導致Pareto解的分布性較差，Pareto解中存在大量相似的解，從而不能給決策者提供更多合理有效的選擇。

發明內容

本發明要解決的技術問題是提供一種混合多目標進化方法，以解決現有技術所存在的Pareto解的分布性較差的問題。

為解決上述技術問題，本發明實施例提供一種混合多目標進化方法，包括：

在第G次迭代時，根據當前迭代次數調整自適應變異中的變異因子和交叉操作中的交叉因子，基于調整后的變異因子和交叉因子，利用自適應全局DE算法對第G代種群中所有個體進行自適應變異和交叉操作產生子種群；

將第G代種群和子種群進行結合，確定結合后的種群中每個個體在多個目標下的QoS指標值，根據確定的QoS指標值計算結合后的種群中每個個體的非支配等級和擁擠度；

根據計算得到的結合后的種群中每個個體的非支配等級和擁擠度，選擇非支配等級低且擁擠度大的N個個體作為新種群，其中，所述新種群包括：非支配解集；

采用局部搜索方法對新種群中的非支配解集進行局部搜索，淘汰分布度不好的個體。

進一步地，在第G次迭代時，根據當前迭代次數調整自適應變異中的變異因子和交叉操作中的交叉因子，基于調整后的變異因子和交叉因子，利用自適應全局DE算法對第G代種群中所有個體進行自適應變異和交叉操作產生子種群之前，所述方法還包括：

在第G次迭代時，計算第G代種群中所有個體在多個目標下的QoS指標值；

根據計算得到的第G代種群中每個個體在多個目標下的QoS指標值，計算第G代種群中每個個體的非支配等級和擁擠度；

根據計算得到的第G代種群中每個個體的非支配等級和擁擠度，從第G代種群中選出非支配等級最小且擁擠度最大的個體作為最優個體。

進一步地，所述計算第G代種群中每個個體的擁擠度包括：

通過擁擠度計算公式計算每個個體的擁擠度，所述擁擠度計算公式表示為：

其中，表示第G代種群中個體x_i,G的擁擠度距離，和分別表示個體x_i+1,G和x_i-1,G在目標m下的QoS指標值，m∈(1,2,…,M)，M表示目標總數，和分別表示在目標m下最大QoS值和最小QoS值。

進一步地，所述利用自適應全局DE算法對第G代種群中所有個體進行自適應變異包括：

通過自適應變異公式對第G代種群中所有個體進行自適應變異，得到第G代種群中每個個體的變異個體所述自適應變異公式表示為：

v_i,G＝(1-β)×x_r1,G+β×x_best,G+F×(x_r2,G-x_r3,G)

其中，v_i,G表示第G代種群中個體x_i,G的變異個體，β表示平衡參數，β＝G/G_max，G_max表示最大迭代次數，x_best,G表示第G代種群中最優的個體，F表示根據當前迭代次數調整后的變異因子，x_r1,G，x_r2,G，x_r3,G是第G代種群中不同于x_i,G的個體，r1，r2，r3∈{1,2,…,N}是隨機生成的數，且r1≠r2≠r3≠i，N表示種群中個體的數目。

進一步地，在通過自適應變異公式對第G代種群中所有個體進行自適應變異，得到第G代種群中每個個體的變異個體之后，所述方法包括：

通過交叉公式對第G代種群中個體x_i,G和變異個體v_i,G進行交叉操作，得到交叉個體，所述交叉公式表示為：