一種改進SLO的多目標服務優化組合方法①

海 燕, 徐 芯, 劉志中

(1.華北水利水電大學信息工程學院,河南 鄭州 450046;2.煙臺大學計算機與控制工程學院,山東 煙臺 264005)

0 引 言

隨著云計算的持續發展及用戶需求不斷增加,服務組合在網絡技術研究領域發揮著愈加重要的作用。龐大的候選服務數量、相互沖突的優化目標給服務優化組合問題帶來了巨大的挑戰。因此,如何高效地從海量組合服務方案中選擇最優的組合服務,是服務計算領域中一個重要的研究問題。最初服務優化組合問題被建模為單目標問題[1],或者將多個目標轉化為單目標問題[2]。隨著多目標優化技術的進步,越來越多的研究致力于使用群體智能算法(例如:人工蜂群優化算法[3]、粒子群優化算法[4]、蟻群優化算法[5]等)來解決服務優化組合問題。針對服務組合的多目標性與用戶需求的復雜性,設置多個相互沖突的優化目標及約束條件,在此基礎上,改進社會學習優化算法(Social Learning Optimization Algorithm, SLO)中的關鍵操作算子,引入Sigmoid擾動學習因子,最終形成一種基于改進社會學習優化算法的多目標服務優化組合方法(improved Social Learning Optimization-multi-objective service composition optimization, ISLO-MOSCO),最后通過實驗驗證了該方法的有效性。

1 多目標服務優化組合問題模型

表1 組合服務的QoS計算方法

選取在服務組合中相互對立且較為重要的三個QoS屬性作為優化目標,依次為成本、響應時間與可靠性。根據表1將服務優化組合問題建模成多目標優化問題,規定全局約束條件為總費用不超過Cmax,響應時間不超過Tmax,可靠性不低于Relmin,則多目標服務優化組合問題的數學模型如式(1)所示,其中,x={x1,x2,...,xn}是決策空間Ω中的n維決策向量。

minF(x)={f1(x),f2(x),f3(x)}s.t.x∈ΩfC(x)Relmin

(1)

為了評估解的優劣,采用Pareto支配概念計算多目標優化算法的適應度值[3]。如果Individual1?Individual2,則認為Individual1優于Individual2,則該解在種群中的支配解數dom(i)加1,該解的適應度值計算方式如式(2):

(2)

2 基于改進SLO的多目標服務優化組合算法

2.1 改進的SLO算法

2.1.1 組合服務編碼模型

2.1.2 微空間內的操作

SLO算法的微空間模擬人類社會智能演化過程受遺傳變異影響的現象,通過選擇操作、交叉操作和變異操作來實現遺傳變異的進化過程。對于多目標服務優化組合問題,采用輪盤賭的選擇方法作為選擇算子,另外兩個操作定義如下。

2.1.2.1 交叉操作

設Xi=(xi1,...,xik,...,xin)與Xj=(xj1,...,xjk,...,xjn)為任意兩個個體,i,j∈{1,...,N},N為種群規模,且i≠j,n表示服務組合流程中子任務的序號,xik,xjk∈{1,2,3,...,m}。利用rand函數生成1～m之間的隨機交叉點位,r為(0,1)的隨機數,pc為交叉率,若r

(3)

圖1 組合服務編碼方式

2.1.2.2 變異操作

設Xi=(xi1,…,xik,…,xin)為種群中任一個體,i∈{1,…,N},N為種群規模,在當前個體的染色體中,根據變異率pm隨機選擇一個變異基因點,假設xik為變異基因點,xik∈{1,2,3,…,m},利用隨機函數在{1,2,3,…,m}范圍內隨機生成一個新的基因xil替換變異個體中變異點的基因xik。變異操作如式(4):

(xi1,…,xil,…,xin)

(4)

2.1.3 學習空間內的操作

2.1.3.1 觀察學習

(5)

2.1.3.2 模仿學習

(6)

2.1.4 信仰空間內的操作

2.1.4.1 知識更新

知識更新操作主要是當學習空間得到新的優秀個體時,對信仰空間內的個體實現知識的更新與積累。更新操作公式如式(7):

α=N*β

(7)

式(7)中,α指當前群體中需要選擇優秀個體的數量;N表示種群規模;β為選擇概率。

2.1.4.2 文化影響

文化影響操作是使用信仰空間內的知識影響微空間內非支配排序等級較低的個體,引導群體向較好的方向演化,提高算法的收斂速度,公式如式(8):

(8)

式(8)中,Xi=(xi1,...,xik,...,xin)為種群中的任一個體,i∈{1,...,N};aj為信仰空間中的任意個體,j∈{0,...,α},α為信仰空間內的個體數量;t是當前迭代次數;ε為更新間隔參數。

2.1.5 修正操作

通過觀察學習與模仿學習產生的新個體中,由于所有個體的每一維變量的取值都為子任務對應的候選服務的序號,若第k維變量的值超過了其取值范圍,則根據以下公式修正該維變量的值,其中m為子任務對應的候選服務總個數。

(9)

2.2 ISLO-MOSCO算法整體流程

針對服務優化組合問題的特點對SLO算法進行了改進,形成了一種面向多目標服務優化組合問題的求解方法。綜上,基于改進社會學習優化算法的服務組合優化算法(ISLO-MOSCO)具體實現步驟如下:

Step1.設置算法參數:初始化算法參數,包括種群規模N,最大迭代次數Max_Iteration,變異概率Pm,交叉概率Pc,信仰空間內的個體數量α和更新間隔參數ε,同時初始化QoS屬性。

Step2.初始化種群對種群進行非支配排序。

Step3.在微空間內,對個體進行選擇操作、交叉操作以及變異操作,并保留優秀個體。

Step4.在學習空間內,對個體進行觀察學習操作與模仿學習操作,并保留優秀的個體。

Step5.在信仰空間內,利用學習空間得到的優秀個體對信仰空間內的個體進行知識的更新與積累,并使用信仰空間內的知識影響微空間內非支配排序等級較低的個體。

Step6.重復Step3-Step5,直至達到最大迭代次數Max_Iteration。

3 仿真實驗及結果分析

為了驗證所提多目標服務優化組合方法的性能,實驗主要從以下四個方面展開:(1)驗證所提方法在不同迭代次數下求解多目標服務優化組合問題的可行性;(2)驗證所提方法在不同問題規模下的適應性;(3)所提ISLO-MOSCO算法與其他算法的性能對比;(4)驗證對SLO算法提出的改進策略的有效性。

3.1 實驗設置

基于上述提出的多目標服務優化組合方法,設置每個候選服務都具有三個QoS屬性,即成本、響應時間、可靠性。實驗采用隨機數據集,將每一組實驗分別運行20次,選取20次測試結果的平均值作為最終實驗結果。

實驗使用Java編程語言實現了基于改進SLO的多目標服務優化組合方法,其中交叉概率設置為0.85,突變概率設置為0.05,知識更新選擇比例設置為10%,文化影響更新間隔設置為5。實驗環境配置為PC,11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz 2.42 GHz,Windows 10(64bit)。

3.2 驗證不同迭代次數下ISLO-MOSCO的性能

設置子任務數量固定為10,將子任務對應的候選服務數量分別設置為10,20,50,100,200。執行ISLO-MOSCO算法,記錄算法在不同迭代次數下的運行時間。實驗結果如圖2所示,橫坐標表示算法的迭代次數,縱坐標表示算法的運行時間,m表示每個子任務對應的候選服務的數量。

圖2 不同候選服務數量下的運行時間

從圖 2可以看出,ISLO-MOSCO算法的運行時間隨迭代次數的增加而增加,存在上下波動的情況。ISLO-MOSCO算法的運行時間與不同的候選服務數量沒有明顯的相關關系,此外,隨著候選服務數量的增加,算法的運行時間并沒有呈指數級增長。因此,可以得出ISLO-MOSCO算法對于解決多目標服務優化組合問題是可行的。

3.3 驗證不同問題規模下ISLO-MOSCO的性能

通過設置不同的子任務的數量和不同的子任務對應的候選服務數量,從而設置不同的問題規模。設置五種問題規模,其子任務數量和候選服務數量分別為5*10,10*20,20*50,30*100,50*200。迭代次數設置為1000,執行ISLO-MOSCO算法,記錄算法在不同問題規模下求解多目標服務優化組合問題得到的組合服務解集的QoS值。實驗結果如圖 3所示,cost,time,reliability分別表示組合服務解集的成本、響應時間與可靠性。

圖3 不同問題規模下解集的QoS值

從圖 3可以看出,ISLO-MOSCO求解多目標服務優化組合問題得到的組合服務解集的成本與時間隨問題規模增大而減小,這是因為當問題規模增大時,構成組合服務的數量也在增大,可以給算法提供更多更好的選擇。當問題規模由5*10增加到20*50時,解集的可靠性不斷增加。當問題規模由20*50增加到50*200時,解集的可靠性不斷降低,表示解集的可靠性隨問題規模增加而具有一定波動性。服務組合解集的成本與響應時間沒有隨問題規模的增大而指數性減少,甚至有所增大,可靠性也沒有隨問題規模的增大而指數性降低。因此,可以得出ISLO-MOSCO算法對于解決多目標服務優化組合問題具有一定的適應性。

3.4 ISLO-MOSCO算法性能對比

采用NSGA-II[8],GA[9],MOEA/D[10]和ISLO-MOSCO算法求解相同的多目標服務優化組合問題。將四種算法的子任務數量設置為10,子任務對應的候選服務數量設置為50,初始種群大小設置為100,記錄四種算法在不同迭代時間下搜索到的組合服務方案解集的適應度值,實驗結果如圖 4所示。

圖4 算法性能比較

從圖 4可以看出,ISLO-MOSCO比NSGA-II算法、GA算法和MOEA/D算法有更快的收斂速度,并且ISLO-MOSCO得到的最終解優于其他三種算法?；谏鲜鰧嶒灲Y果可以得出結論,對SLO提出的改進是有效的,ISLO-MOSCO對于多目標服務優化組合問題是有效的。

3.5 驗證提出的SLO改進策略的有效性

在未改進的SLO中,修改其初始化方式、目標函數以及約束條件,使其能夠解決多目標服務優化組合問題,將SLO與ISLO-MOSCO進行比較。將兩種算法的子任務數量設置為10,子任務對應的候選服務數量設置為50,初始種群大小設置為100,迭代次數設置為1000,記錄兩種算法在不同問題規模下搜索到的組合服務解集的適應度值,實驗結果如圖 5所示。

圖5 驗證SLO改進策略的有效性

從圖 5可以看出,ISLO-MOSCO得到的解優于SLO。隨著問題規模的增加,ISLO-MOSCO與SLO算法得到的解集的QoS值的差距不斷增大?；谏鲜鰧嶒灲Y果可以得出結論,針對SLO算法提出的改進策略是有效的。

4 結 語

在考慮服務組合特點與用戶需求的情況下,如何為用戶選擇最優組合服務方案這一關鍵難題,主要可以從以下兩個方面進行總結:(1)基于社會學習優化算法,設置多個相互沖突的優化目標、約束條件及取值空間,引入Sigmoid擾動學習因子,改進算法中的關鍵操作算子,使得改進的社會學習優化算法能夠有效求解多目標服務優化組合問題;(2)針對研究問題與改進的社會學習優化算法提出了新的多目標服務優化組合方法,基于隨機數據集,將所提多目標服務優化組合方法與四種服務組合方法進行對比,驗證了改進的SLO算法能夠更好地求解服務優化組合問題。在未來的研究中,將考慮動態環境下的服務組合問題以及如何設計環境變化響應策略,以此實現動態多目標服務優化組合。