求解物流Web服務(wù)組合問題的兩階段多目標(biāo)蟻群算法

方清華　倪麗萍　李一鳴

合肥工業(yè)大學(xué)，合肥，230009

?

求解物流Web服務(wù)組合問題的兩階段多目標(biāo)蟻群算法

方清華倪麗萍李一鳴

合肥工業(yè)大學(xué)，合肥，230009

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

關(guān)鍵詞：物流服務(wù)；蟻群算法；服務(wù)組合問題；Pareto最優(yōu)解；多目標(biāo)優(yōu)化

0引言

近年來，云計(jì)算(cloud computing)、物聯(lián)網(wǎng)(internet of things,IoT)迅速發(fā)展，受到越來越多學(xué)者的關(guān)注。云計(jì)算和物聯(lián)網(wǎng)將人類社會(huì)、信息世界和現(xiàn)實(shí)世界更緊密地聯(lián)系、整合在一起?；诜?wù)的信息系統(tǒng)讓現(xiàn)實(shí)世界和虛擬世界的界限變得越來越模糊，也為軟件應(yīng)用程序創(chuàng)新提供了肥沃的土壤[1]。在物流領(lǐng)域，云計(jì)算可以幫助我們?cè)谖锪餍枨罂焖僭鲩L、動(dòng)態(tài)多變的情況下，靈活地開發(fā)各類物流應(yīng)用[2]。一個(gè)新的基于IT的物流服務(wù)模式由此誕生，即云物流服務(wù)模式。

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

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

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

1物流Web服務(wù)組合問題

物流資源的柔性和可擴(kuò)展性是云物流服務(wù)模式的關(guān)鍵，因此，有效解決物流資源的表達(dá)和封裝是物流資源虛擬化的兩個(gè)重點(diǎn)，而服務(wù)組合在保證物流資源之間有效協(xié)作方面至關(guān)重要。

1.1資源虛擬化

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

物流資源具有多樣性、復(fù)雜性和動(dòng)態(tài)性等特性，要建立統(tǒng)一的表達(dá)模型相對(duì)比較困難。由于物流服務(wù)的含義和慣用法不同于傳統(tǒng)Web服務(wù)，因此Web服務(wù)相關(guān)的標(biāo)準(zhǔn)(如WSDL)不能直接應(yīng)用于物流資源的表達(dá)和信息封裝。物流資源的虛擬化框架如圖1所示，該框架分為三層，即物理資源層、虛擬資源層和服務(wù)資源層[13]。

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

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

1.1.1物流資源表述

物流資源是指物流服務(wù)過程中用以支持整個(gè)物流活動(dòng)的各種元素，如設(shè)備資源、人力資源、服務(wù)資源、信息資源和財(cái)政資源等。

物流資源的表達(dá)模型如圖2所示，該模型包括三個(gè)等級(jí)[13]：①物理資源，用以支持整個(gè)物流活動(dòng)的各種資源；②資源的信息表示，如資源的總體特征、屬性和狀態(tài)等；③資源接口，如對(duì)資源的狀態(tài)進(jìn)行查詢和更新。

圖2　物流資源表達(dá)模型

物流資源之間存在復(fù)雜的層級(jí)結(jié)構(gòu)，為滿足共享需求，需要用語義方法來描述物流資源之間的關(guān)系及其屬性，以便規(guī)范它們?cè)诓煌I(lǐng)域的表述，滿足可擴(kuò)展性，便于調(diào)整、修改，并擴(kuò)展其分類和表述方法。

1.1.2物流資源封裝

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

建立資源表達(dá)模型后，就可以在服務(wù)注冊(cè)中心注冊(cè)并發(fā)布物流服務(wù)。

1.2服務(wù)組合

服務(wù)組合就是要找到滿足一些確定功能性需求和非功能性需求的適當(dāng)?shù)腤eb服務(wù)，將多個(gè)功能較單一的服務(wù)進(jìn)行組合，構(gòu)建成功能強(qiáng)大的組合服務(wù)來滿足各種實(shí)際應(yīng)用需求。

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

1.2.1物流Web服務(wù)組合模型

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

根據(jù)對(duì)用戶物流需求的分析，建立適當(dāng)?shù)奈锪鞣?wù)流程模型。物流服務(wù)流程(logistic service processes,LSP)要完成多個(gè)功能，需要多個(gè)抽象物流服務(wù)的具體物流服務(wù)相互組合、配合。物流服務(wù)之間有順序、選擇、并行和循環(huán)等控制關(guān)系，如圖3所示。

圖3　物流服務(wù)流程示意圖

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

圖4　物流服務(wù)組合流程圖

1.2.2物流Web服務(wù)的QoS屬性

目前已經(jīng)提出且應(yīng)用于實(shí)際的QoS屬性指標(biāo)有30多個(gè)，限于篇幅，本文只取物流服務(wù)中最常用、有代表性的5個(gè)QoS屬性：費(fèi)用(cost)C，即服務(wù)的成本，是獲得服務(wù)所需支付的價(jià)格；時(shí)間(time)T，包括服務(wù)的運(yùn)行時(shí)間、等待時(shí)間、通信時(shí)間等；信譽(yù)度 (credibility)Cr，即從服務(wù)使用者角度來評(píng)價(jià)一個(gè)服務(wù)的可信程度；遞送的準(zhǔn)時(shí)性(punctual)P，描述能夠維護(hù)服務(wù)和服務(wù)質(zhì)量的程度；可靠性(reliability)R，表示能夠?yàn)閃eb服務(wù)請(qǐng)求提供服務(wù)的程度。

一個(gè)組合物流服務(wù)的QoS屬性集表示為{C，T，Cr，P，R}。若抽象物流服務(wù)的連接為順序結(jié)構(gòu)，則描述組合物流服務(wù)的服務(wù)質(zhì)量的聚合QoS的計(jì)算方式為

若抽象物流服務(wù)的連接為并行結(jié)構(gòu)，則聚合QoS的計(jì)算方式為

若抽象物流服務(wù)的連接為混合結(jié)構(gòu)，則聚合QoS的計(jì)算方式為上述兩種計(jì)算方式的組合。

QoS屬性的標(biāo)準(zhǔn)化采用如下極差標(biāo)準(zhǔn)化方法：

正向指標(biāo)(最大化屬性)標(biāo)準(zhǔn)化公式(以具體物流服務(wù)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)

負(fù)向指標(biāo)(最小化屬性)標(biāo)準(zhǔn)化公式為

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兩階段多目標(biāo)蟻群算法

2.1基礎(chǔ)蟻群算法概述

蟻群算法采用分布式并行計(jì)算機(jī)制，具有較強(qiáng)的魯棒性，通過螞蟻之間的協(xié)作機(jī)制來實(shí)現(xiàn)對(duì)多目標(biāo)優(yōu)化問題最優(yōu)解的搜索。相比傳統(tǒng)的窮舉算法、貪婪算法，蟻群算法能夠更快地找到問題的最優(yōu)解，在許多組合優(yōu)化問題上取得了較好的效果，如背包問題、TSP問題和車間調(diào)度問題、服務(wù)組合問題等。

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

(3)

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

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

信息素的揮發(fā)與釋放是蟻群算法正反饋機(jī)制的關(guān)鍵?；A(chǔ)蟻群算法采用如下規(guī)則進(jìn)行信息素的更新：

τ(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為預(yù)設(shè)常數(shù)；LCS為組合物流服務(wù)的服務(wù)質(zhì)量構(gòu)成的函數(shù)。

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

(6)

啟發(fā)函數(shù)的形式也有多種，本文基礎(chǔ)蟻群算法的實(shí)現(xiàn)采用如下計(jì)算方法[8]：

(7)

2.2TMACO算法

目前，國內(nèi)外很多學(xué)者已經(jīng)從不同的角度將服務(wù)組合轉(zhuǎn)換為以下的各種已知的數(shù)學(xué)問題，如單目標(biāo)組合優(yōu)化問題和多目標(biāo)組合優(yōu)化問題。單目標(biāo)組合優(yōu)化問題就是由用戶給定各個(gè)QoS屬性的權(quán)重值，通過簡單的線性加權(quán)求和將多個(gè)QoS目標(biāo)聚合轉(zhuǎn)換為單目標(biāo)，產(chǎn)生滿足約束條件的優(yōu)化結(jié)果為最優(yōu)單解，用戶沒有選擇的余地。

然而，服務(wù)的QoS屬性之間存在不可公度性和矛盾性，難以將其值規(guī)范到統(tǒng)一的度量空間而準(zhǔn)確地評(píng)估出服務(wù)的綜合值，且用戶缺乏QoS屬性相關(guān)領(lǐng)域的知識(shí)，難以確切地給出QoS屬性的權(quán)重信息，更難以用確切的數(shù)值來表達(dá)。因此基于QoS 的服務(wù)組合問題一般不存在通常意義上的最優(yōu)解，討論的多是非劣解。

所以本文選擇將物流服務(wù)組合的組合優(yōu)化問題轉(zhuǎn)化為多目標(biāo)組合優(yōu)化問題來求解，即不需事先給定各QoS屬性的權(quán)重值，對(duì)多個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化，最終產(chǎn)生一個(gè)非劣解集，用戶可依其偏好從非劣解集中選擇最滿意的解，因此能更好地滿足用戶的偏好和個(gè)性化需求，也更符合物流服務(wù)組合的實(shí)際情景。

解決多目標(biāo)問題的一般手段是通過對(duì)各個(gè)目標(biāo)進(jìn)行權(quán)衡和折中處理，得到不劣于其他解的一個(gè)解集，稱為非劣解集(Pareto解集)[16]。Pareto支配及Pareto最優(yōu)解集的定義如下。

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

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

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

2.2.1候選服務(wù)預(yù)優(yōu)化階段

本文討論物流服務(wù)組合問題的基礎(chǔ)是提供的具體物流服務(wù)都是可用服務(wù)，但是，在現(xiàn)有市場環(huán)境下，物流公司的整體實(shí)力良莠不一，他們所提供的具體物流服務(wù)的服務(wù)質(zhì)量各方面也是參差不齊的。在候選具體物流服務(wù)集合中，不乏服務(wù)質(zhì)量各方面都是較低水平的候選服務(wù)，即各個(gè)QoS屬性值都較差，也就是被其他具體物流服務(wù)所支配。若算法的尋優(yōu)能力足夠優(yōu)秀，那么這些被支配候選服務(wù)最終肯定不會(huì)出現(xiàn)在非劣解集中的組合服務(wù)中。因?yàn)槿魧⒔M合服務(wù)中被支配候選服務(wù)替換成支配該候選服務(wù)的具體服務(wù)，則替換后的組合服務(wù)會(huì)支配替換前的組合服務(wù)。相關(guān)證明如下：

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

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

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

被支配候選服務(wù)的存在會(huì)大大延長算法的求解時(shí)間。基于此，本文提出候選服務(wù)預(yù)優(yōu)化策略。算法后續(xù)的求解都是在候選服務(wù)預(yù)優(yōu)化策略步驟后求得的非劣候選服務(wù)集中進(jìn)行服務(wù)的選擇。

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

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

非劣具體物流服務(wù)集合按如下規(guī)則產(chǎn)生：對(duì)于任一個(gè)CLSia1，若不存在CLSia2，CLSia1與CLSia2屬于同一個(gè)ALSi，且CLSia2支配CLSia1，則CLSia1屬于非劣候選服務(wù)集。

2.2.2信息素的更新策略

基礎(chǔ)蟻群算法求解服務(wù)組合問題時(shí)，采用個(gè)體中每兩個(gè)相鄰具體物流服務(wù)的相應(yīng)QoS值的差值信息L來指導(dǎo)信息素的更新，L值越小，該個(gè)體釋放的信息素越多。這種相對(duì)距離比較的方式?jīng)]有考慮個(gè)體本身的優(yōu)劣，因此尋優(yōu)效果較差。對(duì)此，Wei等[9]提出了理想最優(yōu)解的定義：一個(gè)理想解向量Fb是解空間中包含每個(gè)單目標(biāo)最優(yōu)值的點(diǎn)，F(xiàn)b可能并不是候選集中存在的具體物流服務(wù)，它只是作為算法試圖實(shí)現(xiàn)的一個(gè)目標(biāo)。顯然，越接近理想解的個(gè)體越優(yōu)，理想解可由計(jì)算得到。

計(jì)算理想解與最差解的算法過程如下。

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

輸入：全部組合物流服務(wù)的QoS值數(shù)據(jù)。

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

算法步驟：

(1)Fork=1 toM

(2)Fori=1 toN

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

(4)End For

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

(6)End For

改進(jìn)多目標(biāo)蟻群算法信息素更新的條件為：在本輪迭代中，能夠添加到Pareto解集的個(gè)體才能在相應(yīng)路徑上釋放相應(yīng)的信息素。

Pareto解集更新函數(shù)的具體實(shí)現(xiàn)步驟如下。

算法名稱：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啟發(fā)函數(shù)的確定

基礎(chǔ)蟻群算法中，啟發(fā)函數(shù)的確定是由具體物流服務(wù)的QoS值確定的。在實(shí)際應(yīng)用中，具體物流服務(wù)的QoS屬性之間存在不可公度性，難以將其值規(guī)范到統(tǒng)一的度量空間，采用這種啟發(fā)函數(shù)往往還是會(huì)出現(xiàn)側(cè)重某一個(gè)或一些QoS屬性的結(jié)果。而有些研究選擇一個(gè)統(tǒng)一的常數(shù)作為啟發(fā)函數(shù)，這樣不能達(dá)到區(qū)分優(yōu)劣的目的。本文在啟發(fā)函數(shù)中考慮具體物流服務(wù)的支配因子，啟發(fā)信息計(jì)算公式為

(8)

其中，N為抽象物流服務(wù)的個(gè)數(shù)。當(dāng)候選服務(wù)集不大時(shí)，被支配候選服務(wù)較少，非劣候選服務(wù)集中候選服務(wù)的D值相差不大，此時(shí)的啟發(fā)函數(shù)相當(dāng)于一個(gè)常數(shù)。而當(dāng)候選服務(wù)集較大時(shí)，采用這樣的啟發(fā)函數(shù)便能夠較好地區(qū)分非劣候選服務(wù)的優(yōu)劣，從而提高求解的速度。

2.2.4懶螞蟻策略

日本北海道大學(xué)進(jìn)化生物研究小組對(duì)蟻群的活動(dòng)進(jìn)行觀察，發(fā)現(xiàn)大部分螞蟻都努力地搜尋食物，而有少部分的螞蟻卻無所事事、左顧右盼，且稱其為“懶螞蟻”[17]。而在后續(xù)研究中發(fā)現(xiàn)，當(dāng)斷絕食物來源時(shí)，大部分的螞蟻表現(xiàn)得一籌莫展，而“懶螞蟻”們卻能帶領(lǐng)蟻群找到它們已偵察到的新食物源?！皯形浵仭辈幌衿渌蟛糠治浵伳菢友?guī)蹈矩，它們能觀察到蟻群的薄弱之處，同時(shí)保持對(duì)新事物的探索狀態(tài)，從而保證蟻群不斷得到新食物源。這就是所謂的“懶螞蟻效應(yīng)”。

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

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

Ln=θ·outAN

(9)

式中，θ為懶螞蟻數(shù)量調(diào)整參數(shù)，0<θ<1。

2.3TMACO算法的實(shí)現(xiàn)步驟

(1)對(duì)原始候選服務(wù)集進(jìn)行預(yù)優(yōu)化。

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

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

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

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

(6)調(diào)整懶螞蟻的數(shù)量。

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

2.4TMACO算法的時(shí)間復(fù)雜度分析

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

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

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

為了驗(yàn)證本文算法的可行性及實(shí)用性，本文所有算法均運(yùn)用Java編程語言，運(yùn)用MyEclipse軟件編寫實(shí)驗(yàn)相關(guān)代碼。本實(shí)驗(yàn)編譯運(yùn)行的計(jì)算機(jī)參數(shù)為：32位Windows 7操作系統(tǒng)、Intel Core 2 E8400 3.00GHz CPU、2.00GB內(nèi)存。

本文實(shí)驗(yàn)中，參照文獻(xiàn)[10]，每個(gè)候選物流服務(wù)抽取五個(gè)QoS指標(biāo)，即交付時(shí)間T、交付費(fèi)用C、交付可靠性R、遞送的準(zhǔn)時(shí)性P及信譽(yù)度Cr。QoS屬性的取值范圍設(shè)置如下：1 h≤T≤24 h，1≤C≤100，0.5≤R≤1，0.5≤P≤1，0.5≤Cr≤1。

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

3.1TMACO算法參數(shù)分析

為探究螞蟻種群數(shù)量以及懶螞蟻數(shù)量調(diào)整參數(shù)的設(shè)置對(duì)算法尋優(yōu)效果的影響，實(shí)驗(yàn)設(shè)置25個(gè)參數(shù)組合，分別是螞蟻種群AN的5個(gè)取值和懶螞蟻數(shù)量調(diào)整參數(shù)θ的5個(gè)取值的兩兩組合，其中參數(shù)組合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組合一致。

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

實(shí)驗(yàn)結(jié)果如圖5～圖8所示。

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

圖5　兩個(gè)參數(shù)對(duì)找到非劣解的個(gè)數(shù)的影響

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

圖6　兩個(gè)參數(shù)對(duì)算法找到非劣解的解值的影響

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

綜上，本文算法參數(shù)設(shè)置為：AN=130，θ=0.6。

圖7　兩個(gè)參數(shù)對(duì)算法收斂代數(shù)的影響

圖8　兩個(gè)參數(shù)對(duì)算法收斂時(shí)間的影響

3.2不同規(guī)模下TMACO算法的效果分析

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

圖9、圖10所示為TMACO算法求解不同規(guī)模的Web服務(wù)選擇問題的實(shí)驗(yàn)結(jié)果。

由圖9可見，隨著問題規(guī)模的增大，TMACO算法尋得問題的非劣解數(shù)量、非劣解的適應(yīng)度值均線性增大，且問題規(guī)模越大時(shí)，非劣解適應(yīng)度的增大趨勢漸緩，因?yàn)閱栴}規(guī)模的增大，解空間中解的數(shù)量增多，非劣解數(shù)量也隨之增多，適應(yīng)度值的基數(shù)增大，適應(yīng)度值也增大。TMACO算法在求解Web服務(wù)選擇問題上表現(xiàn)出了有效性及較好的穩(wěn)定性。由圖10可見，TMACO算法在求解Web服務(wù)選擇問題時(shí)的收斂代數(shù)和收斂時(shí)間隨著問題規(guī)模的增大而增大，收斂時(shí)間的延長趨勢明顯，因?yàn)?，隨著問題規(guī)模增大，解空間非劣解數(shù)量增多，Pareto解集中的解較多，導(dǎo)致算法每求得一個(gè)解，需要與之進(jìn)行比較的次數(shù)激增，因此收斂時(shí)間延長趨勢明顯。

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

圖10　不同規(guī)模下TMACO算法的收斂情況

3.3TMACO算法各策略效果對(duì)比

為驗(yàn)證本文TMACO算法的各策略對(duì)算法效果的貢獻(xiàn)，設(shè)置對(duì)比實(shí)驗(yàn)，在TMACO算法基礎(chǔ)上，分別加以下限制條件：去掉預(yù)優(yōu)化策略(A)、采用基礎(chǔ)蟻群算法的信息素更新(B)、采用基礎(chǔ)蟻群算法的啟發(fā)信息(C)、去掉懶螞蟻局部優(yōu)化策略(D)。實(shí)驗(yàn)選取抽象物流服務(wù)個(gè)數(shù)N為21，每個(gè)抽象物流服務(wù)所包含的具體物流服務(wù)個(gè)數(shù)從區(qū)間[5,10]內(nèi)隨機(jī)選擇?？疾橹笜?biāo)與3.2節(jié)相同。實(shí)驗(yàn)結(jié)果如圖11、圖12所示。

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

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

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

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

3.4TMACO算法與其他算法的對(duì)比

為了驗(yàn)證本文算法的尋優(yōu)效果，設(shè)置對(duì)比實(shí)驗(yàn)，分別為：文獻(xiàn)[19]中的基礎(chǔ)遺傳算法、文獻(xiàn)[5]中的改進(jìn)遺傳算法、文獻(xiàn)[8]中的基礎(chǔ)蟻群算法、文獻(xiàn)[9]中的改進(jìn)蟻群算法。遺傳算法的參數(shù)均參照各自文獻(xiàn)來源進(jìn)行設(shè)置。實(shí)驗(yàn)選取的問題規(guī)模、考查指標(biāo)均與3.3節(jié)相同。實(shí)驗(yàn)結(jié)果如圖13、圖14所示。

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

[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]劉磊,楊冬.求解服務(wù)等級(jí)感知服務(wù)組合問題的多目標(biāo)遺傳算法[J].吉林大學(xué)學(xué)報(bào),2015，45(1)：267-273.

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

[6]劉志中,宋成,薛霄,等.情景感知的物流Web服務(wù)動(dòng)態(tài)優(yōu)化組合研究[J].計(jì)算機(jī)工程與科學(xué),2013,35(9):51-56.

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

[7]盛國軍,溫濤,郭權(quán),等.基于改進(jìn)粒子群的Web服務(wù)組合[J].計(jì)算機(jī)學(xué)報(bào),2013, 36(5):1031-1045.

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

[8]王秀亭,馬力.基于蟻群算法的Web服務(wù)選擇[J].現(xiàn)代電子技術(shù), 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]張煥煥,薛霄,劉志中,等.基于遺傳社會(huì)認(rèn)知算法的物流Web服務(wù)優(yōu)化組合研究[J].計(jì)算機(jī)應(yīng)用研究,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最優(yōu)的QoS路由算法[J],軟件學(xué)報(bào),2005, 16(8): 1484-1489.

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

[17]羅仕奎.懶螞蟻效應(yīng)——懶于雜務(wù),才能勤于動(dòng)腦[J].北京農(nóng)業(yè),2011,36(8):13-14.

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

[18]楊亞南.蟻群算法參數(shù)優(yōu)化及其應(yīng)用[D].南京:南京理工大學(xué),2008.

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

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

(編輯蘇衛(wèi)國)

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

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71301041,71271071)

中圖分類號(hào)：TP181

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

作者簡介：方清華，女，1990年生。合肥工業(yè)大學(xué)管理學(xué)院碩士研究生。研究方向?yàn)閿?shù)據(jù)挖掘、群體智能優(yōu)化算法。倪麗萍，女，1981年生。合肥工業(yè)大學(xué)管理學(xué)院副教授。李一鳴，男，1990年生。合肥工業(yè)大學(xué)管理學(xué)院碩士研究生。