譚文安,吳嘉凱

(1.南京航空航天大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,南京 211106; 2.上海第二工業(yè)大學(xué) 計算機與信息工程學(xué)院,上海 201209)

0 概述

面向服務(wù)計算和面向服務(wù)體系架構(gòu)的推廣和應(yīng)用[1],促進了Web服務(wù)的發(fā)展。Web服務(wù)具有完全開放、松散耦合、具備標準協(xié)議和高度可集成等特征[2],基于Web服務(wù)技術(shù)[3]并采用開放的可擴展標記語言定義的服務(wù),能夠擺脫對平臺的依賴,實現(xiàn)服務(wù)重組,動態(tài)滿足用戶的服務(wù)需求,并且節(jié)約資源和時間。隨著大數(shù)據(jù)時代的到來,Web服務(wù)數(shù)量劇增,涌現(xiàn)出很多功能相似但非功能屬性即服務(wù)質(zhì)量(Quality of Service,QoS)不同的服務(wù)。如何在不同QoS的候選服務(wù)集合中高效實現(xiàn)服務(wù)的選擇和組合,使得組合服務(wù)能夠滿足客戶的功能和非功能需求,是一個典型的NP難題[4]。

近年來,針對基于QoS感知的Web服務(wù)組合問題,國內(nèi)外學(xué)者提出了各種改進的啟發(fā)式算法,獲得了近似最優(yōu)解。文獻[5-6]通過融合其他方法來改進遺傳進化(Genetic Evolutionary,GA)算法。其中:文獻[5]借助模擬退火以及和聲搜索算法改進GA算法的交換策略;文獻[6]通過對候選服務(wù)集局部選優(yōu)的方式縮小搜索空間,提升GA算法性能。由于粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法參數(shù)少、收斂速度快,因此文獻[7-8]對其改進后用于解決服務(wù)組合問題:文獻[7]通過迭代生成的余切序列擾亂粒子的運動速度和位置,提升PSO算法的全局搜索能力;文獻[8]通過優(yōu)化PSO算法的慣性權(quán)重和學(xué)習參數(shù)的方式提升算法的尋優(yōu)能力,但PSO算法普遍存在“早熟”現(xiàn)象,易陷入局部最優(yōu)解。文獻[9-10]提出一種基于差分進化(Differential Evolution,DE)算法的服務(wù)組合方法:文獻[9]通過一種新型的編碼方式提高算法的尋優(yōu)能力,但算法在大規(guī)模組合服務(wù)情況下性能較差;文獻[10]通過引入結(jié)構(gòu)知識,提出基于知識的差分進化(Knowledge-based DE,KDE)算法,加快了算法的收斂速度。針對大規(guī)模服務(wù)組合問題,文獻[11-12]將人工蜂群(Artificial Bee Colony,ABC)算法應(yīng)用于Web服務(wù)組合優(yōu)化:文獻[11]通過精英策略增強搜索能力;文獻[12]采用一種受差分進化啟發(fā)的搜索策略提高搜索效率。此外,文獻[13]提出一種擴展的花朵授粉(Extended Flower Pollination Algorithm,EFPA)算法,在花朵授粉算法的基礎(chǔ)上引入GA算法的變異和交換策略,進一步提升了算法性能。

本文提出一種改進的花朵授粉(Improved FPA,IFPA)算法用于優(yōu)化Web服務(wù)組合。將差分進化算法的變異和交換操作加入到花朵授粉算法中,增強花朵的有效性和多樣性,并利用貪心策略選擇適應(yīng)度值高的花朵,從而加快算法收斂速度,增強算法尋優(yōu)能力,提高組合服務(wù)性能。

1 Web服務(wù)組合問題

1.1 QoS感知的Web服務(wù)組合

工作流管理聯(lián)盟(WFMC)提出的順序(Sequence)、循環(huán)(Circular)、選擇(Selective)和并行(Parallel)4種工作流管理模型結(jié)構(gòu),可支持Web服務(wù)組合建模,其中,并行、選擇和循環(huán)3種基本模型均可轉(zhuǎn)化為順序類型。為便于討論,本文只討論順序模型。

1.2 QoS屬性值及其歸一化

本文引入QoS屬性計算組合服務(wù)的適應(yīng)度值,用于評價Web服務(wù)組合的非功能特性。具體可選取Web服務(wù)的可靠性(rel)和可用性(ava)這兩種效益型屬性和響應(yīng)時間(rtm)、價格(cos)這兩種成本型屬性來描述服務(wù)質(zhì)量[14]。

Web服務(wù)不同的QoS屬性具有不同的衡量方式,因此,在計算組合服務(wù)的適應(yīng)度之前必須對QoS屬性值進行預(yù)處理。本文借鑒文獻[10]方法對QoS進行歸一化操作,計算公式如下:

(1)

1.3 QoS聚合函數(shù)

不同服務(wù)的QoS屬性具有不同的特性,其對應(yīng)的QoS聚合函數(shù)也有所不同,本文借鑒文獻[15],采取累和及累積兩種操作。

組合服務(wù)的響應(yīng)時間和價格屬性通過原子服務(wù)累和而成,聚合函數(shù)如下:

(2)

組合服務(wù)的可用性和可靠性屬性通過其原子服務(wù)累積而成,聚合函數(shù)如下:

(3)

通過加權(quán)求和的方式計算組合服務(wù)CS的服務(wù)質(zhì)量,服務(wù)組合優(yōu)化的數(shù)學(xué)模型可表示為:

(4)

2 基于IFPA算法的服務(wù)組合優(yōu)化

2.1 花朵授粉算法

花朵授粉算法(FPA)由YANG等人于2012年提出,其是一種新型的元啟發(fā)式群智能優(yōu)化算法。FPA模擬植物界中花朵授粉的方式,主要有自花授粉和異花授粉兩種方式[16]。該算法通過轉(zhuǎn)換概率實現(xiàn)局部搜索和全局搜索的動態(tài)轉(zhuǎn)換,平衡兩者之間的關(guān)系。FPA按照以下規(guī)則進行設(shè)計:

1)花朵的異花授粉被視為全局搜索,傳粉者飛行傳粉服從Levy分布。

2)花朵的自花授粉被視為局部搜索。

3)花朵的常性是指兩朵相近的花朵更易授粉,可以認為是一種繁衍概率,與兩朵花之間的相似度成比例。

4)局部授粉和全局授粉的動態(tài)轉(zhuǎn)換由概率p控制。

在異花授粉(全局搜索)過程中,傳粉者通過Levy飛行機制進行傳粉,其尋優(yōu)演化可表示為:

(5)

(6)

其中,λ=1.5,Γ(λ)為標準伽馬函數(shù)。

自花授粉(局部搜索)在花朵附近區(qū)域進行搜索,可表示為:

(7)

其中,ε為[0,1]之間的隨機數(shù)。

2.2 IFPA算法的差分進化機制

差分進化(DE)算法是一種基于群體的進化方法[17],包括初始化、變異、交換、選擇等步驟。DE算法流程簡單,易于實現(xiàn)[18-19]。

研究表明,標準的花朵授粉算法存在一些缺陷,如收斂速度慢、在高維情況下易早熟、全局搜索能力差等。針對上述不足,本文將差分進化算法的變異、交換操作加入到花朵授粉算法中,以增強花朵的有效性和多樣性,并利用貪心策略選擇適應(yīng)度值高的花朵,以加快算法收斂速度,增強FPA算法的尋優(yōu)能力。

2.2.1 變異操作

(8)

其中,i≠r1≠r2≠r3且i,r1,r2,r3∈[1,N],δ為縮放因子,δ∈(0,1)。

2.2.2 交換操作

(9)

2.2.3 選擇操作

為加快算法的收斂速度,直接將種群Xt和變異、交換后的種群Ut混合,依據(jù)貪心策略,按適應(yīng)度值選取N個花朵個體組合成新的種群Xt+1。

2.3 服務(wù)組合建模

2.3.1 編碼方式

本文采用整數(shù)編碼方式表示離散的服務(wù),利用一個整數(shù)數(shù)組S=(s1,s2,…,sn)表示服務(wù)組合的一個解決方案(即一個花粉或花朵),將尋找最優(yōu)組合服務(wù)問題轉(zhuǎn)化為向量S求最優(yōu)解問題,其中,每個整數(shù)si都代表相應(yīng)任務(wù)中選擇的候選服務(wù)索引的序列號。計算每個花粉S的適應(yīng)度值,對該花粉所對應(yīng)的服務(wù)組合方案進行評估,判斷組合服務(wù)的優(yōu)劣。

2.3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)作為Web服務(wù)組合評估函數(shù),計算方法有很多,為便于比較,本文根據(jù)服務(wù)組合優(yōu)化數(shù)學(xué)模型,對于按式(2)累和的屬性進行取平均數(shù)操作,對于按式(3)累積的屬性進行開方操作,最終使適應(yīng)度函數(shù)的值介于(0,1)之間。同時,借鑒文獻[1]引入罰函數(shù)來構(gòu)造適應(yīng)度函數(shù),將約束優(yōu)化問題轉(zhuǎn)變?yōu)闊o約束優(yōu)化問題,實現(xiàn)全局最優(yōu)化。綜合考慮本文所選取的QoS屬性,Web服務(wù)組合的適應(yīng)度函數(shù)值fitness表示如下:

(10)

(11)

2.4 服務(wù)組合算法描述

本文將提出的IFPA算法應(yīng)用于服務(wù)組合優(yōu)化問題,該算法的具體步驟如下:

步驟1初始化參數(shù),初始化種群規(guī)模N、最大迭代次數(shù)tmax、轉(zhuǎn)換概率p、最小縮放因子δ和交叉概率CR。

步驟2初始化種群,并根據(jù)適應(yīng)度函數(shù)計算當前種群適應(yīng)度值,記錄全局最優(yōu)值及其對應(yīng)的最優(yōu)解。

步驟3如果轉(zhuǎn)化概率p

步驟4如果轉(zhuǎn)換概率p>rand(0,1)成立,則進行局部搜索,根據(jù)式(7)對解進行更新,并做越界處理。

步驟5計算步驟3或步驟4新生成的花朵適應(yīng)度值,并與原花朵個體的適應(yīng)度值進行比較,如果新的個體適應(yīng)度值更高,則用新個體替換舊個體,同時記錄整個種群的最優(yōu)值和最優(yōu)解,最終得到新種群Xt。

步驟6利用DE算法中的式(8)對整個種群進行變異操作,并對變異后的種群Vt做越界處理。

步驟7利用DE算法中的式(9)對種群Xt和變異種群Vt進行交換操作,得到最終的新種群Ut,并計算新種群Ut中每個個體的適應(yīng)度值。

步驟8從種群Xt和種群Ut中按貪心策略選取適應(yīng)度較高的N個花朵個體,組成新的第(t+1)代種群Xt+1,并更新全局最優(yōu)值和最優(yōu)解。

步驟9判斷結(jié)束條件,如果滿足,則退出并輸出最優(yōu)值和對應(yīng)的最優(yōu)解,否則轉(zhuǎn)步驟3。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境和數(shù)據(jù)

通過仿真實驗,驗證IFPA算法對基于QoS感知的Web服務(wù)組合優(yōu)化的有效性,分別從可行性和收斂性2個方面對IFPA、KDE[13]和EFPA[14]3種服務(wù)組合優(yōu)化算法,以及DE和FPA 2種傳統(tǒng)優(yōu)化算法進行比較。實驗環(huán)境為:Windows 10,64位操作系統(tǒng),英特爾Core i7-7700HQ@2.80 GHz四核處理器,8 GB內(nèi)存。

實驗選用2個不同的數(shù)據(jù)集D1和D2。數(shù)據(jù)集D1是由ZENG等人提供的QWS數(shù)據(jù)集[20-21],該數(shù)據(jù)集收錄了互聯(lián)網(wǎng)中2 507個Web服務(wù),包含9個非功能屬性。本文從中選出響應(yīng)時間、可用性,可靠性這三大屬性,同時隨機生成數(shù)據(jù)集中沒有的價格屬性,并以這4個屬性評價服務(wù)質(zhì)量。數(shù)據(jù)集D2是隨機生成的,共收錄13 000個Web服務(wù),包含本文實驗所需的QoS屬性。

為模擬真實情況下的Web服務(wù)組合優(yōu)化過程,本文實驗設(shè)置4種不同子任務(wù)數(shù){10,15,20,25},并且設(shè)置4種不同數(shù)量{25,50,75,100}的候選服務(wù)集。為保證實驗的有效性和正確性,將5種優(yōu)化算法在同一數(shù)據(jù)集上進行實驗,并且每組實驗重復(fù)40次。

3.2 實驗參數(shù)設(shè)置

實驗中種群大小均設(shè)為30,最大迭代次數(shù)均設(shè)為200次,4個不同的QoS屬性權(quán)重分別設(shè)為:rtm=0.2,ava=0.2,rel=0.3,cos=0.3,5種群體智能優(yōu)化算法的參數(shù)如表1所示。

表1 參數(shù)設(shè)置Table 1 Parameters setting

3.3 可行性分析

以上文提出的適應(yīng)度函數(shù)評價組合服務(wù)的服務(wù)質(zhì)量,適應(yīng)度值越大代表服務(wù)質(zhì)量越好,組合服務(wù)的質(zhì)量越好;反之,服務(wù)質(zhì)量越差。為驗證IFPA算法在Web服務(wù)組合領(lǐng)域的可行性,在不同任務(wù)數(shù)與候選服務(wù)數(shù)的情況下,比較5種優(yōu)化算法的尋優(yōu)性能。此時選取D1數(shù)據(jù)集,實驗結(jié)果如表2所示。為驗證IFPA在大規(guī)模服務(wù)組合情況下的可行性,候選服務(wù)數(shù)均設(shè)為100,此時選取D2數(shù)據(jù)集,實驗結(jié)果如圖1所示。

表2 不同任務(wù)數(shù)和候選服務(wù)數(shù)下的平均適應(yīng)度Table 2 Average fitness under different number of tasks and candidate services

圖1 不同任務(wù)數(shù)下的最佳適應(yīng)度

由表1可以看出,在不同任務(wù)數(shù)和不同候選服務(wù)數(shù)情況下,相比于其他4種優(yōu)化算法,IFPA的適應(yīng)度值均為最高,即組合服務(wù)的質(zhì)量最好,驗證了IFPA算法的可行性。由圖1可以看出,在大規(guī)模服務(wù)組合情況下,IFPA算法也始終優(yōu)于其他算法。由于IFPA在D1、D2數(shù)據(jù)集上表現(xiàn)均比其他算法優(yōu)秀,因此其不僅可行,而且尋優(yōu)性能更好。

3.4 收斂性分析

為分析IFPA的收斂性,比較不同任務(wù)數(shù)下5種算法的收斂情況,即迭代次數(shù)和平均適應(yīng)度之間的關(guān)系。在較少的迭代次數(shù)下獲得較高的平均適應(yīng)度值,表示收斂能力較好;反之,表示收斂能力較差。實驗選取D1數(shù)據(jù)集,候選服務(wù)數(shù)設(shè)為100,結(jié)果如圖2所示。

圖2 迭代次數(shù)與適應(yīng)度之間的關(guān)系

由圖2可以看出,隨著任務(wù)數(shù)的增加,5種算法的收斂性能均有所下降。當任務(wù)數(shù)為10和15時,IFPA算法在迭代到50次時就基本已經(jīng)收斂;而當任務(wù)數(shù)為20和25時,IFPA算法在迭代50次時還未收斂。在4種不同任務(wù)數(shù)的情況下,IFPA、KDE和EFPA算法的收斂性能優(yōu)于DE和FPA兩種傳統(tǒng)優(yōu)化算法,同時IFPA算法的平均適應(yīng)度值都高于另外4種優(yōu)化算法,而KDE、EFPA則陷入局部最優(yōu)解。相比之下,IFPA算法不僅收斂快,而且尋優(yōu)性能更好。

4 結(jié)束語

針對基于QoS感知的Web服務(wù)組合優(yōu)化問題,本文提出一種改進的花朵授粉算法,以提高組合服務(wù)的服務(wù)質(zhì)量。該算法具有較好的全局搜索能力,其通過變異、交叉的方式提升種群多樣性,并借助貪心策略提高收斂速度。實驗結(jié)果驗證了該算法在尋優(yōu)和收斂方面的優(yōu)越性。本文主要基于靜態(tài)QoS屬性研究Web服務(wù)組合優(yōu)化問題,但在實際情況下,QoS屬性值都是動態(tài)變化的,并且不同屬性之間可能存在某種關(guān)聯(lián)關(guān)系。因此,下一步將從動態(tài)變化的QoS值以及屬性之間的關(guān)聯(lián)這兩方面著手,對本文算法做進一步優(yōu)化。