融合SOM和多目標尋優的Web 服務組合優化方法

景 華，陳世平

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

得益于互聯網技術的日益發展與軟件工程學科的不斷進步，Web的服務組合技術在網絡技術研究領域發揮著愈加重要的作用.但是隨著用戶需求的日益增多，單一的Web服務往往難以滿足用戶日益復雜的需求，越來越多的企業傾向于采用多樣的Web服務組合來完成對業務的構建[1].隨著服務提供者發布的服務個數激增，出現許多功能相類似但是服務質量(Quality of Service，QoS)并不相同的服務，在滿足用戶對于服務質量要求的前提下，如何選擇最優的服務組合，是Web服務組合優化研究領域中的一個重要的研究問題.該問題是一個典型的多目標下的NP-hard問題[2].

目前大多數的解決方法是從QoS角度出發使用元啟發式算法求解優化模型.如文獻[3]從服務水平協議(SLA)的角度提出一種全新的多元優化算法IMVO，其設計的算法在數據集較小的情況下具有良好的優化能力，但隨著數據集增大，其尋優能力明顯下降;文獻[4]提出一種基于柯西變異的煙花算法，但是在算法種群更新過程中完全放棄適應度較差的變異個體，增大了陷入局部最優的可能;文獻[5]則運用了一些傳統的多目標算法如NSGA-II、SPEA2等來解決基于QoS的云服務組合優化問題，但算法的有效性和速率仍有待改進.

此外，由于Web服務的動態性，不少學者開始關注針對服務集的聚類研究.對服務進行聚類的目的在于將同一服務集合中的候選服務按每種規律聚集為不同的類別.如文獻[6]使用K-means算法根據候選服務的QoS屬性進行聚類操作，但是K-means算法需要給出預測的類個數K，該值通常較難把握.文獻[7]使用AGNES層次聚類和K-means算法對初始服務集合進行兩次篩選從而提高組合的可靠性，但兩次聚類操作極大地增加了算法計算時間.文獻[8]提出一種基于邏輯關系的Web服務聚類方法，通過分析服務的OWL-S(Web Ontology Language for Services)語義描述完成聚類，但此類方法對初始的數據要求較高，需要較為完整的OWL-S描述才能較好地完成聚類操作.服務聚類主要有兩個目的，首先對于相類似的服務，他們可在大多數情況下進行相互替換，故其并不需要全部都參與到服務組合的流程中，這樣可以縮小服務選擇中候選服務的規模;其次，對于部分不符合用戶要求的服務，在聚類過程中可能被歸于同類服務，故在組合過程中可以避免調用該類服務從而提高服務表現.

基于以上思路，本文提出一種基于聚類分析和QoS感知相結合的Web服務組合優化方法模型(SO-AFSA).首先基于SOM神經網絡對單個服務集合進行聚類操作，有效減少單個子服務集合的候選服務數量并降低服務間的相似程度;其次使用第一階段的聚類結果構造初始種群，提出一種改進的多目標魚群算法，以解決多目標優化算法中的效率和有效性問題，實驗結果表明，相較于傳統方法，本文提出的算法模型在多個指標上均具有更好的表現.

2 結構與問題描述

2.1 Web服務組合問題描述

定義1(服務質量).服務質量指Web服務的非功能屬性，比如可用性，安全性，可行度等等.本文采用一個四元組表示服務質量：QoS={RT，AV，TH，L}，其中RT表示服務響應時間(Response Time)，AV表示服務可用性(Availability)，TH表示表示吞吐量(Throughput)，L表示時延(Latency).

由于不同QoS屬性的單位并不一致，所以在對QoS屬性進行度量計算的時候，一般需要對數據進行預處理，使得不同的QoS屬性有相同的度量單位[9].本文將不同單位的QoS屬性進行歸一化，將不同單位的屬性都轉換為[0，1]的數值.QoS屬性分為“正向QoS”和“逆向QoS”，正向QoS屬性其指標越大越能滿足需求，比如可用性和吞吐量;而逆向 QoS屬性其指標值越小越能滿足用戶需求，比如服務時延和服務響應時間.針對兩種不同的QoS類型，本文將按照公式(1)進行歸一化：

(1)

定義2(Web服務組合).Web 服務組合指根據用戶提交的信息將任務劃分為細粒度的抽象任務，同時將每個抽象任務對應的候選服務快速組合起來形成完整的服務以滿足不同用戶的需求.設一個Web服務組合Wsc={T1，T2，T3,…,Ti}由i個抽象任務組成，其中Ti表示任務拆分后第i個子任務.Csi={Csi1，Csi2，Csi3,…,Csin} 表示每一個Ti對應的n個候選服務集合，對于每個候選服務Csin有QoS={qos1，qos2，qos3,…,qosm}，表示該候選服務對應共m項QoS屬性值，最后W={w1，w2，w3,…,wm} 表示各QoS指標所占權重.

表1 組合服務QoS計算方法

2.2 QoS多目標優化模型描述

Web服務QoS優化是一個典型的多目標優化問題，且這些目標往往難以同時達到最優.很多學者采取優化模型的方法，將不同的QoS屬性根據其相應的權值向量整合，將多目標問題轉換為單目標問題進行優化.但這種方法并沒有考慮到QoS之間的沖突性，并且計算的結果為QoS聚合值，具有片面性且極易丟失大量的決策信息.文本采用上文提到的4元模型建立多目標優化模型.取在Web服務中相互對立且較為重要的兩個屬性響應時間和時延作為目標函數f1、f2，以服務組合可用性和吞吐量作為約束來構建多目標模型.

(2)

3 SO-AFSA服務組合模型

3.1 QoS服務聚類

3.1.1 自組織映射網絡

綜合考慮上述提到的多種 Web服務聚類方法的優缺點，在此我們引入SOM(Self-organizing Maps)神經網絡來完成對候選服務的聚類.SOM是一種無監督的高維聚類方法，用于描述從高維輸入空間到低維競爭空間的映射，從而實現自動聚類[11].二維的 SOM拓撲結構如圖1所示，其由競爭層和輸入層組成.對于一個任意維度的輸入向量Xi(t)，根據初始的權值計算其與各個神經元之間的歐式距離，距離最小的即為獲勝神經元，同時在每次訓練中按照公式(3)調整獲勝神經元和相鄰神經元的權值.

圖1 SOM拓撲結構

wi(t+1)=wi(t)+η(t)×[Xi(t)-wi(t)]

(3)

其中η(t)是一個值域在0到1 之間隨時間而減小的增益函數，wi(t)表示第i個輸出層節點在第t代的權值向量.修改權值將使獲勝的神經元及其相鄰權值更加靠近輸入樣本，從而使同類的神經元具有相近的權值系數.在學習過程結束之后，同類神經元相對集中，異類神經元逐步發散，從而達到聚類的效果.文獻[12]首次將SOM運用到基于QoS的聚類操作中，但是其對QoS數值的格式有一定的要求，并且沒有給出在聚類之后的具體操作，本文將給出基于一般QoS屬性值的SOM聚類過程.

在聚類操作中我們將使用QoS屬性值對一個候選服務Csi進行描述.對于同一個子任務的候選服務集合Cs，將每一個Csi作為輸入向量訓練SOM網絡從而完成服務聚類.對于服務聚類結果的操作詳見3.3.5

算法1.SOM聚類的實現步驟

輸入：服務集合矩陣Cs

輸出：QoS聚類結果

Step 1.初始化每個節點的權重，其被設置為一個較小的隨機值，同時設定獲勝神經元的初始鄰域，學習率，最大迭代次數Tmax

Step 2.將Cs的一個具體服務Csi輸入SOM網絡，并根據歐式距離找到獲勝節點

Step 3.更新獲勝神經元及其鄰域神經元的連接權重

Step 4.重復Step 3，直到達到最大迭代次數Tmax

3.2 基本人工魚群算法

人工魚群算法(AFSA)是李曉磊在2002年提出的一種元啟發式算法[13].人工魚群算法具有魯棒性強，實現簡單，尋優速度較快以及全局尋優能力強等優點，極其適合解決Web組合優化問題.

設在一個D維空間中有N條人工魚，每條人工魚狀態表示為Xi=(x1，x2，…，xn)，其中i=1，2，…，N.Yi=f(Xi)表示在Xi位置的目標函數值.Visual表示人工魚感知范圍，Step表示人工魚最大移動步長，δ表示擁擠度因子;try_number表示最大試探次數;delta表示魚群擁擠度因子.以下將具體介紹人工魚群算法的4種行為.

3.2.1 覓食行為

覓食行為是人工魚最基本的一種行為，具體可表述為處于Xi位置的人工魚在視野范圍內隨機確定一個新的位置Xj，Xj可用以下公式(4)確定.Yi、Yj表示在Xi、Xj位置的食物濃度.如果滿足Yj> Yi，則人工魚按照公式(5)向Xj移動一步.若在嘗試try_number次后沒有找到滿足條件的Yj，則執行隨機行為.

Xj=Xi+Visual×rand()

(4)

(5)

其中rand()表示一個在0-1之間的隨機數，‖Xj-Xi‖表示兩條人工魚之間的歐式距離.

3.2.2 聚群行為

聚群行為指魚群聚集成群以集體進食及躲避敵害.魚群的中心位置由公式(6)進行定義，其中Xc表示魚群的中心位置.定義人工魚在Xi狀態時的視野范圍內所有的人工魚數量為nf_swarm，Yc為人工魚在Xc位置的食物濃度，若滿足Yc/nf_swarm>delta×Y并且Yc>Yi，則Xi按照公式(7)向Xc的方向移動一步.若無滿足條件的Xc則執行覓食行為.

(6)

(7)

3.2.3 追尾行為

追尾行為是指當魚群中的人工魚發現食物的時候，它們附近的魚會尾隨其方向游動.設人工魚在Xi狀態時視野范圍內的人工魚條數為nf_follow，擁有最大食物濃度的人工魚為Xmax，其食物濃度為Ymax，如果同時滿足Ymax/nf_follow>delta×Yi則向按照公式(8)向Xmax方向前進一步.反之則執行覓食行為.

(8)

3.2.4 隨機行為

隨機行為也是魚群的一種基本行為，對于處在Xi狀態的人工魚按照公式(9)在視野范圍內隨機選擇一個狀態，然后向該方向移動.

Xi|next=Xi+Visual×rand()

(9)

魚群在執行不同行為后，算法將會執行一個評估函數evaluate()對人工魚當前的位置作出評價，然后選擇一種行為執行.評估函數依照具體的問題設定，常用的評估函數函數即選擇各個行為中使人工魚向最優方向上前進最大的行為.

3.3 改進的多目標人工魚群算法

基本的人工魚群算法只適用于單目標的問題，而在多目標優化的問題環境下，則需要對人工魚的4種行為以及算法流程進行修改.本文將從多個方面將基本人工魚群算法改進為多目標的人工魚群算法.

3.3.1 自適應視野及步長

在基本的人工魚群算法中，視野決定了搜索范圍，步長決定了搜索的速度和精度.視野越小，人工魚更有可能執行覓食行為和隨機行為，有利于探尋局部最優解和數據精度的提升，而視野越大，聚群和追尾行為將會更加頻繁，更有益與全局最優解的發現，故對于算法整體過程，需要視野的變化趨勢由大到小，變化速率由快到慢.令視野最大最小值分別為Vismax和Vismin.本文引入logistic模型對人工魚視野進行動態調整，具體變化設定為公式(10)，其中Iteration為當前迭代次數，Max_Iteration為最大迭代次數，α為動態因子，用以調節視野下降速度.

(10)

g(x)=e-πx2

(11)

(12)

而為平衡迭代速度和解的精度，本文基于文獻[14]引入一個變形的正態分布函數來控制步長的變化，具體步長如公式(11)、公式(12)所示.在算法初期步長的減少較為緩慢，有利于迭代速度，算法后期步長迅速減少，有利于算法的收斂.圖2繪制了公式(10)和公式(12)的曲線，我們可以看到兩條曲線的整體下降趨勢均符合預期且始終滿足視野大于步長.

圖2 視野與步長曲線

3.3.2 人工魚群4種行為更新

拓展的多目標人工魚群算法無疑需要基于Pareto支配來判斷所得解的優劣，以下將給出相關定義.

定義3(Pareto支配).對于任意兩個在解空間中的D維向量u和v，當且僅當u和v的任意分量上滿足ui≥vi，且至少存在一項滿足ui>vi，則稱u支配v，記做uv.

定義4(Pareto非支配解).對于u∈S，當且僅當不存在w∈S，使得wu，則稱u為Pareto非支配解.

定義5(Pareto非支配解集).所有Pareto非支配解組成的集合稱為Pareto非支配解集.

過往對多目標人工魚群算法的研究存在將支配關系直接套用在基本的人工魚群算法中的情況，如在文獻[15]中，只是簡單將適應度值的大小比較替換為支配關系的判斷，然而對多目標人工魚群算法中魚群中心位置擁擠判斷、多條人工魚互不支配情況下的行為選擇等問題均沒有給出明確的解答.基于上文給出的Pareto關系的定義，本文將給出多目標人工魚群算法的4種魚群行為及行為選擇策略：

1)覓食行為：對于人工魚Xi，按照公式(4)選擇其視野范圍內的另一條人工魚Xj，如果F(Xj)F(Xi)，則Xi向Xj移動，如果在嘗試try_number次后都沒有滿足條件的Xj，則執行隨機行為.

2)聚群行為：對于人工魚Xi，計算視野范圍內所有人工魚數目nf_swarm和并按公式(6)求得魚群的中心位置Xc.如果F(Xc)F(Xi)，并且滿足nf_swarm/N

3)追尾行為：對于人工魚Xi，先求得視野范圍內的最優人工魚Xbest，即對于Xi視野范圍內的任意X*，有XbestX*，同時求得Xi視野范圍內人工魚數目nf_follow，如果滿足F(Xbest)F(Xi)并且nf_follow/N

4)隨機行為：多目標人工魚群算法總的隨機行為和基本的人工魚群算法保持不變.

對于多目標人工魚群算法的行為選擇，大體思路依舊是選擇使人工魚向最優方向上前進最大的行為.本文默認執行聚群和追尾行為，覓食和隨機行為在前兩種行為中有概率執行.對兩種行為得到的解進行支配關系判斷，其中的非支配解將加入非支配解集.

若出現互不支配的情況，因為人工魚每次只能向一個方向前進，所以只能選擇其中的一個解加入非支配解集并執行對應行為，在此使用聚合函數Aggregation來進行選擇.Xi=(x1，x2，…，xn)共有n個分量，則給定權重向量w=(w1，w2，…，wn)，按照公式(13)將Xi的各分量相加，針對最小化問題將聚合函數值較小的解加入非支配解集.

(13)

3.3.3 外部檔案維護策略

外部檔案的維護是多目標優化算法中非常重要的一個問題.在多目標魚群算法中，我們將維護一個外部檔案集P以保存得到的非支配解.每次迭代后，對于每條人工魚將依照其食物濃度判斷其支配關系，將本次迭代后獲得的的非支配解保存在集合Q中，隨后將集合P和集合Q合并刪去其中的支配解.參考已有的研究基礎[16]，本文引入擁擠距離的概念，在每次所有人工魚完成一次移動行為后每條人工魚按照當前的食物濃度來計算擁擠距離.當外部檔案中非支配解的個數超過檔案集的最大數量Pmax的時候按照擁擠距離刪除部分集合P中的部分非支配解，計算擁擠度過程如下：

算法2.計算人工魚擁擠距離

輸入：人工魚群AFpop，魚群大小N，目標個數object_num

兩權分離度與企業技術創新實證研究——兼論產權性質與業績偏離的調節效應..................................................................................................................................劉 玉 盛宇華（60）

輸出：每條人工魚的擁擠度

Step 1.初始化AFpop中每一條人工魚的擁擠距離CrowdDis=0，當前計算的目標數為j

Step 2.對第j個目標的函數值進行降序排列，設第i條人工魚的在排序后的順序為i′，同時將排序后的第1條和最后一條人工魚的擁擠距離值為無窮大，令i=2(從第2條人工魚開始計算)

Step 3.對于第i條人工魚按照以下公式(14)進行計算，同時令i=i+1

(14)

Step 4.判斷i是否小于N，若是則返回Step 3，否則轉到Step 5

Step 5.令j=j+1，判斷j是否小于object_num，若是則結束結束計算，反之則轉到Step 2

3.3.4 變異算子的添加

(15)

同時，在MOPSO中基于位置的變異方法并不能很好從全局角度尋優，由于差分算子非常有利于種群之間的信息交換并改善收斂精度，本文提出一種基于差分變異算子的變異策略.基本的差分變異算子包含5種變異策略，本文將基于“current-to-best/1”策略實施變異操作.“current-to-best/1”在通常情況下被用于在全局范圍內探索更大的可行解區域，具體如公式(16)所示.

(16)

(17)

圖3 差分變異算子變異策略

3.3.5 人工魚編碼及種群初始化

在進行組合服務的選擇時我們將每條人工魚看做是一個組合服務的解決方案，本文采用實數編碼對人工魚進行編碼，假設一個服務組合Wsc={T1，T2，T3,…,Ti}包含i個子服務，每個子服務Ti對應的候選服務共有n個候選服務，則具體的編碼方式如圖4所示.

圖4 組合服務的編碼

對于算法初始種群的構建，一般的做法是采用隨機生成的方式產生初始種群.但在SO-AFSA中，我們將基于SOM的聚類結果來構建初始種群.因為對于同一個候選服務的相同簇中的服務，其往往具有相類似的QoS屬性，從組合優化的角度完全可以選擇簇中的一個服務來代表整個簇參與初始化流程.因此同一簇的服務，我們將選擇其聚類中心來代表其整個類.設單一原子服務Ti經過SOM聚類后共有n個簇，則包含該服務的服務組合的第i位將從n個聚類中心中隨機選擇一個代表Ti.

3.3.6 模型整體流程

綜上，結合SOM聚類和多目標人工魚群算法的Web 服務組合優化模型(SO-AFSA)具體實現步驟如下：

Step 1.設置算法參數：初始化算法參數，包括種群規模N，最大迭代次數Max_Iteration，最大最小視野Vismax、Vismin和步長Step等，同時初始化Qos屬性.

Step 2.利用SOM篩選服務，并利用SOM的聚類結果構建初始種群.

Step 3.每一條人工魚Xi分別執行聚群和追尾行為，當不滿足聚群和追尾條件時則執行覓食行為，若覓食行為條件亦不滿足則執行隨機行為，取兩次行為最后的位置記為Xnext1和Xnext2.

Step 4.分別計算人工魚Xnext1和Xnext2的食物濃度Ynext1和Ynext2并判斷支配關系，人工魚向非支配解位置移動.若Ynext1和Ynext2互不支配，則按公式(13)計算聚合函數值，人工魚向聚合函數值較小的位置移動.

Step 5.根據當前迭代次數計算變異概率并選擇部分人工魚按照差分變異策略進行變異操作.

Step 6.在每一條人工魚進行移動后，構建本次迭代獲得的Pareto解集并計算擁擠度.將新的Pareto解集加入外部檔案P并對P進行維護.

Step 7.重復Step 3-Step 6直至達到最大迭代次數Max_Iteration.

4 實驗分析

為驗證本文所提出的SO-AFSA模型的有效性，本節將進行一系列實驗.首先對基于SOM過濾服務及種群初始化進行有效性驗證.其次，針對Web服務QoS度量模型，采用SO-AFSA模型和其他幾種經典的多目標優化算法進行對比，實驗程序使用Matlab2019b編寫，運行環境為Mac Os，Intel?Core I5，1.8GHz CPU，8G內存.

4.1 實驗數據

本文實驗將采用真實數據集QWS，該數據集包含2507條真實Web服務的QoS屬性記錄，關于QWS的詳細介紹詳見文獻[18].在實驗中，為模擬真實環境下的服務組合問題，該實驗為工作流設置了不同的任務數，并將QWS數據集中的服務數據分配到這些原子任務的候選服務集，每個候選服務包含4個QoS屬性對應前文提出的QoS四元組.同時，由于在人工魚的行為選擇時需要使用權重，對于響應時間和時延的權重分別設置為0.6和0.4.

4.2 SOM聚類評價驗證

為驗證采用SOM聚類操作對于算法模型具有可行性與有效性，以下將基于不同的候選服務個數來驗證SOM聚類對于服務的過濾和選擇兩方面的效果，同時與K-means聚類算法進行對比.對于服務過濾效果，文獻[19]給出了單獨兩個服務之間QoS相似度的計算方式，本文將不同服務間的相似度相加后與服務個數的比值作為整個服務集合的相似度，來衡量經過聚類操作后候選服務集的相似差異.QoS相似度越小，則表明候選服務具有更大的差異性，從而更有可能找到較好的服務組合;對于服務選擇效果，我們設立一個新的評價指標組合錯誤率(Fault Rate)，該評價指標計算在一次服務組合中使用了不滿足用戶需求的服務的比例.本文將在原數據基礎上添加一定量不符合可用性和吞吐量約束的服務(具體為候選服務數的30%)，并計算該候選服務集合在經過聚類操作后構建的服務組合的錯誤率.

該部分實驗的參數如下：取候選服務個數為50，100，150，200，SOM的輸出層大小為默認的8×8，初始鄰近距離為3.同時為保證兩種算法在聚類后有相近的候選服務個數，選取候選服務個數乘0.4作為K-means的K值.所有實驗結果取30次實驗的平均值，實驗結果如圖5、圖6所示.

圖5 不同服務個數下的QoS相似度

圖6 不同服務個數下的組合錯誤率

從圖5可以觀察到，在經過聚類過濾后，原服務集合相似度出現明顯的下降，并隨服務個數的增多而愈發明顯.在不同候選服務個數下，由于SOM并沒有聚類中心個數的限制，服務個數呈動態變化，故SOM聚類的候選服務其相似度始終小于使用K-means聚類的候選服務.由圖6可見，在不同候選服務個數下，服務組合的錯誤率始終在0.2-0.3之間，但是經過SOM聚類的候選服務的錯誤率始終小于其他兩種情況，并且隨著候選服務個數上升逐漸下降.綜上，可見SOM聚類能有效降低候選服務的數量和調用錯誤服務的可能，并且候選服務個數越大，過濾效果愈發明顯.

4.3 服務組合QoS優化對比

為驗證SO-AFSA在求解基于QoS的服務組合問題的有效性，本文將分兩部分進行試驗.首先，本文將基于隨機的初始種群測試多目標人工魚群算法在Web服務組合優化問題上的表現，其次，將基于SO-AFSA使用SOM聚類結果作為初始種群依據，從而評價模型整體的優劣.兩部分實驗都將與經典的多目標算法MOPSO[17]、NSGA-II[20]、SPEA-II[21]和PESA-II[22]進行對比，各算法的具體參數詳見表2.

表2 參數設置

4.3.1 多目標魚群算法評價

本文將從收斂性和分布性來評價算法表現，在此引入引入MOP中常用的兩個評價指標GD[23]和Spacing[23]，前者計算算法得到的近似解與Pareto前沿的平均距離，從而體現算法的收斂性，后者計算解集中每個解到其他解的最小距離的標準差，從而衡量解集是否分布均勻，兩評價指標均為越小則結果越好.因為GD的計算需要使用到Pareto前沿，但是對于實際問題沒有確定的Pareto前沿可供參考，本實驗參考文獻[24]的實驗方法，將5種算法各迭代1000代，取30次結果的并集，去掉其中被支配和重復的解，將獲得的最后的解集作為Pareto前沿(見圖7(a)).5種算法將基于相同的候選服務，同樣依照上述方法在不同迭代次數下構建解集進行計算評價指標，實驗結果如圖7(b)-圖7(c)所示.

可以看到隨著迭代次數的增加，5種算法的GD值均呈現下降趨勢并逐漸趨向于0，首先該結果充分說明圖7(a)中求得的近似Pareto前沿能夠充分代表最優解集.在GD值方面，隨著迭代次數遞增，雖然PESA-II和MOPSO在部分迭代次數下(前者取200-300，后者取600)能夠逼近多目標人工魚群算法取得的GD值，但是從整體情況看來，多目標人工魚群算法的GD值在任何代數下始終小于其他4種算法.在Spacing值方面，多目標人工魚群算法的表現較為優秀，在不同迭代次數下均優于其余4種算法.綜上，相比其他4種算法，多目標人工魚群算法具有更好的收斂性和均勻性.在圖7(d)可視化顯示了5種算法在運行200代時的結果.可觀察到，SPEA-II和PESA-II兩種算法所取得的最優解明顯被多目標人工魚群算法取得的最優解所支配，同時雖然NSGA-II和MOPSO的部分解優于多目標人工魚群算法，但后者在解數量和分布情況上均優于前者.綜上，對于Web組合優化模型，多目標人工魚群算法相較于上述其他算法能取得更優的Pareto解集.

圖7 多目標魚群算法與其余4種算法的對比

4.3.2 SO-AFSA評價

為驗證SO-AFSA在求解基于QoS服務組合問題的有效性，以下同樣使用上述4種算法作為對比.實驗參考文獻[25]引入響應時間和ANE(Average Normalized Error)兩個評價指標，其中響應時間指算法求得Pareto最優解的時間，用于衡量算法的運行效率，ANE指標衡量求得的服務組合對于各目標的滿足情況，具體表現為優化效果，其值越大表示結果越能滿足各目標函數.所有方法均取200的迭代次數，每個子服務的候選服務數均為50，實驗在不同服務個數下取20次實驗結果均值作為最后結果，如表3、表4所示.

表3 各算法的ANE(%)

從表3可以觀察到，SO-AFSA在服務個數較小(Number of Service=5)時的優化效果略遜于NSGA-II，這是由于受到較小服務個數的限制，SOM聚類對于服務的過濾效果并不顯著.但當服務個數逐漸增加時，SO-AFSA的ANE值逐漸增大，并且始終高于其他4種算法，這是由于聚類操作過濾相類似的候選服務使得SO-AFSA擁有更優的初始種群及服務搜索空間，從而通過差分變異等一系列機制尋得最優解.

同時，通過表4并不難發現，隨著服務個數的增大，各算法的響應時間均隨之增大，NSGA-II的響應時間最長，MOPSO則最短，PESA-II在部分服務個數下的響應時間小于SO-AFSA，即SO-AFSA的優勢并不明顯，這是因為SOM的聚類操作和算法中擁擠距離的計算耗費了大量時間，但整體的響應時間與MOPSO、PESA-II的差距并不大.同時當服務個數上升到20以后，PESA-II的響應時間已沒有明顯的優勢.并且在實驗中我們發現，隨著服務個數的增加，MOPSO中粒子維數的上升使得基于網格密度的維護策略占用更多的時間，使得SO-AFSA和MOPSO在響應時間上的 差距進一步縮小.當故綜合來看，SO-AFSA 能有效處理 Web 服務組合優化問題，并且相較于其余4種算法，更加適應服務個數較多的情況.

表4 各算法響應時間(s)

5 結 論

本文研究了SOM神經網絡在Web服務組合優化問題上的應用，并提出了多目標人工魚群算法，兩者構成SO-AFSA模型，解決了傳統的多目標算法在服務組合優化領域內的一些問題.實驗證明，本文提出的模型能有效提升組合服務的綜合表現.

未來需要進行的工作主要包含兩部分：首先SO-AFSA并沒有考慮 Web服務具有一定的動態性和不確定性，但實際上服務的QoS值是在不斷發生變化的，因此我們需要進一步考慮QoS數據的可靠性.其次，在SO-AFSA中，SOM的聚類操作耗費了組合優化過程的大部分時間，對聚類過程加以改進將會極大改進SO-AFSA在計算時間上的表現.