基于退火果蠅優(yōu)化算法的Web服務(wù)組合

王 妍，姚啟豪，張以文

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

基于退火果蠅優(yōu)化算法的Web服務(wù)組合

王 妍，姚啟豪，張以文*

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

隨著互聯(lián)網(wǎng)中Web服務(wù)數(shù)量急劇增加，如何快速地從大量候選服務(wù)中選擇出滿足用戶QoS需求的服務(wù)組合成為亟待解決的關(guān)鍵問題。QoS感知的服務(wù)組合優(yōu)化問題是典型的NP-hard問題，而智能優(yōu)化算法已成為主流的求解方法。在對(duì)web服務(wù)組合建?；A(chǔ)上，提出一種基于退火操作的果蠅優(yōu)化算法（AFOA）。該算法通過引入模擬退火操作，使個(gè)體在進(jìn)化過程中以一定概率進(jìn)行突變，從而引向全局最優(yōu)解，較好地避免了FOA易早熟收斂陷入局部最優(yōu)的問題。大量實(shí)驗(yàn)結(jié)果表明，該算法在不減弱時(shí)間性能的同時(shí)，全局尋優(yōu)性能較果蠅算法（FOA）、模擬退火算法（SA）有很大的提升。

服務(wù)組合；果蠅優(yōu)化算法；模擬退火；服務(wù)質(zhì)量

隨著服務(wù)計(jì)算技術(shù)的發(fā)展，具有互操作性、跨平臺(tái)性、松耦合以及高度可集成能力等特點(diǎn)的Web服務(wù)技術(shù)得到廣泛應(yīng)用[1]。但隨著Web服務(wù)技術(shù)的推廣，涌現(xiàn)出大量功能相同而服務(wù)質(zhì)量（QoS）屬性不同的Web候選服務(wù)。但單一的Web服務(wù)往往無法滿足用戶的需求，因此，如何高效地把現(xiàn)存各類Web服務(wù)按一定的業(yè)務(wù)邏輯整合，以形成新的滿足不同用戶需求的增值服務(wù)，已成為新的應(yīng)用需求和研究熱點(diǎn)。

在服務(wù)技術(shù)的發(fā)展過程中，出現(xiàn)過許多可執(zhí)行的服務(wù)組合優(yōu)化方案，可概括為基于服務(wù)功能的組合和基于服務(wù)質(zhì)量的組合。但待優(yōu)化問題已呈現(xiàn)出復(fù)雜性、多極性、強(qiáng)約束性、動(dòng)態(tài)性、高維度等特點(diǎn)，導(dǎo)致傳統(tǒng)的優(yōu)化技術(shù)難以適用于新的應(yīng)用場(chǎng)景。例如，基于功能屬性的Web服務(wù)組合方法[2-4]，沒有考慮到服務(wù)質(zhì)量，找到的Web服務(wù)組合并不能滿足用戶的個(gè)性化需求及偏好。而現(xiàn)有的基于QoS約束的服務(wù)組合方法，也存在一些問題。例如，基于預(yù)先設(shè)定工作流程下的Web服務(wù)組合[5,6]以及基于QoS的時(shí)間感知下的服務(wù)組合[7]。前者限制較多，靈活性較差，在候選服務(wù)規(guī)模較大的情況下，尋優(yōu)效果并不理想；后者服務(wù)選擇范圍較大，雖然可獲得較優(yōu)解，但同時(shí)產(chǎn)生巨大的服務(wù)選擇時(shí)間開銷。另有一些基于性能函數(shù)的Web服務(wù)組合方法，當(dāng)一些性能函數(shù)存在很小誤差時(shí)，整體的尋優(yōu)能力也會(huì)大大下降[8]。

隨著Web服務(wù)技術(shù)的進(jìn)一步發(fā)展，智能優(yōu)化算法逐步廣泛應(yīng)用于Web組合領(lǐng)域并表現(xiàn)出傳統(tǒng)優(yōu)化技術(shù)無法替代的優(yōu)勢(shì)，例如：遺傳算法，粒子群算法，蟻群算法等。但這些算法同樣也存在一些缺陷，例如，遺傳算法(GA)，計(jì)算量較大，且拓展新空間的能力十分有限，易陷入局部最優(yōu)解；粒子群算法(PSO)，在數(shù)據(jù)較離散的情況下，尋優(yōu)效果不理想，且同樣易陷入局部最優(yōu)解；而蟻群算法（ACO）的計(jì)算過程則十分復(fù)雜。

為了有效解決以上問題，提出一種基于模擬退火下的果蠅優(yōu)化算法(AFOA)。與傳統(tǒng)遺傳算法相比，AFOA尋優(yōu)效果好，算法簡單，參數(shù)少易調(diào)節(jié)，且計(jì)算量少，以及克服了傳統(tǒng)服務(wù)組合優(yōu)化算法收斂速度差，易陷入局部最優(yōu)的缺陷。大量實(shí)驗(yàn)結(jié)果表明，與經(jīng)典智能算法SA和FOA相比，AFOA具有尋優(yōu)效率高，穩(wěn)定性好，以及較強(qiáng)的全局尋優(yōu)能力等特點(diǎn)。

1 相關(guān)算法

1.1 果蠅算法

果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）[9]是一種受果蠅覓食行為啟發(fā)從而推演出的尋求全局優(yōu)化的新方法，其核心思想是利用果蠅優(yōu)于其它物種的嗅覺和視覺，不斷改變位置從而尋找到最佳覓食點(diǎn)。果蠅具有優(yōu)秀的嗅覺和敏銳的視覺，易發(fā)現(xiàn)食物以及同類聚集的位置，并向該方向飛去。它屬于演化式計(jì)算的范疇，亦屬于人工智能的領(lǐng)域，在實(shí)際應(yīng)用上沒有領(lǐng)域限制。根據(jù)果蠅覓食的特性，F(xiàn)OA算法的具體描述過程如算法1。

算法1：FOA算法Step 1.Init(X_axis,Y_axis) Step 2.Get(X,Y) Step 3.Calculate(Disti,Si) Step 4.Smelli=Function(Si) Step 5.[bestSmell bestIndex]=min(Smell) Step 6.Set(X_axis,Y_axis) Step 7.Repeat(Step 2～Step 6)

其中，(X_axis,Y_axis)表示果蠅種群的位置，Si表示果蠅個(gè)體的氣味濃度判定值，Smelli表示果蠅個(gè)體的氣味濃度值，F(xiàn)unction( )表示味道濃度判定函數(shù)。

1.2 模擬退火算法

模擬退火(Simulated Annealing，SA)是一種通用概率算法[10]，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。其思想來源于固體從某一較高初溫出發(fā)，冷卻過程中分子會(huì)逐漸趨向有序化，在每個(gè)溫度達(dá)到平衡態(tài)，最后在常溫態(tài)時(shí)，內(nèi)能最小。對(duì)于溫度T的每一個(gè)取值，算法都采用Metropolis[11]接受準(zhǔn)則來進(jìn)行判斷，從而持續(xù)進(jìn)行“產(chǎn)生新解～計(jì)算目標(biāo)函數(shù)差～判斷是否接受～接受或舍棄”迭代，同時(shí)逐步減少溫度參數(shù)T，算法終止時(shí)所得的解即為近似最優(yōu)解。模擬退火算法模型描述如算法2[12]。

算法2：SA算法Step 1.Init(S,T,T-r,T-Min) Step 2.Get(S') Step 3.Δt=C()S'-C()SStep 4.IfΔt＞0,Δt=S'else ifexp( ) Δt/T＞random( ) 0,1,S=S'Step 5.T=T*T-rStep 6.Repeat Step 2～Step 5 whileT＞T-Min

其中，S表示初始狀態(tài)，T表示初始溫度，T-r表示退火速度，T-Min表示溫度下限，C()表示評(píng)價(jià)函數(shù)。

2 基于QoS的Web服務(wù)組合

本文提出的優(yōu)化算法建立于兩個(gè)實(shí)驗(yàn)?zāi)Ｐ椭?，一個(gè)是Web服務(wù)模型，另一個(gè)是AFOA算法模型。通過Web服務(wù)的構(gòu)建，可以清晰地定義和使用Web服務(wù)的各種屬性，以及在實(shí)驗(yàn)中為Web服務(wù)指定一個(gè)量化的指標(biāo)。而通過構(gòu)建AFOA算法模型，則可以清楚地描述該算法中各參數(shù)在Web服務(wù)組合中代表的實(shí)際意義，便于算法實(shí)現(xiàn)。

2.1 問題描述

定義1服務(wù)質(zhì)量(Quality of Service，QoS)

服務(wù)質(zhì)量是指服務(wù)能夠滿足規(guī)定和潛在需求的特征和特性的總和。隨著Web服務(wù)的廣泛普及，服務(wù)質(zhì)量將變成一個(gè)判定服務(wù)提供者是否成功的重要因素。本文采用一個(gè)四元組QoS=(T,A,C,R)來評(píng)價(jià)Web服務(wù)質(zhì)量，其中T表示W(wǎng)eb服務(wù)的響應(yīng)時(shí)間（Response-Time），A表示W(wǎng)eb服務(wù)的可用性（Availablility），C表示調(diào)用一次服務(wù)的代價(jià)（Cost），R表示W(wǎng)eb服務(wù)的信譽(yù)度（Reputation）。

可用性是指一個(gè)Web服務(wù)可以提供某項(xiàng)特定服務(wù)的時(shí)間，即在時(shí)間段t內(nèi)成功訪問Web服務(wù)的時(shí)間所占比例，A=tsuccess/t，tsuccess表示在時(shí)間段t內(nèi)成功訪問服務(wù)的時(shí)間。

響應(yīng)時(shí)間是指從用戶提交服務(wù)請(qǐng)求到服務(wù)執(zhí)行完成返回結(jié)果所消耗的時(shí)間。主要包括Web服務(wù)執(zhí)行時(shí)間Texe、網(wǎng)絡(luò)傳輸時(shí)間Ttrans和其它時(shí)間消耗Toth，即T=Texe+Ttrans+Toth。

費(fèi)用是指從用戶提交Web服務(wù)請(qǐng)求到服務(wù)執(zhí)行完成返回結(jié)果所需要的所有費(fèi)用。主要包括Web服務(wù)軟件(SaaS)、硬件(laaS)、平臺(tái)(PaaS)等服務(wù)基礎(chǔ)成本Cserv和服務(wù)管理成本Cmanag，即C=Cserv+Cmanag。

定義2Web服務(wù)

本文采用一個(gè)四元組S={ID,Source,F,QoS}來表示W(wǎng)eb服務(wù)。其中，ID是Web服務(wù)的唯一標(biāo)識(shí)，Source表示資源的名稱及發(fā)布者等描述信息，F(xiàn)指Web服務(wù)的功能性描述，QoS指Web服務(wù)質(zhì)量。

定義3Web服務(wù)組合

服務(wù)組合是一個(gè)多元組，SC=(s1,s2,s3,…,sn-1,sn），其中s1至sn分別表示每個(gè)Web子服務(wù)，且s1∈S1,s2∈S2,s3∈S3,…,sn-1∈Sn-1,sn∈Sn，同時(shí)，S1至Sn稱為Web服務(wù)組合的子服務(wù)集，Si中子服務(wù)功能相同但服務(wù)質(zhì)量不同。則可得SC∈S1×S2×S3×…×Sn-1×Sn。常見的四種 QoS的基本計(jì)算模型如表1所示。其中，ρi為第i個(gè)分支被選中的概率，μ為循環(huán)次數(shù)。

表1 QoS參數(shù)計(jì)算公式

由于其他三種非順序型可以轉(zhuǎn)換為順序型結(jié)構(gòu)，本文采用順序結(jié)構(gòu)為基礎(chǔ)研究Web服務(wù)組合優(yōu)化問題。

2.2 算法建模

每條服務(wù)組合由N個(gè)子服務(wù)組成，每個(gè)子服務(wù)屬于不同的子服務(wù)集。把每個(gè)子服務(wù)作為單個(gè)果蠅個(gè)體，每條組合當(dāng)作一個(gè)果蠅種群。然后對(duì)N個(gè)果蠅分別進(jìn)行果蠅迭代算法進(jìn)行計(jì)算。對(duì)于每個(gè)組合，利用fitness函數(shù)進(jìn)行計(jì)算，并尋找到最優(yōu)解。

本文采用離散型編碼方式，每個(gè)果蠅個(gè)體表示的是其在所歸屬子服務(wù)集中的位置信息。例如，Pi,j,k表示的是第i次迭代第j個(gè)種群中的第k個(gè)果蠅個(gè)體在子服務(wù)集中所對(duì)應(yīng)的位置。

以每個(gè)中心位置隨機(jī)產(chǎn)生K*N個(gè)領(lǐng)域個(gè)體，定義果蠅嗅覺搜索范圍Rd為[-R，R]，則新個(gè)體為

其中NPi,j,k表示以Pi,j,k種群個(gè)體產(chǎn)生的鄰域解的位置，并代入下次迭代。

對(duì)鄰域解內(nèi)的個(gè)體，計(jì)算Smell值，并選取最優(yōu)的個(gè)體，使得種群向這個(gè)個(gè)體的位置轉(zhuǎn)移。

其中，SC(NPi,j,k)表示第i次迭代的第j個(gè)種群的第k個(gè)個(gè)體在子服務(wù)集中所對(duì)應(yīng)的位置，Disti,j,k表示第i次迭代過程中第j個(gè)果蠅種群中第k只果蠅的距離，Smelli,j,k表示第i次迭代過程中第j個(gè)果蠅種群的第k只果蠅的smell值。

不同類型的指標(biāo)具有不同的量綱。為消除量綱和量綱單位不同所帶來的不可公度性，在合作評(píng)價(jià)前需要將所有指標(biāo)按某種效用函數(shù)歸一化到某一無量綱區(qū)間（一般是將其歸一化到[0,1]區(qū)間）。本文只考慮離散型指標(biāo)，按公式（3）進(jìn)行歸一化處理。

Fitness函數(shù)用來評(píng)價(jià)組合服務(wù)的適應(yīng)度(本文中越小越好)，通過不同服務(wù)組合的Fitness值來判斷各個(gè)服務(wù)組合的優(yōu)劣程度。結(jié)合公式（3）的預(yù)處理結(jié)果，F(xiàn)itness函數(shù)可以定義為

由于果蠅算法存在易于陷入局部最優(yōu)解的情況，在此引入模擬退火操作，以一定概率突變，使得其產(chǎn)生突變個(gè)體增加尋優(yōu)能力并引向全局最優(yōu)解，從而一定程度上避免了果蠅算法在搜索上陷入局部最優(yōu)的情況。

給定初始溫度T、冷卻速率T_r，由果蠅種群S產(chǎn)生新的個(gè)體S'，并產(chǎn)生新的Fitness函數(shù)值。由此計(jì)算增量：

根據(jù)公式（5），若Δt'＞0，則接受S'作為新的種群位置。否則，以公式（6）來評(píng)價(jià)是否存在突變個(gè)體，并接受其作為新的種群位置。

2.3 AFOA算法實(shí)現(xiàn)

在引入退火機(jī)制的基礎(chǔ)上，本文提出一種改進(jìn)的果蠅優(yōu)化算法，即退火果蠅優(yōu)化算法（AFOA）。AFOA算法詳細(xì)描述如下：

Step 1：確定初始溫度T，冷卻速率T_r，初始化產(chǎn)生N個(gè)種子果蠅種群位置Pos0～Posn。

Step 2：通過果蠅嗅覺搜索，對(duì)N個(gè)果蠅個(gè)體產(chǎn)生KN個(gè)新的鄰近果蠅個(gè)體，組合成K個(gè)果蠅種群。

Step 3：根據(jù)公式(1)，計(jì)算種群位置。

Step 4：根據(jù)公式(2)，計(jì)算種群個(gè)體的smell值，得到新的鄰近較優(yōu)位置。

Step5：將氣味smell集合轉(zhuǎn)換成服務(wù)組合記錄。

Step6：根據(jù)公式(4)，計(jì)算每條服務(wù)組合記錄的Fitness函數(shù)值。在每次迭代中，比較當(dāng)前解與全局已尋最優(yōu)解，保留找到的最小Fitness值的果蠅位置。

Step7：根據(jù)新得到的Fitness函數(shù)值，結(jié)合當(dāng)前溫度，隨機(jī)突跳并判斷果蠅移動(dòng)情況。若滿足公式(5)＞0，則接受其作為新的種群位置，否則以公式(6)來評(píng)價(jià)是否存在突變個(gè)體，并接受其作為新的種群位置。

Step8：更新最優(yōu)解，更新退火溫度T=T*T_r。

Step9：重復(fù)Step 3～Step 8，迭代Lk次。

Step10：輸出最優(yōu)組合。

從時(shí)間復(fù)雜度方面，要迭代Lk次，并且每個(gè)種度為O(Lk*KN*N)。與果蠅算法復(fù)雜度一致?？梢?，AFOA并沒有提高時(shí)間復(fù)雜度，并通過大量實(shí)驗(yàn)結(jié)果表明在相同的時(shí)間要求下，本文改進(jìn)算法的尋優(yōu)性能更優(yōu)。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

在實(shí)驗(yàn)過程中采用的是Zeng等提供的QWS數(shù)據(jù)集[13]。實(shí)驗(yàn)環(huán)境為：Windows 8.1，Inter(R) Core(TM)I5-3470 CPU@3.20 GHz 3.20 GHz，4.00 GB RAM，64位操作系統(tǒng)，Visual Studio 2010，C++。果蠅算法可依賴參數(shù)有KN(即新鄰近解的個(gè)數(shù)，實(shí)驗(yàn)中的popsize)，R(新位置產(chǎn)生范圍，實(shí)驗(yàn)中的步長L)等，模擬退火可依賴的的參數(shù)有T，T_r等，對(duì)于不同的參數(shù)或?qū)?shí)驗(yàn)效率產(chǎn)生影響，因此先對(duì)參數(shù)設(shè)置進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)配置

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 迭代次數(shù)不同時(shí)的尋優(yōu)性能

為分析不同迭代次數(shù)下FOA、SA以及AFOA的尋優(yōu)性能，在初始溫度10 000 000，候選服務(wù)規(guī)模100，種群規(guī)模120，子任務(wù)數(shù)分別為5、10、15和20，不同迭代次數(shù)的設(shè)置下，重復(fù)50次試驗(yàn)所得尋優(yōu)效果如圖1～4所示。

由圖1～4易知，整體而言，隨著迭代次數(shù)的增加，在不同子服務(wù)數(shù)下AFOA的尋優(yōu)效果均顯著優(yōu)于SA和FOA，且隨著迭代次數(shù)的增加尋優(yōu)能力在不斷增強(qiáng)。因此，AFOA在不同迭代次數(shù)下具有很強(qiáng)的尋優(yōu)能力。

3.2.2 候選服務(wù)規(guī)模不同時(shí)的尋優(yōu)性能

為了進(jìn)一步探究FOA、SA以及AFOA的尋優(yōu)性能，通過在迭代次數(shù) 500，初始溫度群要產(chǎn)生KN個(gè)鄰近的新果蠅個(gè)體，所以總復(fù)雜10 000 000，種群規(guī)模120，子任務(wù)數(shù)分別為5、10、15和20，候選服務(wù)規(guī)模不同的情況下進(jìn)行50次重復(fù)試驗(yàn)，所得結(jié)果如圖5～8所示。

圖1 子任務(wù)數(shù)為5時(shí)不同迭代次數(shù)下的尋優(yōu)效果

圖2 子任務(wù)數(shù)為10時(shí)不同迭代次數(shù)下的尋優(yōu)效果

圖3 子任務(wù)數(shù)為15時(shí)不同迭代次數(shù)下的尋優(yōu)效果

圖4 子任務(wù)數(shù)為20時(shí)不同迭代次數(shù)下的尋優(yōu)效果

圖5 子任務(wù)數(shù)為5時(shí)不同候選服務(wù)規(guī)模下的尋優(yōu)效果

圖6 子任務(wù)數(shù)為10時(shí)不同候選服務(wù)規(guī)模下的尋優(yōu)效果

由圖5～8可清楚得知，在不同候選服務(wù)規(guī)模的情況下，AFOA的整體尋優(yōu)效果普遍高于SA和FOA。此外，F(xiàn)OA的尋優(yōu)能力時(shí)而高于SA，時(shí)而低于SA，但無論兩者孰優(yōu)孰劣，AFOA的尋優(yōu)效果始終優(yōu)于兩者。因此，AFOA在不同候選服務(wù)規(guī)模下具有優(yōu)秀的尋優(yōu)能力。

圖7 子任務(wù)數(shù)為15時(shí)不同候選服務(wù)規(guī)模下的尋優(yōu)效果

圖8 子任務(wù)數(shù)為20時(shí)不同候選服務(wù)規(guī)模下的尋優(yōu)效果

圖9 不同迭代次數(shù)下的時(shí)間開銷

3.2.3 時(shí)間性能

為分析AFOA與FOA、SA之間的時(shí)間開銷，通過在初始溫度10 000 000，候選服務(wù)規(guī)模125，種群規(guī)模120，子任務(wù)數(shù)分別為20，不同迭代次數(shù)的設(shè)置下，重復(fù)50次試驗(yàn)所得時(shí)間開銷如圖9所示。由圖可知，AFOA的時(shí)間開銷與FOA算法相近，略低于SA。由計(jì)算的時(shí)間復(fù)雜度可知AFOA與FOA、SA算法時(shí)間復(fù)雜度相近，具體時(shí)間差異則由編譯環(huán)境，編譯時(shí)機(jī)等運(yùn)行機(jī)制造成。因此，AFOA算法在和其他兩種算法的時(shí)間性能方面勢(shì)均力敵的情況下，仍能取得很好的尋優(yōu)效果。

4 結(jié)論

為了更好的解決服務(wù)組合優(yōu)化問題，本文提出了一種在果蠅算法和模擬退火算法的基礎(chǔ)上進(jìn)行完美融合的更加優(yōu)化的智能算法（AFOA），該算法是在果蠅依據(jù)氣味尋求最優(yōu)解的過程中引入退火機(jī)制對(duì)產(chǎn)生的最優(yōu)解進(jìn)行一定概率突變，使得其產(chǎn)生突變個(gè)體進(jìn)而產(chǎn)生進(jìn)化過程并引向全局最優(yōu)解，從而可以有效的避免在搜索過程中陷入局部最優(yōu)解的風(fēng)險(xiǎn)。為了驗(yàn)證AFOA算法的有效性和可靠性，與多種算法進(jìn)行了比較分析，大量的仿真模擬實(shí)驗(yàn)結(jié)果表明AFOA算法所用時(shí)間與FOA、SA算法相近，但AFOA算法的尋優(yōu)能力顯著高于FOA算法和SA算法。下一步我們將更加深入的研究如何在最適合的位置進(jìn)行突變和找出最適合的突變概率，進(jìn)一步提高算法的效率。

[1]陳國彬.基于Qos約束的Web服務(wù)組合算法[J].控制工程，2014，21（4）：609-612.

[2]El Falou M,Bouzid M,Mouaddib A I,et al.A distributed planning approach for web services composition [C].Web Services(ICWS),2010 IEEE International Conference on IEEE,2010：337-344.

[3]Bertoli P,Kazhamiakin R,Paolucci M,et al.Continuous Orchestration of Web Services via Planning[C]. ICAPS.2009.

[4]Hoffmann J,Bertoli P,Helmert M,et al.Messagebased web service composition,integrity constraints, and planning under uncertainty：A new connection[J]. Journal of Artificial Intelligence Research,2009：49-117.

[5]Zeng L Z,Benatallah B,Ngu A H,et al.QoS-aware middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5)：311-327.

[6]Menasce D A.Composing web services：a QoS view [J].IEEE Internet Computing,2004,8(6)：88-90.

[7]Zou G B,Lu Q,Chen Y X,et al.QoS-Aware dynamic composition of web services using numerical temporal planning[J].IEEE Transactions on Services Computing,2014,7(1)：2-15.

[8]Volk F,Sokoli J,Muehlhaeuser M.Performance functions for QoS prediction in web service composites [C]//2014 IEEE 21ST INTERNATIONAL CONFERENCE ON WEB SERVICES(ICWS 2014),2014：574-581.

[9]Xing B,Gao W J.Fruit fly optimization algorithm[M]. Innovative ComputationalIntelligence：A Rough Guide to 134 CleverAlgorithms,2014：167-170.

[10]陳華根，吳健生，王家林，等.模擬退火算法機(jī)理研究[J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2004，32（6）：802-805.

[11]蔣惠波，劉 彬，袁衛(wèi)華.基于Metropolis準(zhǔn)則的自適應(yīng)隨機(jī)搜索算法研究[J].中國西部科技，2015（3）：17-19.

[12]龐 峰.模擬退火算法的原理及算法在優(yōu)化問題上的應(yīng)用[D].長春：吉林大學(xué)，2006.

[13]Zeng L Z,Benatallah B,Ngu A H,et al.QoS-aware middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5)：311-327.

Web service composition based on annealing fruit fly optimization algorithm

WANG Yan,YAO Qi-hao,ZHANG Yi-wen
(Key Laboratory of Intelligent Computing and Signal Processing,Anhui University,Hefei Anhui230031,China)

With the rapid increase in the number of web services in the internet,it is a key problem to be solved urgently that how to select the service composition quickly,meeting the users’QoS requirements from a large number of candidate services.QoS-aware service composition optimization problem is a typical NP-hard problem,and the intelligent optimization algorithm becomes the mainstream solution.On the basis of the web service composition modeling,this paper proposes a novel algorithm named annealing fruit fly optimization algorithm(AFOA).By introducing simulated annealing operation,the individual mutates at a certain probability in the evolution process,thereby leading to the global optimal solution and avoiding FOA being premature to converge into local optimum.Substantial experiments show that without weakening the time performance,AFOA still has a great improvement in the global optimization capacity compared with fruit fly optimization algorithm(FOA)and simulated annealing algorithm(SA).

service composition;fruit fly optimization algorithm;simulated annealing;quality of service

TP311

：A

：1004-4329（2016）04-067-07

10.14096/j.cnki.cn34-1069/n/1004-4329(2016)04-067-07

2016-07-09

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

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