梁合蘭，杜彥華，李蘇劍

（北京科技大學(xué) 機(jī)械工程學(xué)院，北京 100083）

0 引言

隨著面向服務(wù)的體系架構(gòu)及云計(jì)算的迅速發(fā)展，Web服務(wù)（簡(jiǎn)稱(chēng)服務(wù)）已經(jīng)成為企業(yè)信息系統(tǒng)的重要組成元素。如何在海量的候選服務(wù)中快速靈活地選擇并構(gòu)建出滿(mǎn)足用戶(hù)需求的最優(yōu)服務(wù)流程，已經(jīng)成為當(dāng)前學(xué)術(shù)界和工業(yè)界關(guān)注的熱點(diǎn)問(wèn)題［1-3］。

由于企業(yè)業(yè)務(wù)策略、法律法規(guī)設(shè)定等原因，服務(wù)流程中常常存在時(shí)序約束［2-3］。如果時(shí)序約束存在錯(cuò)誤或者不一致，將會(huì)對(duì)企業(yè)造成不必要的損失甚至災(zāi)難性的后果。而測(cè)量不精確、信息不完備、描述信息模糊及信息包含噪聲等原因，往往導(dǎo)致時(shí)序約束具有不確定性［2］。因此，在服務(wù)流程構(gòu)建過(guò)程中必須考慮模糊不確定情況下的時(shí)序一致性問(wèn)題，以保證服務(wù)流程的正常執(zhí)行。

針對(duì)基于服務(wù)質(zhì)量（Quality of Service，QoS）的服務(wù)優(yōu)選或組合問(wèn)題，國(guó)內(nèi)外從服務(wù)組合［4-7］、云制造［8-12］和服務(wù)流程優(yōu)化［2-3，13-20］三個(gè)領(lǐng)域分別開(kāi)展了相關(guān)研究。但是，上述研究少有考慮不確定情況下的QoS全局優(yōu)化問(wèn)題，特別是少有考慮帶模糊不確定性的服務(wù)時(shí)序約束問(wèn)題。在求解方面，上述研究方法多用于求解確定性服務(wù)組合模型，不能直接套用到模糊問(wèn)題求解上，且求解效率有待提高。

針對(duì)上述研究［2-20］的不足，本文提出一種新的服務(wù)流程構(gòu)建與優(yōu)化方法。首先，建立了模糊情況下帶時(shí)序約束的服務(wù)流程優(yōu)化模型，該模型不但能有效表達(dá)QoS屬性及時(shí)序約束的模糊化內(nèi)涵，而且具有較好的普適性；然后，基于模糊機(jī)會(huì)約束理論及模糊滿(mǎn)意度法，將多目標(biāo)模糊約束模型進(jìn)行等價(jià)轉(zhuǎn)化，采用基于信息素的混合遺傳算法實(shí)現(xiàn)模型求解。該算法借鑒蟻群算法中的信息素思想，不僅利用親代染色體和服務(wù)自身攜帶的局部?jī)?yōu)化信息，還利用信息素記錄的全局優(yōu)化信息指導(dǎo)染色體的交叉，從而提高算法效率。

與上述已有方法［2-20］相比，本文的主要?jiǎng)?chuàng)新點(diǎn)如下：①構(gòu)建了模糊情況下帶時(shí)序約束的服務(wù)流程優(yōu)化模型，彌補(bǔ)了現(xiàn)有研究缺乏描述QoS屬性及時(shí)序約束模糊不確定性的不足；②設(shè)計(jì)了高效的求解方法。首先，基于模糊機(jī)會(huì)約束和滿(mǎn)意度法的模型等價(jià)轉(zhuǎn)化，既保留了模糊信息量，也滿(mǎn)足了啟發(fā)式算法求解模糊服務(wù)流程優(yōu)化問(wèn)題的需求；然后，通過(guò)基于信息素的混合遺傳算法來(lái)實(shí)現(xiàn)更好的執(zhí)行時(shí)間和求解精度。

1 相關(guān)工作

目前，針對(duì)服務(wù)優(yōu)選或組合問(wèn)題，國(guó)內(nèi)外學(xué)者從服務(wù)組合、云制造和服務(wù)流程優(yōu)化三個(gè)領(lǐng)域分別開(kāi)展了相關(guān)研究，下面分別進(jìn)行詳細(xì)述評(píng)。

1.1 服務(wù)組合方面

這方面與本問(wèn)題相關(guān)的具體研究?jī)?nèi)容包括基于QoS計(jì)算的服務(wù)組合［4-5］、基于語(yǔ)義的QoS 服務(wù)組合［6-7］等。具體來(lái)說(shuō)，文獻(xiàn)［4］針對(duì)基于中間件平臺(tái)的QoS 感知的確定性服務(wù)組合問(wèn)題，建立了整數(shù)規(guī)劃模型并進(jìn)行求解；文獻(xiàn)［5］設(shè)計(jì)了改進(jìn)變異算子求解確定性服務(wù)組合問(wèn)題，該模型考慮了服務(wù)組合和原子服務(wù)的時(shí)間約束；文獻(xiàn)［6-7］設(shè)計(jì)了基于語(yǔ)義的QoS全局優(yōu)化模型，并通過(guò)重心法實(shí)現(xiàn)了QoS屬性去模糊化。

上述研究［4-7］側(cè)重于封裝的服務(wù)組合和原子服務(wù)的時(shí)間要求，少有考慮具有模糊不確定性的服務(wù)時(shí)序約束。且針對(duì)不確定情況下QoS全局優(yōu)化的研究［6-7］，采用去模糊化處理，存在不能反映決策者風(fēng)險(xiǎn)偏好等業(yè)務(wù)因素的不足。

1.2 制造網(wǎng)格與云制造方面

制造網(wǎng)格基于網(wǎng)格技術(shù)將分散資源進(jìn)行封裝和集成，以透明的方式為用戶(hù)提供各類(lèi)制造服務(wù)，從而實(shí)現(xiàn)資源的集成和優(yōu)化運(yùn)行［8］。針對(duì)確定性網(wǎng)格服務(wù)組合問(wèn)題，文獻(xiàn)［8］提出了基于粒子群優(yōu)化算法的制造網(wǎng)格資源服務(wù)組合優(yōu)選方法；針對(duì)資源服務(wù)優(yōu)選問(wèn)題沒(méi)有考慮用戶(hù)感受及QoS評(píng)估的語(yǔ)義差異性等不足，文獻(xiàn)［9］提出基于了直覺(jué)模糊集的服務(wù)匹配算法。

云制造是一種利用網(wǎng)絡(luò)和云制造服務(wù)平臺(tái)，按用戶(hù)需求組織網(wǎng)上制造資源，為用戶(hù)提供各類(lèi)按需制造服務(wù)的一種網(wǎng)絡(luò)化制造新模式［10］。針對(duì)制造云服務(wù)組合問(wèn)題，文獻(xiàn)［11］建立了基于QoS的多任務(wù)云服務(wù)組合問(wèn)題模型，并提出基于矩陣實(shí)數(shù)編碼的改進(jìn)遺傳算法求解；文獻(xiàn)［12］在語(yǔ)義服務(wù)和模糊集理論的基礎(chǔ)上，提出一種語(yǔ)義服務(wù)模糊匹配方法。

上述研究［8-12］多針對(duì)確定性服務(wù)優(yōu)選問(wèn)題的建模及求解。對(duì)于不確定情況下的服務(wù)優(yōu)選問(wèn)題［9，12］，采用模糊匹配方法只能滿(mǎn)足單個(gè)服務(wù)的最優(yōu)選擇，不能保證服務(wù)組合的全局最優(yōu)。目前缺乏不確定情況下QoS全局優(yōu)化的建模及求解方法。

1.3 服務(wù)流程

相關(guān)研究工作主要集中于服務(wù)QoS 的不確定性表征及基于QoS的服務(wù)流程優(yōu)化兩個(gè)方面。

（1）QoS的不確定性表征 主要有基于概率分布理論［2-3］、基于區(qū)間數(shù)理論［13-14］、基于模糊數(shù) 理論［15-16］三類(lèi)方法。其中，基于概率分布的方法將QoS屬性定義成服從一定分布的隨機(jī)量，但由于統(tǒng)計(jì)量不足或隨機(jī)因素規(guī)律性不強(qiáng)，將導(dǎo)致分布規(guī)律產(chǎn)生偏差或無(wú)法得到分布函數(shù)；基于區(qū)間數(shù)的方法通過(guò)區(qū)間數(shù)描述屬性值的變化，但屬性值在區(qū)間上遵循均勻分布，不能反映服務(wù)的偏好性；基于模糊數(shù)的方法通過(guò)模糊數(shù)描述QoS屬性，較好地反映了服務(wù)的不確定性及偏好性。

（2）基于QoS的服務(wù)流程優(yōu)化 主要可分為兩類(lèi)方法：①精確求解方法，如整數(shù)規(guī)劃、分支定界［13，17］；②啟發(fā)式優(yōu)化算法［18-20］，如蟻群算法、遺傳算法。精確算法在求解大規(guī)模服務(wù)優(yōu)化問(wèn)題上存在計(jì)算時(shí)間較長(zhǎng)的弊端；啟發(fā)式優(yōu)化算法在執(zhí)行時(shí)間上具有更好的優(yōu)勢(shì)，但此類(lèi)算法多用于求解確定性服務(wù)流程優(yōu)化模型，不能直接套用到模糊問(wèn)題求解上，而且其進(jìn)化過(guò)程多單一地依靠局部或全局優(yōu)化信息，求解效率有待提高。此外，目前在建模方面也缺乏帶模糊時(shí)序約束的服務(wù)流程優(yōu)化模型。

2 問(wèn)題描述及形式化模型

為構(gòu)建優(yōu)化的服務(wù)流程，首先需要根據(jù)業(yè)務(wù)需求進(jìn)行抽象服務(wù)流程定義。本文首先介紹基于Petri網(wǎng)的抽象服務(wù)流程模型，并在服務(wù)流程不確定因素分析的基礎(chǔ)上，建立本文問(wèn)題的形式化模型。

2.1 服務(wù)流程的抽象模型

Petri網(wǎng)作為一種具有直觀圖形表示的形式化模型，在模型的邏輯、時(shí)間和性能的分析方面得到了廣泛應(yīng)用，因此本文使用Petri網(wǎng)定義抽象服務(wù)流程。

定義1 Petri網(wǎng)PN［21］。PN=（P，T，F(xiàn)），其中：P表示庫(kù)所集合；T表示任務(wù)集合；F?（P×T）∪（T×P）表示連庫(kù)所和變遷的有向弧集合。

定義2 工作流網(wǎng)WF-Net［21］。一個(gè)Petri網(wǎng)只有當(dāng)滿(mǎn)足以下條件時(shí)可以稱(chēng)為工作流網(wǎng)：①包含2個(gè)特殊的庫(kù)所ε和θ，其中：ε是初始庫(kù)所，即·ε=?；θ是結(jié)束庫(kù)所，即θ·=?。②如果添加一個(gè)變遷來(lái)連接庫(kù)所θ和ε，即·t=｛θ｝，t·=｛ε｝，則Petri網(wǎng)被連接起來(lái)。

2.2 服務(wù)流程的不確定因素分析

服務(wù)流程的不確定因素主要包括以下兩方面：①由于測(cè)量不精確、信息不完備等原因，部分QoS屬性度量具有模糊不確定性；②時(shí)間屬性及客戶(hù)對(duì)服務(wù)時(shí)序要求的模糊性，將導(dǎo)致模糊時(shí)序約束的產(chǎn)生。

（1）模糊QoS屬性

流程由服務(wù)組合而成，為構(gòu)建QoS優(yōu)化的服務(wù)流程，必須定義候選服務(wù)的質(zhì)量屬性。根據(jù)國(guó)際標(biāo)準(zhǔn)ISO 8402和ITU E.800對(duì)QoS的定義，本文考慮其中時(shí)間、成本和可靠性（為表述一致，后文中均按此順序描述）3個(gè)最具代表性的QoS屬性。

因?yàn)槿我饽：龜?shù)都可以利用一個(gè)梯形模糊數(shù)逼近［22］，所以本文采用梯形模糊數(shù)反映QoS 屬性的模糊性，如圖1所示。

圖1顯示了服務(wù)的第k個(gè)質(zhì)量屬性xk2，xk3，xk4］，k=1，2，3。式中：xk1和xk4分別為梯形模糊數(shù)的上界和下界，［xk2，xk3］為隸屬度為1的點(diǎn)集。例如，某服務(wù)的時(shí)間屬性～A1=［4，5，7，9］表示該服務(wù)最理想的處理時(shí)間為［5，7］個(gè)單位時(shí)間；隨著所要求的處理時(shí)間的減少或增加，服務(wù)在相應(yīng)時(shí)間內(nèi)完成的可能性減少，當(dāng)服務(wù)時(shí)間在［0，4）或（9，+∞）時(shí)，其完成可能性為0。

（2）模糊時(shí)序約束

作為流程中常見(jiàn)的時(shí)間信息，時(shí)序約束通常表示活動(dòng)之間的時(shí)序關(guān)系、某個(gè)活動(dòng)執(zhí)行期限以及活動(dòng)與某個(gè)日期集綁定等。實(shí)際服務(wù)流程中往往存在時(shí)序約束，但是傳統(tǒng)的確定性時(shí)間窗不能反映時(shí)序約束的不確定性和偏好性，因此本文用梯形模糊時(shí)間窗代替?zhèn)鹘y(tǒng)時(shí)間窗的定義。梯形模糊時(shí)間窗表示為關(guān)于時(shí)間π的梯形模糊數(shù)，時(shí)間不確定性或偏好性由該模糊數(shù)的隸屬度函數(shù)μ（～π）表示。

為了表達(dá)一致，采用相對(duì)時(shí)序約束形式［2］表達(dá)所有約束。例如，抽象服務(wù)流程中存在相對(duì)時(shí)序約束DR（i，j）≤［0，0，7，9］，表示客戶(hù)最希望任務(wù)j能在任務(wù)i開(kāi)始后7個(gè)時(shí)間單位內(nèi)完成，其滿(mǎn)意度為1；否則，隨著處理時(shí)間的增加，顧客滿(mǎn)意度減少，應(yīng)盡量避免；當(dāng)任務(wù)j的結(jié)束時(shí)間離任務(wù)i開(kāi)始時(shí)間大于9個(gè)時(shí)間單位時(shí)，客戶(hù)滿(mǎn)意度為0，即顧客不能接受。

此外，時(shí)間屬性的模糊性將導(dǎo)致服務(wù)流程的處理時(shí)間DR（i，j）存在模糊性。根據(jù)其取值區(qū)間，模糊時(shí)序約束滿(mǎn)足程度可分為完全滿(mǎn)足、部分滿(mǎn)足和完全違反三大類(lèi)（如圖2），但該分類(lèi)原則僅簡(jiǎn)單判定了模糊約束是否滿(mǎn)足一致性，而在實(shí)際業(yè)務(wù)環(huán)境中，決策者更關(guān)注模糊時(shí)序約束的滿(mǎn)足程度是否達(dá)到特定服務(wù)水平，且針對(duì)不同的服務(wù)流程，可能存在不同的服務(wù)水平要求。

為了量化判定服務(wù)流程是否滿(mǎn)足模糊時(shí)序約束，本文定義模糊時(shí)序約束滿(mǎn)足性如下：

定義3 模糊時(shí)序約束滿(mǎn)足性［23］。設(shè)抽象服務(wù)流程中存在模糊時(shí)序約束Pos｛DR（i，j）≤～B｝≥α，且～B=［y1，y2，y3，y4］，α∈［0，1］及DR（i，j）的模糊處理時(shí)間為=［x1，x2，x3，x4］。定義時(shí)序約束的滿(mǎn)足程度為Pos｛DR（i，j）≤～B｝=Area｛［E，F(xiàn)］∩μ其 中：［E，F(xiàn)］表示邊及圍成的區(qū)域表示的隸屬度函數(shù)，Area｛·｝表示面積計(jì)算。若Pos｛DR（i，j）≤｝≥α成立，則模糊時(shí)序約束滿(mǎn)足。

以時(shí)序約束Pos｛DR（i，j）≤［0，0，7，9］｝≥0.9為例，現(xiàn)已知任務(wù)i開(kāi)始到任務(wù)j結(jié)束的模糊時(shí)間窗DR（i，j）=［4，5，7-10］。根據(jù)定義3，可計(jì)算出2=4，即4=0.875。因?yàn)?.875＜0.9，所以可判斷時(shí)序約束Pos｛DR（i，j）≤［0，0，7，9］｝≥0.9不滿(mǎn)足。

根據(jù)模糊時(shí)序約束滿(mǎn)足性定義，變量α反映了模糊時(shí)序約束滿(mǎn)足程度的最低要求。因此，流程決策者應(yīng)根據(jù)模糊時(shí)序約束的重要程度對(duì)α進(jìn)行設(shè)置。以網(wǎng)上購(gòu)物流程為例，該流程中存在多個(gè)時(shí)序約束，其中部分約束是由于法律法規(guī)、業(yè)務(wù)安全性等原因設(shè)置的，如“客戶(hù)必須在60s內(nèi)完成支付平臺(tái)驗(yàn)證碼輸入”，針對(duì)這類(lèi)嚴(yán)格不能違反的約束，可將其α設(shè)置為1；部分約束是為提高客戶(hù)服務(wù)水平、便于業(yè)務(wù)操作等原因設(shè)定的，如“顧客網(wǎng)上下單到代理商發(fā)貨的時(shí)間控制在24h內(nèi)”，該類(lèi)約束非嚴(yán)格不能違反，但也需保證達(dá)到預(yù)期的服務(wù)水平下限要求。因此，企業(yè)可綜合考慮企業(yè)戰(zhàn)略目標(biāo)、客戶(hù)等級(jí)、產(chǎn)品特點(diǎn)等因素設(shè)置相應(yīng)的α值。

2.3 本文問(wèn)題的形式化模型

圖3描述了一個(gè)模糊情況下帶時(shí)序約束的抽象服務(wù)流程模型。該模型由兩條并行抽象服務(wù)流程WF-Net1和WF-Net2組成。模糊時(shí)序約束1～3分別用于描述WF-Net1內(nèi)及WF-Net1和WF-Net2任務(wù)間的時(shí)序要求。針對(duì)流程中的每一個(gè)任務(wù)，均存在一個(gè)可實(shí)現(xiàn)該任務(wù)功能的候選服務(wù)集合。

為了執(zhí)行該抽象服務(wù)流程，定義服務(wù)流程的執(zhí)行計(jì)劃如下：

定義4 執(zhí)行計(jì)劃EP［20］。設(shè)存在抽象服務(wù)流程WF-Net=（P，T，F(xiàn)），其任務(wù)集合T=｛t1，t2，…，tn｝，任一任務(wù)ti均存在一個(gè)候選服務(wù)集合Si=｛si1，si2，…，simi｝，則抽象服務(wù)流程的執(zhí)行計(jì)劃可定義為一個(gè)任務(wù)與候選服務(wù)的匹配序列EP=｛〈t1，s1i〉，〈t2，s2j〉，…，〈tn，snk〉｝。其中，序列中包含了抽象服務(wù)流程的所有任務(wù)，且任一任務(wù)有且僅有一個(gè)候選服務(wù)與之匹配。

由于各候選服務(wù)集合中往往存在大量質(zhì)量不同的服務(wù)，這些服務(wù)將組合出大量具有不同QoS特征的執(zhí)行計(jì)劃。因此，必須在海量的候選服務(wù)中快速靈活地編制出最佳的執(zhí)行計(jì)劃，以保證在滿(mǎn)足時(shí)序約束條件下的服務(wù)流程QoS最大化。具體就本文所考慮的三類(lèi)QoS屬性而言，即希望所編制的執(zhí)行計(jì)劃在時(shí)間、成本和可靠性這三方面達(dá)到最佳配置。

綜上分析，本文問(wèn)題的形式化模型可描述如下：

目標(biāo)函數(shù)（1）和目標(biāo)函數(shù)（2）表示所選擇的服務(wù)流程應(yīng)使完成服務(wù)流程的時(shí)間和成本盡可能小，且可靠性盡可能大。約束（3）表示任一任務(wù)的開(kāi)始時(shí)間應(yīng)不小于流程中緊前任務(wù)的完成時(shí)間；約束（4）表示服務(wù)流程中各時(shí)序約束的滿(mǎn)足程度應(yīng)不小于該約束的最小滿(mǎn)足度。需要強(qiáng)調(diào)的是，為了簡(jiǎn)化，若一個(gè)事務(wù)由多條并行抽象服務(wù)流程組成，則假設(shè)多服務(wù)流程同時(shí)開(kāi)始。如果已知某服務(wù)流程開(kāi)始時(shí)間較晚，則在其他流程的起始點(diǎn)增加一個(gè)虛任務(wù)，且其處理時(shí)間為相應(yīng)的開(kāi)始時(shí)間差，從而保持各服務(wù)流程的開(kāi)始時(shí)間一致。

從模型定義可以看出，本文模型具有以下優(yōu)點(diǎn)：

（1）通過(guò)多模糊目標(biāo)的定義，有效描述了模糊情況下基于QoS最優(yōu)的服務(wù)流程選擇標(biāo)準(zhǔn)。與基于QoS屬性線性加權(quán)的單目標(biāo)模型［19-20］相比，多模糊目標(biāo)能使服務(wù)流程中各QoS屬性均趨向較優(yōu)狀態(tài)，避免了整體QoS加權(quán)值最優(yōu)而部分QoS 屬性取值過(guò)低的缺陷；此外，由于函數(shù)中不需要設(shè)置各目標(biāo)的權(quán)重值，避免了結(jié)果對(duì)權(quán)重向量敏感的不足。

（2）通過(guò)模糊時(shí)序約束滿(mǎn)足性的量化判定，有效描述了服務(wù)流程中的模糊時(shí)序約束。決策者可根據(jù)模糊時(shí)序約束的重要程度，設(shè)定不同的滿(mǎn)足度閾值α，從而實(shí)現(xiàn)服務(wù)流程中時(shí)序約束的柔性配置。

（3）該模型能有效反映不確定環(huán)境下QoS屬性的模糊不確定性，且由于確定性或區(qū)間型數(shù)據(jù)均可處理成梯形模糊數(shù)，針對(duì)存在確定性或區(qū)間型數(shù)據(jù)的QoS屬性或時(shí)序約束，本文模型仍可適用，即該模型具有較好的普適性。

3 模型求解

針對(duì)上述問(wèn)題模型，本文提出模糊情況下帶時(shí)序約束的服務(wù)流程優(yōu)化方法，如圖4所示。

（1）求解階段1 多目標(biāo)模糊約束模型轉(zhuǎn)化?；谀：龣C(jī)會(huì)約束規(guī)劃和模糊滿(mǎn)意度法，將模糊規(guī)劃問(wèn)題轉(zhuǎn)化為以QoS滿(mǎn)意度最大化為目標(biāo)的清晰等價(jià)模型。

（2）求解階段2 針對(duì)清晰等價(jià)模型的求解，提出改進(jìn)的混合遺傳算法。該算法借鑒蟻群算法中的信息素思想，在遺傳交叉中綜合考慮了局部?jī)?yōu)化信息和信息素記錄的全局優(yōu)化信息，從而加快了求解效率。

3.1 多目標(biāo)模糊約束模型的轉(zhuǎn)化

文獻(xiàn)［6-7］基于重心法實(shí)現(xiàn)QoS 屬性去模糊化，但該方法將在較大程度上損失模糊屬性的語(yǔ)義，不能反映服務(wù)流程執(zhí)行的可靠性、決策者的風(fēng)險(xiǎn)偏好等業(yè)務(wù)因素。為保留模糊信息量，本文首先基于模糊機(jī)會(huì)約束及其清晰等價(jià)轉(zhuǎn)化理論，將3.3節(jié)的模糊約束模型轉(zhuǎn)化成多目標(biāo)機(jī)會(huì)約束的清晰等價(jià)模型?？紤]到模型中的不同優(yōu)化目標(biāo)難以直接比較，進(jìn)一步基于模糊滿(mǎn)意度法，將多目標(biāo)模糊約束模型轉(zhuǎn)化成以QoS 滿(mǎn)意度最大化為目標(biāo)的清晰等價(jià)模型。

（1）模糊問(wèn)題的清晰等價(jià)轉(zhuǎn)化

首先，按照模糊隨機(jī)規(guī)劃理論，將帶模糊數(shù)的目標(biāo)函數(shù)（1）和目標(biāo)函數(shù)（2）轉(zhuǎn)化成目標(biāo)機(jī)會(huì)約束函數(shù)。根據(jù)屬性的不同性質(zhì)，“時(shí)間”、“成本”應(yīng)為成本型屬性，其轉(zhuǎn)化公式為式（5）和式（6）；而“可靠性”為效益型屬性，轉(zhuǎn)化公式為式（7）和式（8）。

從模糊約束規(guī)劃的建模思想可知，γ反映了目標(biāo)函數(shù)在不確定環(huán)境下的實(shí)現(xiàn)機(jī)會(huì)。根據(jù)其定義，γ越小、約束條件成立的可能性越小，即所選擇的服務(wù)流程不滿(mǎn)足滿(mǎn)意值的風(fēng)險(xiǎn)越大。因此，決策者應(yīng)綜合考慮服務(wù)流程的特點(diǎn)、自身風(fēng)險(xiǎn)偏好等因素進(jìn)行γ的設(shè)置和調(diào)整。例如，對(duì)于金融、高價(jià)值制造等服務(wù)流程來(lái)說(shuō)，γ的取值更側(cè)重于不確定情況下服務(wù)流程QoS的魯棒性。因此，針對(duì)該類(lèi)流程應(yīng)設(shè)置γ＞0.5，從而規(guī)避不確定情況下QoS的不穩(wěn)定性。與之相對(duì)的普通制造、服務(wù)類(lèi)等服務(wù)流程具有市場(chǎng)競(jìng)爭(zhēng)激烈、服務(wù)流程靈活等特點(diǎn)，對(duì)服務(wù)流程的QoS優(yōu)劣更為敏感。因此，適當(dāng)調(diào)低γ的水平，如設(shè)置γ≤0.5，將更有利于選擇出不確定情況下存在高QoS可能性的服務(wù)流程。

針對(duì)模糊屬性值計(jì)算，根據(jù)服務(wù)聚合計(jì)算公式［20］和模糊數(shù)運(yùn)算原則，可得計(jì)算公式如表1所示。

表1 模糊屬性的聚合計(jì)算公式

根據(jù)表1并結(jié)合抽象服務(wù)流程模型實(shí)例，可計(jì)算出該服務(wù)流程實(shí)例的第i個(gè)模糊質(zhì)量屬性值（X）=［Qi1（X），Qi2（X），Qi3（X），Qi4（X）］，其中i=1，2，3。由于上述計(jì)算僅涉及梯形模糊數(shù)的加法及乘以常量運(yùn)算，根據(jù)模糊數(shù)運(yùn)算法則，所得的仍為梯形模糊數(shù)。因此，機(jī)會(huì)約束式（6）和式（8）可執(zhí)行清晰等價(jià)轉(zhuǎn)化［24］。

（2）基于滿(mǎn)意度的多目標(biāo)轉(zhuǎn)化

經(jīng)上述處理后，2.3 節(jié)的模糊約束模型即轉(zhuǎn)化成多目標(biāo)機(jī)會(huì)約束的清晰等價(jià)模型。在多目標(biāo)處理上，考慮到各QoS的屬性量綱不一，在進(jìn)行QoS綜合評(píng)價(jià)時(shí)，不同結(jié)果難以直接進(jìn)行比較。因此，本文基于最大模糊滿(mǎn)意度法［25］，將多目標(biāo)模型轉(zhuǎn)化為QoS最優(yōu)且不確定性程度最小的QoS滿(mǎn)意度最大化模型。

綜上，可得轉(zhuǎn)化后的模型如下：

式中：目標(biāo)函數(shù)定義為所有滿(mǎn)意度中最小的一個(gè)；λi為第i個(gè)屬性的滿(mǎn)意度；Qmaxi和Qmini分別表示服務(wù)流程中第i個(gè)屬性的理想解上界和理想解下界。式（12）和式（13）分別為式（6）和式（8）對(duì)應(yīng)的清晰等價(jià)形式。

當(dāng)然，服務(wù)流程中可能存在某些屬性（如可用性），該類(lèi)屬性的聚合計(jì)算涉及模糊數(shù)的乘法運(yùn)算。根據(jù)模糊數(shù)運(yùn)算法則，梯形模糊數(shù)乘積后將不再是梯形模糊數(shù)，因此無(wú)法轉(zhuǎn)化為清晰等價(jià)形式。針對(duì)該類(lèi)屬性，可基于模糊模擬技術(shù)產(chǎn)生輸入及輸出數(shù)據(jù)，利用神經(jīng)元網(wǎng)絡(luò)對(duì)產(chǎn)生數(shù)據(jù)進(jìn)行訓(xùn)練，從而逼近不確定函數(shù)［25］。

3.2 基于信息素的混合遺傳算法

通過(guò)3.1節(jié)轉(zhuǎn)化后的模型可歸結(jié)為組合優(yōu)化問(wèn)題。針對(duì)組合優(yōu)化問(wèn)題的求解，遺傳算法、蟻群算法等啟發(fā)式優(yōu)化算法具有較好的執(zhí)行時(shí)間優(yōu)勢(shì)。其中，遺傳算法借鑒自然界中生物遺傳和進(jìn)化的規(guī)律，主要通過(guò)選擇、交叉和變異算子實(shí)現(xiàn)種群的并行全局搜索，并通過(guò)評(píng)價(jià)函數(shù)執(zhí)行種群的優(yōu)勝劣汰，該算法具有大規(guī)模搜索、隨機(jī)性、魯棒性、并行性及問(wèn)題域無(wú)關(guān)等特性［26］。因此，與其他智能優(yōu)化算法相比，遺傳算法更適合于處理維數(shù)很高、規(guī)模較大的無(wú)數(shù)值概念類(lèi)［27］優(yōu)化問(wèn)題。

標(biāo)準(zhǔn)遺傳算法主要依靠隨機(jī)搜索策略，容易陷入未成熟收斂和搜索效率較低［5］。雖然文獻(xiàn)［19-20］對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行了改進(jìn)，但在構(gòu)造子個(gè)體時(shí)仍只利用了父代攜帶的局部信息。針對(duì)文獻(xiàn)［19-20］的缺陷，本文設(shè)計(jì)了基于信息素的混合遺傳求解算法。該算法參考文獻(xiàn)［28］的算法思想，然而文獻(xiàn)［28］針對(duì)的是旅行商問(wèn)題（Traveling Salesman Problem，TSP），與本文問(wèn)題有較大區(qū)別，因此本算法結(jié)合問(wèn)題的特點(diǎn)做了以下調(diào)整：①設(shè)計(jì)了多抽象服務(wù)流程優(yōu)化問(wèn)題的編碼規(guī)則，并提出帶獎(jiǎng)勵(lì)—懲罰的適應(yīng)度函數(shù)；②設(shè)計(jì)了適用于本問(wèn)題的交叉算子，并重新定義了能見(jiàn)度參數(shù)，用于度量不確定情況下服務(wù)質(zhì)量的優(yōu)劣程度；③與文獻(xiàn)［28］的排序選擇、變異算法不同，本文采用基于錦標(biāo)賽選擇方法與最優(yōu)保留相結(jié)合的選擇策略，降低了算法的時(shí)間復(fù)雜度，通過(guò)非均衡的變異概率函數(shù)，實(shí)現(xiàn)了變異操作的動(dòng)態(tài)調(diào)整。

下面描述具體算法設(shè)計(jì)。

3.2.1 染色體及適應(yīng)度函數(shù)定義

本文的染色體定義為｛x1，x2，…，xn｝，xi∈［1，mi］。其中：n表示服務(wù)流程中任務(wù)的個(gè)數(shù)，mi表示第i個(gè)任務(wù)的候選服務(wù)數(shù)量。若一個(gè)事務(wù)由多條并行抽象服務(wù)流程組成，則對(duì)抽象服務(wù)流程進(jìn)行排序，并依次對(duì)流程中的任務(wù)進(jìn)行編碼。

以4.1 節(jié)的并行抽象服務(wù)流程WF-Net1和WF-Net2為例。首先將流程中的任務(wù)排序?yàn)椋踭11，t12，t14，t15，t16，t18，t19，t21，t22，t23，t24，t25，t26］；然后依次從各候選服務(wù)集合中選擇一個(gè)服務(wù)作為該基因位的值，即可生成一個(gè)染色體編碼方案。例如，染色體｛3，2，1，2，3，1，2，1，2，1，1，3，2｝表示任務(wù)t11選擇第3個(gè)候選服務(wù)，t12選擇第2個(gè)候選服務(wù)。

為了使目標(biāo)函數(shù)值越高的可行個(gè)體具有較高適應(yīng)度，從而有更大的機(jī)會(huì)遺傳給下一代，本文設(shè)計(jì)了帶獎(jiǎng)勵(lì)—懲罰的適應(yīng)度函數(shù)

式中：Fitness（X）為X的適應(yīng)度，取值范圍為［0，3］；F（X）為按式（9）計(jì)算的目標(biāo)函數(shù)值，取值范圍為［0，1］；V（X）為X的時(shí)序約束違反個(gè)數(shù)；Vnum為時(shí)序約束數(shù)量；P為X的獎(jiǎng)勵(lì)值，當(dāng)X為可行染色體時(shí)P=1，否則P=0。

3.2.2 基于信息素的交叉算子

在交叉時(shí)，針對(duì)每個(gè)任務(wù)，首先判斷親代染色體是否均選擇了同一個(gè)候選服務(wù)，是則將該候選服務(wù)保留到子代中；否則，算子按照式（16），以pp（0≤pp≤1）的概率選擇最合適的服務(wù)（QoS較優(yōu)且信息素值較高），而以1-pp的概率按照式（17）進(jìn)行輪盤(pán)選擇。

式中：Nk（g）表示第g代第k個(gè)任務(wù)選中的服務(wù)；Sk表示第k個(gè)任務(wù)的候選服務(wù)集合；τj（g）表示第g代第j個(gè)服務(wù)的信息素值；ηj為服務(wù)j的能見(jiàn)度，按式（18）計(jì)算；β為調(diào)節(jié)信息素和能見(jiàn)度之間相對(duì)重要性的參數(shù)；r為隨機(jī)數(shù)。變量R定義如下：

能見(jiàn)度ηj用于反映服務(wù)j的QoS 優(yōu)劣程度。為使整體質(zhì)量較優(yōu)的服務(wù)被選中的概率較高，本文定義ηj如下：

式中：qmaxki和qminki分別為第k個(gè)任務(wù)第i個(gè)屬性的模糊上限和模糊下限；表示候選服務(wù)j第i個(gè)屬性的梯形模糊數(shù)。

從上述過(guò)程可以看出，本文設(shè)計(jì)的交叉算子在構(gòu)造子個(gè)體時(shí)，除了繼承親代染色體的服務(wù)選擇信息外，還依靠基于能見(jiàn)度的局部信息及基于信息素的全局優(yōu)化信息指導(dǎo)服務(wù)的選擇，并通過(guò)一定概率的隨機(jī)選擇保持了種群的多樣性。此外，由于本文設(shè)計(jì)的交叉算子是按照染色體中的基因位順序依次對(duì)各任務(wù)重新編碼，該方法將不會(huì)改變父代染色體中的任務(wù)排列順序，且均適用于單流程或多服務(wù)流程的構(gòu)建優(yōu)化問(wèn)題。

3.2.3 信息素更新策略

在遺傳算法每代運(yùn)算后，各服務(wù)的信息素值將按照最大—最小螞蟻系統(tǒng)［29］中的機(jī)制進(jìn)行更新，具體公式如下：

式中：ρ表示信息素的持久度；Fitness（GS）為當(dāng)前全局最優(yōu)解GS的適應(yīng)度。此外，在每次更新中，令τmax=Fitness（GS）／1-ρ，τmin=τmax／2n。若τi（g+1）＞τmax，則τi（g+1）=τmax；若τi（g+1）＜τmin，則τi（g+1）=τmin。從而保證信息素值被限制在區(qū)間［τmin，τmax］之內(nèi)。

由式（19）和式（20）可知，非全局最優(yōu)解中服務(wù)的信息素將因信息素的“蒸發(fā)”而減少；而包含在全局最優(yōu)解中的服務(wù)信息素將得到加強(qiáng)，且全局最優(yōu)解的適應(yīng)度越高，該解對(duì)應(yīng)的各候選服務(wù)的信息素強(qiáng)度增加量越大，從而有利于提高相應(yīng)服務(wù)在交叉操作中被選中的概率。

3.2.4 求解過(guò)程

綜上可得基于信息素的混合遺傳算法的求解過(guò)程如下：

算法1 基于混合遺傳的服務(wù)流程優(yōu)化算法。

輸入：抽象服務(wù)流程WF-Net=（P，T，F(xiàn)）；模糊時(shí)序約束集合ψ=｛…，Pos｛DR（i，j）≤～dk｝≥αk，…｝；候選服務(wù)集合CS=｛s11，…，snmn｝；算法設(shè)置參數(shù)，包括：種群規(guī)模pop＿size，迭代次數(shù)G，基于最大信息素與能見(jiàn)度選擇的概率pp，信息素與能見(jiàn)度的相對(duì)比重β，信息素持久度系數(shù)ρ，交叉概率pc，變異概率函數(shù)pm（g）和錦標(biāo)賽候選規(guī)模tour＿size。

輸出：執(zhí)行計(jì)劃X=｛x1，x2，…，xn｝。

步驟1 按抽象服務(wù)流程排序，對(duì)各流程中的任務(wù)依次從其候選服務(wù)集合中隨機(jī)選取一個(gè)服務(wù)作為染色體基因。根據(jù)模糊屬性的聚合計(jì)算公式和抽象服務(wù)流程實(shí)例，計(jì)算染色體的滿(mǎn)意度F（X），并結(jié)合時(shí)序約束判定結(jié)果V（X），獲得染色體的適應(yīng)度。重復(fù)本步驟pop＿size次，即生成初始的染色體群體pop，種群大小為pop＿size。

步驟2 按pop中的染色體順序依次生成隨機(jī)數(shù)r：若r不大于交叉概率pc，則將第i個(gè)染色體標(biāo)識(shí)為候選親代染色體。重復(fù)本步驟pop＿size次，從而確定參與交叉的候選親代染色體集合R。

步驟3 在集合R中按輪盤(pán)賭策略選擇兩個(gè)染色體作為親代染色體，初始化k=1，并按下列操作生成新個(gè)體：

（1）當(dāng)雙親染色體第k個(gè)基因位的值相同，則保留親代的值；否則，按照式（16）確定第k個(gè)基因位的值。

（2）k=k+1，重復(fù)步驟（1），直到n個(gè)任務(wù)均匹配上服務(wù)。

（3）生成隨機(jī)數(shù)r，若r不大于第g代變異概率pm（g），則對(duì)新個(gè)體執(zhí)行單點(diǎn)變異操作。

步驟4 將新個(gè)體放入臨時(shí)種群tempop，若tempop中的個(gè)體數(shù)量不小于pop＿size／2，則轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟3。

步驟5 對(duì)tempop與pop中的染色體，執(zhí)行基于錦標(biāo)賽選擇方法與最優(yōu)保留相結(jié)合的選擇機(jī)制。即每次隨機(jī)從tour＿size個(gè)染色體中選擇最佳方案，重復(fù)本步驟pop＿size次，從而選出pop＿size個(gè)染色體賦給pop。進(jìn)一步，將適應(yīng)度最高的個(gè)體替換pop中適應(yīng)度最低的個(gè)體，從而生成下一代初始種群。

步驟6 判斷是否已達(dá)到迭代次數(shù)G，是則輸出最終結(jié)果；否則執(zhí)行信息素更新策略，轉(zhuǎn)步驟2。

本文算法綜合了遺傳算法和蟻群算法的特點(diǎn)，并通過(guò)以下設(shè)計(jì)達(dá)到提高算法精度和收斂速度的目的：①在交叉操作方面，既考慮了優(yōu)良親代染色體的局部信息，也考慮了信息素所攜帶的全局優(yōu)化信息（如步驟3（1）～步驟3（2）），從而避免了文獻(xiàn)［19-20］中單純依靠局部信息進(jìn)行交叉的不足；②在選擇操作方面，與文獻(xiàn)［19-20，28］的排序選擇策略相比，采用基于錦標(biāo)賽選擇方法與最優(yōu)保留相結(jié)合的選擇策略（如步驟5），有利于降低選擇操作的時(shí)間復(fù)雜度；③在變異操作方面，通過(guò)設(shè)計(jì)變異概率函數(shù)（如步驟3（3）），使變異概率隨著迭代次數(shù)的增加而逐步降低，既有利于保持種群的多樣性，也便于算法快速收斂。

4 算例分析

為驗(yàn)證本文算法的可行性，通過(guò)一個(gè)手機(jī)生產(chǎn)實(shí)例［20］來(lái)介紹和應(yīng)用本文方法。

4.1 實(shí)例說(shuō)明

為了簡(jiǎn)化模型，假設(shè)一個(gè)新手機(jī)生產(chǎn)在現(xiàn)實(shí)的生產(chǎn)企業(yè)中包含2個(gè)流程：電子主板生產(chǎn)流程（WFNet1）和外圍部件生產(chǎn)流程（WF-Net2）。這2個(gè)流程的并行情況如圖5所示。

每個(gè)任務(wù)均執(zhí)行服務(wù)外包策略，相關(guān)候選服務(wù)信息如表1所示。其中候選服務(wù)的QoS屬性由［時(shí)間，成本，可靠性］組成，且上述屬性均為梯形模糊數(shù)。如對(duì)任務(wù)t11來(lái)說(shuō)，有三個(gè)候選服務(wù)s111～s113可為其提供服務(wù)。其中服務(wù)s111完成該任務(wù)的模糊時(shí)間為［4，6，8，10］、成本為［2，3，4，6］、可靠性為［2，4，5，6］。

為了縮短產(chǎn)品投放市場(chǎng)的時(shí)間、獲得更大的市場(chǎng)占有率，設(shè)置相關(guān)的時(shí)序約束如下：

（1）Pos｛DR（t23，t25）≤［0，0，17，21］｝≥0.9，表示決策者希望“在外圍部件的技術(shù)文檔撰寫(xiě)開(kāi)始之后最好能在17個(gè)工作日內(nèi)完成外圍部件的生產(chǎn)，最晚不能超過(guò)21個(gè)工作日”，且所選擇的服務(wù)流程滿(mǎn)足該模糊時(shí)序約束的程度應(yīng)不小于90%。

（2）Pos｛DR（t23，t19）≤［0，0，7，12］｝≥1，表示決策者要求“在外圍部件的技術(shù)文檔撰寫(xiě)開(kāi)始之后最好能在7個(gè)工作日內(nèi)完成主板的生產(chǎn)，最晚不能超過(guò)12個(gè)工作日”，且所選擇的服務(wù)流程滿(mǎn)足該模糊時(shí)序約束的程度應(yīng)為1。

4.2 模型建立及轉(zhuǎn)化

根據(jù)2.3節(jié)的形式化模型定義，結(jié)合本案例的時(shí)序約束，可建立問(wèn)題模型如下：

表2 各任務(wù)對(duì)應(yīng)的候選服務(wù)

按照多目標(biāo)模糊約束模型的轉(zhuǎn)化式（9）～式（14），代入本實(shí)例的參數(shù)并化簡(jiǎn)，可建立清晰等價(jià)模型如下：

進(jìn)一步，在式（26）～式（29）的模型中，還需對(duì)置信水平γ進(jìn)行設(shè)置。因?yàn)槭謾C(jī)加工屬于制造類(lèi)服務(wù)流程，且市場(chǎng)競(jìng)爭(zhēng)激烈，所以該流程對(duì)QoS的優(yōu)劣比較敏感；但是，由于手機(jī)產(chǎn)品價(jià)值較高，其對(duì)不確定情況下QoS的魯棒性同樣具有較高要求。綜上分析，針對(duì)本實(shí)例，設(shè)置γi=0.5（i=1，2，3）。此外，還將在4.4節(jié)對(duì)比不同置信水平下求解結(jié)果的差異，并就置信水平設(shè)置對(duì)優(yōu)化結(jié)果的影響進(jìn)行詳細(xì)分析。

4.3 算法求解

針對(duì)上述模型，采用基于信息素的混合遺傳算法進(jìn)行求解。在算法參數(shù)設(shè)置方面，根據(jù)問(wèn)題規(guī)模，設(shè)置pop＿size=30，G=50，pc=0.8，tour＿size=5；與信息素相關(guān)的參數(shù)參考文獻(xiàn)［28，29］設(shè)置為：pp=0.9，β=3，ρ=0.95；變異概率函數(shù)參考文獻(xiàn)［30］設(shè)置為：pm（g）=0.15×（1-0.1（1-g／G））。實(shí)驗(yàn) 在2.1GHz的英特爾酷睿2雙核處理器和1GB 內(nèi)存的臺(tái)式機(jī)上完成。由于算法具有隨機(jī)性，以某次求解為例，具體求解過(guò)程如下：

按照算法的步驟1所述，首先隨機(jī)生成30個(gè)染色體，組成初始染色體群體pop。以第1個(gè)染色體為例，其編碼為｛3，2，1，2，3，1，2，1，2，1，1，3，2｝，通過(guò)計(jì)算，其對(duì)應(yīng)的三個(gè)目標(biāo)函數(shù)的滿(mǎn)意度分別為｛0.67，0.72，0.51｝，由于不滿(mǎn)足第一個(gè)時(shí)序約束，適應(yīng)度為1.01。相應(yīng)地，通過(guò)計(jì)算其他染色體的適用度可以看出，初始解的適應(yīng)度范圍為［0.65，2.43］，可行解個(gè)數(shù)為11。

生成初始解后，根據(jù)步驟2，按0.8的交叉概率共選擇出21個(gè)染色體組成候選親代染色體集合R。根據(jù)步驟3和步驟4，依次從R中按輪盤(pán)賭選擇兩個(gè)親代染色體執(zhí)行交叉和變異操作，生成臨時(shí)種群tempop。以適應(yīng)度為2.42的染色體｛3，2，1，1，3，1，1，3，1，2，1，2，1｝為例，與適應(yīng)度為2.39的染色體｛3，2，2，1，2，1，2，3，2，2，1，1，2｝的交叉和變異過(guò)程如下：親代染色體中有7個(gè)基因位相同，將直接繼承到子代中，其他6個(gè)基因位根據(jù)式（16）重新選擇服務(wù)，最終生成適應(yīng)度為2.45的新染色體｛3，2，2，1，1，1，1，3，1，2，1，2，1｝。由于所生成的隨機(jī)數(shù)r大于第1代變異概率閾值pm=0.15×（1-0.1（1-1／50））=0.134，即新染色體｛3，2，2，1，1，1，1，3，1，2，1，2，1｝不執(zhí)行變異操作。根據(jù)步驟5，對(duì)tempop與pop中的染色體，基于錦標(biāo)賽選擇與最優(yōu)保留方法執(zhí)行選擇操作，并確定第1代的染色體組pop。可以看出其適應(yīng)度的范圍為［0.86，2.46］，與初始解比較可知，適應(yīng)度得到了優(yōu)化。

重復(fù)上述步驟2～步驟5，當(dāng)?shù)螖?shù)為21時(shí)，解收斂為｛2，2，1，2，2，1，1，3，2，2，2，2，1｝，其適應(yīng)度為2.50，對(duì)應(yīng)的滿(mǎn)意度分別為｛0.61，0.62，0.50｝?；谒@得的最優(yōu)解，客戶(hù)可依次為各任務(wù)匹配相應(yīng)的服務(wù)，從而確定最優(yōu)執(zhí)行計(jì)劃。

4.4 結(jié)果分析

目標(biāo)機(jī)會(huì)約束的置信水平γ反映了目標(biāo)函數(shù)在不確定環(huán)境下的實(shí)現(xiàn)機(jī)會(huì)。為觀察不同置信水平對(duì)優(yōu)化結(jié)果的影響，改變模糊目標(biāo)中的置信水平γi（i=1，2，3），并記錄目標(biāo)函數(shù)的滿(mǎn)意度變化，結(jié)果如表3所示。

表3 改變置信水平對(duì)優(yōu)化結(jié)果的影響

從表3可以看出，隨著置信水平γi由0.9 降至0.3，最小滿(mǎn)意度不斷增大。表明在不確定環(huán)境下，當(dāng)手機(jī)決策者趨向于選擇存在高QoS可能的服務(wù)流程時(shí)，它可能承擔(dān)的服務(wù)流程不能兌現(xiàn)QoS承諾的風(fēng)險(xiǎn)將增加，該結(jié)論與實(shí)際相符。同時(shí)表3也表明，采用本文的多目標(biāo)模糊約束模型轉(zhuǎn)化方法能較好地保留模糊信息量，并讓手機(jī)決策者直觀觀察到風(fēng)險(xiǎn)與效益的關(guān)系，從而權(quán)衡并做出決策。

5 算法性能的對(duì)比分析

為了驗(yàn)證本文算法在計(jì)算效率上的優(yōu)越性，進(jìn)一步從求解精度和算法執(zhí)行時(shí)間兩方面，將本文算法與改進(jìn)遺傳算法［20］、混合優(yōu)化算法［28］及最大-最小蟻群算法［29］進(jìn)行對(duì)比。

在案例設(shè)計(jì)方面，本文設(shè)計(jì)了三種不同的實(shí)驗(yàn)，包括不同的任務(wù)數(shù)量、不同的候選服務(wù)數(shù)量和不同的時(shí)序約束數(shù)量。參數(shù)設(shè)置為pop＿size=100，G=5000，pc=0.8，tour＿size=10，γi=0.5，β=3，pp=0.9，ρ=0.95，pm（g）=0.15×（1-0.1（1-g／G））。每個(gè)候選服務(wù)的QoS 都是隨機(jī)產(chǎn)生的。具體對(duì)各屬性來(lái)說(shuō)，依次產(chǎn)生4個(gè)范圍在［1，10］的隨機(jī)數(shù)，并對(duì)上述隨機(jī)數(shù)按從小到大排序，從而獲得該屬性對(duì)應(yīng)的梯形模糊數(shù)。所有的實(shí)驗(yàn)均在2.1GHz的英特爾酷睿2 雙核處理器和1 GB 內(nèi)存的臺(tái)式機(jī)上完成?？紤]到算法的隨機(jī)性，每組數(shù)值取20次結(jié)果的平均值。

（1）任務(wù)數(shù)量的不同

此組實(shí)驗(yàn)是為了研究任務(wù)數(shù)量增加的、不同算法的求解精度和運(yùn)行時(shí)間的差異。在此實(shí)驗(yàn)中，任務(wù)數(shù)量從10增加到50，增幅定為5；固定每個(gè)任務(wù)候選服務(wù)的數(shù)量為20，時(shí)序約束的數(shù)量為5。實(shí)驗(yàn)結(jié)果如圖6和圖7所示。

從圖6可以看出，本文的求解精度與混合優(yōu)化算法［28］及最大-最小蟻群算法［29］基本相同，明顯優(yōu)于改進(jìn)遺傳算法［20］，且隨著任務(wù)數(shù)量的增加，求解優(yōu)化效果越明顯。由圖7可以看出，本文算法的計(jì)算時(shí)間明顯低于其他三種算法。從時(shí)間增長(zhǎng)趨勢(shì)上看，隨著任務(wù)數(shù)量的增加，本文求解時(shí)間的增長(zhǎng)率最小，而蟻群算法［29］的增長(zhǎng)率明顯高于其他三類(lèi)算法。

（2）候選服務(wù)數(shù)量的不同

此組實(shí)驗(yàn)是為了研究不同算法的求解精度及計(jì)算時(shí)間隨候選服務(wù)數(shù)量的變化而變化的情況。在這組實(shí)驗(yàn)中，候選服務(wù)的數(shù)量從10增加到50，增幅為5；任務(wù)和時(shí)序約束的個(gè)數(shù)分別固定為30 和5。實(shí)驗(yàn)結(jié)果如圖8和圖9所示。

從圖8可以看出，本文的求解精度與混合優(yōu)化算法［28］及最大-最小蟻群算法［29］基本相同，明顯優(yōu)于改進(jìn)遺傳算法［20］。隨著任務(wù)數(shù)量的增加，上述算法較改進(jìn)遺傳算法［20］的優(yōu)化程度呈上升趨勢(shì)。由圖9可以看出，本文算法的計(jì)算時(shí)間明顯低于其他三種算法。雖然從增長(zhǎng)趨勢(shì)上看，隨著候選服務(wù)數(shù)量的增加，本文算法計(jì)算時(shí)間的增長(zhǎng)率高于改進(jìn)遺傳算法［20］，但是由于單個(gè)任務(wù)對(duì)應(yīng)的候選服務(wù)數(shù)一般不會(huì)超過(guò)50個(gè)，可以認(rèn)為本文的計(jì)算效率仍較改進(jìn)遺傳算法［20］具有優(yōu)勢(shì)。

（3）時(shí)序約束數(shù)量的不同

此組實(shí)驗(yàn)是為了研究時(shí)序約束個(gè)數(shù)的增加對(duì)求解精度和計(jì)算時(shí)間的影響。在這組實(shí)驗(yàn)中，時(shí)序約束數(shù)量從5增加到45，增幅為5；任務(wù)及其候選服務(wù)的數(shù)量分別固定為30和10。實(shí)驗(yàn)結(jié)果如圖10 和圖11所示。

從圖10可以看出，本文的求解精度與混合優(yōu)化算法［28］及最大-最小蟻群算法［29］基本相同，明顯優(yōu)于改進(jìn)遺傳算法［20］。此外，隨著約束數(shù)量的增加，本文算法的求解精度穩(wěn)定，而改進(jìn)遺傳算法的求解精度明顯呈下降趨勢(shì)。由圖11可以看出，本文算法的計(jì)算時(shí)間最短，而蟻群算法［29］的計(jì)算時(shí)間最長(zhǎng)。從增長(zhǎng)趨勢(shì)上看，隨著約束數(shù)量的增加，改進(jìn)遺傳算法［20］的計(jì)算時(shí)間增長(zhǎng)明顯呈上升趨勢(shì)，其他三類(lèi)算法的計(jì)算時(shí)間增長(zhǎng)率均較小。

綜上分析，通過(guò)設(shè)計(jì)不同任務(wù)數(shù)量、候選服務(wù)數(shù)量和時(shí)序約束數(shù)量的實(shí)驗(yàn)，對(duì)比發(fā)現(xiàn)：

（1）針對(duì)上述多組實(shí)驗(yàn)，本文算法的求解精度均優(yōu)于改進(jìn)遺傳算法［20］，計(jì)算精度提高了1%～29.6%，特別是隨著問(wèn)題規(guī)模的增大，求解精度的優(yōu)化效果更明顯。在求解時(shí)間上，本文算法均優(yōu)于改進(jìn)遺傳算法，其計(jì)算時(shí)間節(jié)約了46.6%～69.2%。但需指出，隨著候選服務(wù)數(shù)量的增加，本文算法的求解時(shí)間的增長(zhǎng)率高于改進(jìn)遺傳算法。

（2）針對(duì)上述多組實(shí)驗(yàn)，本文算法的求解精度與混合優(yōu)化算法［28］基本相同，計(jì)算精度最大差別為1.3%。在求解時(shí)間上，本文算法明顯優(yōu)于混合優(yōu)化算法，計(jì)算時(shí)間節(jié)約了58.1%～68.8%。而從時(shí)間增長(zhǎng)趨勢(shì)上看，隨著問(wèn)題規(guī)模的增大，兩種算法的求解時(shí)間增長(zhǎng)率接近。

（3）針對(duì)上述多組實(shí)驗(yàn)，本文算法的求解精度與最大-最小蟻群算法［29］基本相同，計(jì)算精度最大差別為1%。在求解時(shí)間上，本文算法明顯優(yōu)于最大-最小蟻群算法，計(jì)算時(shí)間節(jié)約了82.6%～96.5%。隨著問(wèn)題規(guī)模的增大，本文算法在求解時(shí)間上的增長(zhǎng)率明顯低于最大-最小蟻群算法。

分析其原因，就算法的求解精度來(lái)說(shuō)，因?yàn)楦倪M(jìn)遺傳算法［20］僅利用了雙親染色體指導(dǎo)子代生成，而本文算法及其他兩種算法［28-29］均通過(guò)信息素記錄迭代過(guò)程中的求解經(jīng)驗(yàn)，并基于所學(xué)習(xí)到的全局信息指導(dǎo)子代生成，所以更有利于獲得較好的求解結(jié)果。特別是隨著任務(wù)數(shù)、服務(wù)數(shù)量和約束的增加，解空間不斷擴(kuò)大，通過(guò)信息素反映的全局信息在尋優(yōu)過(guò)程中發(fā)揮的作用更加明顯。

就算法的求解時(shí)間而言，因?yàn)樽畲?最小蟻群算法［29］的運(yùn)算開(kāi)銷(xiāo)大量花費(fèi)在基于信息素概率的子代生成計(jì)算上，基于信息素的遺傳算法框架降低了算法的時(shí)間復(fù)雜度；且與改進(jìn)遺傳算法［20］和混合優(yōu)化算法［28］相比，本文算法通過(guò)改進(jìn)的選擇及變異策略也進(jìn)一步降低了算法的時(shí)間復(fù)雜度，所以具有比其他三類(lèi)算法更好的求解時(shí)間優(yōu)勢(shì)。但從算法流程可知，隨著候選服務(wù)數(shù)量的增大，信息素更新及基于信息素交叉操作的運(yùn)算量將增大，而候選服務(wù)數(shù)量的增加對(duì)改進(jìn)遺傳算法［20］的時(shí)間復(fù)雜度影響較小，因此在候選服務(wù)數(shù)量增加的情況下，本文算法的求解時(shí)間增長(zhǎng)率會(huì)高于改進(jìn)遺傳算法［20］。

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

本文針對(duì)普遍存在的時(shí)序約束不確定情況，構(gòu)建了模糊情況下帶時(shí)序約束的服務(wù)流程優(yōu)化模型。在求解方面，首先基于模糊機(jī)會(huì)約束理論和最大模糊滿(mǎn)意度法，將多目標(biāo)模糊規(guī)劃模型轉(zhuǎn)化成以滿(mǎn)意度最大化為目標(biāo)的清晰等價(jià)模型，提出基于信息素的混合遺傳算法進(jìn)行求解。該算法不僅利用親代和服務(wù)自身的局部信息，還利用以信息素形式保存的全局信息，因此加快了收斂效率。本文設(shè)計(jì)了不同任務(wù)數(shù)量、候選服務(wù)數(shù)量和時(shí)序約束數(shù)量的實(shí)驗(yàn)，結(jié)果表明：與已有成果相比，本文算法在執(zhí)行時(shí)間和求解精度上具有明顯優(yōu)勢(shì)。

在本文基礎(chǔ)上，未來(lái)將在如下方面進(jìn)一步展開(kāi)工作：①針對(duì)流程執(zhí)行過(guò)程中出現(xiàn)的時(shí)序異常，如何實(shí)現(xiàn)服務(wù)流程的動(dòng)態(tài)調(diào)整，從而保證時(shí)序一致性；②對(duì)除基本結(jié)構(gòu)之外的工作流復(fù)雜模式進(jìn)行討論。

［1］CHEN J，YANG Y.Multiple states based temporal consistency for dynamic verification of fixed-time constraints in grid workflow systems［J］.Concurrency and Computation：Practice and Experience，2007，19（7）：965-982.

［2］DU Yanhua，WANG Xiaofei，YAO Jianshi.Probability based timed compatibility of Web service composition［J］.Practical Applications of Intelligent Systems Advances in Intelligent and Soft Computing，2012，124：31-39.

［3］LIU X，YANG Y，JIANG Y，et al.Preventing temporal violations in scientific workflows：where and how ［J］.IEEE Transactions on Software Engineering，2011，37（6）：805-825.

［4］ZENG L，BENATALLAH，B，DUMAS M，et al.Quality driven Web services composition［C］／／Proceedings of the 12th International Conference World Wide Web.New York，N.Y.，USA：ACM，2003：411-421.

［5］ROSENBERG F，MULLER M，LEITNER P，et al.Metaheuristic optimization of large-scale QoS-aware service compositions［C］／／Proceedings of 2010IEEE International Conference on Services Computing.Washington，D.C.，USA：IEEE，2010：97-104.

［6］YANG F，SU S，LI Z.Hybrid QoS-aware semantic Web service composition strategies［J］.Science in China Series F：Information Sciences，2008，51（11）：1822-1840.

［7］LI Zhen，YANG Fangchun，SU Sen.Fuzzy multi-attribute decision making-based algorithm for semantic Web service composition［J］.Journal of Software，2009，20（3）：583-596（in Chinese）.［李 禎，楊放春，蘇 森.基于模糊多屬性決策理論的語(yǔ)義Web 服務(wù)組合算法［J］.軟件學(xué)報(bào)，2009，20（3）：583-596.］

［8］TAO Fei，ZHAO Dongming，HU Yefa，et al.Resource service composition and its optimal selection based on particle swarm optimization in manufacturing grid system ［J］.IEEE Transactions on Industrial Informatics，2008，4（4）：315-327.

［9］TAO Fei，ZHAO Dongming，ZHANG Lin.Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system ［J］.Knowledge and Information System，2010，25（1）：185-208.

［10］LI Bohu，ZHANG Lin，WANG Shilong，et al.Cloud manufacturing：a new service oriented networked manufacturing model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1-7，16（in Chinese）.［李伯虎，張 霖，王時(shí)龍，等.云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（1）：1-7，16.］

［11］LIU Weining，LI Yiming，LIU Bo.Service composition in cloud manufacturing based on adaptive mutation particle swarm optimization［J］.Journal of Computer Applications，2012，32（10）：2869-2874（in Chinese）.［劉衛(wèi)寧，李一鳴，劉波.基于自適應(yīng)粒子群算法的制造云服務(wù)組合研究［J］.計(jì)算機(jī)應(yīng)用，2012，32（10）：2869-2874.］

［12］BAI L，LIU M.Fuzzy sets and similarity relations for semantic Web service matching［J］.Computers and Mathematics with Applications，2011，61（8）：2281-2286.

［13］DU Yanhua，LI Hong，AI Lifeng.Dynamic configuration of service based processes in cloud computing using linear programming［C］／／Proceedings of the 9th World Congress on Intelligent Control and Automation.Washington，D.C.，USA：IEEE，2012：3509-3514.

［14］CHEN J，YANG Y.Localizing temporal constraints in scientific workflows［J］.Journal of Computer and System Sciences，2010，76（6）：464-474.

［15］WANG P.QoS-aware web services selection with intuitionistic fuzzy set under consumer's vague perception［J］.Expert Systems with Applications，2009，36（3）：4460-4466.

［16］JESJE C，JULIA S，VALETTE R.Fuzzy continuous resource allocation mechanisms in workflow management systems［C］／／Proceedings of 2009 23rd Brazilian Symposium on Software Engineering.Washington，D.C.，USA：IEEE Computer Society，2009：236-251.

［17］ARDAGNA D，PERNICI B.Adaptive service composition in flexible processes［J］.IEEE Transactions on Software Engi-neering，2007，33（6）：369-384.

［18］YU J，BUYYA R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms［J］.Scientific Programming，2006，14（3）：217-230.

［19］AI L，TANG M.A penalty-based genetic algorithm for QoSaware web service composition with inter-service dependencies and conflicts［C］／／Proceedings of International Conference on Computational Intelligence for Modeling Control &Automation.Washington，D.C.，USA：IEEE，2008：738-743.

［20］DU Y，WANG X，AI L.Dynamic selection of services under temporal constraints in cloud computing［C］／／Proceedings of 2012International Conference on E-Business Engineering.Washington，D.C.，USA：IEEE，2012：252-259.

［21］DU Y，XIONG P，F(xiàn)AN Y，et al.Dynamic checking and solution to temporal violations in concurrent workflow processes［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part A：Systems and Humans，2011，41（6）：1166-1181.

［22］HU Baoqing.Fuzzy basic theory［M］.Wuhan：Wuhan University Press，2010（in Chinese）.［胡寶清.模糊理論基礎(chǔ)［M］.武漢：武漢大學(xué)出版社，2010.］

［23］ZHOU Y，MURATA T，DEFANTI T.Modeling and performance analysis using extended fuzzy-timing Petri nets for networked virtual environment［J］.IEEE Transactions on System，Man，and Cybernetics—Part B：Cybernetics，2000，30（5）：737-755.

［24］LU M.On crisp equivalents and solutions of fuzzy programming with different chance measures［J］.Information，2003，6（2）：125-134.

［25］LIU Baoding，ZHAO Ruiqing，WANG Gang.Uncertain programming with applications［M］.Beijing：Tsinghua University Press，2003（in Chinese）.［劉寶錠，趙瑞清，王 綱.不確定規(guī)劃及應(yīng)用［M］.北京：清華大學(xué)出版社，2003.］

［26］LIU Weining，LIU Bo，SUN Dihua.Multi-task oriented service composition in cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2013，19（1）：199-209（in Chinese）.［劉衛(wèi)寧，劉 波，孫棣華.面向多任務(wù)的制造云服務(wù)組合［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013，19（1）：199-209.］

［27］ZHOU Ming，SUN Shudong.Genetic algorithms：theory and application［M］.Beijing：National Defense Industry Press，1996：11-14（in Chinese）.［周 明，孫樹(shù)棟.遺傳算法原理及應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，1996：11-14.］

［28］ZHAO F，LI S，SUN J，et al.Genetic algorithm for the onecommodity pickup-and-delivery traveling salesman problem［J］.Computer &Industry Engineering，2009，56（4）：1642-1648.

［29］STUTZLE T，HOOS H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889-898.

［30］WANG Wenbin，SUN Qibo，ZHAO Xinchao，et al.Web services selection approach with QoS global optimal based on discrete particle swarm optimization with non-uniform mutation algorithm［J］.Acta Electronica Sinica，2010，38（12）：2774-2779（in Chinese）.［王文彬，孫其博，趙新超，等.基于非均衡變異離散粒子群算法的QoS全局最優(yōu)Web服務(wù)選擇方法［J］.電子學(xué)報(bào)，2010，38（12）：2774-2779.］