求解物流Web服務組合問題的兩階段多目標蟻群算法

方清華　倪麗萍　李一鳴

合肥工業大學，合肥，230009

?

求解物流Web服務組合問題的兩階段多目標蟻群算法

方清華倪麗萍李一鳴

合肥工業大學，合肥，230009

摘要：針對基于QoS的物流Web服務組合優化問題，提出了兩階段多目標蟻群優化(TMACO)算法。首先，針對原始數據集中存在被支配候選服務而增加算法求解時間的問題，提出了基于Pareto支配的預優化策略；其次，針對屬性權重難以確定的問題，提出了不依賴權重的信息素更新策略和啟發信息策略；最后，針對基礎蟻群算法容易陷入局部最優的問題，提出了懶螞蟻策略。實驗結果表明，TMACO算法具有良好性能，相對于基礎蟻群算法、利用解與理想解距離來更新信息素的改進蟻群算法、遺傳算法以及用支配程度作為解的個體評價的改進遺傳算法，TMACO算法有更高的尋優能力，能夠找到更多更優的非劣解。

關鍵詞：物流服務；蟻群算法；服務組合問題；Pareto最優解；多目標優化

0引言

近年來，云計算(cloud computing)、物聯網(internet of things,IoT)迅速發展，受到越來越多學者的關注。云計算和物聯網將人類社會、信息世界和現實世界更緊密地聯系、整合在一起。基于服務的信息系統讓現實世界和虛擬世界的界限變得越來越模糊，也為軟件應用程序創新提供了肥沃的土壤[1]。在物流領域，云計算可以幫助我們在物流需求快速增長、動態多變的情況下，靈活地開發各類物流應用[2]。一個新的基于IT的物流服務模式由此誕生，即云物流服務模式。

云物流服務模式就是基于云計算，對物流服務進行服務供應和服務管理。云是一種部署在互聯網上的虛擬資源庫，用戶通過付費得到資源的使用權。云物流服務模式可以對資源進行動態配置，以更好地滿足用戶的請求。物流服務涵蓋了個人物流服務和綜合物流服務[3]。目前，云物流服務模式在理論和實踐上存在以下問題：①物流資源因地理分布不同而異，具有多變性、形態多樣性和區域自治性，這使得云物流平臺上的資源共享和資源管理比其他云計算平臺更復雜、更困難。②物流平臺上的物流Web服務具有分布不均的特性，每個抽象Web服務對應的具體Web服務數量龐大，導致要找到“最優”具體Web服務變得異常困難。此外，這些大量的具體Web服務中，可能有的服務是不可用或已失效的，需要運用基于信任的方法來解決這類問題[4]。基于上述問題，本文闡述了資源虛擬化和組合服務的概念，重點研究在可用具體Web服務集合中，快速找到最優的服務組合。目前主要運用智能優化算法來求解，如遺傳算法(genetic algorithm，GA)[5-6]、粒子群算法(PSO)[7]、蟻群算法(ACO)[8-9]等。

劉磊等[5]提出了多目標遺傳算法(SMOGA)，將個體的支配強度和被支配強度相結合進行個體評價，根據評價結果進行環境選擇并生成個體的交叉概率，進而提出了結合局部搜索的個體變異策略。但其實驗中問題的規模較小，新個體評價方法在算法中的效果較難驗證。劉志中等[6]基于改進的遺傳算法，將全局QoS(quanlity of service)約束分解成局部QoS約束，在物流服務流程執行過程中，依據當前情景信息，選出滿足局部QoS約束的最優物流服務。將全局QoS約束分解成局部QoS約束可能會導致某些只有部分屬性較差但整體屬性較優的服務被過濾，且最后提供的結果可選項較少，較難滿足用戶變化的需求。張煥煥等[10]基于遺傳算法的交叉變異思想，對社會認知算法中的模仿學習和觀察學習過程進行改進，并應用在離散型物流Web服務優化組合問題中，通過實驗證明改進算法具有較高尋優能力。Zhao等[11]將具有QoS全局最優Web服務選擇的問題轉化為QoS感知的多目標多選擇Web服務組合優化問題，最終找到Pareto最優解。王秀亭等[8]把蟻群算法引入Web服務選擇領域，將基于QoS的Web服務選擇問題轉化為最優路徑選擇問題，并給出蟻群算法求解Web服務組合問題的模型，測試了蟻群算法求解Web服務選擇問題的有效性，但并未對基礎蟻群算法進行改進。Wei等[9]闡述了解空間理想解的概念，并利用解與理想解的距離指導信息素的更新，驗證了其改進算法能夠在巨大搜索空間找到接近最優的解。像這樣用距離評價一個解的方法更易于理解，有良好的可解釋性。

許多研究仍無法避免算法初期由于缺乏對搜索空間的知識，求解速度較慢、屬性權重難以確定以及算法容易陷入局部最優的問題。本文針對上述問題，提出相應的改進策略，提出兩階段多目標蟻群優化(two-stage multi-objective ant colony optimization,TMACO)算法，并研究如何在云物流服務模式下，運用TMACO算法更快地找到更多更優質的物流Web服務組合優化問題的非劣解。

1物流Web服務組合問題

物流資源的柔性和可擴展性是云物流服務模式的關鍵，因此，有效解決物流資源的表達和封裝是物流資源虛擬化的兩個重點，而服務組合在保證物流資源之間有效協作方面至關重要。

1.1資源虛擬化

虛擬化象征著計算資源的抽象化，是資源共享和動態分配的關鍵，其目的是為用戶和基于異構、自治資源的應用提供異構統一的集成操作平臺[12]。在物流領域，尤其在互聯網環境下，資源虛擬化能夠讓用戶更方便、更靈活地利用物流資源，包括物流設備和云物流計算機系統中的計算資源，它不僅能將物理資源抽象成統一的邏輯資源形式，還可以通過資源服務的組合，為用戶提供更高效、創新的資源形式。資源的虛擬化主要有兩個任務：一是通過分析物流資源的功能與特點，建立一個資源表達模型；二是通過運用Web服務技術構建服務描述的方法來封裝服務的資源信息。

物流資源具有多樣性、復雜性和動態性等特性，要建立統一的表達模型相對比較困難。由于物流服務的含義和慣用法不同于傳統Web服務，因此Web服務相關的標準(如WSDL)不能直接應用于物流資源的表達和信息封裝。物流資源的虛擬化框架如圖1所示，該框架分為三層，即物理資源層、虛擬資源層和服務資源層[13]。

圖1　物流資源的虛擬化框架

在物理資源層，通過使用物聯網相關技術，如RFID、傳感器和全球定位系統等，可以檢測到分布式物流資源，并將它們整合到云物流系統中[14]。在虛擬資源層，基于對物流資源特點的分析，將物理資源抽象成邏輯資源，并以此建立資源的表達模型。物流資源在服務封裝層被封裝成服務。這樣便能以管理服務的方式來管理物流資源。

1.1.1物流資源表述

物流資源是指物流服務過程中用以支持整個物流活動的各種元素，如設備資源、人力資源、服務資源、信息資源和財政資源等。

物流資源的表達模型如圖2所示，該模型包括三個等級[13]：①物理資源，用以支持整個物流活動的各種資源；②資源的信息表示，如資源的總體特征、屬性和狀態等；③資源接口，如對資源的狀態進行查詢和更新。

圖2　物流資源表達模型

物流資源之間存在復雜的層級結構，為滿足共享需求，需要用語義方法來描述物流資源之間的關系及其屬性，以便規范它們在不同領域的表述，滿足可擴展性，便于調整、修改，并擴展其分類和表述方法。

1.1.2物流資源封裝

物流資源信息是從不同角度來描述的，我們著重關注位置、服務的功能和狀態信息。資源的表達模式為LRE=〈LRid,LRpro,LRint〉。其中，LRid是物流資源在物理資源層的標識，它對用戶透明，每個資源在全局空間有且只有一個通用資源標識符(URI)，它在一個特殊的命名空間中聲明；LRpro表示虛擬資源層的物流資源信息，用XML語言來描述和封裝；LRint定義的是使用Web服務描述語言(WSDL)在資源界面層進行的操作集合。

建立資源表達模型后，就可以在服務注冊中心注冊并發布物流服務。

1.2服務組合

服務組合就是要找到滿足一些確定功能性需求和非功能性需求的適當的Web服務，將多個功能較單一的服務進行組合，構建成功能強大的組合服務來滿足各種實際應用需求。

對服務組合的研究一般是基于QoS的服務組合進行的，Canfora等[15]已經證明基于QoS 的服務組合是NP難題。目前的研究主要是將服務組合問題視為優化問題，服務搜索過程中主要考慮服務的質量屬性，求解過程主要運用智能優化算法。本文把服務組合問題看作多目標優化問題，并給出了蟻群算法求解基于QoS的服務組合問題的模型。

1.2.1物流Web服務組合模型

具體物流服務(concrete logistic service,CLS)是由物流服務提供商在服務注冊中心中發布的可用物流服務。抽象物流服務 (abstract logistic service, ALS)是功能相似的一類物流服務集合。一個抽象物流服務包含多個具體物流服務，這些具體物流服務可由不同服務物流提供商提供，具有不同的QoS值。

根據對用戶物流需求的分析，建立適當的物流服務流程模型。物流服務流程(logistic service processes,LSP)要完成多個功能，需要多個抽象物流服務的具體物流服務相互組合、配合。物流服務之間有順序、選擇、并行和循環等控制關系，如圖3所示。

圖3　物流服務流程示意圖

假設一個物流服務流程由N個抽象物流服務組成，即LSP={ALS1，ALS2，…，ALSN}，每個抽象物流服務有Ni個候選具體物流服務，即ALSi={CLSi1, CLSi2…,CLSiNi}，每個具體物流服務有M個QoS屬性：〈Q1,Q2,…,QM〉。物流服務組合就是為物流服務流程的每一個子流程服務選出一個具體物流服務，使物流服務整體評價達到最優，選出的具體物流服務集合稱為組合物流服務，記作CS，物流服務組合流程示意圖見圖4。

圖4　物流服務組合流程圖

1.2.2物流Web服務的QoS屬性

目前已經提出且應用于實際的QoS屬性指標有30多個，限于篇幅，本文只取物流服務中最常用、有代表性的5個QoS屬性：費用(cost)C，即服務的成本，是獲得服務所需支付的價格；時間(time)T，包括服務的運行時間、等待時間、通信時間等；信譽度 (credibility)Cr，即從服務使用者角度來評價一個服務的可信程度；遞送的準時性(punctual)P，描述能夠維護服務和服務質量的程度；可靠性(reliability)R，表示能夠為Web服務請求提供服務的程度。

一個組合物流服務的QoS屬性集表示為{C，T，Cr，P，R}。若抽象物流服務的連接為順序結構，則描述組合物流服務的服務質量的聚合QoS的計算方式為

若抽象物流服務的連接為并行結構，則聚合QoS的計算方式為

若抽象物流服務的連接為混合結構，則聚合QoS的計算方式為上述兩種計算方式的組合。

QoS屬性的標準化采用如下極差標準化方法：

正向指標(最大化屬性)標準化公式(以具體物流服務CLSia為例)為

q(k)=q(k)max(i)-q(k)(i)q(k)max(i)-q(k)min(i) q(k)max(i)≠q(k)min(i) 1 q(k)max(i)=q(k)min(i){

(1)

負向指標(最小化屬性)標準化公式為

q(k)=q(k)-q(k)min(i)q(k)max(i)-q(k)min(i) q(k)max(i)≠q(k)min(i) 1 q(k)max(i)=q(k)min{

(2)

2兩階段多目標蟻群算法

2.1基礎蟻群算法概述

蟻群算法采用分布式并行計算機制，具有較強的魯棒性，通過螞蟻之間的協作機制來實現對多目標優化問題最優解的搜索。相比傳統的窮舉算法、貪婪算法，蟻群算法能夠更快地找到問題的最優解，在許多組合優化問題上取得了較好的效果，如背包問題、TSP問題和車間調度問題、服務組合問題等。

螞蟻的移動過程是蟻群算法解決物流服務組合問題的核心，利用蟻群算法求解物流服務組合問題模型中，當螞蟻為當前抽象物流服務選出一個具體物流服務后，下一步則需要計算當前具體物流服務與下一個抽象物流服務所包含的所有具體物流服務的轉移概率，采用輪盤賭方法確定螞蟻的方向。轉移概率計算公式為

(3)

i，j=1,2，…，N；a=1,2，…，Ni

式中，τ(i,a)(j,b)為具體物流服務CLSia到具體物流服務CLSjb路徑上的信息素；η(j,b)為具體物流服務CLSjb的啟發信息；α、β為信息素和啟發函數的相對重要程度。

信息素的揮發與釋放是蟻群算法正反饋機制的關鍵。基礎蟻群算法采用如下規則進行信息素的更新：

τ(i,a)(j,b)(t+n)=(1-ρ)τ(i,a)(j,b)(t)+

Δτ(i,a)(j,b)0<ρ<1

(4)

(5)

i，j=1,2，…，N；a=1,2，…，Ni；b=1,2，…，Nj

式中，ρ為信息素的消逝速度；Q為預設常數；LCS為組合物流服務的服務質量構成的函數。

Dorigo提出了三種不同的信息素更新策略，本文采用應用最廣泛的Ant-cyclesystem模型，模型中的LCS的計算公式如下：

(6)

啟發函數的形式也有多種，本文基礎蟻群算法的實現采用如下計算方法[8]：

(7)

2.2TMACO算法

目前，國內外很多學者已經從不同的角度將服務組合轉換為以下的各種已知的數學問題，如單目標組合優化問題和多目標組合優化問題。單目標組合優化問題就是由用戶給定各個QoS屬性的權重值，通過簡單的線性加權求和將多個QoS目標聚合轉換為單目標，產生滿足約束條件的優化結果為最優單解，用戶沒有選擇的余地。

然而，服務的QoS屬性之間存在不可公度性和矛盾性，難以將其值規范到統一的度量空間而準確地評估出服務的綜合值，且用戶缺乏QoS屬性相關領域的知識，難以確切地給出QoS屬性的權重信息，更難以用確切的數值來表達。因此基于QoS 的服務組合問題一般不存在通常意義上的最優解，討論的多是非劣解。

所以本文選擇將物流服務組合的組合優化問題轉化為多目標組合優化問題來求解，即不需事先給定各QoS屬性的權重值，對多個目標同時進行優化，最終產生一個非劣解集，用戶可依其偏好從非劣解集中選擇最滿意的解，因此能更好地滿足用戶的偏好和個性化需求，也更符合物流服務組合的實際情景。

解決多目標問題的一般手段是通過對各個目標進行權衡和折中處理，得到不劣于其他解的一個解集，稱為非劣解集(Pareto解集)[16]。Pareto支配及Pareto最優解集的定義如下。

Pareto支配當且僅當以下2個條件都成立時，稱解x1支配解x2(目標為最小化)： ①fk(x1)≤fk(x2)(k=1,2,…,M)，即x1的各個目標都不比x2的各個目標差； ②?k∈{1,2,…,M}:fk(x1)

Pareto最優解集在一個可行解的集合X中，那些不被X中任何一個解所支配的解的集合Xp(Xp?X)稱為Pareto 最優解集。

為了有效求解物流Web服務組合問題，本文提出兩階段多目標蟻群算法TMACO算法。

2.2.1候選服務預優化階段

本文討論物流服務組合問題的基礎是提供的具體物流服務都是可用服務，但是，在現有市場環境下，物流公司的整體實力良莠不一，他們所提供的具體物流服務的服務質量各方面也是參差不齊的。在候選具體物流服務集合中，不乏服務質量各方面都是較低水平的候選服務，即各個QoS屬性值都較差，也就是被其他具體物流服務所支配。若算法的尋優能力足夠優秀，那么這些被支配候選服務最終肯定不會出現在非劣解集中的組合服務中。因為若將組合服務中被支配候選服務替換成支配該候選服務的具體服務，則替換后的組合服務會支配替換前的組合服務。相關證明如下：

求證若組合服務中存在被支配具體物流服務，則該組合服務一定不是非劣組合服務。

已知CLSb支配CLSa，組合物流服務CSi包含CLSa。

證明記Q1為最大化屬性(如可靠性)，Q2為最小化屬性(如成本)，記CSi·Q1=ConΔCLSa·Q1，CSi·Q2=ConΔCLSa·Q2，Δ表示聚合，Con為常數；由于CLSb支配CLSa，因此有CLSb·Q1>CLSa·Q1，CLSb·Q2ConΔCLSa·Q1=CSi·Q1，ConΔCLSb·Q2

被支配候選服務的存在會大大延長算法的求解時間。基于此，本文提出候選服務預優化策略。算法后續的求解都是在候選服務預優化策略步驟后求得的非劣候選服務集中進行服務的選擇。

定義一個具體物流服務被其他具體物流服務支配的程度(簡稱被支配因子)和支配其他具體物流服務的程度(簡稱支配因子)分別記為BD和D。

對于所有具體物流服務，必有0≤BD(CLS),D(CLS)

非劣具體物流服務集合按如下規則產生：對于任一個CLSia1，若不存在CLSia2，CLSia1與CLSia2屬于同一個ALSi，且CLSia2支配CLSia1，則CLSia1屬于非劣候選服務集。

2.2.2信息素的更新策略

基礎蟻群算法求解服務組合問題時，采用個體中每兩個相鄰具體物流服務的相應QoS值的差值信息L來指導信息素的更新，L值越小，該個體釋放的信息素越多。這種相對距離比較的方式沒有考慮個體本身的優劣，因此尋優效果較差。對此，Wei等[9]提出了理想最優解的定義：一個理想解向量Fb是解空間中包含每個單目標最優值的點，Fb可能并不是候選集中存在的具體物流服務，它只是作為算法試圖實現的一個目標。顯然，越接近理想解的個體越優，理想解可由計算得到。

計算理想解與最差解的算法過程如下。

算法名稱：CalFF(計算理想解與最差解的算法)

輸入：全部組合物流服務的QoS值數據。

輸出：解空間的理想解fb，最差解fw。

算法步驟：

(1)Fork=1 toM

(2)Fori=1 toN

(3)計算第i個抽象物流服務所包含的所有具體物流服務的k屬性值的最大最小值maxki，minki;

(4)End For

(5)根據k屬性的聚合計算方式,將N個minki相加或相乘，得到fb(k);將N個maxki相加或相乘，得到fw(k);

(6)End For

改進多目標蟻群算法信息素更新的條件為：在本輪迭代中，能夠添加到Pareto解集的個體才能在相應路徑上釋放相應的信息素。

Pareto解集更新函數的具體實現步驟如下。

算法名稱：ChangeParetoList

輸入:解sca，Pareto解集PList。

輸出:Pareto解集PList

算法步驟：

(1)IsGood=true;

(2)If PList.Lenght==0

(3)將sca插入PList;IsGood=true;

(4)End If

(5)For each sci in PList

(6)If sci支配sca

(7)IsGood=false;break;

(8)End If

(9)If sca支配sci

(10)將sci從PList中刪除;continue;

(11)End If

(12)End For

(13)If IsGood==true

(14)將sca插入PList; IsInsert=false;

(15)End If

2.2.3啟發函數的確定

基礎蟻群算法中，啟發函數的確定是由具體物流服務的QoS值確定的。在實際應用中，具體物流服務的QoS屬性之間存在不可公度性，難以將其值規范到統一的度量空間，采用這種啟發函數往往還是會出現側重某一個或一些QoS屬性的結果。而有些研究選擇一個統一的常數作為啟發函數，這樣不能達到區分優劣的目的。本文在啟發函數中考慮具體物流服務的支配因子，啟發信息計算公式為

(8)

其中，N為抽象物流服務的個數。當候選服務集不大時，被支配候選服務較少，非劣候選服務集中候選服務的D值相差不大，此時的啟發函數相當于一個常數。而當候選服務集較大時，采用這樣的啟發函數便能夠較好地區分非劣候選服務的優劣，從而提高求解的速度。

2.2.4懶螞蟻策略

日本北海道大學進化生物研究小組對蟻群的活動進行觀察，發現大部分螞蟻都努力地搜尋食物，而有少部分的螞蟻卻無所事事、左顧右盼，且稱其為“懶螞蟻”[17]。而在后續研究中發現，當斷絕食物來源時，大部分的螞蟻表現得一籌莫展，而“懶螞蟻”們卻能帶領蟻群找到它們已偵察到的新食物源。“懶螞蟻”不像其他大部分螞蟻那樣循規蹈矩，它們能觀察到蟻群的薄弱之處，同時保持對新事物的探索狀態，從而保證蟻群不斷得到新食物源。這就是所謂的“懶螞蟻效應”。

本文參考“懶螞蟻效應”，在種群中劃分出Ln個懶螞蟻，它們并不像其他螞蟻那樣一步一步地求解，而是直接隨機復制非劣解集中的一個個體的路徑，并進行單位隨機變異，作為自己的路徑。采取這樣的局部優化策略能夠增加解的多樣性，利于跳出局部最優的困局；同時，相對于隨機生成解的方式，這樣的策略能夠較好地保持解的優良性，加快求解速度。

算法運行前期，加入解集中的解較少，新解加入的門檻較低，這時種群的尋解能力較強，而解集中解的平均質量不高，懶螞蟻策略無法體現優勢，因此懶螞蟻應少些；隨著解集的頻繁更新，解的平均質量不斷提高，新解加入的門檻提高，此時應設置多一些懶螞蟻繼承解集中的優解，并通過變異操作增加解的多樣性，保持種群的尋優能力，促進算法跳出局部最優困局。因此，本文設置自動更新懶螞蟻數量Ln的懶螞蟻局部優化策略，即第一次迭代時，設置懶螞蟻數為0；此后，根據每次迭代未能加入解集的螞蟻數outAN,更新下一次迭代的懶螞蟻數量，懶螞蟻具體數量的計算方式如下：

Ln=θ·outAN

(9)

式中，θ為懶螞蟻數量調整參數，0<θ<1。

2.3TMACO算法的實現步驟

(1)對原始候選服務集進行預優化。

(2)對算法進行初始化。初始化螞蟻種群、各個參數以及非劣解集，計算每一個具體物流服務的D值、BD值，兩階段多目標蟻群算法迭代開始。

(3)為除懶螞蟻外的其他螞蟻計算當前具體物流服務到下一個抽象物流服務的所有具體物流服務的選擇概率，用輪盤賭方法選擇具體物流服務，將其序號加入螞蟻的路徑，聚合QoS值，直到螞蟻得到一個完整的解。嘗試更新非劣解集。

(4)懶螞蟻局部優化策略。為每只懶螞蟻復制解并進行單位變異，嘗試更新非劣解集。

(5)信息素的更新。每段路徑執行信息素的揮發操作。在本次迭代中，能成功更新非劣解集的解(包括懶螞蟻)，在相應路徑上釋放信息素。

(6)調整懶螞蟻的數量。

(7)若連續5次迭代，Pareto解集數量不變，則結束循環，輸出非劣解集；否則，返回步驟(3)，繼續迭代。

2.4TMACO算法的時間復雜度分析

TMACO算法求解物流服務組合問題模型中，螞蟻種群規模為AN，最大迭代次數為MAXNC，算法的時間復雜度分析如下：

初始化算法各參數，計算具體物流服務的D值及BD值(需要常數次)，時間復雜度為O(N×Ni2)；初始化螞蟻種群需要AN次，時間復雜度為O(AN)；尋優過程，AN只螞蟻構造一次解，與非劣解集中的所有解進行比較，算法總共迭代MAXNC次，時間復雜度為O(MAXNC×(AN2+AN3))。

3實驗結果與分析

為了驗證本文算法的可行性及實用性，本文所有算法均運用Java編程語言，運用MyEclipse軟件編寫實驗相關代碼。本實驗編譯運行的計算機參數為：32位Windows 7操作系統、Intel Core 2 E8400 3.00GHz CPU、2.00GB內存。

本文實驗中，參照文獻[10]，每個候選物流服務抽取五個QoS指標，即交付時間T、交付費用C、交付可靠性R、遞送的準時性P及信譽度Cr。QoS屬性的取值范圍設置如下：1 h≤T≤24 h，1≤C≤100，0.5≤R≤1，0.5≤P≤1，0.5≤Cr≤1。

根據文獻[18]得出的蟻群算法相關參數范圍，本文選擇的參數值分別為：α=1，β=5，ρ=0.7，Q=10。各維QoS的權重分別為0.15，0.2，0.25，0.1，0.3[10]。

3.1TMACO算法參數分析

為探究螞蟻種群數量以及懶螞蟻數量調整參數的設置對算法尋優效果的影響，實驗設置25個參數組合，分別是螞蟻種群AN的5個取值和懶螞蟻數量調整參數θ的5個取值的兩兩組合，其中參數組合1～5為AN取值70，θ取值依次為0.3、0.4、0.5、0.6、0.7，組合6～10、11～15、16～20、20～25的AN取值分別為90、110、130、150，θ取值與1～5組合一致。

實驗選取抽象物流服務個數N為6，每個抽象物流服務所包含的具體物流服務個數為區間[5,10]內隨機選擇。實驗分別獨立運行10次，從以下六個方面考查算法的性能：①平均解個數(非劣解的平均數量，即0次非劣解數量的平均值)；②最多解個數(非劣解最多數量，即10次非劣解數量的最大值)；③平均收斂時間(找到所有非劣解的時間的平均值，即10次收斂時間的平均值)，收斂時間的單位為s；④最短收斂時間(找到所有非劣解的時間的最短時間，即10次收斂時間的最小值)；⑤平均解值(每次運行得到一個最優解，即10次最優解的平均值)；⑥最優解(10次最優解的最小值)。

實驗結果如圖5～圖8所示。

由圖5的組合1～5可見，隨著懶螞蟻數量調整參數θ的增大，TMACO算法找到的平均非劣解個數、最多解個數增多，到組合4，即當θ值為0.6時，增加趨勢變緩，其他組合(如組合6～10、11～15等)的情況類似；從整體上看，到組合16～20，即螞蟻種群個數AN達到130時，非劣解的增加趨勢變得緩慢。因為解空間的非劣解數量是固定的，所以隨著螞蟻數量AN的增加，螞蟻對解空間的搜索能力增強，能夠找到的非劣解數量也隨之增加；但當AN增加到一定數量時，能找到的解空間中的非劣解越來越少，直到所有非劣解被找到。

圖5　兩個參數對找到非劣解的個數的影響

由圖6可見，所有參數組合找到的最優解都是一致的，即所有參數組合在獨立運行10次的情況下，至少有一次能找到指定權重的問題的最優解，證明了TMACO算法求解該問題的有效性。從整體上看，隨著AN和θ的增大，平均解值有減小的趨勢，波動范圍在0.02以內，其中，組合25得到的平均解值逼近最優解值，說明10次獨立運行所得到的最優解的質量都較高。

圖6　兩個參數對算法找到非劣解的解值的影響

由圖7可見，隨著AN和θ的增大，平均收斂代數越來越少，收斂時間越來越長，即螞蟻數量越多，懶螞蟻數量比例越大，算法找到越多非劣解所需循環次數越少。而最小迭代代數的變化規律不太明顯。由圖8可見，收斂時間隨著螞蟻數量和懶螞蟻比例的增加而增加，螞蟻數量達到130時，增加趨勢變緩；同樣螞蟻數量的5組實驗中，θ值取0.6時，收斂時間增加幅度較小。

綜上，本文算法參數設置為：AN=130，θ=0.6。

圖7　兩個參數對算法收斂代數的影響

圖8　兩個參數對算法收斂時間的影響

3.2不同規模下TMACO算法的效果分析

為探究TMACO算法對求解Web服務選擇問題的穩定性及有效性，對問題設置不同實驗規模，本文設置7組不同規模的實驗，每組的抽象物流服務個數分別為6,9,12,15,18,21,24，每組中，每個抽象物流服務所包含的具體物流服務個數從區間[5,10]內隨機選擇。實驗從算法尋得的非劣解數量、最優解適應度值、收斂代數、收斂時間四個方面考查算法的性能。

圖9、圖10所示為TMACO算法求解不同規模的Web服務選擇問題的實驗結果。

由圖9可見，隨著問題規模的增大，TMACO算法尋得問題的非劣解數量、非劣解的適應度值均線性增大，且問題規模越大時，非劣解適應度的增大趨勢漸緩，因為問題規模的增大，解空間中解的數量增多，非劣解數量也隨之增多，適應度值的基數增大，適應度值也增大。TMACO算法在求解Web服務選擇問題上表現出了有效性及較好的穩定性。由圖10可見，TMACO算法在求解Web服務選擇問題時的收斂代數和收斂時間隨著問題規模的增大而增大，收斂時間的延長趨勢明顯，因為，隨著問題規模增大，解空間非劣解數量增多，Pareto解集中的解較多，導致算法每求得一個解，需要與之進行比較的次數激增，因此收斂時間延長趨勢明顯。

圖9　不同規模下TMACO算法尋得的解的情況

圖10　不同規模下TMACO算法的收斂情況

3.3TMACO算法各策略效果對比

為驗證本文TMACO算法的各策略對算法效果的貢獻，設置對比實驗，在TMACO算法基礎上，分別加以下限制條件：去掉預優化策略(A)、采用基礎蟻群算法的信息素更新(B)、采用基礎蟻群算法的啟發信息(C)、去掉懶螞蟻局部優化策略(D)。實驗選取抽象物流服務個數N為21，每個抽象物流服務所包含的具體物流服務個數從區間[5,10]內隨機選擇。考查指標與3.2節相同。實驗結果如圖11、圖12所示。

圖11　本文算法各策略尋得的解的情況

圖12　本文算法各策略的收斂情況

由圖11可見，在尋得非劣解數量上，TMACO算法最多，D算法最少；在最優解適應度上，TMACO算法最優，D算法最差，即沒有懶螞蟻策略的算法(D)效果最差，說明懶螞蟻策略在增加算法多樣性上效果較好，其對TMACO算法尋優性能方面的貢獻較大，信息素更新策略(B)次之。由圖12可見，在收斂代數上，TMACO算法最少，說明TMACO算法用較少的迭代次數就能找到更多的非劣解，其次是A算法，D算法最多，即去除懶螞蟻策略時，算法需要較多次迭代才能找到更多非劣解，說明懶螞蟻策略在提高算法收斂速度上貢獻較大；在收斂時間上，D算法最短，TMACO算法最長，說明懶螞蟻策略較其他兩種策略在TMACO算法時間上占據較大比重，預優化策略次之。

綜上，在算法的尋優性能和收斂速度上，懶螞蟻策略和信息素更新策略貢獻較大，這兩種策略是TMACO算法的核心。

3.4TMACO算法與其他算法的對比

為了驗證本文算法的尋優效果，設置對比實驗，分別為：文獻[19]中的基礎遺傳算法、文獻[5]中的改進遺傳算法、文獻[8]中的基礎蟻群算法、文獻[9]中的改進蟻群算法。遺傳算法的參數均參照各自文獻來源進行設置。實驗選取的問題規模、考查指標均與3.3節相同。實驗結果如圖13、圖14所示。

圖13　TMACO算法與其他算法尋得的解的情況

圖14　TMACO算法與其他算法的收斂情況

由圖13看出，從尋得非劣解數量上看，TMACO算法最多，改進遺傳算法次之，基礎蟻群算法最少；從解的適應度值上看，TMACO算法的最優解的適應度值最優，其次是改進遺傳算法，說明TMACO算法的尋優性能較好，不僅能較其他算法找到更多的非劣解，更能找到適應度值較優的非劣解。由圖14可看出，在收斂時間上，蟻群算法普遍長于遺傳算法，因為遺傳算法的時間復雜度要小于蟻群算法的時間復雜度。TMACO算法的收斂時間只比文獻[9]的改進蟻群算法稍長。而從收斂代數上看，TMACO算法最少，其次為改進遺傳算法，即TMACO算法收斂只需較少的迭代次數。由此可見，較之其他算法，TMACO算法能以較少迭代次數找到較多、且質量優的非劣解。

綜上所述，本文提出的TMACO算法在求解基于QoS的物流Web服務組合問題上，表現出了良好的尋優性能和收斂特性，是一種有效的組合優化問題求解方法。

4結語

本文重點研究了基于QoS的物流Web服務選擇問題。為了實現物流資源的有效整合，闡述了一種物流資源表達和服務封裝的方法。此外，為了為每一個物流階段找到最優的具體物流服務，建立了基于QoS的物流Web服務選擇模型，并通過提出的兩階段多目標蟻群算法來求解該問題。但是本文對服務組合過程中物流Web服務的動態性、不穩定性等問題并未進行討論，還需要進一步的研究。下一步我們將在更多數據集中驗證TMACO算法的性能，對算法參數的優化選擇以及算法的收斂問題進行研究，并進一步尋找制約蟻群算法收斂速度的深層原因以及算法對數據敏感性的規律。

參考文獻：

[1]GuinardD,TrifaV,KarnouskosS,etal.InteractingwiththeSOA-basedInternetofThingsDiscovery,Query,Selection,andOn-demandProvisioningofWebServices[J].TransactionsonServicesComputing， 2010,3(3):223-235.

[2]SchuldtA,HribernikKA,GehrkeJD,etal.CloudComputingforAutonomousControlinLogistics[C]∥Proceedingsof40thAnnualConferenceoftheGermanSocietyforComputerScience.Berlin, 2010:305-310.

[3]HoltkampB,SteinbussS,GsellH,etal.TowardsaLogisticsCloud[C]∥ProceedingsoftheSixthInternationalConferenceonSemantics.Beijing,2010:305-308.

[4]GarruzzoS,RosaciD,SarnèGML.IntegratingTrustMeasuresinMulti-agentSystems[J].InternationalJournalofIntelligentSystems， 2012,27:1-15.

[5]劉磊,楊冬.求解服務等級感知服務組合問題的多目標遺傳算法[J].吉林大學學報,2015，45(1)：267-273.

LiuLei,YangDong.Multi-objectiveGeneticOptimizationAlgorithmforSLA-awareServiceCompositionProblem[J].JournalofJilinUniversity,2015，45(1)：267-273.

[6]劉志中,宋成,薛霄,等.情景感知的物流Web服務動態優化組合研究[J].計算機工程與科學,2013,35(9):51-56.

LiuZhizhong,SongCheng,XueXiao,etal.ResearchonDynamicOptimalCompositionofContext-awareLogisticsWebService[J].ComputerEngineering&Science, 2013,35(9):51-56.

[7]盛國軍,溫濤,郭權,等.基于改進粒子群的Web服務組合[J].計算機學報,2013, 36(5):1031-1045.

ShengGuojun,WenTao,GuoQuan,etal.WebServiceCompositionBasedonModifiedParticleSwarmOptimization[J].ChineseJournalofComputer,2013, 36(5): 1031-1045.

[8]王秀亭,馬力.基于蟻群算法的Web服務選擇[J].現代電子技術, 2013,36(12):9-11.

WangXiuting,MaLi.WebServiceSelectionBaseonAntColonyAlgorithm[J].ModernElectronicsTechnique, 2013,36(12):9-11.

[9]WeiZ,CarlK,TaimingF,etal.QoS-basedDynamicWebServiceCompositionwithAntColonyOptimization[C]//ACSAC2010:IEEE34thAnnualComputerSoftwareandApplicationsConference.Vasteras,Sweden,2010:493-502.

[10]張煥煥,薛霄,劉志中,等.基于遺傳社會認知算法的物流Web服務優化組合研究[J].計算機應用研究,2014,31(6):1752-1754.

ZhangHuanhuan,XueXiao,LiuZhizhong,etal.ResearchonOptimizationofLogisticsWebServiceBasedonGenrticSocialCongnitiveOptimizationAlgorithm[J].ApplicationResearchofComputers, 2014,31(6):1752-1754.

[11]ZhaoS,MaL,WangL,etal.AnimprovedAntColonyOptimizationAlgorithmforQoS-awareSynamicWebServiceComposition[C]//ICICEE2012:InternationalConferenceonIndustrialControlandElectronicsEngineering.Xi’an, 2012:1998-2001.

[12]SahooJ,MohapatraS,LathR.Virtualization:aSurveyonConcepts,TaxonomyandAssociatedSecurityIssues[C]∥ICCNT2010:Proceedingsof2ndInternationalConferenceonComputerandNetworkTechnology.Bangkok,Thailand, 2010:222- 226.

[13]LiWenfeng,ZhongYe,WangXun,etal.ResourceVirtualizationandServiceSelectioninCloudLogistics[J].JournalofNetworkandComputerApplications, 2013,36(6): 1696-1704.

[14]AtzoriL,IeraA,MorabitoG.TheInternetofThings:aSurvey[J].ComputerNetworks,2010,54: 2787-2805.

[15]CanforaG,PentaMD,EspesitoR,etal.ALightweightApproachforQoS-awareServiceComposition[C]∥PICSOC2004:Proceedingsofthe2ndInternationalConferenceonServiceOrientedComputing.NewYork:ACM, 2004:36-47.

[16]鄭彥興,田菁,竇文華.基于Pareto最優的QoS路由算法[J],軟件學報,2005, 16(8): 1484-1489.

ZhengYanxing,TianJing,DouWenhua.AQoSRoutingAlgorithmBasedonParetooptimal[J].JournalofSoftware,2005,16(8): 1484-1489.

[17]羅仕奎.懶螞蟻效應——懶于雜務,才能勤于動腦[J].北京農業,2011,36(8):13-14.

LuoShikui.LazyAntEffect—LazyChorestoBeDiligentinTheirBrains[J].BeijingAgriculture, 2011,36(8):13-14.

[18]楊亞南.蟻群算法參數優化及其應用[D].南京:南京理工大學,2008.

[19]方周,陳榮平,蔡美玲.遺傳算法在Web服務組合中的應用[J].計算機與現代化,2007, 48(12): 118-121.

FangZhou,ChenRongping,CaiMeiling.ApplicationofGeneticAlgorithmsinWebServiceComposition[J].ComputerandModernization, 2007,48(12):118-121.

(編輯蘇衛國)

Two-stage Multi-objective Ant Colony Optimization for Solving Logistics Web Service Composition

Fang QinghuaNi LipingLi Yiming

Hefei University of Technology,Hefei,230009

Abstract：A two-stage multi-objective ACO(TMACO) was proposed to solve logistics Web services composition optimization problems. First, to solve the time increases rised by candidate services which was dominated in the raw data, a pre-optimization strategy was proposed based on Pareto dominated ideology; secondly, since the weights of each attribute were difficult to determine, a non-dependent weight pheromone update strategy and inspiration information policy were included in the TMACO; and finally, the basic ACO was easy to fall into local optimum problem, a lazy ant strategy was proposed to solve this problem. The experimental results show that TMACO algorithm has good performance. Its optimization capability is better than that of the basic ACO,the improved ACO which used the distance of the solution and the ideal solution to update the pheromone,the basic genetic algorithm and improved genetic algorithm which applied the dominant factor to evaluate a solution, TMACO optimization algorithm has a higher ability to find more and better Pareto solutions.

Key words:logistics service; ant colony optimization (ACO); service composition problem; Pareto optimal solution; multi-objective optimization

收稿日期：2015-06-12

基金項目：國家自然科學基金資助項目(71301041,71271071)

中圖分類號：TP181

DOI：10.3969/j.issn.1004-132X.2016.10.009

作者簡介：方清華，女，1990年生。合肥工業大學管理學院碩士研究生。研究方向為數據挖掘、群體智能優化算法。倪麗萍，女，1981年生。合肥工業大學管理學院副教授。李一鳴，男，1990年生。合肥工業大學管理學院碩士研究生。