基于改進遺傳算法的Web服務優化組合研究

徐　甜　劉凌霞

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

?

基于改進遺傳算法的Web服務優化組合研究

徐甜劉凌霞

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

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

關鍵詞Web服務遺傳算法服務組合服務質量

0引言

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

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

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

1Web服務組合的數學模型

(1)

(2)

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

Web服務的QoS屬性值及約束值為：

(3)

式中，q1,q2,…,qk為Web服務的QoS屬性值，c1,c2,…,ck表示QoS屬性對應的約束值。

Web服務優化組合問題的數學模型可以描述為：

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

(4)

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

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

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

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

2改進遺傳算法

2.1標準遺傳算法

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

2.2遺傳算法的改進

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

2.2.1自適應交叉操作

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

(5)

(6)

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

交叉概率使用自適應交叉概率，即：

(7)

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

2.2.2自適應變異操作

(8)

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

構建如下關系：

(9)

式中，T為最大進化代數。

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

變異概率使用自適應變異概率，即：

(10)

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

2.2.3反向搜索

(11)

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

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

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

(2) 產生初始種群。

(3) 計算個體適應度值，并根據適應度值對個體進行排序，保留最優個體。

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

(12)

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

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

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

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

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

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

① Griewank 函數：

(13)

② Rastrigin函數：

(14)

③ Schaffer函數

(15)

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

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

3仿真實驗

3.1仿真環境

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

3.2不同算法的比較分析

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

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

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

圖4　不同算法的優化結果比較

4結語

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

參考文獻

[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] 王創偉,錢雪忠.蟻群算法在Web服務組合問題中的應用研究[J].計算機工程與設計,2007,28(24):5912-5914.

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

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

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

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

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

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

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

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

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

[13] 王肖燕.基于QoS的Web物流服務組合的優化模型[D].廣東:中山大學,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。徐甜，副教授，主研領域：機器學習，數據挖掘。劉凌霞，副教授。

中圖分類號TP391

文獻標識碼A

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