王 笑，徐漢川，王忠杰，涂志瑩，徐曉飛

(哈爾濱工業(yè)大學(xué) 計(jì)算學(xué)部，黑龍江 哈爾濱 150001)

0 引言

隨著大數(shù)據(jù)、云計(jì)算、物聯(lián)網(wǎng)等理論和技術(shù)的快速發(fā)展，Internet上可用的軟件服務(wù)越來(lái)越多，現(xiàn)實(shí)中的各類物理資源及人工服務(wù)也通過(guò)虛擬化和物聯(lián)網(wǎng)技術(shù)被接入Internet,并與線上的軟件服務(wù)建立協(xié)同和集成，這兩個(gè)趨勢(shì)使互聯(lián)網(wǎng)上的可用服務(wù)數(shù)量急劇增加。與此同時(shí)，客戶需求也越來(lái)越傾向于大粒度和個(gè)性化，涉及到的應(yīng)用業(yè)務(wù)與數(shù)據(jù)體現(xiàn)出很強(qiáng)的復(fù)雜性、關(guān)聯(lián)性與跨界性，單一的服務(wù)往往難以滿足此類需求，通常需要多項(xiàng)服務(wù)的集成。這種跨越大量領(lǐng)域、服務(wù)、業(yè)務(wù)流程和規(guī)則的服務(wù)生態(tài)系統(tǒng)構(gòu)成了服務(wù)互聯(lián)網(wǎng)或大服務(wù)[1-2]，其中用戶對(duì)服務(wù)的需求海量且個(gè)性化，服務(wù)資源數(shù)量眾多且跨領(lǐng)域，需要在海量需求和服務(wù)間進(jìn)行服務(wù)匹配，通過(guò)聚合不同領(lǐng)域的服務(wù)，產(chǎn)生復(fù)合服務(wù)解決方案，以滿足用戶需求。例如，養(yǎng)老服務(wù)中，某老人患有糖尿病，不愿接受到養(yǎng)老院養(yǎng)老，而子女白天上班，無(wú)法照顧老人。通過(guò)構(gòu)建服務(wù)解決方案，可以將護(hù)工預(yù)約、護(hù)工日常護(hù)理、健康商城、老人健康檔案、慢病管理、醫(yī)院就醫(yī)等跨領(lǐng)域和組織的服務(wù)整合在一起提供給老人，滿足老人的居家養(yǎng)老需求。因此，如何高效構(gòu)建用戶滿意的服務(wù)方案是服務(wù)互聯(lián)網(wǎng)中服務(wù)設(shè)計(jì)和優(yōu)化的核心問(wèn)題。

服務(wù)方案構(gòu)建的核心問(wèn)題是在可用服務(wù)與用戶需求間建立匹配關(guān)系，即服務(wù)供需雙邊匹配。研究人員已對(duì)服務(wù)供需匹配問(wèn)題進(jìn)行了大量研究，傳統(tǒng)服務(wù)組合[3]和服務(wù)選擇[4]技術(shù)將每個(gè)用戶需求視為獨(dú)立的個(gè)體，以某個(gè)或某些目標(biāo)最優(yōu)化為目標(biāo)，在滿足約束的前提下，根據(jù)現(xiàn)有可用服務(wù)構(gòu)造出用戶滿意的優(yōu)化服務(wù)解決方案。典型方法包括精確算法[5-6]、演化算法[7-11]、基于深度學(xué)習(xí)的算法[12-13]以及將服務(wù)組合問(wèn)題轉(zhuǎn)化為經(jīng)典規(guī)劃問(wèn)題[14-15]與基于圖的方法[16-17]。CHATTOPADHYAY[18]對(duì)服務(wù)組合問(wèn)題提出一種近似機(jī)制來(lái)獲得接近于最優(yōu)解的時(shí)間。RODRIGUEZ-MIER等[6]提出一種使用精確算法的方法，該方法使用一種混合的局部—全局策略來(lái)優(yōu)化QoS感知服務(wù)組合問(wèn)題。HAYTAMY等[10]提出一個(gè)基于深度學(xué)習(xí)的服務(wù)組合框架，該框架融合了長(zhǎng)短期記憶人工神經(jīng)網(wǎng)絡(luò)(Long Short-Term Memory, LSTM) 和粒子群優(yōu)化算法。ZHOU等[8]在云制造領(lǐng)域中提出了解決多目標(biāo)服務(wù)組合問(wèn)題的自適應(yīng)多種群差分人工蜂群算法。但是，在服務(wù)互聯(lián)網(wǎng)場(chǎng)景下，用戶需求和服務(wù)資源數(shù)量龐大，算法搜索空間巨大，現(xiàn)有的服務(wù)組合和服務(wù)選擇技術(shù)難以高效快速地得到滿足大規(guī)模個(gè)性化用戶需求的服務(wù)方案。經(jīng)過(guò)大量的實(shí)踐觀察和分析，發(fā)現(xiàn)服務(wù)與服務(wù)間、需求與需求間均存在相似性和關(guān)聯(lián)性，某些領(lǐng)域服務(wù)也會(huì)頻繁地在一起關(guān)聯(lián)使用，如淘寶購(gòu)物服務(wù)中，用戶只能選擇支付寶服務(wù)，而在京東購(gòu)物服務(wù)中，只能選擇微信或者京東錢(qián)包服務(wù)。這類相似性與關(guān)聯(lián)性是領(lǐng)域服務(wù)先驗(yàn)知識(shí)的一種體現(xiàn)，如果能夠挖掘出蘊(yùn)含其中的關(guān)聯(lián)關(guān)系，將歷史上成功的可復(fù)用服務(wù)解決方案(服務(wù)模式)和用戶經(jīng)常提出的關(guān)聯(lián)需求(需求模式)用于服務(wù)方案的構(gòu)建和用戶需求聲明中，則可以將服務(wù)匹配的粒度從小粒度的原子服務(wù)和需求提升為大粒度的構(gòu)建模塊，有效縮減搜索空間，提升用戶滿意度。如果可刻畫(huà)服務(wù)模式與需求模式間的關(guān)聯(lián)關(guān)系，則可以進(jìn)一步提高服務(wù)匹配的效率，實(shí)現(xiàn)服務(wù)方案的快速高效構(gòu)建。

在現(xiàn)有研究中，通過(guò)數(shù)據(jù)挖掘技術(shù)從歷史中挖掘模式已經(jīng)成為服務(wù)組合中一種主導(dǎo)的方法[19-20]。PERRYEA等[21]在基于社區(qū)的服務(wù)組合方法中，利用歷史上的復(fù)合解決方案盡可能地滿足新的需求。LIU等[22]使用FP-growth算法從歷史服務(wù)解決方案中挖掘服務(wù)模式。XU等[23]提出“需求—工程”(RE2SEP)兩段式服務(wù)開(kāi)發(fā)范型，對(duì)服務(wù)模式進(jìn)行了定義，并提出了將需求模式與服務(wù)模式通過(guò)情境信息進(jìn)行匹配。雖然當(dāng)前已經(jīng)有不少對(duì)服務(wù)模式的研究，但是對(duì)需求模式的研究還不足，只是根據(jù)用戶提出的需求使用服務(wù)模式進(jìn)行服務(wù)組合或者服務(wù)選擇。同時(shí)，對(duì)于服務(wù)模式使用情境的研究較少，只是單純使用歷史出現(xiàn)的全部或部分服務(wù)流程進(jìn)行復(fù)用。

另外，為了更好地理解用戶需求，需要提供一種表達(dá)能力強(qiáng)且易于用戶之間建模的需求模型。面向目標(biāo)的建模技術(shù)常用于需求建模當(dāng)中，ASADI等[24]提出一種基于描述邏輯的方法，在一個(gè)共同的知識(shí)庫(kù)中表達(dá)模型之間的關(guān)系。ROLLAND等[25]和YU[26]將目標(biāo)模型應(yīng)用與需求工程的系統(tǒng)分析和設(shè)計(jì)以及信息和軟件系統(tǒng)開(kāi)發(fā)中。HORKOFF等[27]通過(guò)與功能和非功能目標(biāo)的聯(lián)系來(lái)分析和證明模型的正確性。但是，這些方法沒(méi)有以服務(wù)開(kāi)發(fā)為中心，而且必須對(duì)指定的目標(biāo)模型進(jìn)行人工分析，才能得到相應(yīng)的候選服務(wù)[28]。同時(shí)，這些模型大多太過(guò)復(fù)雜，對(duì)于沒(méi)有建模經(jīng)驗(yàn)的終端用戶，使用這些模型提出需求十分困難。

基于以上分析和思考，本文提出一種基于供需雙邊模式的服務(wù)方案高效匹配方法，其核心思想是挖掘領(lǐng)域先驗(yàn)知識(shí)中服務(wù)間、需求間以及服務(wù)與需求間的關(guān)聯(lián)特征，利用模塊化的思想提升服務(wù)匹配中供需雙邊構(gòu)建單元的粒度，從而提高服務(wù)匹配效率和用戶滿意度。本文首先建立了基于雙邊模式的服務(wù)匹配問(wèn)題模型;之后針對(duì)用戶需求端，提出了基于意圖樹(shù)的需求和需求模式模型;針對(duì)服務(wù)提供端，提出了服務(wù)模式模型及挖掘策略;進(jìn)而根據(jù)歷史服務(wù)方案中的用戶情境信息等內(nèi)容構(gòu)建了多維雙邊模式關(guān)聯(lián)矩陣，并提出了關(guān)聯(lián)矩陣的適應(yīng)性更新策略;最后，針對(duì)3種典型的服務(wù)場(chǎng)景，設(shè)計(jì)了不同類型的算法，驗(yàn)證本文所提基于雙邊模式的匹配方法相較于傳統(tǒng)方法的有效性。

1 基于供需雙邊模式的服務(wù)匹配問(wèn)題模型與方法框架

1.1 基于供需雙邊模式的服務(wù)匹配問(wèn)題模型

本文采用的優(yōu)化策略是利用供需雙邊模式(服務(wù)模式與需求模式)及其關(guān)聯(lián)矩陣來(lái)縮小搜索空間，提高匹配效率，實(shí)現(xiàn)服務(wù)方案的高效快速構(gòu)建。由于最小化問(wèn)題和最大化問(wèn)題可以等價(jià)轉(zhuǎn)化，服務(wù)互聯(lián)網(wǎng)中基于供需雙邊模式的服務(wù)匹配問(wèn)題模型可定義如下：

minF(x)=(Gu(x),Gs(x),Gp(x))T。

(1)

s.t.

hi(x)≤0,i=1,2,…,uh;

(2)

cpj(x)>0,j=1,2,…,|SSP|;

(3)

sspk?sspl,k,l∈SSP。

(4)

其中決策變量x為服務(wù)方案，x=SSP,SEQ。其中：SSP為服務(wù)方案構(gòu)造單元集合，由|SP|個(gè)服務(wù)模式sp和|S|個(gè)原子服務(wù)s構(gòu)成，即ssp∈{sp1,sp2,…,sp|SP|,s1,s2…,s|s|}，|SSP|=|SP|+|S|;SEQ為服務(wù)方案中構(gòu)造單元間執(zhí)行順序集合，SEQ={seqij|sspi需要在sspj之前執(zhí)行,sspi,sspj∈SSP}。式(1)為優(yōu)化目標(biāo)函數(shù)向量，根據(jù)目標(biāo)訴求方可分為用戶目標(biāo)Gu(x)，服務(wù)提供商目標(biāo)Gs(x)以及第三方平臺(tái)目標(biāo)Gp(x)，根據(jù)優(yōu)化目標(biāo)數(shù)量可以分為單目標(biāo)、多目標(biāo)以及超多目標(biāo)(目標(biāo)數(shù)量超過(guò)4個(gè))優(yōu)化問(wèn)題。每個(gè)目標(biāo)的計(jì)算方式由目標(biāo)本身和方案流程決定，服務(wù)系統(tǒng)的優(yōu)化目標(biāo)通常包括時(shí)間、成本、資源利用率、可靠性、資源均衡利用等。式(2)為用戶需求中提出的約束，hi(x)≤0表示用戶提出的第i個(gè)約束，uh為約束數(shù)量，不等式中大于和小于可以相互轉(zhuǎn)化，以小于等于代指所有類型約束。式(3)為服務(wù)能力約束，cpj(x)為服務(wù)方案x中服務(wù)模式spj或原子服務(wù)sj當(dāng)前服務(wù)能力值，所用服務(wù)的服務(wù)能力需要大于0。式(4)為順序約束，約束了服務(wù)流程中服務(wù)的先后順序，sspk?sspl表示服務(wù)模式spk或原子服務(wù)sk需要在服務(wù)模式spl或原子服務(wù)sl之前執(zhí)行。

1.2 問(wèn)題求解框架

針對(duì)服務(wù)供需匹配問(wèn)題，提出如圖1所示的求解框架。具體求解環(huán)節(jié)如下：

(1)在用戶需求端，維護(hù)歷史需求庫(kù)，并從中挖掘得到需求模式庫(kù)。

(2)在服務(wù)提供端，維護(hù)可用原子服務(wù)集，并從歷史服務(wù)方案中挖掘得到服務(wù)模式庫(kù)。

(3)構(gòu)建雙邊模式關(guān)聯(lián)矩陣，利用服務(wù)日志中的歷史匹配記錄，得到需求模式與服務(wù)模式間的匹配關(guān)系。

(4)構(gòu)建服務(wù)解決方案，針對(duì)特定需求，建立需求模型，對(duì)用戶需求進(jìn)行匹配，得到一組能夠最優(yōu)匹配所提需求的需求模式。進(jìn)一步通過(guò)關(guān)聯(lián)矩陣找到每個(gè)需求模式對(duì)應(yīng)的一組服務(wù)模式，針對(duì)用戶提出的優(yōu)化目標(biāo)，適應(yīng)性地選擇優(yōu)化算法得到匹配的服務(wù)模式，最終構(gòu)造一個(gè)滿足用戶需求的優(yōu)化服務(wù)方案。

其中：環(huán)節(jié)(1)～(3)為服務(wù)方案構(gòu)造所需基礎(chǔ)數(shù)據(jù)準(zhǔn)備階段，需要維護(hù)歷史需求庫(kù)、需求模式庫(kù)、原子服務(wù)庫(kù)、服務(wù)模式庫(kù)和雙邊模式關(guān)聯(lián)矩陣;環(huán)節(jié)(4)為針對(duì)特定需求構(gòu)建服務(wù)方案環(huán)節(jié)。

2 供需雙邊模式與關(guān)聯(lián)矩陣

2.1 基于意圖樹(shù)的需求模型與需求模式

2.1.1 基于意圖樹(shù)的需求模型

在常用需求建模方法中，面向目標(biāo)的建模技術(shù)因其具有形式直觀、易于理解、表達(dá)能力強(qiáng)、不需過(guò)多專業(yè)知識(shí)等優(yōu)點(diǎn)，被廣泛應(yīng)用于需求工程中的需求建模[24,27]?；谀繕?biāo)建模的方法理念，本文提出一種基于意圖樹(shù)的需求模型iTree，

iTree=G,E

其中意圖樹(shù)iTree由意圖節(jié)點(diǎn)集合G={G1,G2,…,Gn}與意圖關(guān)聯(lián)關(guān)系集E構(gòu)成。一個(gè)意圖樹(shù)節(jié)點(diǎn)Gi包括意圖、約束和優(yōu)化目標(biāo)，Gi=intension,{constaint},{OptObjective}。意圖樹(shù)節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系有分解與依賴兩種。需求模型可以由用戶直接手工建立，也可以通過(guò)其他需求獲取的方式建立，如通過(guò)與用戶對(duì)話等方式。

如圖2所示為iTree模型中的元素及其關(guān)系，詳細(xì)介紹如下：

(1)User表示用戶。

(2)Role表示角色。一個(gè)用戶可以被分配不同的角色。

(3)Intension表示意圖。用戶通過(guò)意圖來(lái)描述自己的功能性需求。

(4)Decomposition表示分解。上層意圖可以分解為若干下層意圖。該關(guān)系有“與”和“或”兩種。“與”關(guān)系表示當(dāng)下層意圖均被滿足時(shí)，上層意圖同時(shí)被滿足;“或”關(guān)系表示當(dāng)任意一個(gè)下級(jí)意圖能被滿足時(shí)，上層意圖即可被滿足。

(5)Dependency表示依賴。同級(jí)意圖之間某意圖的實(shí)現(xiàn)依賴于另一意圖。

(6)Constraint表示約束。用戶通過(guò)約束來(lái)描述自己的非功能性需求。約束使用鍵值對(duì)定義：Cons=Conskey,Constype,Consvalue，分別表達(dá)約束名、約束數(shù)據(jù)類型和約束值。

(7)OptObjective表示優(yōu)化目標(biāo)。用戶使用優(yōu)化目標(biāo)表達(dá)自己的偏好，如解質(zhì)量?jī)?yōu)先或求解速度優(yōu)先，此指標(biāo)在服務(wù)方案構(gòu)建時(shí)予以考慮。

圖3給出了一個(gè)居家老人日常生活需求的iTree模型實(shí)例。老人通過(guò)意圖樹(shù)表達(dá)自己的日常生活需求：老人需要找一名保姆、找一名家庭醫(yī)生并進(jìn)行慢病管理、辦理健康檔案與居民健康一卡通、使用健康商城服務(wù)購(gòu)買(mǎi)醫(yī)療用品。意圖樹(shù)中描述了老人對(duì)意圖的偏好和非功能性需求，如：老人對(duì)服務(wù)的偏好是最少花費(fèi)；在家庭醫(yī)生服務(wù)意圖中，老人對(duì)非功能性需求進(jìn)行了指定：花費(fèi)在0～3 000元間，并進(jìn)一步表達(dá)了自己的需求：需要與醫(yī)生交流、進(jìn)行健康管理以及醫(yī)生隨訪服務(wù)。

2.1.2 基于意圖樹(shù)的需求模式

在大量的用戶需求中，某些需求中包含的意圖間存在較強(qiáng)的關(guān)聯(lián)性，這些關(guān)聯(lián)意圖集往往會(huì)在多個(gè)需求中被重復(fù)提出，這些頻繁出現(xiàn)的關(guān)聯(lián)意圖集體現(xiàn)了領(lǐng)域用戶需求的先驗(yàn)知識(shí)，本文對(duì)其進(jìn)行挖掘并刻畫(huà)為需求模式(RP)。需求模式是對(duì)用戶需求的模塊化描述，在用戶需求聲明過(guò)程中，利用需求模式，通過(guò)需求補(bǔ)全、推薦、重構(gòu)等操作，可將碎片化和不精確的原始需求，快速完整地轉(zhuǎn)換為合理優(yōu)化的需求。進(jìn)一步，將需求模式同服務(wù)模式關(guān)聯(lián)，形成供需雙邊模式關(guān)聯(lián)矩陣，增大匹配粒度，提高匹配效率，高效構(gòu)建服務(wù)方案。

基于意圖樹(shù)的需求模式是由多棵子意圖樹(shù)組成的森林，RP=info,{iTreei}。其中：info表示需求模式的基本信息，如需求模式描述和使用頻率等;{iTreei}為意圖樹(shù)集合。在圖3所示的例子中，存在兩個(gè)需求模式，一個(gè)是“家庭醫(yī)生服務(wù)”，另一個(gè)是“慢病管理服務(wù)”，其中家庭醫(yī)生服務(wù)需求模式包含了醫(yī)生交流服務(wù)、健康管理服務(wù)、隨訪服務(wù)3個(gè)頻繁出現(xiàn)的子意圖以及指定家庭醫(yī)生服務(wù)的約束為花費(fèi)在0～3 000元間。

需求模式的構(gòu)建可以采用人工定義和自動(dòng)挖掘兩種手段。自動(dòng)挖掘包括兩個(gè)階段：

第一階段：頻繁意圖樹(shù)結(jié)構(gòu)挖掘。該過(guò)程以挖掘頻繁樹(shù)結(jié)構(gòu)為目標(biāo)，考慮意圖與結(jié)構(gòu)，不考慮約束。使用gSpan算法挖掘頻繁結(jié)構(gòu)。

第二階段：需求模式挖掘。從需求全集中提取包含頻繁結(jié)構(gòu)的子意圖樹(shù)，根據(jù)約束進(jìn)行聚類，最后得到具有相同結(jié)構(gòu)及意圖，但約束不同的需求模式。

由于篇幅限制，本文只簡(jiǎn)要介紹需求模式挖掘算法思路，詳細(xì)算法以及如何利用需求模式進(jìn)行需求的自動(dòng)補(bǔ)全、推薦、重構(gòu)等內(nèi)容將在后續(xù)論文進(jìn)行描述。

2.2 面向關(guān)聯(lián)知識(shí)復(fù)用的服務(wù)模式

在服務(wù)互聯(lián)網(wǎng)環(huán)境下，服務(wù)之間存在著相似性和關(guān)聯(lián)性，即某些服務(wù)之間經(jīng)常會(huì)關(guān)聯(lián)在一起搭配使用，如第1章所述的京東商城和天貓商城的例子。本文對(duì)歷史服務(wù)方案和領(lǐng)域知識(shí)中，經(jīng)常被高頻使用的服務(wù)流程和服務(wù)搭配進(jìn)行分析和挖掘，形成服務(wù)模式(SP)[29]。服務(wù)模式定義如下：

SP=SPinfo,SPfr,SPprocess,SPinstance。

其中：SPinfo表示服務(wù)模式的基本信息，如名稱、所屬領(lǐng)域等；SPfr描述了服務(wù)模式完成的功能；SPprocess描述服務(wù)流程，實(shí)現(xiàn)時(shí)可采用業(yè)務(wù)流程建模與標(biāo)注(Business Process Modeling Notation, BPMN)格式描述和存儲(chǔ)；SPinstance是服務(wù)模式的實(shí)例集，SPinstance=S,SPQoS，其中：S為該服務(wù)模式實(shí)例綁定的服務(wù)集合，服務(wù)可以使用傳統(tǒng)的網(wǎng)絡(luò)服務(wù)的本體語(yǔ)言(Ontology Web Language for Services, OWL-S)或Web服務(wù)描述語(yǔ)言(Web Services Description Language, WSDL)等服務(wù)模型進(jìn)行建模，SPQoS為服務(wù)模式實(shí)例的質(zhì)量指標(biāo)信息。

如圖4所示為服務(wù)模式中的元素及其關(guān)系。

與利用原子服務(wù)構(gòu)建服務(wù)方案相比，服務(wù)模式挖掘了歷史服務(wù)方案中成功的案例并將其重用，減少搜索空間，提高構(gòu)建效率；此外，由于服務(wù)模式體現(xiàn)了領(lǐng)域先驗(yàn)的服務(wù)使用知識(shí)，可以預(yù)先準(zhǔn)備建立關(guān)聯(lián)，降低關(guān)聯(lián)成本；且服務(wù)模式是經(jīng)過(guò)實(shí)踐驗(yàn)證的成功案例，可獲得更好的用戶滿意度。

在之前的研究中，已提出采用頻繁模式增長(zhǎng)(Frequent Pattern growth, FP-growth)算法從服務(wù)系統(tǒng)的歷史日志中挖掘服務(wù)模式[22]。該算法包括兩個(gè)步驟：利用緊湊的數(shù)據(jù)結(jié)構(gòu)FP-Tree，對(duì)日志進(jìn)行壓縮，避免多次的數(shù)據(jù)庫(kù)掃描；使用FP-growth算法挖掘出頻繁的服務(wù)模式。

如圖5所示的服務(wù)模式為一個(gè)“慢病管理”服務(wù)模式的流程示例，內(nèi)含5個(gè)服務(wù)：慢病篩查服務(wù)、簽約服務(wù)、醫(yī)生咨詢服務(wù)、健康評(píng)估服務(wù)和應(yīng)用健康卡服務(wù)。

2.3 供需雙邊模式關(guān)聯(lián)矩陣

2.3.1 關(guān)聯(lián)矩陣定義

通過(guò)2.1節(jié)和2.2節(jié)介紹的需求模式和服務(wù)模式，可以通過(guò)固化需求間和服務(wù)間的關(guān)聯(lián)關(guān)系，形成需求模式和服務(wù)模式，通過(guò)提升需求與服務(wù)的構(gòu)建單元粒度，縮小搜索空間?？蛇M(jìn)一步利用歷史服務(wù)方案中供需雙邊模式間的成功匹配先驗(yàn)知識(shí)，構(gòu)建雙邊模式間的多維概率關(guān)聯(lián)矩陣，支持服務(wù)方案構(gòu)建中的快速搜索。該關(guān)聯(lián)矩陣由R,S,RP,SP,Context五個(gè)維度構(gòu)成，其中：R為需求集合，S為服務(wù)集合，RP為需求模式集合，SP為服務(wù)模式集合，Context為情境信息集合。如圖6所示為供需雙邊模式關(guān)聯(lián)矩陣的示意圖，圖中：x軸為需求模式，y軸為服務(wù)模式，z軸為情境信息。

五個(gè)維度間存在多種關(guān)聯(lián)關(guān)系，需求模式與服務(wù)模式分別蘊(yùn)含了需求間的關(guān)聯(lián)和服務(wù)間的關(guān)聯(lián)，本節(jié)重點(diǎn)闡述需求模式與服務(wù)模式在不同情境下的關(guān)聯(lián)關(guān)系，關(guān)聯(lián)關(guān)系的強(qiáng)弱通過(guò)匹配度pij∈[0,1)進(jìn)行度量。

假設(shè)共有n個(gè)需求模式與m個(gè)服務(wù)模式，關(guān)聯(lián)矩陣定義如下。

(1)當(dāng)情境ctk相同時(shí)，設(shè)需求模式rpi可以匹配mi個(gè)服務(wù)模式，aij為需求模式rpi與服務(wù)模式spj的匹配度。若二者不能匹配，則匹配度aij=0。由于每個(gè)需求模式只對(duì)應(yīng)少量服務(wù)模式，mi通常遠(yuǎn)小于m，故需求模式與服務(wù)模式之間關(guān)系可以表達(dá)為稀疏矩陣：

(5)

(2)當(dāng)同一需求模式rpi所處的用戶情境不同時(shí)，其對(duì)應(yīng)的服務(wù)模式也不同。設(shè)有c個(gè)情境信息，設(shè)bk,j為情境ctk時(shí)，需求模式rpi與服務(wù)模式spj的匹配度，若二者不能匹配，則匹配度bk,j=0。為簡(jiǎn)單起見(jiàn)，本文設(shè)每個(gè)情境信息對(duì)應(yīng)的候選服務(wù)模式都有m0個(gè)，則相應(yīng)匹配關(guān)系可表達(dá)為稀疏矩陣：

(6)

2.3.2 用戶情境信息

在不同情境下，同一需求模式能夠匹配的服務(wù)模式可能不同。因此，在服務(wù)方案構(gòu)建過(guò)程中，需要依據(jù)服務(wù)情境信息的不同，采用不同的策略和優(yōu)化方法，因此在關(guān)聯(lián)矩陣構(gòu)建時(shí)，要考慮情境維度的信息。

本文所考慮的情境信息包括兩類：

(1)用戶情境，即用戶年齡、性別等自然信息以及用戶的職業(yè)、人際關(guān)系等群體信息。

(2)環(huán)境情境，即時(shí)間、地點(diǎn)等用戶提出需求時(shí)所處的環(huán)境。

采用鍵值對(duì)形式對(duì)情境進(jìn)行建模，對(duì)于連續(xù)型情境，使用標(biāo)準(zhǔn)化歐氏距離度量?jī)蓚€(gè)情境的相似程度,對(duì)于離散型情境，按照one-hot編碼規(guī)則轉(zhuǎn)換為連續(xù)型情境。由于抽象后的情境維度可能過(guò)高，本文使用主成分分析法(Principal Component Analysis, PCA)[31]進(jìn)行降維。

2.3.3 雙邊模式匹配度計(jì)算

雙邊模式匹配度是需求模式在某情境下匹配服務(wù)模式的匹配概率。匹配度的計(jì)算需要考慮歷史、當(dāng)前和未來(lái)3部分服務(wù)數(shù)據(jù)。因?yàn)闅v史中使用次數(shù)較高的服務(wù)模式當(dāng)前可能不會(huì)出現(xiàn)，且新需求模式，服務(wù)模式對(duì)存在冷啟動(dòng)問(wèn)題，服務(wù)模式的約束值也可能會(huì)發(fā)生變化，所以歷史和當(dāng)前部分?jǐn)?shù)據(jù)的匹配度計(jì)算需考慮包括時(shí)間衰減、約束滿足度和匹配次數(shù)3個(gè)參數(shù)。

(1)時(shí)間衰減Ti,表示第i次匹配的時(shí)間衰減程度,

Ti=1-e-(t0-ti)。

(7)

式中t0表示當(dāng)前時(shí)間，ti表示第i次匹配時(shí)間點(diǎn)。

(2)約束滿足度Ci,表示第i次匹配時(shí)需求模式約束滿足程度，

(8)

式中：n為約束數(shù)量，cj為第j個(gè)約束的服務(wù)模式滿足度。對(duì)于枚舉值，滿足約束為1，不滿足為0；對(duì)于范圍值的情況，服務(wù)模式滿足度定義如下：

(9)

式中：wmin與wmax指需求模式中約束的最小值與最大值，w為約束的實(shí)際值。

(3)匹配次數(shù)記為N。

綜合3個(gè)參數(shù)，包含歷史和當(dāng)前部分信息的匹配度

(10)

未來(lái)部分的匹配度pf需要結(jié)合特定領(lǐng)域?qū)ξ磥?lái)需求與服務(wù)的使用情況進(jìn)行預(yù)測(cè)，有針對(duì)性地調(diào)整匹配度。

需求模式中每個(gè)子需求的預(yù)測(cè)值為pf,ri，則需求模式的預(yù)測(cè)值

其中：n為子需求的個(gè)數(shù);ai為子需求i的權(quán)值，本文認(rèn)為需求模式中約束多的子需求為更重要的部分，在匹配度計(jì)算中權(quán)值越大，因此ai為子需求i約束的數(shù)量。同理，服務(wù)模式的預(yù)測(cè)值pf,s即為每個(gè)服務(wù)預(yù)測(cè)值的平均值。在實(shí)際應(yīng)用中，可根據(jù)使用具體情境，采用對(duì)應(yīng)的預(yù)測(cè)模型，獲得需求和服務(wù)的變化趨勢(shì)，設(shè)計(jì)預(yù)測(cè)值pf,ri的計(jì)算方法。綜上，包含歷史、當(dāng)前和未來(lái)3個(gè)部分信息的匹配度

(11)

其中，由于歷史和當(dāng)前部分可以同時(shí)考慮，統(tǒng)一用k1表示歷史和當(dāng)前部分的權(quán)重;k2表示將來(lái)部分的權(quán)重，k2的大小與需求和服務(wù)預(yù)測(cè)的置信度有關(guān)，預(yù)測(cè)的置信度越低，k2越小。

將p歸一化即為最后得到的匹配度。

關(guān)聯(lián)矩陣在使用時(shí)，首先通過(guò)用戶情境信息找到Ak，再根據(jù)需求模式找到與其對(duì)應(yīng)的服務(wù)模式集，經(jīng)過(guò)優(yōu)化得到最終的服務(wù)方案。如圖3的需求模型，用戶提出居家老人的日常生活意圖樹(shù)，假設(shè)其情境信息的一部分為60歲，哈爾濱，則根據(jù)其情境信息，就只會(huì)找到適合60歲且地點(diǎn)在哈爾濱的家庭醫(yī)生和慢病管理的服務(wù)模式。

2.4 供需雙邊模式關(guān)聯(lián)矩陣的構(gòu)建與更新方法

2.4.1 供需雙邊模式關(guān)聯(lián)矩陣的構(gòu)建算法

算法1雙邊模式關(guān)聯(lián)矩陣構(gòu)建算法。

輸入:服務(wù)方案集合solution;

輸出:關(guān)聯(lián)矩陣A。

1 begin

2 用戶情境集合X=?;匹配時(shí)間點(diǎn)集合D=?;關(guān)聯(lián)矩陣A=?

3 foreach服務(wù)方案si∈solution do

4 foreach (rpj,spk)∈sido

/* X[(rpj,spk)]與D[(rpj,spk)]初始為空列表*/

5 X[(rpj,spk)]←X[(rpj,spk)]+ci//ci為si中用戶情境

6 D[(rpj,spk)]←D[(rpj,spk)]+ti//ti為si中匹配時(shí)間點(diǎn)

7 end

8 end

9 foreach (rpj,spk)∈X do

10 Cij←X[(rpj,spk)]

11 Tij←D[(rpj,spk)]

12 使用PCA算法對(duì)Cij降維

13 使用Birch算法對(duì)Cij聚類

14 計(jì)算匹配度，并將聚類結(jié)果與匹配度加入A中

15 end

16 返回A

17 end

2.4.2 供需雙邊模式關(guān)聯(lián)矩陣的更新策略

由實(shí)驗(yàn)可知，當(dāng)服務(wù)日志中總方案數(shù)量很多時(shí)，更新時(shí)間會(huì)達(dá)到1個(gè)小時(shí)甚至更多，關(guān)聯(lián)矩陣更新代價(jià)巨大。因此，需要根據(jù)總服務(wù)方案數(shù)量動(dòng)態(tài)調(diào)整更新頻率，在更新效率與更新效果間進(jìn)行均衡。本節(jié)根據(jù)關(guān)聯(lián)矩陣的特點(diǎn)針對(duì)性地提出了關(guān)聯(lián)矩陣的適應(yīng)性更新策略，關(guān)聯(lián)矩陣在滿足一定條件時(shí)進(jìn)行更新，以實(shí)時(shí)調(diào)整關(guān)聯(lián)矩陣的內(nèi)容。

(1)新增策略 該策略包含兩部分：

2)增加新的需求模式，服務(wù)模式。此時(shí),在服務(wù)日志中找到新增模式的匹配情況，并更新關(guān)聯(lián)矩陣。

(3)服務(wù)質(zhì)量變化策略 服務(wù)質(zhì)量發(fā)生變化會(huì)導(dǎo)致匹配度中約束滿足度發(fā)生變化，這時(shí)也需要對(duì)關(guān)聯(lián)矩陣中的匹配度進(jìn)行更新。

在關(guān)聯(lián)矩陣使用時(shí)，需定期判斷是否滿足上述策略。如滿足策略1或策略2，使用算法2對(duì)關(guān)聯(lián)矩陣進(jìn)行更新；如滿足策略3，對(duì)使用該服務(wù)的需求模式，服務(wù)模式對(duì)的匹配度進(jìn)行更新。當(dāng)需求模式，服務(wù)模式對(duì)在某情境下的匹配度降低到某一閾值時(shí)，在匹配中不予考慮，視為該對(duì)失效，但在關(guān)聯(lián)矩陣中保留數(shù)據(jù)，隨關(guān)聯(lián)矩陣進(jìn)行更新。

雙邊模式關(guān)聯(lián)矩陣的更新算法如算法2所示，從歷史記錄中取出需要更新的需求模式，服務(wù)模式對(duì)，讀取其PCA模型與Birch模型，將新的匹配記錄加入模型中并計(jì)算匹配度。

算法2雙邊模式關(guān)聯(lián)矩陣更新算法。

輸出:更新后的關(guān)聯(lián)矩陣A。

1 begin

2 用戶情境X′=?;匹配時(shí)間點(diǎn)D′=?

3 foreach服務(wù)方案si∈solution do

4 foreach(rpj,spk)∈sido

/* X′[(rpj,spk)]與D′[(rpj,spk)]初始為空列表*/

5 if(rpj,spk)∈rpsp and匹配時(shí)間點(diǎn)大于上次更新時(shí)間do

6 X′[(rpj,spk)]←X′[(rpj,spk)]+ci//ci為si中用戶情境

7 D′[(rpj,spk)]←D′[(rpj,spk)]+ti//ti為si中匹配時(shí)間點(diǎn)

8 end

9 end

10 foreach (rpj,spk)∈X′ do

13 if (rpi,spj)?X do

16 end else

17 Cij←X[(rpj,spk)]

20 計(jì)算匹配度，并將聚類結(jié)果與匹配度加入A中

21 end

22 返回A

23 end

3 基于供需雙邊模式的服務(wù)方案構(gòu)建算法

服務(wù)方案構(gòu)建算法的目標(biāo)是獲得優(yōu)化的服務(wù)執(zhí)行方案Solution，

Solution=Info,SSP,Process,Q。

其中：Info為基本信息；SSP為方案中使用的服務(wù)模式SP與原子服務(wù)集合S；Process為服務(wù)流程；Q為質(zhì)量指標(biāo)。如圖1所示，構(gòu)建算法流程分為需求匹配、服務(wù)模式與原子服務(wù)選擇、生成服務(wù)流程3個(gè)步驟。

3.1 需求匹配方法

需求匹配的目標(biāo)是利用歷史需求信息，使用需求模式去覆蓋意圖樹(shù)的過(guò)程。其結(jié)果包含可被需求模式匹配的意圖集(體現(xiàn)為對(duì)應(yīng)的需求模式集)和不能被匹配的意圖集兩部分。

匹配算法采用基于優(yōu)先規(guī)則的迭代方式，逐步使用需求模式覆蓋意圖樹(shù)中未被覆蓋的意圖，即使需求模式中包含的意圖和需求樹(shù)中待匹配意圖完全相同，且需求模式中的約束包含待匹配意圖的約束。

需求匹配優(yōu)先規(guī)則的順序如下：

(1)優(yōu)先考慮覆蓋率更高的匹配方案；

(2)優(yōu)先考慮使用更少需求模式的匹配方案；

(3)優(yōu)先考慮需求模式平均使用頻率更高的匹配方案。

限于篇幅，匹配算法流程不再贅述。

3.2 構(gòu)建服務(wù)方案

在得到需求模式集和單獨(dú)的意圖集之后，該環(huán)節(jié)基于雙邊模式關(guān)聯(lián)矩陣和服務(wù)的描述信息，利用算法得到優(yōu)化后的服務(wù)方案。

構(gòu)建步驟分為以下兩個(gè)部分：

(1)對(duì)需求進(jìn)行需求匹配。根據(jù)需求匹配的結(jié)果和匹配情境，從關(guān)聯(lián)矩陣中找到與各需求模式對(duì)應(yīng)的匹配度較高的服務(wù)模式集，并在服務(wù)庫(kù)中找到與各單獨(dú)意圖對(duì)應(yīng)服務(wù)功能的服務(wù)集。如果某需求模式找不到對(duì)應(yīng)的服務(wù)模式，則對(duì)該需求模式利用更小粒度的需求模式進(jìn)行需求匹配，并重復(fù)以上步驟。

(2) 在上述集合當(dāng)中選擇合適的服務(wù)模式和服務(wù)，并構(gòu)建服務(wù)流程。利用匹配算法，最終得到滿足約束且優(yōu)化目標(biāo)最優(yōu)的服務(wù)方案。

由于在不同實(shí)際應(yīng)用場(chǎng)景中，服務(wù)數(shù)量和需求數(shù)量規(guī)模不同，追求的質(zhì)量與效率的偏好不同，因此，本文提出3類算法，并將雙邊模式以及關(guān)聯(lián)矩陣融入其中：精確算法(Bilateral Pattern Precise Algorithm, BP-PA)，適用于數(shù)據(jù)規(guī)模較小且用戶需要最優(yōu)解的場(chǎng)景；貪心算法(Bilateral Pattern Approximation Algorithm, BP-AA)，適用于數(shù)據(jù)規(guī)模適中且用戶對(duì)算法效率要求較高的場(chǎng)景；人工蜂群算法(Bilateral Pattern Artificial Bee Colony Algorithm, BP-ABC)，適用于數(shù)據(jù)規(guī)模較大且用戶需要質(zhì)量較好解的場(chǎng)景。

BP-PA算法通過(guò)遍歷每個(gè)服務(wù)方案來(lái)獲得最優(yōu)解，在實(shí)際應(yīng)用中通常使用各種不同的剪枝算法來(lái)提高運(yùn)行速度，如：若當(dāng)前遍歷的部分服務(wù)方案已經(jīng)劣于當(dāng)前最優(yōu)方案，不再繼續(xù)對(duì)該部分服務(wù)方案的后續(xù)服務(wù)進(jìn)行遍歷等。

BP-ABC算法(算法5)使用的可行性準(zhǔn)則定義如下：如果解x1和解x2滿足以下3點(diǎn)之一，則稱解x1支配解x2：①解x1滿足約束而解x2不滿足約束；②解x1和解x2均不滿足約束，但x1總約束滿足度較大；③解x1和解x2均滿足約束，但解x1帕累托支配解x2。

算法3精確算法(BP-PA)。

輸入:用戶意圖樹(shù)iTree，需求模式集RP，服務(wù)模式集SP和原子服務(wù)集S，關(guān)聯(lián)矩陣A，用戶需求情境ctk;

輸出:最優(yōu)服務(wù)方案x*。

1 begin

2 x*←?

3 調(diào)用需求匹配算子reqMatch，利用RP覆蓋iTree，獲得需求匹配結(jié)果：需求模式集RP′，未能匹配的意圖集R′(見(jiàn)3.1節(jié))。

4 從A中根據(jù)ctk找到子矩陣Ak并根據(jù)RP′中各rpi找到對(duì)應(yīng)的服務(wù)模式集SPi，在S中找到R′中意圖rj與服務(wù)功能對(duì)應(yīng)的服務(wù)集Sj。

5 對(duì)SPi中服務(wù)模式以及Sj中原子服務(wù)按照優(yōu)化目標(biāo)排序

6 foreach服務(wù)模式spim∈SPi與原子服務(wù)sjn∈Sjdo

7 調(diào)用服務(wù)流程構(gòu)建算子constructingProcess獲得服務(wù)方案x

8 if x滿足約束且優(yōu)化目標(biāo)優(yōu)于x*

9 x*←x

10 end else continue

11 end

12 返回x*

13 end

算法4貪心算法(BP-AA)。

輸入:用戶意圖樹(shù)iTree，需求模式集RP，服務(wù)模式集SP和原子服務(wù)集S，關(guān)聯(lián)矩陣A，用戶需求情境ctk;

輸出:最優(yōu)服務(wù)方案x*。

1 begin

2 x*←?; success←0; i←0;初始化循環(huán)次數(shù)N

3 調(diào)用需求匹配算子reqMatch，利用RP覆蓋iTree，獲得需求匹配結(jié)果：需求模式集RP′，未能匹配的意圖集R′(見(jiàn)3.1節(jié))。

4 從A中根據(jù)ck找到子矩陣Ak并根據(jù)RP′各rpi找到對(duì)應(yīng)的服務(wù)模式集SPi，在S中找到R′中意圖rj與服務(wù)功能對(duì)應(yīng)的服務(wù)集Sj。

5 對(duì)SPi中服務(wù)模式以及Sj中原子服務(wù)按照優(yōu)化目標(biāo)排序

6 while success=0 and i

7 根據(jù)貪心準(zhǔn)則選擇服務(wù)模式進(jìn)行替換

8 調(diào)用服務(wù)流程算子buildingProcess獲得服務(wù)方案x*

9 i←i+1

10 if x*滿足約束

11 success←1

12 end else continue

13 end

14 返回x*

15 end

算法5人工蜂群算法(BP-ABC)。

輸入:用戶意圖樹(shù)iTree，需求模式集RP，服務(wù)模式集SP和原子服務(wù)集S，關(guān)聯(lián)矩陣A，用戶需求情境ctk;

輸出:最優(yōu)服務(wù)方案x*。

1 begin

2 x*←?;j←0;初始化循環(huán)次數(shù)MCN;偵察蜂參數(shù)limit;食物源個(gè)數(shù)SN；跟隨蜂個(gè)數(shù)d

3 調(diào)用需求匹配算子reqMatch，利用RP覆蓋iTree，獲得需求匹配結(jié)果：需求模式集RP′，未能匹配的意圖集R′(見(jiàn)3.1節(jié))。

4 從A中根據(jù)ck找到子矩陣Ak并根據(jù)RP′各rpi找到對(duì)應(yīng)的服務(wù)模式集SPi，在S中找到R′中意圖rj與服務(wù)功能對(duì)應(yīng)的服務(wù)集Sj。

5 根據(jù)SPi與Sj隨機(jī)生成SN個(gè)服務(wù)方案xi

6 foreach j

7 foreach xido

8 隨機(jī)選擇xi中1維用其他服務(wù)模式替換。

11 counti←0

12 end else counti←counti+1

13 隨機(jī)選擇d個(gè)服務(wù)方案，使用NSGA Ⅱ多目標(biāo)優(yōu)化法優(yōu)化

14 foreach xido

15 if counti>limit do

16 隨機(jī)生成服務(wù)方案xi

17 end else continue

18 end

19 記錄當(dāng)前最優(yōu)的服務(wù)方案x*;j←j+1

20 end

21 返回x*

22 end

3.3 生成服務(wù)流程

本節(jié)介紹將選擇后的服務(wù)模式和原子服務(wù)構(gòu)造成一個(gè)流程的方法。在服務(wù)方案歷史執(zhí)行流程中對(duì)每個(gè)服務(wù)模式和服務(wù)加上時(shí)間戳，用來(lái)記錄服務(wù)與服務(wù)模式間的執(zhí)行順序。順序執(zhí)行的服務(wù)/服務(wù)模式，時(shí)間戳依次加1，并行執(zhí)行的，時(shí)間戳相同。

若將P中的服務(wù)模式和服務(wù)表示為圖中的點(diǎn)，大于1的值表示為圖中的邊，可以將P表示成一張有向圖。因?yàn)镻中服務(wù)模式間的偏序關(guān)系可能存在環(huán)，所以使用貪心算法去掉環(huán)，使用的貪心策略為：去掉Σpij最大的spi的入邊。去環(huán)后的P即為一個(gè)合理的服務(wù)流程。服務(wù)流程構(gòu)建算子constructingProcess如算法6所示。

算法6服務(wù)流程構(gòu)建算子constructingProcess。

輸入:服務(wù)模式集SP，服務(wù)集S，順序比矩陣P;

輸出:服務(wù)流程s*。

1 begin

2 t←0;SP′←SP+S;ti←0為各服務(wù)模式/服務(wù)的時(shí)間戳

3 while SP′≠? do

4 foreach spi∈SP′ and spj∈SP′ do

5 si←0

6 if pij<1 do

7 si←si+1

8 end

9 end

10 將si最小的spi放入集合SP″中，s←minsi

11 if s=0 do

12 foreach spi∈SP″ do

13 ti←t

14 SP′←SP′SP″

15 end else

16 foreach spi∈SP″ and spj∈SP′ do

17 spm←Σpij最大的服務(wù)模式

18 if pmj<1 do

19 pmj←1; pjm←1

20 end

21 SP′←SP′{spm}

22 end

23 t←t+1

24 end

25 返回依據(jù)時(shí)間戳升序原則生成的服務(wù)流程s*

26 end

4 實(shí)驗(yàn)與分析

本章將對(duì)所設(shè)計(jì)的基于雙邊模式的3個(gè)服務(wù)方案構(gòu)建算法進(jìn)行實(shí)驗(yàn)分析，并與對(duì)應(yīng)不采用模式的傳統(tǒng)算法進(jìn)行比較。此外，對(duì)所提雙邊模式關(guān)聯(lián)矩陣的更新策略進(jìn)行實(shí)驗(yàn)，分析其有效性。

4.1 實(shí)驗(yàn)環(huán)境

本文選擇公開(kāi)服務(wù)數(shù)據(jù)集CrossWOZ[32]作為實(shí)驗(yàn)數(shù)據(jù)集，CrossWOZ是一個(gè)大規(guī)模的中文跨領(lǐng)域數(shù)據(jù)集。它包含5個(gè)領(lǐng)域的6 012個(gè)需求對(duì)話及相關(guān)服務(wù)資源，服務(wù)資源包括：酒店、餐廳、景點(diǎn)、地鐵和出租車(chē)5大類。下面是數(shù)據(jù)集提供的一條需求對(duì)話示例。

CrossWOZ

usr:你好，可以幫我推薦一個(gè)評(píng)分是4.5分以上的景點(diǎn)嗎？

Hello, could you recommend an attraction with a rating of 4.5 or higher?

sys:天安門(mén)城樓，簋街小吃和北京歡樂(lè)谷都是很不錯(cuò)的地方呢。

Tiananmen, Gui Street, andBeiJjing Happy Velleyare very nice places.

usr:我喜歡北京歡樂(lè)谷,你知道這個(gè)景點(diǎn)周邊的酒店都是什么嗎?

I likeBeijing Happy Valley. What hotels are around this attrraction?

sys:那可多了，有A酒店，B酒店，C酒店。

There are many, such as hotel A, hotel B, and hotel C.

usr:太好了，我正打算在景點(diǎn)附近找個(gè)酒店住宿呢，知道哪家評(píng)分是4分以上，提供叫醒服務(wù)的不？

Great! I am planning to find a hotel to stay near the attraction. Which one has a rating of 4 or higher and offers wake-up call service？

針對(duì)本文所提方法的特點(diǎn)，對(duì)數(shù)據(jù)作以下處理，以形成服務(wù)、服務(wù)模式、需求、需求模式和雙邊模式關(guān)聯(lián)矩陣等實(shí)驗(yàn)數(shù)據(jù)：

(1)將數(shù)據(jù)集中的對(duì)話轉(zhuǎn)化為意圖樹(shù)作為需求數(shù)據(jù)，共6 012棵意圖樹(shù)；數(shù)據(jù)集中服務(wù)資源作為可用服務(wù)，為增加可用服務(wù)規(guī)模，以驗(yàn)證算法的求解效率，增加華為應(yīng)用商店中評(píng)分較高的地圖與天氣預(yù)報(bào)服務(wù)，共2 569個(gè)服務(wù)。

(2)隨機(jī)選取1 000棵意圖樹(shù)作為訓(xùn)練集，挖掘得到需求模式集；從訓(xùn)練集中生成對(duì)應(yīng)服務(wù)方案集，從中挖掘得到服務(wù)模式集。

(3)對(duì)所選的1 000棵意圖樹(shù)形成的訓(xùn)練集進(jìn)行需求模式與需求的匹配，根據(jù)匹配結(jié)果中包含的需求模式在服務(wù)方案中對(duì)應(yīng)的服務(wù)模式，構(gòu)造雙邊模式關(guān)聯(lián)矩陣。

4.2 基于雙邊模式的服務(wù)方案構(gòu)建算法的實(shí)驗(yàn)與分析

對(duì)BP-PA、BP-AA、BP-ABC三個(gè)本文所提出的基于雙邊模式的服務(wù)方案構(gòu)造算法，以及S-PA、S-AA、S-ABC三個(gè)對(duì)應(yīng)的不使用雙邊模式的算法進(jìn)行對(duì)比。將CrossWOZ數(shù)據(jù)集中除1 000條訓(xùn)練集之外的其余5 012條數(shù)據(jù)作為驗(yàn)證集，從可用服務(wù)數(shù)量、需求復(fù)雜度(所含意圖的數(shù)量)、雙邊模式關(guān)聯(lián)矩陣在匹配中可用程度(通過(guò)需求模式對(duì)需求的覆蓋程度來(lái)度量)3方面輸入數(shù)據(jù)的變化進(jìn)行實(shí)驗(yàn)分析，用算法執(zhí)行時(shí)間和解質(zhì)量?jī)蓚€(gè)指標(biāo)進(jìn)行對(duì)比。其中解質(zhì)量指標(biāo)采用當(dāng)前對(duì)比算法所得解同最優(yōu)解的比值(解質(zhì)量比)度量，如式(12)所示：

(12)

為公平對(duì)比，進(jìn)行解質(zhì)量比對(duì)比時(shí)，BP-PA和S-PA算法所生成服務(wù)方案的解質(zhì)量比是在執(zhí)行時(shí)間8 s下獲得；BP-ABC和S-ABC算法所生成服務(wù)方案的解質(zhì)量比是在執(zhí)行時(shí)間0.5 s下獲得；BP-AA和S-AA算法的解質(zhì)量比的獲得沒(méi)有時(shí)間限制。

進(jìn)行執(zhí)行時(shí)間對(duì)比時(shí)，BP-PA和S-PA算法的執(zhí)行時(shí)間是在所生成服務(wù)方案的解質(zhì)量比為0.95的前提下獲得；BP-ABC和S-ABC算法的執(zhí)行時(shí)間是在所生成服務(wù)方案的解質(zhì)量比為0.98的前提下獲得；BP-AA和S-AA算法的執(zhí)行時(shí)間沒(méi)有解質(zhì)量比限制。

針對(duì)S-ABC和BP-ABC算法，運(yùn)行10次，取平均值。

(1)不同可用服務(wù)數(shù)量下實(shí)驗(yàn)結(jié)果

本節(jié)在可用服務(wù)數(shù)量為100～2 500時(shí)對(duì)6個(gè)算法進(jìn)行對(duì)比，以驗(yàn)證各算法在不同可用服務(wù)數(shù)據(jù)規(guī)模下的求解速度和求解質(zhì)量，結(jié)果如圖7與圖8所示。由于執(zhí)行時(shí)間數(shù)據(jù)差異較大，為了能夠清晰地加以區(qū)分，將2個(gè)精確算法的執(zhí)行時(shí)間單獨(dú)列出。

由圖7與圖8可見(jiàn)，無(wú)論是解質(zhì)量還是算法效率，使用雙邊模式下均優(yōu)于不使用雙邊模式，且服務(wù)數(shù)量越多，數(shù)據(jù)規(guī)模越大，使用雙邊模式的表現(xiàn)越好。由于數(shù)據(jù)的關(guān)系，在服務(wù)數(shù)量為1 800時(shí)，不使用雙邊模式的精確算法的解質(zhì)量比發(fā)生突變，這是因?yàn)樵谠摲秶鷥?nèi)出現(xiàn)了一個(gè)質(zhì)量較好的服務(wù)，但是由于執(zhí)行時(shí)間被限制在8 s，導(dǎo)致精確算法并沒(méi)有搜索到該服務(wù)就已經(jīng)停止。由于其他算法能搜索到該服務(wù)，故此點(diǎn)為異常點(diǎn)。

(2)不同意圖樹(shù)節(jié)點(diǎn)數(shù)量下實(shí)驗(yàn)結(jié)果

本節(jié)在意圖樹(shù)節(jié)點(diǎn)數(shù)量為2～7時(shí)對(duì)6種算法進(jìn)行實(shí)驗(yàn)，以驗(yàn)證各算法在不同需求復(fù)雜程度下的求解速度和求解質(zhì)量，結(jié)果如圖9與圖10所示。

從圖9和圖10可見(jiàn)，無(wú)論是解質(zhì)量還是算法效率，使用雙邊模式的算法均優(yōu)于不使用雙邊模式，且意圖樹(shù)節(jié)點(diǎn)數(shù)量越多，需求越復(fù)雜，使用雙邊模式的表現(xiàn)越好。觀察不使用雙邊模式的人工蜂群算法在解質(zhì)量比的表現(xiàn)，可以發(fā)現(xiàn)在意圖樹(shù)節(jié)點(diǎn)數(shù)量在7時(shí)發(fā)生突變，原因是運(yùn)行時(shí)間0.5 s不足以讓算法收斂，得到滿意的解。

(3)不同需求模式覆蓋比例下實(shí)驗(yàn)結(jié)果

本節(jié)在需求模式覆蓋比例不同時(shí)對(duì)6種算法進(jìn)行實(shí)驗(yàn)，以驗(yàn)證各算法在關(guān)聯(lián)矩陣的可用程度不同時(shí)的求解速度和求解質(zhì)量。如實(shí)驗(yàn)(2)所示，由于意圖樹(shù)規(guī)模對(duì)實(shí)驗(yàn)結(jié)果有較大影響，選擇使用節(jié)點(diǎn)數(shù)量為5的意圖樹(shù)作為實(shí)驗(yàn)集，結(jié)果如圖11與圖12所示。

如圖11與圖12所示，在解質(zhì)量方面，使用雙邊模式的算法要優(yōu)于不使用雙邊模式的算法，且需求模式覆蓋比例越高，使用雙邊模式的算法解質(zhì)量比越好。在算法效率方面，當(dāng)需求模式覆蓋比例為0(關(guān)聯(lián)矩陣不發(fā)揮作用)時(shí)，使用雙邊模式的算法退化為不使用雙邊模式的算法，由于使用雙邊模式的算法需要進(jìn)行需求匹配，算法執(zhí)行時(shí)間要多于不使用雙邊模式的算法，隨著需求模式覆蓋比例的增加，使用雙邊模式的算法在匹配效率方面逐漸優(yōu)于不使用雙邊模式的算法。

(4)3種求解策略對(duì)比

本實(shí)驗(yàn)中BP-PA和BP-ABC算法的執(zhí)行時(shí)間是在所生成服務(wù)方案的解質(zhì)量比為0.97的前提下獲得的，實(shí)驗(yàn)結(jié)果如圖13所示。當(dāng)服務(wù)規(guī)模較小(100～200)，在獲得近似解質(zhì)量比的情況下，3個(gè)算法的時(shí)間差距不大(0.1～0.25 s)，因此選擇BP-PA算法以得到最優(yōu)的解質(zhì)量比；在服務(wù)規(guī)模中等(300～1 500)時(shí)，BP-PA算法執(zhí)行時(shí)間較長(zhǎng)(0.5～1.25 s)，而B(niǎo)P-ABC算法求解時(shí)間較BP-AA算法長(zhǎng)，因此選擇BP-AA算法平衡算法速度與解質(zhì)量；在服務(wù)規(guī)模較大(1 600～2 500)時(shí)，BP-ABC和BP-AA的求解速度相互起伏，無(wú)法通過(guò)平均時(shí)間判定算法優(yōu)劣，因此本文對(duì)服務(wù)數(shù)量在1 600～2 500，BP-ABC和BP-AA兩個(gè)算法的箱形圖(如圖14)進(jìn)行分析。

對(duì)兩組數(shù)據(jù)進(jìn)行t檢驗(yàn)，結(jié)果如表1所示。

表1 服務(wù)數(shù)量在1 600～2 500時(shí)BP-ABC和BP-AA算法的執(zhí)行時(shí)間t檢驗(yàn)

由于樣本數(shù)量大，本文選擇顯著度水平α=0.025，當(dāng)p<α?xí)r，拒絕零假設(shè)，即有顯著差異。當(dāng)服務(wù)數(shù)量為2 300時(shí)，兩組數(shù)據(jù)均值有顯著差異，這時(shí)BP-ABC的均值為0.245，BP-AA的均值為0.303，前者的平均執(zhí)行時(shí)間要少于后者。對(duì)于其他服務(wù)數(shù)量，均值無(wú)顯著差異，而B(niǎo)P-ABC的矩形箱明顯偏下，大部分需求的執(zhí)行時(shí)間優(yōu)于BP-AA，因此優(yōu)先選擇BP-ABC提升求解速度。

4.3 關(guān)聯(lián)矩陣更新策略實(shí)驗(yàn)與分析

首先對(duì)使用關(guān)聯(lián)矩陣更新策略的必要性進(jìn)行驗(yàn)證。實(shí)驗(yàn)內(nèi)容為當(dāng)總服務(wù)方案數(shù)量在0～200 000時(shí)更新關(guān)聯(lián)矩陣并記錄執(zhí)行時(shí)間，結(jié)果如圖15所示。

由實(shí)驗(yàn)可知，更新時(shí)間與總方案數(shù)量基本呈線性關(guān)系，當(dāng)日志中的方案數(shù)量為25 000時(shí)，更新時(shí)間為125 s，但當(dāng)方案數(shù)量很大時(shí)(超過(guò)175 000)，日志中方案不斷累積，更新時(shí)間會(huì)達(dá)到1 000 s甚至更多，關(guān)聯(lián)矩陣更新代價(jià)巨大。由此可見(jiàn)，有必要對(duì)關(guān)聯(lián)矩陣采用動(dòng)態(tài)更新頻率和策略。

下面對(duì)關(guān)聯(lián)矩陣更新策略的有效性進(jìn)行驗(yàn)證。由于數(shù)據(jù)集中沒(méi)有時(shí)間信息，本文通過(guò)百度指數(shù)網(wǎng)站收集2019年各景區(qū)逐日網(wǎng)絡(luò)關(guān)注度數(shù)據(jù)來(lái)模擬一年中各景區(qū)每日的訪問(wèn)量，模擬每日各需求出現(xiàn)的數(shù)量。首先使用精確算法生成最優(yōu)解并挖掘服務(wù)模式，再根據(jù)精確解中的每個(gè)景區(qū)，得到對(duì)應(yīng)需求每日被提出的次數(shù)。因?yàn)閿?shù)據(jù)中沒(méi)有服務(wù)QoS變化的信息，所以本文不對(duì)策略3進(jìn)行實(shí)驗(yàn)驗(yàn)證。本文假設(shè)每次更新的總方案數(shù)量相同。如2.4.2節(jié)所述，當(dāng)某需求模式，服務(wù)模式對(duì)在某情境下的匹配度降低到一定程度時(shí)，在匹配中不予考慮，且4.2節(jié)已經(jīng)通過(guò)實(shí)驗(yàn)證明使用雙邊模式生成服務(wù)方案在效率和匹配質(zhì)量上要優(yōu)于不使用雙邊模式，所以本節(jié)以匹配成功率和更新的次數(shù)來(lái)度量更新策略的效果，匹配成功率越高，更新次數(shù)越少，策略越優(yōu)。

(1)策略1：新增策略

本節(jié)對(duì)策略1的參數(shù)a進(jìn)行分析，結(jié)果如表2所示?？梢园l(fā)現(xiàn)，隨著參數(shù)a的降低，匹配成功率增大，更新次數(shù)增多，但是當(dāng)a過(guò)小時(shí)，更新次數(shù)迅速增加但匹配成功率變化不大，策略效果達(dá)到瓶頸。綜合考慮，本文選擇a=0.1作為策略1的參數(shù)。

表2 策略1參數(shù)設(shè)置

(2)策略2：突變策略

對(duì)策略2的參數(shù)b進(jìn)行分析，結(jié)果如表3所示。可以發(fā)現(xiàn)，隨著b的增大，匹配成功率增大，更新次數(shù)增多。與參數(shù)a相似，當(dāng)b過(guò)大時(shí)，更新次數(shù)迅速增加但是匹配成功率變化不大。綜合考慮，本文選擇b=0.8作為策略2的參數(shù)。

表3 策略2參數(shù)設(shè)置

(3)同時(shí)考慮兩種更新策略

如表4的4～6行所示，同時(shí)使用兩種策略比僅使用一種策略的匹配成功率高，且更新次數(shù)相近，說(shuō)明同時(shí)使用兩種策略要優(yōu)于單獨(dú)使用一種策略。觀察表的前3行與后3行，可以發(fā)現(xiàn)定期更新策略要劣于使用本文提出的關(guān)聯(lián)矩陣更新策略。因此，本文提出的關(guān)聯(lián)矩陣更新策略在匹配成功率與更新次數(shù)上表現(xiàn)較優(yōu)，在關(guān)聯(lián)矩陣使用過(guò)程中有較好的效果。

表4 關(guān)聯(lián)矩陣更新策略實(shí)驗(yàn)驗(yàn)證

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

針對(duì)服務(wù)互聯(lián)網(wǎng)中的服務(wù)供需匹配這類復(fù)雜優(yōu)化問(wèn)題，本文基于模塊化的思想提出了基于供需雙邊模式的服務(wù)匹配問(wèn)題模型。當(dāng)服務(wù)日志中已經(jīng)存在了一定的歷史服務(wù)方案，利用領(lǐng)域先驗(yàn)知識(shí)挖掘需求模式與服務(wù)模式，增加匹配粒度，提高重用效率。設(shè)計(jì)多維關(guān)聯(lián)矩陣建立需求模式和服務(wù)模式的關(guān)系，提出自適應(yīng)關(guān)聯(lián)矩陣更新策略動(dòng)態(tài)調(diào)整更新頻率，進(jìn)一步提高匹配效率。針對(duì)3種不同場(chǎng)景設(shè)計(jì)3種算法構(gòu)建服務(wù)方案，通過(guò)對(duì)各算法的求解質(zhì)量與執(zhí)行時(shí)間的對(duì)比，證明所提的使用雙邊模式的算法(以S-ABC算法與BP-ABC為例)在時(shí)間上提高了41.2%，在質(zhì)量上提高了1.12%。通過(guò)對(duì)關(guān)聯(lián)矩陣更新策略的匹配成功率與更新次數(shù)的對(duì)比，證明本文提出的關(guān)聯(lián)矩陣自適應(yīng)更新策略(與每14天更新作比較)在匹配成功率上提高了7.9%。

在未來(lái)工作中，將進(jìn)一步研究關(guān)聯(lián)矩陣的多維數(shù)學(xué)模型建模，優(yōu)化存儲(chǔ)和查詢的數(shù)據(jù)結(jié)構(gòu)，索引技術(shù)等內(nèi)容，提升檢索效率，降低存儲(chǔ)空間，解決矩陣稀疏性等問(wèn)題。同時(shí)，考慮將方法擴(kuò)展至分布式環(huán)境中，需求與需求模式、服務(wù)與服務(wù)模式以及關(guān)聯(lián)矩陣將如何存儲(chǔ)，節(jié)點(diǎn)間應(yīng)以何種策略協(xié)作以完成全局目標(biāo)構(gòu)建優(yōu)化的服務(wù)解決方案將是今后的研究重點(diǎn)。