基于QoS多目標優(yōu)化的Web服務組合方法

劉 彬，張仁津

（貴州師范大學 數(shù)學與計算機科學學院，貴州 貴陽550001）

0 引 言

Web服務作為面向服務的體系結(jié)構(gòu) （service oriented architecture，SOA）軟件的一種重要形式，已廣泛得到工業(yè)界和學術(shù)界的認可并應用于金融、電子商務、電子政務、物聯(lián)網(wǎng)等多個領(lǐng)域。通常，單個Web服務的功能比較有限，很難滿足復雜的業(yè)務需求，所以需要依據(jù)業(yè)務需求將這些單個服務根據(jù)功能和服務質(zhì)量 （quality of service，QoS）集成為組合服務［1－3］，完成復雜的業(yè)務。隨著公共網(wǎng)絡(luò)上web服務的種類和數(shù)量日益增多，雖然這為Web服務組合提供了廣泛的資源，但也為Web服務組合帶來了新的問題，從大量的組合方案中找出滿足用戶要求的最優(yōu)方案并不是一件容易的事，這是一個NP難問題。例如在一個業(yè)務包括10子任務，每個子任務通過調(diào)用具體Web服務來實現(xiàn)的，若每個子任務有10個候選服務，則該業(yè)務的組合方案就有1010種。如何對候選服務進行選擇，得到最優(yōu)的服務組合方案，成為亟待解決的問題。文獻 ［4］提出一種基于事件的服務組合方法，以簡單服務事件語言為基礎(chǔ)，通過模塊化方法構(gòu)造組合服務方案。文獻 ［5］以Bayes方法對Web服務的信任模型，以遺傳算法進行服務組合，但沒有考慮Web服務中的各種QoS屬性的沖突問題，這可能會導致對Web服務的要求過高等問題，間接增加了使用者的成本。更多研究者是以QoS屬性為基礎(chǔ)實現(xiàn)Web服務組合，采用的算法包括量子貪心算法［6］、量子遺傳算法［7］、免疫遺傳算法［8］、蟻群算法［9］、禁忌搜索和模擬退火相結(jié)合的混合算法［10］、禁忌搜索算法［11］、蟻群算法［12］。這些研究工作雖然采用了不同的算法實現(xiàn)Web服務組合，但都是采用某種方法把多種不同的QoS屬性要求人為轉(zhuǎn)換成為一個目標函數(shù)，這種轉(zhuǎn)換都可能導致與用戶的實際關(guān)注要求有偏差，容易導致用戶得不到最合適的服務。普通用戶通常只能給出組合服務QoS屬性 （如服務價格，服務時間，可用性等）的最低要求，而這些要求很難同時達到最優(yōu)，有時這些屬性還有可能是對立的，如服務時間短的服務通常服務價格會比較高，所以Web服務組合優(yōu)化問題是一個典型的多目標優(yōu)化問題。在我們的研究工作中，是把Web服務組合作為多目標優(yōu)化問題進行處理，即針對服務的多個QoS屬性進行優(yōu)化，更符合使用者的要求。

1 多目標優(yōu)化問題的數(shù)學描述

不失一般性，一個多目標優(yōu)化問題可以定義為一個三元組：（X，C，F(xiàn)）。其中X是n維決策空間，即x＝ （x1，x2，…，xn）X；C是一組決策變量必須同時滿足的約束集合；F是含有m≥2個目標函數(shù)的矢量，可表示為：F＝（f1（x），f2（x），…，fm（x））。多目標優(yōu)化就是讓些不同的目標函數(shù)最小化。

定義1（可行解） 如果xX且滿足C中的所有約束條件，則稱x為可行解。

定義2（可行解集合） 所有可行解的集合稱為可行解集合，記為Xf，顯然XfX。

定義3（Pareto占優(yōu)） 假設(shè)xA，xBXf，則xA對xB是Pareto占優(yōu)的充要條件是：i＝1，2，…，m，fi（xA）≤fi（xB）且j＝1，2，…，m，fj（xA）＜fj（xB），記為：xAxB，也稱為xA支配xB。

定義4（Pareto最優(yōu)解） 如果一個可行解x＊滿足條件：xXf使xx＊，則x＊被稱為Pareto最優(yōu)解（或非支配解）。

定義5（Pareto最優(yōu)解集） 所有Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集。

多目標優(yōu)化的目標就是找出非支配解的Pareto最優(yōu)解集。但在實際工作中，由于Pareto最優(yōu)解集可能會有太多的元素甚至是無限集合，導致計算機效率很低甚至無法完成，因此在實際工作中更傾向于搜索出一個分布均衡的Pareto最優(yōu)解集的子集。

2 Web服務組合模型

一個復雜的業(yè)務可以分成m個子任務，每個子任務都有一個或多個Web服務可以完成所需的功能，實現(xiàn)這個業(yè)務的Web服務組合如圖1所示，S為任務起點，E為任務終點，WSi（i＝1，2，…，m）為能夠完成第i個子任務的候選Web服務集合，從S到E的任何一條路徑所包含的Web服務即為可以完成此業(yè)務的組合服務 （只考慮了功能）。Web服務可以表示為Wij＝ ｛Fij，Qij｝，其中Fij為功能屬性集合；Qij為服務質(zhì)量屬性集合。顯然候選Web服務集合WSi中Web服務實體的F都能完成第i個子任務的功能。每個Web服務的Q都包含n個QoS屬性，即Qij＝｛，，…，｝。

圖1 Web服務組合模型

3 基于QoS的多目標蟻群優(yōu)化

蟻群優(yōu)化最初是用于解決旅行商這一經(jīng)典組合優(yōu)化問題，很快應用于順序排序、廣義分配、多重背包、網(wǎng)絡(luò)路由等各種各樣的問題?，F(xiàn)在許多研究者開始研究多目標蟻群優(yōu)化［13－14］，并已成功用于資源分配［15］、旅行問題［16－17］、

網(wǎng)格計算［18］、流水作業(yè)調(diào)度［19］、開放工廠安排［20］等。

3.1 QoS屬性的預處理

根據(jù)第1節(jié)的描述，多目標優(yōu)化中采用的標準是：目標函數(shù)數(shù)值越小，則性能越優(yōu)。但對于Web服務的QoS屬性來說，并不是全部滿足這種要求。QoS屬性可以分為兩類，一類是負屬性，這類屬性取值越大，性能越低，如執(zhí)行時間、服務價格等；另一類是正屬性，這類屬性取值越大，性能越高，如服務評價、可用性等。而且各種不同屬性的數(shù)值屬性差別很大，例如價格是貨幣單位，而可用性是百分比。我們?yōu)榱税堰@種存在著巨大差異的各種屬性用于多目標蟻群優(yōu)化的單一啟發(fā)式信息中 （因為在我們的方案中是采用各種QoS屬性啟發(fā)式信息之和作為啟發(fā)式信息），必須要讓它們的數(shù)值不能相差太大，否則會導致數(shù)值過大的啟發(fā)式信息淹沒數(shù)值很小的啟發(fā)式信息。同時還要滿足目標函數(shù)規(guī)定的數(shù)值越小性能越好的要求，所以需要對Web服務的QoS屬性進行預處理。

如圖1所示結(jié)構(gòu)中的任一Web服務Wij，設(shè)它有n個QoS屬性，即Qij＝ ｛，，…，｝。若第r個屬性為負屬性，其處理后的屬性vrij如式 （1）所示。若第r個屬性為正屬性，其處理后的屬性如式 （2）所示，其中是圖1中全部Web服務中第r個屬性中的最大值，分子中加1是為了保證分子不為0（為了用于啟發(fā)式信息）。式（1）、式 （2）中的表示圖1中全部 Web服務的第r個屬性之和。通過式 （1）、式 （2）就能把 Web服務的所有QoS屬性值都轉(zhuǎn)換到具有這樣的特征：

（1）數(shù)值越小表示相應性能越好；

（2）每個屬性都是與同類屬性數(shù)值之和的一個比例值，不同屬性數(shù)值之間比原始數(shù)值更具有可比較性；

（3）因為各種QoS屬性轉(zhuǎn)換后的數(shù)值差別不會特別大，不會出現(xiàn)大數(shù)值掩蓋小數(shù)值的問題，可以方便用于蟻群優(yōu)化中的啟發(fā)式信息

由于服務使用者在請求服務時要求的是組合服務的QoS屬性，為了確保數(shù)值的一致性，也必須做類似處理，設(shè)服務使用者要求的QoS屬性Q＝ ｛q1，q2，…，qn｝，則QoS屬性qr如果是負屬性，按式 （3）處理，如果為正屬性則按式 （4）處理，式 （3）、式 （4）分母與式 （1）、式（2）中的分母為相同的值，式 （4）中的qrmax和式 （2）中的qrmax相同

根據(jù)圖1所示的模型，組合服務的QoS屬性與其組合成員的QoS屬性的關(guān)系與具體的屬性有關(guān)，如組合服務價格是由成員服務價格之和確定，組合服務可用性是由成員服務可用性最低的決定。因為我們這里采用的是經(jīng)預處理后的QoS屬性，與未經(jīng)處理的有所不同。如未處理的組合服務可用性是由成員服務可用性最低的確定，而經(jīng)預處理后數(shù)值越小代表可用性越高，因此在經(jīng)過我們這種方法預處理后，組合服務可用性是由成員服務可用性最高的確定。如圖1所示，假設(shè)一個組合服務中需要m個成員服務，幾種常用的組合QoS屬性與成員QoS屬性的關(guān)系如表1所示。

表1 組合服務QoS屬性值

3.2 多信息素表的蟻群優(yōu)化算法

要針對Web服務組合中的多個QoS屬性進行優(yōu)化，在蟻群優(yōu)化中就是要把多個QoS屬性轉(zhuǎn)換為啟發(fā)式信息和信息素進行處理，在我們算法中對每一個QoS屬性 （對應一個目標函數(shù)）都分別用一個變量保存信息素和啟發(fā)式信息。如服務實體Wij的第k個QoS屬性的信息素表示為τki（j），第k個QoS屬性的啟發(fā)式信息表示為ηki（j）。螞蟻在如圖1所示W(wǎng)eb組合圖中選擇下一個Web實體時按式 （5）的概率進行選擇 （包括起始點和前m－1個候選服務集合），α和β參數(shù)分別決定了信息素和啟發(fā)式信息的相對影響力。在式 （5）中采用的啟發(fā)式信息并不是單個QoS屬性的啟發(fā)式信息，而是用戶關(guān)注的所有QoS屬性的啟發(fā)式信息之和［17］，由式 （6）求出 （假設(shè)需要優(yōu)化的QoS屬性個數(shù)為n）。因為最終要優(yōu)化的是用戶關(guān)注的多個QoS屬性，如果在此公式中采用單個屬性的啟發(fā)式信息，那么構(gòu)建的解只會是對單個QoS屬性的優(yōu)化。因此我們在此采用全部用戶關(guān)注的QoS屬性的啟發(fā)式信息之和作為螞蟻選擇路徑的啟發(fā)式信息，螞蟻在選擇路徑時受到多個QoS屬性啟發(fā)式信息的影響，故所產(chǎn)生的結(jié)果就會同時對多個QoS屬性對應的目標函數(shù)進行優(yōu)化

信息素是蟻群系統(tǒng)中搜索解空間的基礎(chǔ)，如果局部衰減得過小會導致探索的空間縮小到很小，如果局部信息素增長到過高會導致停滯現(xiàn)象，因此通常把信息素限制在一個區(qū)間 ［τmin，τmax］。用于 Web服務組合的多信息素蟻群算法求解的構(gòu)建算法如下算法1所示。

算法1：多信息素蟻群優(yōu)化算法

（1）所有信息素初始化為τmax；

（2）蟻群中每只螞蟻從1～n（n為目標函數(shù)的個數(shù)）中隨機選取一個值i，然后以第i個信息素表中的信息素

構(gòu)建一個解 （詳見算法2）；

（3）更新第i個信息素表中的所有信息素值 （詳見3.3節(jié)）；

（4）如果達到最大循環(huán)次數(shù)就結(jié)束，否則跳轉(zhuǎn)到 （2）。

算法2：解的構(gòu)建算法

（1）初始化解為空；

（2）按式 （5）的概率選擇下一個服務，并把選中的服務加入解中；

（3）如果無后續(xù)服務則返回，否則轉(zhuǎn)到 （2）。

3.3 信息素更新

信息素是蟻群優(yōu)化算法中引導螞蟻行為的一個至關(guān)重要的因素，因此信息素的更新是蟻群優(yōu)化的一個核心問題。為了讓信息素能有效地引導螞蟻構(gòu)建出良好的解，我們采取的措施是在每一個循環(huán)周期內(nèi)所有螞蟻都隨機地選擇一個信息素表，并依據(jù)此信息素表構(gòu)建解后按以下方法更新信息素：首先，為模擬信息素的蒸發(fā)，信息素表中的所有信息素都要減少一部分，如式 （7）所示，其中ρ∈ （0，1）為蒸發(fā)因子；其次，在當前循環(huán)內(nèi)可以得到n個與目標函數(shù) （對應n個QoS屬性）對應的最優(yōu)解，設(shè)Si為當前循環(huán)中使第i個目標函數(shù)fi最小的解，為從第一個循環(huán)開始到當前循環(huán) （包括當前循環(huán)）中得到使第i個目標函數(shù)fi最小的解，在第i個信息素表中Sibest包含的Web服務的信息素增加一個量△τk，如式 （8）所示?！鳓觡由式 （9）求出，即當前循環(huán)中如果Si優(yōu)于，則△τk＞1，且Si越好，△τk的值越大；否則△τk≤1，且Si越差，△τk的值越小。如果當前循環(huán)中如果Si優(yōu)于Sibest，信息素更新后，＝Si。因此，經(jīng)過信息素更新后，沒有被選擇的候選服務的每個信息素的值都會減少一部分 （除非已經(jīng)降低至τmin），具體算法見算法3。

算法3：信息素更新算法

（1）初始化i＝1；

（2）按式 （7）更新第i個信息素表中的信息素值，如果某個信息素的值小于最小值τmin則設(shè)置為τmin，如果某個信息素的值大于最大值τmax則設(shè)置為τmax；；

（3）把所有解分別代入fi求出Si，依據(jù)式 （9）求出△τk，把當前循環(huán)最優(yōu)解Si中包含的所有Web服務在第i個信息素表中對應的信息素的值增加△τk。如果某個信息素的值小于最小值τmin則設(shè)置為τmin，如果某個信息素的值大于最大值τmax則設(shè)置為τmax；

（4）如果Si優(yōu)于Sibest，Sibest＝Si；

（5）如果還有未更新的信息素表，i增加1，跳轉(zhuǎn)到（3）；否則返回。

4 仿真實驗及分析

假設(shè)一個業(yè)務可以由10個子任務組合而成，每個子任務都有10個候選Web服務。需要優(yōu)化如表1所示的4個QoS屬性，故可定義如式 （10）所示的4個目標函數(shù)

其它參數(shù)取值：τmin＝10，τmax＝100，ρ＝0.01，螞蟻數(shù)取100，循環(huán)次數(shù)取1000，啟發(fā)式信息ηi（j）按式 （6）取值，服務實體Wij的第k個QoS屬性的信息素因為篇幅的原因，只針對α＝2，β＝2和α＝1，β＝4兩組參數(shù)進行比較，測試情況分別如圖2和圖3所示。●代表f1的平均值，■代表f2的平均值，▲代表f3的平均值，★代表f4的平均值。從圖中可以看出，這4個目標函數(shù)隨著循環(huán)次數(shù)的增加，全部都得到了優(yōu)化，后一組參數(shù)目標函數(shù)收斂要明顯快于前一組。其原因在于：螞蟻在優(yōu)化任何一種QoS質(zhì)量屬性時都要受到啟發(fā)式信息的影響，而我們采用的啟發(fā)式信息包含了全部需要優(yōu)化的QoS質(zhì)量屬性的啟發(fā)式信息，所以能同時對多個目標函數(shù)進行優(yōu)化；后一組數(shù)據(jù)由于啟發(fā)式信息對螞蟻路徑選擇起到的作用更大，所以目標函數(shù)收斂更快。

通過仿真實驗可知，我們能把Web服務組合問題作為多目標優(yōu)化問題進行處理，將多種差別很大QoS屬性經(jīng)過預處理后用多信息素單啟發(fā)式信息的蟻群優(yōu)化能有效地實現(xiàn)多目標函數(shù)的優(yōu)化，實驗結(jié)果穩(wěn)定，具有較好的魯棒性，達到了預期的目標。

5 結(jié)束語

Web服務的組合是面向服務體系結(jié)構(gòu)軟件中的一個十分重要的問題，它極大地影響著Web服務應用的推廣。以QoS屬性為基礎(chǔ)的Web服務組合涉及到QoS的多個屬性，目前常用的方法是通過某種方法把多個QoS屬性轉(zhuǎn)化為一個量后再進行優(yōu)化，但這種方法對權(quán)重很敏感，可能會導致與用戶的實際關(guān)注要求有偏差。在我們的組合方法中把服務組合建模為多目標優(yōu)化問題，對每個用戶關(guān)注的QoS屬性建立一個目標函數(shù)，采用多個信息素表和一個啟發(fā)式信息表的蟻群優(yōu)化對QoS多個屬性同時進行優(yōu)化，最終產(chǎn)生一組Pareto最優(yōu)解。雖然多目標優(yōu)化要比單目標優(yōu)化要復雜得多，但這種多目標優(yōu)化模型可以靈活地對用戶感興趣的QoS屬性進行優(yōu)化，搜索出的結(jié)果能更好地滿足用戶要求，因此有很好的用應前景。

［1］Farhan Hassan Khan，Younus Javed M，Saba Bashir，et al.QoS based dynamic web services composition ＆execution ［J］.International Journal of Computer Science and Information Security，2010，7 （2）：147－152.

［2］Piergiorgio Bertoli，Marco Pistore，Paolo Traverso.Automated composition of web services via planning in asynchronous domains［J］.Artificial Intelligence，2010，174 （3－4）：316－361.

［3］Esra Kirci Ozorhan，Esat Kaan Kuban，Nihan Kesim Cicekli.Automated web services composition with the event calculus［J］.Information Sciences，2010，180 （19）：3589－3613.

［4］LI Xin，CHENG Bo，YANG Guowei，et al.Method of web services composition based on events ［J］.Journal of Software，2009，20 （12）：3101－3116 （in Chinese）.［李鑫，程渤，楊國緯，等.一種基于事件的Web服務組合方法 ［J］.軟件學報，2009，20 （12）：3101－3116.］

［5］YUN Ben－sheng，YAN Junwei，LIU Min.Method to optimize web service composition based on Bayes trust model［J］.Computer Integrated Manufacturing Systems，2010，16 （5）：1103－1110 （in Chinese）. ［云本勝，嚴雋薇，劉敏.基于Bayes信任模型的Web服務組合優(yōu)化方法 ［J］.計算機集成制造系統(tǒng)，2010，16 （5）：1103－1110.］

［6］XU Bin，LUO Sen，YAN Yixin.Efficient composition of semantic web services with end－to－end QoS optimization ［J］.Tsinghua Science ＆ Technology，2010，15 （6）：678－686.

［7］LIU Feng，LEI Zhenming.Research on user－aware QoS based web services composition ［J］.The Journal of China Universities of Posts and Telecommunications，2009，16 （6）：125－130.

［8］CHEN Liang，SUN Min.Web services composition method based on immune genetic algorithm ［J］.Computer Engineering，2010，36 （10）：226－228 （in Chinese）.［陳亮，孫敏.基于免疫遺傳算法的 Web服務組合方法 ［J］.計算機工程，2010，36 （10）：226－228.］

［9］WANG Chuangwei，QIAN Xuezhong.Application of ant colony algorithm in web services composition problem ［J］.Computer Engineering and Design，2007，28 （24）：5912－5915 （in Chinese）. ［王創(chuàng)偉，錢雪忠.蟻群算法在Web服務組合問題中的應用研究［J］.計算機工程與設(shè)計，2007，28 （24）：5912－5915.］

［10］Jong Myoung Ko，Chang Ouk Kim，Ick－Hyun Kwon.Qualityof－service oriented web service composition algorithm and planning architecture ［J］.The Journal of Systems and Software，2008，81 （11）：2079－2090.

［11］DONG Zongran，LI Yingqiu，CHEN Ming－h(huán)ua.Web services composition optimization based on tabu search algorithm ［J］.Computer Engineering and Design，2010，31 （5）：942－945（in Chinese）.［董宗然，李迎秋，陳明華.基于禁忌搜索算法的Web服務組合優(yōu)化 ［J］.計算機工程與設(shè)計，2010，31（5）：942－945.］

［12］SHEN Ji－quan，ZHENG Xuefeng，TU Xuyan.An approach to service composition based on ant colony algorithm ［J］.Journal of Wuhan University of Technology：Transportation Science ＆ Engineering，2009，33 （6）：1179－1182 （in Chinese）.［沈記全，鄭雪峰，涂序彥.一種基于蟻群算法的服務組合方法 ［J］.武漢理工大學學報：交通科學與工程版，2009，33 （6）：1179－1182.］

［13］Daniel Angus，Clinton Woodward.Multiple objective ant colony optimization ［J］.Swarm Intelligence，2009，3 （1）：69－85.

［14］Christine Solnon，Khaled Ghédira.Ant colony optimization for multi－objective optimization problems ［C］.Proceedings of 19th IEEE International Conference on Tools with Artificial Intelligence. Patras： IEEE Computer Society， 2007：450－457.

［15］Chaharsooghi S K，Amir H Meimand Kermani.An effective ant colony optimization algorithm （ACO）for multi－objective resource allocation problem （MORAP） ［J］.Applied Mathematics and Computation，2008，100 （1）：167－177.

［16］Daniel Angus.Crowding population－based ant colony optimisation for the multi－objective travelling salesman problem ［C］.Proceedings of the IEEE Symposium on Computational Intelligence in Multicriteria Decision Making.Honolulu：IEEE Computer Society，2007：333－340.

［17］García－Martínez C，Cordón O，Herrera F.A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi－criteria TSP ［J］.European Journal of Operational Research，2007，180 （1）：116－148.

［18］YANG Yahong，WU Guiling，CHEN Jianping，et al.Multiobjective optimization based on ant colony optimization in grid over optical burst switching networks ［J］.Experts Systems with Applications，2010，37 （2）：1769－1775.

［19］Betul Yagmahan，Mehmet Mutlu Yenisey.Ant colony optimization for multi－objective flow shop scheduling problem ［J］.Computers ＆Industrial Engineering，2008，54 （3）：411－420.

［20］Hadi Panahi，Reza Tavakkoli－Moghaddam.Solving a multiobjective open shop scheduling problem by a novel hybrid ant colony optimization ［J］.Expert Systems with Applications，2011，38 （3）：2817－2822.