徐　甜　劉凌霞

(安陽師范學(xué)院計算中心　河南 安陽 455000)

?

基于改進遺傳算法的Web服務(wù)優(yōu)化組合研究

徐甜劉凌霞

(安陽師范學(xué)院計算中心河南 安陽 455000)

摘要為了獲得更優(yōu)的Web服務(wù)優(yōu)化組合方案，提出一種基于改進遺傳算法的Web服務(wù)優(yōu)化組合方法。首先將Web服務(wù)組合優(yōu)化方案的可行解看作遺傳算法的個體。然后通過遺傳算法模擬自然界的生物進化過程，找到Web服務(wù)組合的最優(yōu)解，同時在標準遺傳算法引入多尺度交叉算子和信息共享因子，提高問題的求解速度。最后進行仿真對比實驗。結(jié)果表明，改進遺傳算法可以快速、準確找到Web服務(wù)組合問題的最優(yōu)解，為解決Web服務(wù)組合問題提出了一種新的解決思路。

關(guān)鍵詞Web服務(wù)遺傳算法服務(wù)組合服務(wù)質(zhì)量

0引言

隨著互聯(lián)網(wǎng)和電子商業(yè)的迅速發(fā)展，Web服務(wù)技術(shù)市場日益成熟，大量的企業(yè)將應(yīng)用、資源和技術(shù)加入到互聯(lián)網(wǎng)上的Web服務(wù)中實現(xiàn)共享，然而單個Web服務(wù)功能比較單一，不能滿足現(xiàn)代企業(yè)多樣性的應(yīng)用需求，這樣Web組合服務(wù)應(yīng)運而生[1]。Web組合服務(wù)將單個Web服務(wù)采用一定的技術(shù)組合在一起，產(chǎn)生功能更強大的服務(wù)，用戶可以按照自己需求選擇相應(yīng)的服務(wù)，以創(chuàng)造更多的價值，降低企業(yè)成本。但是在互聯(lián)網(wǎng)上存在大量的Web服務(wù)，如果從海量服務(wù)中選擇客戶真正要求的服務(wù)，成為當(dāng)前電子商務(wù)研究中的重點，具有十分重要的意義[2]。

針對Web組合服務(wù)優(yōu)化問題，國內(nèi)外學(xué)術(shù)界對其開展了大量的研究，已經(jīng)取得了許多研究進展，文獻[3]將Web組合服務(wù)優(yōu)化問題看作一個0-1背包問題，候選服務(wù)對應(yīng)一個物品包，QoS優(yōu)化目標屬性與物品的價值相對應(yīng)，然后采用分支定界法對包進行選擇；文獻[4]將Web組合服務(wù)優(yōu)化問題看作為一個有向無環(huán)圖，這樣Web服務(wù)問題求解變成了一個多約束的路徑選擇問題；文獻[5]將Web組合服務(wù)優(yōu)化問題映射成為一個覆蓋網(wǎng)絡(luò)，然后采用Dijkstra的最短算法進行求解，這些算法均存在求解速度慢，效率低等缺陷，不能滿足Web服務(wù)組合優(yōu)化在線優(yōu)化要求[6]。近年來，隨著智能優(yōu)化算法研究的不斷深入，有學(xué)者將它們引入到Web服務(wù)組合優(yōu)化問題求解中。由于它們有并行計算、群體尋優(yōu)的等特點，十分適合對大規(guī)模、復(fù)雜的Web服務(wù)組合優(yōu)化問題進行求解。如文獻[7]提出基于蟻群算法的Web服務(wù)組合優(yōu)化模型，但是蟻群算法存在易陷入局部最優(yōu)等缺陷；文獻[8]提出基于模擬退火算法的Web服務(wù)組合優(yōu)化模型；文獻[9]提出基于粒子群優(yōu)化算法Web服務(wù)組合優(yōu)化模型；文獻[10]提出基于遺傳算法Web服務(wù)組合優(yōu)化模型。相對其他算法，它們獲得不錯的效果，同時大量研究結(jié)果表明，遺傳算法更適合于大規(guī)模的Web服務(wù)組合問題求解，具有較明顯的優(yōu)勢。但是遺傳算法存在一些自身難以克服的缺陷：收斂速度慢、易陷入局部最優(yōu)等，為此許多學(xué)者從不同角度對遺傳算法進行了改進，不同程度改善了Web服務(wù)組合的解[11,12]。

為了獲得更優(yōu)的Web服務(wù)優(yōu)化組合方案，提出一種基于改進遺傳算法的Web服務(wù)優(yōu)化組合方法。首先將Web服務(wù)組合優(yōu)化方案的可行解看作遺傳算法的個體。然后通過遺傳算法模擬自然界的生物進化過程，找到是Web服務(wù)組合的最優(yōu)解，同時針對遺傳算法的不足進行改進，以提高問題求解的速度。最后進行仿真對比實驗。

1Web服務(wù)組合的數(shù)學(xué)模型

(1)

(2)

式中，qcom為組合服務(wù)的QoS屬性；qmax、qmin為組合服務(wù)QoS屬性值的最大、最小值。

Web服務(wù)的QoS屬性值及約束值為：

(3)

式中，q1,q2,…,qk為Web服務(wù)的QoS屬性值，c1,c2,…,ck表示QoS屬性對應(yīng)的約束值。

Web服務(wù)優(yōu)化組合問題的數(shù)學(xué)模型可以描述為：

Maxf(CSi)f(CSi)=w1×q1+w2×q2+…+ wk×qk

(4)

式中，CSi為第i個Web服務(wù)組合方案。

根據(jù)式(3)可知，Web服務(wù)組合優(yōu)化問題是指在滿足用戶要求條件下，找到一個QoS較優(yōu)的組合服務(wù)資源。

對式(3)的組合優(yōu)化問題，如果采用人工方法進行求解，無法實現(xiàn)。本文利用改進遺傳算法對Web服務(wù)組合優(yōu)化問題進行優(yōu)化，以獲得更優(yōu)的Web服務(wù)組合優(yōu)化方案。

圖1　標準遺傳算法的工作流程

2改進遺傳算法

2.1標準遺傳算法

1962年，Holland教授等提出了一種基于概率的隨機搜索算法—遺傳算法GA。其將問題的潛在的解表示為個體，并采用適應(yīng)度函數(shù)評價個體的優(yōu)劣，并經(jīng)過交叉、變異、選擇等遺傳操作，找到問題的最優(yōu)解，標準遺傳算法的工作流程如圖1所示[14]。

2.2遺傳算法的改進

大量研究表明，標準遺傳算法存在一定的缺陷，如全局搜索能力差、易出現(xiàn)早熟等，這樣找到問題解是一個局部最優(yōu)解，而非全局最優(yōu)解。為此，本文提出了一種改進遺傳算法。通過引入具有引向因子的交叉算子，并且引入信息共享因子，在保證子代個體向最佳個體靠近的同時，防止早熟收斂現(xiàn)象發(fā)生，改善了解的質(zhì)量，最后利用反向搜索找到問題的全局解。

2.2.1自適應(yīng)交叉操作

標準遺傳算法的交叉算子缺乏方向性，收斂速度慢、搜索效率低。為此，在交叉算子基礎(chǔ)上，改進遺傳算法采用最佳個體替代其中一個交叉?zhèn)€體，并引入了引向因子，使個體搜索有了方向性，加快了收斂速度。同時，引入粒子群算法的群體間信息共享機制，保證個體搜索方向朝著群體最優(yōu)方向進行，不易出現(xiàn)局部收斂現(xiàn)象，克服出現(xiàn)局部最優(yōu)解難題。

(5)

(6)

式中，γ,β∈[0,1]的隨機數(shù)。

交叉概率使用自適應(yīng)交叉概率，即：

(7)

式中，Pc1、Pc2分別為最大和最小交叉概率；fmax、favg分別為種群中最大和平均個體適應(yīng)度；f為種群中個體適應(yīng)度。

2.2.2自適應(yīng)變異操作

(8)

式中，μ的值隨著進化代數(shù)t的增加逐漸減小。

構(gòu)建如下關(guān)系：

(9)

式中，T為最大進化代數(shù)。

根據(jù)式(9)可知，在種群進化初期，r值較小，此時變異尺度較大，加快全局搜索的速度；在進化后期，r值較大，局部搜索能力強。

變異概率使用自適應(yīng)變異概率，即：

(10)

式中，Pm1、Pm2分別為最大和最小變異概率。

2.2.3反向搜索

(11)

式中，xmax(t)和xmin(t)分別為第t代變異操作前的最大值和最小值。

2.3改進遺傳算法的工作步驟

(1) 參數(shù)初始化。確定種群規(guī)模popsize，最大和最小交叉概率分別為：Pc1和Pc2，最大和最小變異概率分別為Pm1和Pm2，最大迭代次數(shù)T。

(2) 產(chǎn)生初始種群。

(3) 計算個體適應(yīng)度值，并根據(jù)適應(yīng)度值對個體進行排序，保留最優(yōu)個體。

(4) 根據(jù)式(12)計算個體被選擇的概率，然后進行輪盤賭選擇。

(12)

式中，q為最佳個體被選中的概率。

(5) 計算每個個體交叉的概率，然后進行交叉操作。

(6) 保存變異前種群最優(yōu)個體和最差個體，然后計算個體的變異概率，并進行變異操作。

(7) 利用反向搜索產(chǎn)生新種群。

(8) 如果滿足算法終止要求，則輸出最優(yōu)結(jié)果，不然返回步驟(3)繼續(xù)進行。

采用3個標準函數(shù)對標準遺傳算法和改進遺傳算法性能進行測試，3個標準函數(shù)具體如下：

① Griewank 函數(shù)：

(13)

② Rastrigin函數(shù)：

(14)

③ Schaffer函數(shù)

(15)

3個標準測試函數(shù)的求解曲線如圖2所示。從圖2可以清楚看出，對于3個標準測試函數(shù)，相對標準遺傳算法，改進遺傳算法的收斂速度快，同時對于多峰值函數(shù)，改進遺傳算法可以較好地找到最優(yōu)解，而標準遺傳算法卻陷入局部最優(yōu)解。結(jié)果表明，改進遺傳算法由于引入具有引向因子的交叉算子，并且引入信息共享因子，在保證子代個體向最佳個體靠近的同時，防止早熟收斂現(xiàn)象發(fā)生，改善了解的質(zhì)量，提高了算法的收斂性能，可以獲得理想的結(jié)果。

圖2　標準遺傳算法和改進遺傳算法的性能對比

3仿真實驗

3.1仿真環(huán)境

為了測試改進遺傳算法的Web組合服務(wù)問題求解有效性，在CPU：Pentium(R) 3.00 GHz，4.00 GB RAM，Windows XP操作系統(tǒng)，100 Mb/s局域網(wǎng)，采用Java語言實現(xiàn)服務(wù)Web 組合服務(wù)算法的仿真實驗。設(shè)Web組合服務(wù)由20個Web子服務(wù)串聯(lián)而成，每個服務(wù)節(jié)點有20個候選服務(wù)可供選擇，每個候選服務(wù)的QoS參數(shù)采用隨機方法在一定的范圍內(nèi)生成，具體參見文獻[14]。

3.2不同算法的比較分析

使用文獻[11,12]遺傳算法和改進遺傳算法對Web組合服務(wù)問題進行求解，它們的平均運行時間如圖3所示。由圖3可以看出，對比各算法，改進遺傳算法搜索速度明顯加快。主要由于引入了多尺度變異算子和反向搜索策略，加快算法收斂的速度，提高了Web組合服務(wù)問題的求解效率，證明本文對遺傳算法進行改進，并應(yīng)用Web組合服務(wù)問題求解的思想是可行的，且具有一定的優(yōu)越性。

圖3　不同算法的平均運行時間比較

使用文獻[11,12]遺傳算法和改進遺傳算法的的Web組合服務(wù)最優(yōu)方案的優(yōu)化結(jié)果如圖4所示。從圖4可以清晰地看出，本文改進遺傳算法的性能明顯優(yōu)于對比算法。對比結(jié)果表明，采用本文算法對Web組合服務(wù)問題進行求解，搜索能力較強，可以快速地找到用戶條件的服務(wù)組合，是一種有效解決Web組合服務(wù)問題的方法。

圖4　不同算法的優(yōu)化結(jié)果比較

4結(jié)語

Web服務(wù)組合優(yōu)化是當(dāng)前電子商務(wù)領(lǐng)域中的一個研究熱點問題，本文借助信息共享機制和多尺度交叉算子，提出一種基于改進遺傳算法的Web服務(wù)優(yōu)化組合方法。實驗結(jié)果表明，改進遺傳算法的全局搜索能力強，而且搜索速度快，可以在較短時間找到Web服務(wù)組合優(yōu)化問題的最優(yōu)解。

參考文獻

[1] Chen Ming,Wang Zhenwu.An approach for web services composition based on QoS and discrete particle swarm optimization[C]//Proceedings of the Eighth ACIS International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing,2010:37-41.

[2] Canfora G,Penta M Di,Esposito R,et al.A lightweight approach for QoS-aware service composition[C]//Proceedings of the 2nd International Conference on Service Oriented Computing,2014,1:36-47.

[3] 王創(chuàng)偉,錢雪忠.蟻群算法在Web服務(wù)組合問題中的應(yīng)用研究[J].計算機工程與設(shè)計,2007,28(24):5912-5914.

[4] 彭曉明,何炎祥,朱兵艦.蟻群算法在Web服務(wù)組合中的應(yīng)用[J].計算機工程,2009,35(10):181-187.

[5] 劉莉萍,陳志剛,劉愛心.基于粒子群算法的Web服務(wù)組合研究[J].計算機工程,2008,34(5):104-106.

[6] 周清雷,陳明昭,張兵.多目標人工蜂群算法在服務(wù)組合優(yōu)化中的應(yīng)用[J].計算機應(yīng)用研究,2012,29(10):3626-3628.

[7] 李東民,鐘佩思,劉梅,等.基于業(yè)務(wù)流程的物流Web服務(wù)組合匹配研究[J].青島農(nóng)業(yè)大學(xué)學(xué)報,2009,26(1):56-60.

[8] 戴雪梅,姜浩.基于帶權(quán)圖規(guī)劃算法的語義Web服務(wù)組合[J].計算機技術(shù)與發(fā)展,2013,20(3):68-75.

[9] 夏虹,李增智.粒子群算法求解Web服務(wù)組合中基于QoS的服務(wù)選擇[J].北京郵電大學(xué)學(xué)報,2012,32(4):63-67.

[10] 黃振光,徐家興,余陽.三段式動態(tài)服務(wù)組合優(yōu)化算法[J].計算機集成制造系統(tǒng),2012,18(8):1712-1718.

[11] 張成文,蘇森,陳俊亮.基于遺傳算法的QoS感知的Web服務(wù)選擇[J].計算機學(xué)報,2009,29(7):1029-1037.

[12] 毛一梅,樂嘉錦.基于遺傳算法的Web服務(wù)組合優(yōu)化[J].計算機應(yīng)用與軟件,2008,25(11):199-201,277.

[13] 王肖燕.基于QoS的Web物流服務(wù)組合的優(yōu)化模型[D].廣東:中山大學(xué),2012.

[14] Liu Qing,Zhang Shilong.Web service composition with QoS bound based on simulated annealing algorithm[J].Journal of Southeast University,20011,24(3):308-311.

ON OPTIMISATION OF WEB SERVICE COMPOSITION BASED ON IMPROVED GENETIC ALGORITHM

Xu TianLiu Lingxia

(DepartmentofComputingCenter,AnyangNormalUniversity,Anyang455000,Henan,China)

AbstractIn order to obtain better optimisation scheme of Web service composition, this paper proposes an optimisation method which is based on the improved genetic algorithm. First, it deems the feasible optimisation scheme of Web service composition as the individual of genetic algorithm, and then simulates the biological evolution in nature through genetic algorithm to find optimal solution of Web service composition; meanwhile it introduces multi-scale crossover operator and information sharing factor to standard genetic algorithm to improve problem’s solving speed. Finally we carry out the comparative experiments in simulation. Results show that the improved genetic algorithm can find the optimal solution of Web service composition problem quickly and accurately, this provides a new solution idea to the problem of Web service composition.

KeywordsWeb servicesGenetic algorithmService compositionQuality of service

收稿日期：2014-08-13。徐甜，副教授，主研領(lǐng)域：機器學(xué)習(xí)，數(shù)據(jù)挖掘。劉凌霞，副教授。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.007