王 妍，劉瑜嵐，荊紫慧，張以文

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230031）

基于混沌機(jī)制和改進(jìn)粒子群算法的Web服務(wù)組合優(yōu)化

王 妍，劉瑜嵐，荊紫慧，張以文*

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230031）

隨著互聯(lián)網(wǎng)和大數(shù)據(jù)的迅速發(fā)展，如何從大量Web服務(wù)中選擇合適服務(wù)及組合以滿足用戶需求已成為新的熱點(diǎn)。本文提出一種改進(jìn)的混沌粒子群優(yōu)化（ICPSO）算法，應(yīng)用到Web服務(wù)組合優(yōu)化問(wèn)題。針對(duì)傳統(tǒng)PSO算法易陷入早熟收斂和局部最優(yōu)的缺點(diǎn)，該算法引入了混沌擾動(dòng)機(jī)制使粒子易跳出局部極值，增強(qiáng)了種群多樣性，從而提高算法尋優(yōu)能力。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了ICPSO算法的可行性和有效性。

服務(wù)組合；ICPSO算法；混沌機(jī)制；服務(wù)質(zhì)量

隨著面向服務(wù)計(jì)算（service-oriented computing）技術(shù)的迅速發(fā)展，基于Web服務(wù)的分布式計(jì)算模式正成為技術(shù)發(fā)展的趨勢(shì)[1,2]。Web服務(wù)作為一種能夠自適應(yīng)、自描述和模塊化的應(yīng)用模式，吸收了分布式計(jì)算、網(wǎng)格計(jì)算和XML等各種技術(shù)的優(yōu)點(diǎn)，包括平臺(tái)無(wú)關(guān)性、松散耦合性、規(guī)范約束協(xié)議以及封裝性等，使其廣泛應(yīng)用于基于Internet環(huán)境的異構(gòu)系統(tǒng)的互操作與應(yīng)用系統(tǒng)集成。

然而，越來(lái)越多的功能相同或相近而服務(wù)質(zhì)量不同的服務(wù)出現(xiàn)在網(wǎng)絡(luò)上。而單個(gè)Web服務(wù)所具有的功能一般都比較單一，無(wú)法滿足用戶服務(wù)質(zhì)量（Quality of Service,QoS）的復(fù)雜需求，因此如何從多個(gè)功能單一的Web候選服務(wù)中挑選出若干服務(wù)并形成一個(gè)滿足用戶復(fù)雜需求的組合服務(wù)已成為服務(wù)計(jì)算領(lǐng)域的研究重點(diǎn)[3,4]。為了能夠滿足用戶業(yè)務(wù)需求，提供更強(qiáng)大的服務(wù)功能，有必要根據(jù)特定的應(yīng)用場(chǎng)景和需求對(duì)現(xiàn)有的服務(wù)進(jìn)行有效的組合。因此Web服務(wù)組合問(wèn)題也就成了典型的NP-hard問(wèn)題。

為此，本文提出了一種基于混沌理論的改進(jìn)的粒子群算法來(lái)解決Web服務(wù)組合優(yōu)化問(wèn)題，其基本思想體現(xiàn)在以下幾個(gè)方面：

1 相關(guān)工作

近年來(lái)，工業(yè)界和學(xué)業(yè)界分別應(yīng)用不同的方法對(duì)Web服務(wù)組合優(yōu)化問(wèn)題進(jìn)行了研究。在服務(wù)組合優(yōu)化問(wèn)題研究中，服務(wù)組合模型是由多個(gè)服務(wù)節(jié)點(diǎn)按照一定的邏輯順序關(guān)系組成，每個(gè)服務(wù)節(jié)點(diǎn)是若干服務(wù)實(shí)例的抽象類，這些候選服務(wù)實(shí)例具有相同功能但不同非功能屬性（QoS），且QoS又是評(píng)價(jià)一個(gè)Web服務(wù)的重要指標(biāo)。目前，基于QoS的服務(wù)組合優(yōu)化方法主要可分為兩大類，第一類是傳統(tǒng)計(jì)算方式的優(yōu)化方法，如窮舉法、動(dòng)態(tài)規(guī)劃、線性規(guī)劃、和圖算法等。Alrifai等人[5]提出了一個(gè)把全局優(yōu)化和局部選擇技術(shù)結(jié)合在一起的混合方案去解決服務(wù)組合問(wèn)題。范小芹等人[6]利用隨機(jī)型離散事件系統(tǒng)的馬爾科夫決策過(guò)程(MDP),提出了Web服務(wù)各隨機(jī)QoS指標(biāo)的度量方法，設(shè)計(jì)出隨機(jī)QoS感知的可靠Web服務(wù)組合算法。第二類是智能優(yōu)化算法，如遺傳算法、蟻群算法、粒子群算法等。張成文等人[7]提出一種基于遺傳算法的QoS感知的Web服務(wù)選擇算法，可以有效的從全部組合方案中選出滿足用戶QoS需求的服務(wù)組合。Zhang等人[8]在服務(wù)組合優(yōu)化過(guò)程中應(yīng)用蟻群算法提出了一個(gè)基于QoS的動(dòng)態(tài)服務(wù)組合方法。與遺傳算法和蟻群算法相比，粒子群算法具有參數(shù)少、收斂速度快的特點(diǎn)，在很多優(yōu)化問(wèn)題上表現(xiàn)出良好的搜索能力。劉莉平等人[9]針對(duì)現(xiàn)有服務(wù)組合中QoS優(yōu)化的不足，利用粒子群算法的智能優(yōu)化原理加快粒子群的搜索速度，提出了一種基于粒子群算法的QoS動(dòng)態(tài)服務(wù)組合算法，不過(guò)該算法中種群的粒子容易陷入局部最優(yōu)值。范小芹等人[10]提出了一種面向動(dòng)態(tài)Web服務(wù)選擇的離散粒子群算法，為了增強(qiáng)算法的全局搜索能力，定義相關(guān)的準(zhǔn)則。胡旺等人[11]采用簡(jiǎn)化粒子群優(yōu)化方程和添加極值擾動(dòng)算子兩種策略，提出了簡(jiǎn)化粒子群優(yōu)化算法，避免了由粒子速度引起的粒子發(fā)散而導(dǎo)致后期收斂慢和精度低的問(wèn)題。基于以上分析，PSO算法較其他方法能更好的解決服務(wù)組合優(yōu)化問(wèn)題，但在進(jìn)行組合時(shí)種群的粒子易被當(dāng)前全局最優(yōu)粒子吸引而快速收斂于局部最優(yōu)值。同時(shí)，候選服務(wù)的規(guī)模越來(lái)越大，傳統(tǒng)的優(yōu)化技術(shù)已無(wú)法有效地處理該問(wèn)題。為此，本文提出了改進(jìn)的混沌粒子群算法解決服務(wù)組合優(yōu)化問(wèn)題，引入混沌優(yōu)化思想提高種群多樣性。

2 組合服務(wù)模型描述

定義1 Web服務(wù)（WS）是一種具有跨平臺(tái)、低耦合、高度可集成、模塊化的軟件應(yīng)用程序。用WSi=(Ii,Oi,QoSi)表示一個(gè)服務(wù)，其中Ii為第i個(gè)服務(wù)的輸入，Oi為第i個(gè)服務(wù)的輸出，QoSi為其對(duì)應(yīng)的非功能屬性服務(wù)質(zhì)量。

定義2 服務(wù)質(zhì)量（QoS）是服務(wù)的非功能屬性，本文中服務(wù) QoS用一個(gè)四元組表示QoS=(T,C,A,R)，其中T表示響應(yīng)時(shí)間，C表示調(diào)用一次服務(wù)的費(fèi)用，A表示可用性，R表示可靠性。

定義3 候選服務(wù)集（SS）是由一組具體Web服務(wù)組成的集合，這些服務(wù)具有一樣的功能但QoS不同。組合服務(wù)模型中每個(gè)服務(wù)都有一個(gè)相對(duì)應(yīng)的候選服務(wù)集，用SSj表示第 j個(gè)服務(wù)對(duì)應(yīng)的候選服務(wù)集。

定義4 組合服務(wù)（CS）是由候選服務(wù)集中服務(wù)依據(jù)服務(wù)模型，形成的一個(gè)具體的Web服務(wù)序列。用一個(gè)五元組表示CS=(QoS,L,S,W,F)，其中本文服務(wù)包含四個(gè)QoS屬性，L是服務(wù)直接關(guān)系的集合，W 是屬性權(quán)重 W={w1,w2,w3,w4}且w1+w2+w3+w4=1，S是組合模型中的所有服務(wù)集S={S1,S2,...,Sj,...,Sn}，F(xiàn)是組合服務(wù)評(píng)價(jià)函數(shù)。

Web組合服務(wù)有多個(gè)原子服務(wù)組合而成，原子服務(wù)之間有明確的邏輯執(zhí)行循序。服務(wù)組合是根據(jù)各原子服務(wù)間的邏輯關(guān)系，重用已有的Web服務(wù)，組合成能夠滿足用戶業(yè)務(wù)需求的服務(wù)組合。根據(jù)其邏輯執(zhí)行關(guān)系，服務(wù)組合流程有如下四種基本結(jié)構(gòu)。

以上模型的QoS計(jì)算公式如表1所示。

對(duì)以上Web服務(wù)的QoS屬性，可劃分為兩種類型：積極型和消極型。積極型（positive型)，其指標(biāo)值越大服務(wù)質(zhì)量越好，如可靠性、可用性。消極型（negative型)，如響應(yīng)時(shí)間、費(fèi)用等，其指標(biāo)越小，服務(wù)質(zhì)量越好。為統(tǒng)一度量組合服務(wù)的QoS屬性，需要對(duì)各個(gè)QoS屬性進(jìn)行標(biāo)準(zhǔn)化?？刹捎霉剑?）和（2）分別對(duì)消極屬性和積極屬性進(jìn)行歸一化處理。

3 標(biāo)準(zhǔn)PSO算法

PSO算法是1995年由Eberhart和Kennedy博士提出的一種啟發(fā)式進(jìn)化計(jì)算方法[12]，來(lái)源于對(duì)生物群體智能行為的簡(jiǎn)化模擬。PSO算法在初始階段隨機(jī)產(chǎn)生一個(gè)初始種群并賦予種群中每個(gè)粒子一個(gè)隨機(jī)速度，在飛行過(guò)程中粒子速度依據(jù)自身以及種群飛行經(jīng)驗(yàn)進(jìn)行不斷調(diào)整，使整個(gè)種群能夠飛向更好的搜索區(qū)域，從而發(fā)現(xiàn)較優(yōu)的解。

PSO具體算法具體實(shí)現(xiàn)步驟描述如下：

Step 1初始化粒子群，隨機(jī)初始化種群中每個(gè)粒子的位置與速度。

Step 2根據(jù)適應(yīng)度函數(shù)Fitness(x)，計(jì)算出每個(gè)粒子位置的適應(yīng)度值。

Step 3更新pbest，對(duì)比粒子本次迭代位置與其歷史最佳位置，若 Fitness(xi)＞Fitness(pbest)，則Fitness(pbest)=Fitness(xi)。

Step 4更新gbest，找出當(dāng)前種群中適應(yīng)度值最大的粒子，假設(shè)為xg，若Fitness(xg)＞Fitness(gbest)，則Fitness(gbest)=Fitness(xg)。

Step 5根據(jù)公式（3）和（4）更新粒子的位置和速度。

Step 6檢驗(yàn)是否滿足終止條件(通常是達(dá)到最大迭代次數(shù)或得到滿足一定條件的較優(yōu)解)，若滿足，終止迭代，算法結(jié)束。否則返回步驟Step 2。

4 基于改進(jìn)ICPSO算法的服務(wù)組合算法

4.1 混沌機(jī)制及其特性

一般將由確定性方程得到的具有隨機(jī)性的運(yùn)動(dòng)狀態(tài)稱為混沌，混沌狀態(tài)廣泛存在于自然現(xiàn)象和社會(huì)現(xiàn)象中，是非線性系統(tǒng)中一種較為普遍的現(xiàn)象，其行為復(fù)雜且類似隨機(jī)?；煦缱兓^(guò)程看似一片混亂，但實(shí)際上并不是一片混亂，而是有著內(nèi)在結(jié)構(gòu)的一類現(xiàn)象。

混沌變量有以下特點(diǎn)：隨機(jī)性即它的分布雜亂，如同隨機(jī)變量。遍歷性即它可以遍歷空間區(qū)域內(nèi)的所有狀態(tài)且不重復(fù)。規(guī)律性該變量是由確定的混沌模型迭代導(dǎo)出的。

混沌優(yōu)化算法是一種智能優(yōu)化算法，利用混沌特性在一定范圍內(nèi)進(jìn)行優(yōu)化搜索。其基本思想是首先產(chǎn)生一組混沌變量，其數(shù)量與待求解問(wèn)題中的優(yōu)化變量相同，利用混沌變量具有隨機(jī)性、遍歷性和規(guī)律性的特點(diǎn)進(jìn)行混沌擾動(dòng)產(chǎn)生新解，同時(shí)把混沌變量的運(yùn)動(dòng)范圍映射到優(yōu)化變量的解空間，對(duì)優(yōu)化變量做出優(yōu)劣評(píng)價(jià)，經(jīng)多次迭代，最終產(chǎn)生最優(yōu)解。Logistic映射方程是一個(gè)典型的混沌系統(tǒng)[13]：

其中μ為控制變量，當(dāng)μ=4時(shí)，系統(tǒng)（5）進(jìn)入完全混沌狀態(tài)，對(duì)于任意的χ(0)∈[0,1],可根據(jù)Logistic方程迭代出一個(gè)序列χ(1)，χ(2)，χ(3),…。

4.2 算法改進(jìn)策略

4.2.1 混沌初始化種群

假設(shè)種群中有m個(gè)粒子群，搜索空間為n維,即Web服務(wù)組合模型中有n個(gè)服務(wù)類。粒子位置變量則表示服務(wù)組合優(yōu)化的解（即可行的組合服務(wù)方案），粒子的位置可用一個(gè)n維向量來(lái)表示，本文采用整數(shù)編碼，若第j個(gè)服務(wù)類Sj對(duì)應(yīng)的候選服務(wù)集規(guī)模為hj，候選服務(wù)集中的每個(gè)候選服務(wù)依次進(jìn)行編碼，則第z個(gè)候選服務(wù)對(duì)應(yīng)的編號(hào)為z，其中z是區(qū)間[1,hj]上的整數(shù)，初始化時(shí)粒子位置的每一維都是整數(shù)，即對(duì)應(yīng)得候選服務(wù)集中Web服務(wù)的編號(hào)。例如向量 xi=(xi,1,xi,2,...,xi,n)表示粒子i的位置，則xi,j表示第i種服務(wù)組合方案中第j個(gè)服務(wù)類的編號(hào)為xi,j的候選服務(wù)。

本文采用混沌序列初始化粒子群中的粒子，對(duì)簡(jiǎn)單的一維邏輯混沌映射模型公式（5）的進(jìn)行重寫，描述形式如下：

其中，μ取值與公式（5）相同，t是迭代次數(shù)，ctj為粒子位置在 j維上的混沌變量，初始化生一個(gè)n維的混沌序列，采用 公 式（6）進(jìn) 行 m-1次 混 沌 迭 代 ，即則產(chǎn)生 m-1個(gè)混沌序列，然后將每個(gè)混沌序列利用公式（4）行映射到粒子位置解空間，最終得到m個(gè)粒子的初始化位置。

hj是第k個(gè)粒子位置第j維的解空間大小，即第j個(gè)服務(wù)類的候選服務(wù)規(guī)模。對(duì)變量四舍五入，保證粒子位置映射到解空間。

4.2.2 早熟收斂處理機(jī)制

PSO算法解決服務(wù)組合優(yōu)化問(wèn)題時(shí)種群易陷入早熟收斂狀態(tài)，導(dǎo)致得到的解很可能不是全局最優(yōu)的，本文根據(jù)種群的多樣性和種群在進(jìn)化過(guò)程中找到最優(yōu)解的波動(dòng)程度，判斷種群是否陷入早熟收斂，同時(shí)采用Chaos-Process混沌擾動(dòng)機(jī)制處理粒子群早熟收斂狀態(tài)，提高種群多樣性。本文參考文獻(xiàn)[14]，當(dāng)粒子群多樣性小于0.35且K代最優(yōu)算法平均數(shù)在連續(xù)10代內(nèi)不發(fā)生變化，則認(rèn)為滿足收斂條件，粒子群早熟，此時(shí)啟動(dòng)混沌擾動(dòng)機(jī)制增加種群多樣性。

混沌擾動(dòng)機(jī)制Chaos-Process描述如下：

For（j=1:n）：

將Chaos1i[j]映射到粒子維數(shù)區(qū)間[1,n]內(nèi)得到num1，然后將Chaos2i[j]映射到第num1維服務(wù)類的候選服務(wù)集中得到服務(wù)編號(hào)num2。用num2替換 xi[num1]得到新的粒子位置 xi_new，但Fitness(xi)＜Fitness(xi_new)，則xi=xi_new。

當(dāng)種群陷入早熟收斂時(shí)，經(jīng)過(guò)Chaos-Process混沌擾動(dòng)機(jī)制處理使種群中所有粒子進(jìn)行混沌搜索，提高種群多樣性，加速全局最優(yōu)解粒子以及其它粒子附近的進(jìn)一步搜索，而且可以使粒子更易跳出局部極值，提高算法的尋優(yōu)能力。

4.3 ICPSO算法描述

ICPSO算法首先使用Skyline操作[15]對(duì)所有服務(wù)類對(duì)應(yīng)的候選服務(wù)集進(jìn)行處理，剔除那些被其他服務(wù)支配的候選服務(wù)，保留可能成為最優(yōu)服務(wù)組合的潛在候選者，從而得到Skyline服務(wù)。然后從每個(gè)服務(wù)類的Skyline服務(wù)中進(jìn)行Web服務(wù)選擇，提高了服務(wù)選擇效率。采用混沌序列初始化粒子群，使初始種群保留了經(jīng)典PSO算法中的隨機(jī)性，同時(shí)由于混沌的特性使得種群的多樣性得到提高。Chaos-Process混沌擾動(dòng)機(jī)制針對(duì)粒子群易陷入早熟收斂狀態(tài)，進(jìn)行有效處理，提高種群多樣性改善解質(zhì)量。

ICPSO算法具體實(shí)現(xiàn)描述如下：輸入：所有服務(wù)類的候選服務(wù)集輸出：最優(yōu)組合服務(wù)

Step 1：使用Skyline操作處理所有服務(wù)類的候選服務(wù)集，得到每個(gè)服務(wù)類的Skyline服務(wù)。

Step 2：設(shè)置當(dāng)前迭代次數(shù)t=0，并混沌初始化粒子群中m個(gè)粒子的位置。

Step 3：計(jì)算粒子群中粒子的適應(yīng)度值

Step 5：根據(jù)

Step 6：t=t+1。

Step 7：計(jì)算粒子群中所有粒子適應(yīng)度值

Step 8：更新粒子歷史最優(yōu)解

Step 10：計(jì)算粒子群多樣性psdis和K代最優(yōu)算術(shù)平均kma，判斷粒子群是否收斂。

Step 11：If（滿足收斂條件）then啟動(dòng)Chaos-Process增加種群多樣性。

Step 12：If t＜T（最大迭代次數(shù)）then轉(zhuǎn)到Step 5。

Step 13：結(jié)束。

其中，搜索空間為 n維，種群規(guī)模為 m，X=(x1,x2,…,xm)表示整個(gè)粒子群。粒子 i位置xi=(xi,1,xi,2,…,xi,n)，速度 vi=(vi,1,vi,2,…,vi,n)，粒子 i歷史最優(yōu)解 pi=(pi,1,pi,2,…,pi,n)，全局最優(yōu)解pg=(pg,1,pg,2,…,pg,n)。

5 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文的實(shí)驗(yàn)數(shù)據(jù)采用公共數(shù)據(jù)集QWS[16,17]。實(shí)驗(yàn)基于順序型服務(wù)組合模型，且模型中包含7個(gè)服務(wù)類，默認(rèn)情況下每個(gè)服務(wù)類的候選服務(wù)集規(guī)模為500，最大迭代次數(shù)為500次，每個(gè)候選服務(wù)有 4個(gè) QoS屬性，即響應(yīng)時(shí)間(T，response time)、可靠性（R，reliability）、可用性（A，availability）和費(fèi)用（C，cost）。QoS屬性值在規(guī)定范圍內(nèi)均勻分布，參數(shù)取值范圍參考表1。ICPSO代表本文提出的算法，CPSO代表文獻(xiàn)[18]中提出的算法是由Wang等人[19]提出的改進(jìn)粒子群算法以解決服務(wù)組合優(yōu)化問(wèn)題。假設(shè)種群規(guī)模m=100，對(duì)于以下實(shí)驗(yàn)結(jié)果，算法運(yùn)行50次取平均值。

5.1 可行性

為驗(yàn)證本文提出的ICPSO算法在解決Web服務(wù)組合優(yōu)化問(wèn)題的可行性，將ICPSO算法與其它算法分別在不同服務(wù)候選規(guī)模下與不同迭代次數(shù)下的求解質(zhì)量進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖1所示。

通過(guò)圖1的實(shí)驗(yàn)結(jié)果可以看出，本文算法的尋優(yōu)結(jié)果明顯優(yōu)于算法其它兩種算法，CPSO算法與Proposed by Wang算法的尋優(yōu)結(jié)果差不多。在ICPSO算法中，本文針對(duì)粒子群算法易陷入早熟收斂，導(dǎo)致所求得的解為局部最優(yōu)解的缺點(diǎn)采用Chaos-Process混沌擾動(dòng)機(jī)制進(jìn)行早熟收斂處理。引入混沌優(yōu)化的思想使種群中所有粒子進(jìn)行混沌搜索，提高種群多樣性，加速全局最優(yōu)粒子以及其它粒子附近的進(jìn)一步搜索，而且可以使粒子更易跳出局部極值，從而使更易找到更好的解。

5.2 穩(wěn)定性

為驗(yàn)證本文提出的ICPSO算法在解決Web服務(wù)組合優(yōu)化問(wèn)題的穩(wěn)定性，將ICPSO算法與其它算法分別在不同服務(wù)候選規(guī)模下與不同迭代次數(shù)下的運(yùn)行50次實(shí)驗(yàn)所求得解的方差進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果如圖2。

通過(guò)圖2的實(shí)驗(yàn)結(jié)果可以看出，本文的ICPSO算法在不同服務(wù)候選規(guī)模下與不同迭代次數(shù)下的方差小于其它兩種算法，所以ICPSO算法具有較好的穩(wěn)定性，總體上比CPSO算法好。隨著候選服務(wù)規(guī)模的增加，組合服務(wù)可選方案數(shù)量也增加，因此增加了服務(wù)選擇難度，總體上方差值也有小服務(wù)的增加，即候選服務(wù)規(guī)模越大選優(yōu)性能穩(wěn)定性越差。但由于ICPSO算法先采用Skyline操作對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，剔除冗余服務(wù)減少了服務(wù)選擇空間，在粒子群初始化階段，利用混沌的特征初始化種群，使初始種群中粒子位置既保留了經(jīng)典PSO的隨機(jī)性，又利用混沌變量的優(yōu)點(diǎn)提高種群的多樣性與搜索的遍歷性，以及對(duì)于粒子群陷入早熟時(shí)的處理操作提高求解質(zhì)量，增加較優(yōu)組合服務(wù)被選中的幾率，因此算法穩(wěn)定性也有所提高。

6 結(jié)束語(yǔ)

本文研究了標(biāo)準(zhǔn)粒子群算法在Web服務(wù)組合優(yōu)化問(wèn)題上的應(yīng)用，結(jié)合Skyline技術(shù)以及混沌的思想提出一種改進(jìn)的混沌粒子群算法（ICPSO），在數(shù)據(jù)預(yù)處理階段引入Skyline操作，減少服務(wù)選擇搜索空間，提高服務(wù)選擇效率。在初始化階段混沌初始化種粒子群，當(dāng)種群陷入早熟收斂狀態(tài)時(shí)，采用Chaos-Process混沌擾動(dòng)機(jī)制增加粒子群多樣性，增強(qiáng)全局搜索能力，提高服務(wù)組合質(zhì)量。最后通過(guò)仿真實(shí)驗(yàn)對(duì)算法的綜合性能驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，ICPSO在服務(wù)優(yōu)化問(wèn)題上，較其他算法有更好的可行性和有效性。

[1]Papazoglou M P,Traverso P,Dustdar S,et al.Service-Oriented Computing:State of the Art and Research Challenges[J].Computer,2007,40(11):38-45.

[2]鄧水光，吳朝暉.Web服務(wù)組合方法綜述[J].中國(guó)科技論文在線，2008，3（2）：79-84．

[3]Zhang Y W,Cui G M,Zhao S,et al.IFOA4WSC:a quick and effective algorithm for QoS-aware service composition[J].International Journal of Web&Grid Services,2016,12(1):81-108.

[4]王尚廣，孫其博，楊放春.基于全局QoS約束分解的Web服務(wù)動(dòng)態(tài)選擇[J].軟件學(xué)報(bào)，2011，22（7）：1426-1439．

[5]Alrifai M,Risse T,Nejdl W.A hybrid approach for efficient Web service composition with end-to-end QoS constraints[J].Acm Transactions on the Web,2012,6 (2):373-382.

[6]范小芹，蔣昌俊，王俊麗，等.隨機(jī)QoS感知的可靠Web服務(wù)組合[J].軟件學(xué)報(bào)，2009,20（3）：546-556．

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

[8]Zhang W,Chang C K,Feng T M,et al.QoS-Based Dynamic Web Service Composition with Ant Colony Optimization[C]//Computer Software and Applications Conference(COMPSAC),2010 IEEE 34th Annual. IEEE,2010:493-502.

[9]劉莉平，陳志剛，劉愛心.基于粒子群算法的Web服務(wù)組合研究[J].計(jì)算機(jī)工程，2008，34（5）：104-106．

[10]范小芹，蔣昌俊，方賢文，等.基于離散微粒群算法的動(dòng)態(tài)Web服務(wù)選擇[J].計(jì)算機(jī)研究與發(fā)展，2010，47（1）：147-156．

[11]胡 旺，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報(bào)，2007，18（4）：861-868．

[12]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//International Symposium on MICRO Machine and Human Science.1995:39-43.

[13]Alatas B,Akin E,Ozer A B.Chaos embedded particle swarm optimization algorithms[J].Chaos Solitons& Fractals,2009,40(4):1715-1734.

[14]溫 濤，盛國(guó)軍，郭 權(quán)，等.基于改進(jìn)粒子群算法的Web服務(wù)組合[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（05）：1031-1046．

[15]Alrifai M,Skoutas D,Risse T.Selecting skyline services for QoS-based web service composition[C]//International Conference on World Wide Web.2010:11-20.

[16]Al-Masri E,Mahmoud Q H.Discovering the best web service:A neural network-based solution[C]//IEEE International Conference on Systems.IEEE,2009: 4250-4255..

[17]Al-Masri E,Mahmoud Q H.QoS-based Discovery and Ranking of Web Services[C]//Computer Communications and Networks,2007.ICCCN 2007.Proceedings of 16th International Conference on.IEEE,2007:529-534.

[18]Wang L,He Y X.Web Service Composition Based on QoS with Chaos Particle Swarm Optimization[C]// Wireless Communications Networking and Mobile Computing(WiCOM),2010 6th International Conference on.IEEE,2010:1-4.

[19]Wang S G,Sun Q B,Zou H,et al.Particle Swarm Optimization with Skyline Operator for Fast Cloud-based Web Service Composition[J].Mobile Networks&Applications,2013,18(1):116-121.

Web service composition optimization based on chaotic mechanism and improved particle swarm optimization

WANG Yan,LIU Yu-lan,JING Zi-hui,ZHANG Yi-wen*
(Key Laboratory of Intelligent Computing and Signal Processing,Anhui University,Hefei Anhui 230031,China)

with the rapid development of internet and big data,it becomes a hotspot to select appropriate ones from substantial web services and composite them to meet users’requirements.So an improved chaotic particle swarm optimization algorithm(ICPSO)is presented and applied to web service composition optimization problem.As the traditional PSO is easy to fall into premature convergence and local optimum,chaotic mechanism is introduced to make the particle jump out of local optimum,thereby enhancing population diversity and improving the optimization capacity.Finally the feasibility and effectiveness of ICPSO are verified through simulation experiments.

service composition;improved chaotic particle swarm optimization algorithm;chaotic mechanism;QoS

TP311

A

1004-4329（2017）01-066-07

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）01-066-07

2016-07-15

安徽省自然科學(xué)基金(1408085MF132)；大學(xué)生科研訓(xùn)練計(jì)劃項(xiàng)目（KYXL2014060）資助。

張以文（1976- ），男，博士，副教授，研究方向：服務(wù)計(jì)算、云計(jì)算。Email：yuji912@163.com。