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

徐　甜　劉凌霞

(安陽(yáng)師范學(xué)院計(jì)算中心　河南 安陽(yáng) 455000)

?

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

徐甜劉凌霞

(安陽(yáng)師范學(xué)院計(jì)算中心河南 安陽(yáng) 455000)

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

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

0引言

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

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

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

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屬性對(duì)應(yīng)的約束值。

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

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

(4)

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

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

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

圖1　標(biāo)準(zhǔn)遺傳算法的工作流程

2改進(jìn)遺傳算法

2.1標(biāo)準(zhǔn)遺傳算法

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

2.2遺傳算法的改進(jìn)

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

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

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

(5)

(6)

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

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

(7)

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

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

(8)

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

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

(9)

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

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

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

(10)

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

2.2.3反向搜索

(11)

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

2.3改進(jìn)遺傳算法的工作步驟

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

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

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

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

(12)

式中，q為最佳個(gè)體被選中的概率。

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

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

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

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

采用3個(gè)標(biāo)準(zhǔn)函數(shù)對(duì)標(biāo)準(zhǔn)遺傳算法和改進(jìn)遺傳算法性能進(jìn)行測(cè)試，3個(gè)標(biāo)準(zhǔn)函數(shù)具體如下：

① Griewank 函數(shù)：

(13)

② Rastrigin函數(shù)：

(14)

③ Schaffer函數(shù)

(15)

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

圖2　標(biāo)準(zhǔn)遺傳算法和改進(jìn)遺傳算法的性能對(duì)比

3仿真實(shí)驗(yàn)

3.1仿真環(huán)境

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

3.2不同算法的比較分析

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

圖3　不同算法的平均運(yùn)行時(shí)間比較

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

[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ù)組合問(wèn)題中的應(yīng)用研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(24):5912-5914.

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

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

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

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

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

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

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

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

[12] 毛一梅,樂(lè)嘉錦.基于遺傳算法的Web服務(wù)組合優(yōu)化[J].計(jì)算機(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)域：機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘。劉凌霞，副教授。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

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