基于改進花朵授粉算法的Web服務組合優化

譚文安,吳嘉凱

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

0 概述

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

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

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

1 Web服務組合問題

1.1 QoS感知的Web服務組合

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

1.2 QoS屬性值及其歸一化

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

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

(1)

1.3 QoS聚合函數

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

組合服務的響應時間和價格屬性通過原子服務累和而成,聚合函數如下:

(2)

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

(3)

通過加權求和的方式計算組合服務CS的服務質量,服務組合優化的數學模型可表示為:

(4)

2 基于IFPA算法的服務組合優化

2.1 花朵授粉算法

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

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

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

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

4)局部授粉和全局授粉的動態轉換由概率p控制。

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

(5)

(6)

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

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

(7)

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

2.2 IFPA算法的差分進化機制

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

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

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混合,依據貪心策略,按適應度值選取N個花朵個體組合成新的種群Xt+1。

2.3 服務組合建模

2.3.1 編碼方式

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

2.3.2 適應度函數

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

(10)

(11)

2.4 服務組合算法描述

本文將提出的IFPA算法應用于服務組合優化問題,該算法的具體步驟如下:

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

步驟2初始化種群,并根據適應度函數計算當前種群適應度值,記錄全局最優值及其對應的最優解。

步驟3如果轉化概率p

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

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

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

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

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

步驟9判斷結束條件,如果滿足,則退出并輸出最優值和對應的最優解,否則轉步驟3。

3 實驗與結果分析

3.1 實驗環境和數據

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

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

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

3.2 實驗參數設置

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

表1 參數設置Table 1 Parameters setting

3.3 可行性分析

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

表2 不同任務數和候選服務數下的平均適應度Table 2 Average fitness under different number of tasks and candidate services

圖1 不同任務數下的最佳適應度

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

3.4 收斂性分析

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

圖2 迭代次數與適應度之間的關系

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

4 結束語

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