質量感知的多目標云制造服務組合優化算法

劉桂森,賈兆紅,2+

(1.安徽大學 計算機科學與技術學院,安徽 合肥 230601;2.安徽大學 計算智能與信號處理教育部重點實驗室,安徽 合肥 230601)

0 引言

云制造3.0系統為制造業與信息通信技術的深度融合提供了智能制造系統新模式[1]。云制造融合了網絡化制造和服務、云計算、高性能計算、物聯網等技術,實現硬件設備、計算系統、軟件、數據、知識等分類資源的統一制造、集中管理和運營,為制造全生命周期過程提供可隨時獲取、按需使用、安全可靠、優質廉價的各類制造服務,是一種面向服務的網絡化制造模式[2]。

在云制造環境中,用戶將制造任務提交到服務平臺,服務平臺通過分析任務復雜度分解任務,并根據用戶需求從平臺中選擇符合的服務進行組合,以共同執行用戶任務[3]。然而,云計算的服務提供商不斷提供功能相似但質量不同的云服務[4],如何在大量云服務中選擇組合以滿足用戶的服務質量(Quality of Service,QoS)期望,即QoS感知云服務組合(Quality of Service—Cloud Service Composition,QoS-CSC)問題[5],成為計算服務供應中的關鍵問題[6]。

例如,隨著現代社會的發展,汽車的私人定制逐漸成為一種趨勢。一款車包括基礎、外部配置、內部配置、安全配置、特色配置5部分?；A部分包括汽車的發動機、變速箱、底盤三大件,是汽車的主要組成部分;外部配置包括天窗類型、行李架、輪轂等;內部配置包括方向盤、液晶儀表等;安全配置包括主動安全和被動安全;特色配置指車載冰箱、車內香氛裝置等。汽車的每個模塊及部件均有多家供應商,每家供應商提供的零部件都具有相同功能但功能屬性不同,如成本、時間、可靠性、可用性、信譽度等QoS,如何從不同供應商中選擇合適的廠家零部件,以完成汽車的私人定制,滿足用戶需求,是云制造服務組合(Cloud Manufacturing Service Composition,CMSC)的關鍵。

隨著云環境中類似的單一服務越來越多,CMSC問題也成為NP-hard(non-deterministic polynomial—hard)問題[7]。由于數學模型的非線性特性以及大量的候選服務,采用線性和整數規劃等精確方法通常不可行。BAO等[8]用有限狀態機來規定Web服務的合法調用順序,提出一種基于樹修剪的改進算法來創建Web服務組合樹,生成所有可行的執行路徑后,采用簡單加權技術選擇最佳解決方案;CHEN等[9]將帶有約束的多目標優化問題改成兩個主要目標,即最小QoS風險(使QoS目標與用戶約束之間的差異最小)和最大化QoS性能;JIAN等[10]提出改進的鳥群優化算法,在基本鳥群優化的基礎上引入二階震蕩方程和鳥類的歷史位置記憶來最小化服務組合的整體時間成本;ZHOU等[11]提出一種混合人工蜂群算法,將CMSC問題轉變為雙目標問題求解;LIANG等[12]將CMSC分為上升和下降的QoS標準,采用具有雙重限制的服務選擇模型進行優化;YANG等[13]提出一種增強型灰狼優化(Enhanced Multi-Objective Grey Wolf Optimizer,EMOGWO)算法,同時優化QoS與能源消耗兩個目標。另外,遺傳算法(Genetic Algorithm,GA)[14]、粒子群優化(Particle Swarm Optimization,PSO)算法[15]、MOEAQI(multi-objective evolutionary algorithm framework for service selection with QoS constraints and inter-service correlations)算法等也用于求解服務組合問題,但是這些算法往往通過加權組合將多目標問題簡化為單目標問題,很少考慮同時優化4個或4個以上目標。在多維空間中平衡開發與探索面臨諸多挑戰[16],如非支配解的指數增長所帶來的收斂壓力損失[17],以及無效的多樣性維持機制所導致的反收斂現象[18]。本文針對同時優化時間、成本、可靠性、可用性、信譽度的服務組合問題,提出一種基于自適應選擇和反向學習策略的進化算法(Evolutionary Algorithm based on Adaptive selection and Reverse learning Strategy,ARSEA),首先根據QoS對服務進行聚類,剔除效果比較差的服務,其次為目標空間中的參考向量分配近鄰和遠鄰參考向量,然后采用反向學習策略增加初始種群的多樣性,在迭代過程中通過動態調整選擇概率自適應選擇參與交配的父代個體,以統一算法的多樣性與收斂性。

1 問題描述

1.1 相關定義

在云制造環境下,不同于單一的制造任務,加工前為了提高產品質量,需將復雜的制造任務分解成多個子任務,根據每個子任務的功能需求生成多個候選服務CS,即一組功能相同但非功能屬性不同的服務,構成相應的云服務集CSS,再從相應的候選云服務集中獲得每個子任務的制造服務[19]。在此基礎上,基于邏輯序列所選CS組成的組合制造服務(Composite Manufacturing Service,CMS)可以同時滿足功能和QoS要求。因此,復雜制造任務的執行過程分為4個步驟:①分析請求和分解任務;②搜索和匹配;③組成服務和選擇優化;④執行和反饋任務。針對步驟3,給出以下定義。

定義1復雜制造任務。ZT={T1,T2,…,Ti},ZT為復雜制造總任務,Ti為所分解的第i個子任務,i=1,2,…,n。

定義3服務質量。QoS={q1,q2,…,qr},QoS表示CS的非功能屬性,如時間、成本、效率或可用性,qr為CS的第r個服務質量屬性值,r=1,2,…,m。

其中,本文擴展了服務質量的屬性個數。

1.2 服務質量模型

由于QoS由多個側重于不同方面的非功能度量組成,很難有所有度量值同時最佳的解決方案,往往采用一組各度量值相互權衡的Pareto最優解,即改進其中一個度量值可能導致其他度量值惡化。例如,時間和成本通常是一對相互矛盾的屬性,縮短時間可能增加成本。鑒于可測量性的重要性,本文針對CMSC的順序、平行、選擇和循環4種基本復合結構,研究不同結構復合服務的聚合QoS公式(如表1),對這5個QoS進行組合評估,使整體QoS值達到最優以滿足用戶要求。對5個屬性指標的描述如下:

表1 不同結構復合服務的聚合QoS公式

(1)時間 從用戶提交制造任務到該任務完成并返回結果的時間。

(2)成本 當所執行的云制造服務完成后,服務提供商向用戶收取的服務費用。

(3)可靠性 在給定的時間和條件下,成功執行制造任務的能力。

(4)可用性 在云制造服務平臺中,用戶在一定時間內成功調用制造服務的能力。

(5)信譽度 指服務提供商完成該制造任務的信譽履約度。

根據文獻[15],可以將平行結構、選擇性結構和循環結構轉化為順序結構。另外,由于聚合QoS標準值尺度不同會嚴重影響基于分解的多目標進化算法(Multi-Objective Evolutionary Algorithm,MOEA)標度函數,所有聚合的QoS值均在[0,1]內歸一化?？煽啃?、可用性、信譽度屬于正屬性,時間和成本屬于負屬性。對于QoS的正屬性,較大的值性能更好;對于負屬性,較小的值性能更好。正準則和負準則的歸一化方法如下:

(1)

Q(qosr(x)=(Q1(qos1(x)),Q2(qos2(x)),Q3(qos3(x)),
Q4(qos4(x)),Q5(qos5(x)))。

s.t.

x∈Ω。

(2)

其中:Q1～Q5分別表示時間、成本、可靠性、可用性和信譽度指標;Ω表示決策空間。

2 ARSEA算法

2.1 算法框架

本文所提的ARSEA算法流程如下:

算法1ARSEA框架。

輸入:種群規模N、權重向量的鄰居向量個數H、初始交配選擇的概率Q、間隔代數L、變異概率P。

輸出:歸檔種群EP。

步驟1過濾候選服務。

步驟2在目標空間中生成均勻的參考向量,并為每個參考向量確定其近鄰參考向量和遠鄰參考向量。

步驟3種群初始化。

步驟4采用反向學習策略進一步優化初始種群。

步驟5迭代:

(1)對種群中的每個個體采用選擇策略,然后交叉、變異得到新個體Y,更新近鄰解。

(2)將種群中的非支配個體加入歸檔種群EP,并更新歸檔種群EP。

(3)采用概率更新策略改變交配選擇概率。

首先采用K-means聚類過濾候選服務;然后在目標空間生成一組均勻的參考向量,根據向量之間的余弦角度找出每個向量的近鄰向量和遠鄰向量;其次,將初始化種群中的個體與參考向量一一對應。步驟4采用反向學習策略生成反轉的種群,通過比較反轉種群與原初始種群產生最終的初始種群,以提高種群的多樣性。在迭代搜索過程中,先通過選擇策略從父代選出優秀個體參與交配,再根據Pareto方法從新生個體與其他個體中選擇較優的解放入歸檔種群EP,根據新解的貢獻度自動更新父代選擇概率來平衡全局開發與局部探索。

2.2 過濾候選服務

隨著智能制造的高速持續發展,云制造平臺中的服務越來越多,在CMSC的方案中,可供選擇的候選服務也越來越多,需要根據候選服務的QoS對服務進行選擇過濾以縮短求解時間,而聚類方法有助于提升服務選擇的效率。K-means聚類按照類內相似度最大化和類間相似度最小化原則對數據樣本進行分組,是最常用的無監督聚類方法之一。因此本文基于K-means對候選云服務集進行聚類,并對候選服務進行等級劃分,在得到的每一簇中去除等級最差的候選服務,如算法2所示。

算法2過濾候選服務。

輸入:決策空間信息S1、聚類的簇數Nc(默認與目標數一致)。

輸出:決策空間信息S。

步驟1隨機選擇Nc個候選服務作為簇的中心。

步驟2對于每一個簇,計算簇的質心。

步驟3對于每個候選服務,計算其與Nc個簇質心的歐式距離,將其加入距離最小的簇中。

步驟4再次計算各個簇的質心,如果質心位置不變,則執行步驟5,否則轉步驟3。

步驟5對每一個簇中的候選服務,采用式(3)計算函數d并進行排序,剔除本簇后10%的候選服務。

2.3 反向學習策略

由于CMSC為NP-hard問題,在算法初始階段采用如算法3所示的反向學習策略改進初始種群在解空間的分布,以提高算法的多樣性。首先,在每個子任務候選云服務集中計算每個候選服務與最優服務之間的距離

(3)

算法3反向學習。

輸入:初始種群P1、決策空間信息S。

輸出:種群P。

步驟2對P1中的每個體,計算每個候選服務在上述排序中的位置,選擇其相反位置的候選服務組成新的個體。

步驟3由新的個體組成新的初始種群P2。

步驟4利用切比雪夫法則比較并保留較優的個體,得到最終的初始種群P。

2.4 選擇策略及概率更新策略

本文采用算法4所示的選擇策略。在選擇父代重組交配時,相近個體間交配有利于算法的局部開發能力,較遠個體間交配有利于算法的全局探索能力,而且在選擇相近個體時,從其近鄰范圍內的非支配個體中挑選父代更有利于算法收斂。另外,通過自適應改變交配選擇概率,算法可以自動調整搜索方向。

算法4選擇策略。

輸入:初始交配選擇的概率Q。

輸出:交配父代x1,x2。

步驟1如果產生的隨機數大于Q,則隨機選擇其遠鄰向量對應的個體作為x1,x2。

步驟2如果產生的隨機數小于等于Q,則先確定其近鄰向量對應的個體群中非支配解的個數n,如果n>2,則隨機選擇個體群中的非支配個體作為x1,x2,否則隨機選擇個體群中的個體作為x1,x2。

在種群進化過程中,算法進行全局和局部搜索的需求是可變的,因此本文采用如圖1所示的概率更新流程圖更新交配選擇概率,以平衡算法的開發和探索能力。早期需要提高算法的全局探索能力,隨著迭代的進行需要更好的局部開發能力,因此為了在開發和探索之間取得平衡,采用式(4)自適應地調整交配概率,使算法間隔一定代數后,可以自動調整Q的大小,其中n1和n2分別為前L代種群中由近鄰和遠鄰交配產生的新個體數。

(4)

2.5 算法的時間復雜度分析

3 仿真實驗及結果分析

為了評估所提ARSEA的性能,選用4種對比算法,即具有對抗性搜索的自適應雙種群進化算法(Adaptive Dual-population evolutionary Paradigm with Adversarial Search,ADPAS)[20]、EMOGWO算法、基于支配和分解的多目標進化算法(Multi-Objective Evolutionary Algorithm based on Dominance and Decomposition,MOEA/DD)和基于參考向量引導的多目標優化進化算法(Reference Vector guided Evolutionary Algorithm for many-objective optimization,RVEA)[21],其中ADPAS和EMOGWO是兩種解決CMSC最先進的算法,MOEA/DD和RVEA是兩種最新提出的經典MOEA。另外對ARSEA的策略進行了驗證。

3.1 實驗設計

采用15個隨機生成的測試算例驗證ARSEA在各種條件下的探索和開發性能,算例的因素和取值范圍如表2所示。每個實例由工作流中的子任務和候選服務組成,代表不同的CMSC場景。優化目錄m的數量設置為5,子任務和候選服務分別記為T和S,例如T20S60表示有20個子任務,每個子任務有60個候選服務、5個優化目標。

表2 算例的因素和取值范圍

每個候選服務均有時間、成本、可靠性、可用性、信譽度QoS標準,并隨機生成一個綜合QoS數據集,其取值范圍如表3所示。所有算法均使用C++編程,在Core i5、3.40 GHz處理器和16 GB RAM的Windows 10 PC上運行。

表3 QoS數據取值范圍

3.2 參數設置

采用田口法為ARSEA選取合適的參數。ARSEA考慮的主要參數包括交配選擇概率的更新代數L、鄰居向量的個數H和變異概率P,取值范圍如表4所示。根據田口法設計了9個參數組合實例組,如表5所示。

表4 ARSEA參數取值范圍

表5 參數組合

采用反轉世代距離IGD評估具有不同參數組合的ARSEA性能,用15個測試實例中每個參數組合的ARSEA的平均IGD值作為響應變量,在MINITAB 19版本上運行。實驗結果如圖2所示,其中x軸表示不同因素對應的水平,y軸表示均值響應值,平均值越小表示對應組合參數的ARSEA效果越好。從圖2可見,最佳參數值為L=3,H=15,P=0.1。

ARSEA其他參數的設置與4種比較算法相同,即種群規模N=126,交叉概率設置為1.0,迭代次數為500。初次交配選擇的概率P1=0.3,以確保搜索開始時ARSEA具有更好的勘探能力。對于每個實例,每個算法重復運行30次,取其平均值作為最終的統計結果。

3.3 評價指標

采用如下3個評價指標:

(1)非支配解集規模NNS表示每種算法獲得的非支配解決方案的數量,獲得的非支配解決方案越多,為決策者提供的選擇越多,算法的多樣性也就越好。

(2)反轉世代距離IGD描述非支配解集與Pareto邊界的接近程度,用于評估解集的收斂性和多樣性[22],定義為

(5)

式中:υ為某一種比較算法獲得的非支配解集;ρ為所有算法獲得的非支配單個集合的并集。IGD值越小,算法的收斂性和多樣性越好,越接近真實的Pareto前沿。

(3)間距度量Spacing反映非支配解集前沿分布的均勻性[23],定義為

(6)

3.4 實驗結果

ARSEA中采用的策略包括反向學習策略、選擇策略和概率更新策略。首先設計ARSEA的變體驗證所提策略的有效性,其次將ARSEA與其他先進算法進行比較。在表6～表10中,第1列均為實例編碼,每個實例組的最佳結果用粗體顯示。

3.4.1 反向學習策略的性能

本文設計了不含反向學習策略的ARSEA變體ARSEA-NRL(ARSEA-non-reverse learning)與ARSEA進行比較,結果如表6所示。

表6 在IGD和NNS下反向學習策略的驗證實驗結果

從表6的NNS值可見,ARSEA-NRL在5個實例上勝過ARSEA,ARSEA在其他10個實例上可以獲得更多的非支配解,而且ARSEA在大規模服務組合問題上的優勢更加明顯。另外,從IGD值可見,ARSEA明顯優于ARSEA-NRL,說明ARSEA的解質量更好,更接近問題實際的Pareto前沿,表明所提反向學習策略有益于提高算法性能。

3.4.2 選擇策略的性能

設計采用隨機選擇方法的ARSEA變體ARSEA-R(ARSEA-random)進行驗證,實驗結果如表7所示。

表7 選擇策略的驗證實驗結果

從表7可見,ARSEA在IGD和NNS上分別有3個實例稍遜于ARSEA-R,而在其他10個實例上,ARSEA全部優于ARSEA-R,表明ARSEA不但能夠找到質量更好的解,而且能夠幫助算法提高解的多樣性。

3.4.3 概率更新策略的性能

將ARSEA算法中的選擇概率分別設置為固定值0.2,0.5,0.8,對應算法分別記為ARSEA-A,ARSEA-B,ARSEA-C,實驗結果如表8所示。

表8 概率更新策略的驗證實驗結果

由表8可見,ARSEA在10個實例上的NNS值較大,其他3個變體在5個實例上具有優勢,說明ARSEA可以在大部分實例上找到更多的非支配解。雖然在小規模服務組合問題中,ARSEA的IGD值較其他算法沒有明顯優勢,但是在較大規模實例上的結果都是最好的,表明自適應調整選擇概率可以在算法的開發和探索之間取得更好的平衡。

3.4.4 算法整體性能比較

4種對比算法與ARSEA的比較結果如表9和表10所示。

表9 5種算法的IGD比較結果

續表9

表10 5種算法的間距度量Spacing比較結果

由表9可見,雖然在3個小規模的服務組合實例中,ARSEA的結果不如其他算法,但是其他實例上ARSEA的結果都是最好的,表明ARSEA在求解CMSC上能夠找到更多且質量更好的解。由表10可見,ARSEA在所有測試實例上的Spacing值最小,說明ARSEA找到的解分布更均勻,多樣性更好。

為了直觀地比較5種算法的性能,圖3～圖5展示了5種算法的IGD、Spacing值和計算時間的對比結果。ARSEA的計算時間最少,其在圖3中的IGD平均值最低,在圖4中的曲線最靠下,表明在收斂性和多樣性上ARSEA較其他4種算法都具有絕對優勢。

較低的S值表明ARSEA得到的歸檔種群在Pareto前沿上的分布更加均勻,各個目標之間比較平衡,多樣性更好;較低的IGD值表明ARSEA得到的解的收斂性和多樣性較好,說明ARSEA在CMSC 5個目標同時優化問題上可以得到較好的解決方案。而且,ARSEA求解服務組合方案的用時最少,說明ARSEA中過濾候選服務的方法很適合解決具有大量候選服務的CMSC問題。從實驗結果整體來看,ARSEA比其他算法在CMSC問題上得到的解更接近問題真實的Pareto前沿,而且解的均勻性更好。算法求解多目標CMSC問題得到的每個非支配解,經過解碼后都是一種制造服務的組合方案,用戶可以根據需要選擇歸檔種群中的方案執行制造服務,使組合服務的整體QoS達到最優。

從15組實例的每種子任務中各選2組,組成6組實例,繪制出ARSEA在這6組實例上IGD值的箱線圖,如圖6所示,其中每組圖中x軸分為5組,每組代表的算法分別是ARSEA,ADPAS,EMOGWO,MOEA/DD,RVEA,每組x軸下方是服務組合的5個屬性,通過這些圖可以明顯看出5個算法之間的差異,ARSEA雖然在部分算例的前兩個屬性指標上稍差,但是另外3個屬性指標值遠小于其他對比算法。因此,綜合圖3和圖4可以看出,ARSEA的整體性能較好,其可以獲得更好的解決方案。

在汽車的私人定制過程中,用戶可以選擇自己的個性化零部件,每個零部件都有若干服務提供商,這些服務提供商具有相同的功能屬性和不同的非功能屬性(如時間、成本、可靠性等)。從不同供應商中選擇合適的廠家生產零部件來完成汽車的私人定制,使非功能屬性最優,是一個多目標CMSC優化問題,可以采用ARSEA解決該問題。ARSEA的求解時間最少,效率最高,所求得的非支配解集的多樣性和收斂性較好,即汽車私人定制的解決方案數最多,給用戶的選擇最多,其求得的解決方案在整體QoS上優于其他算法。因此,采用ARSEA選擇合適的供應商生產零部件,使用戶整體的時間、成本、可靠性等最優,用戶滿意度最高。

4 結束語

本文從多目標優化的角度研究CMSC問題,提出基于自適應選擇和反向學習策略的進化算法ARSEA,采用K-means聚類剔除較差的候選服務,采用反向學習策略增加種群的多樣性,將參考向量分為近鄰和遠鄰參考向量,利用選擇策略和自適應調整的概率更新策略更好地平衡算法的開發與探索性能,從而為用戶提供更為優質的服務組合。隨著全球生態環境問題越來越嚴峻,綠色生態、可持續發展變得愈加重要,未來的研究將關注制造服務提供商的環境保護能力,將電價函數等加入優化目標,考慮結合服務提供商能耗的CMSC優化問題。