徐錢元，曹 健，王 磊

（上海交通大學計算機科學與工程系，上海201100）

1 引言

目前軟件服務(wù)作為網(wǎng)絡(luò)上信息處理能力的一種抽象形式得到了廣泛關(guān)注。面向服務(wù)的計算SOC（Service Oriented Computing）［1］泛指以軟件服務(wù)為基礎(chǔ)構(gòu)造應(yīng)用這一新開發(fā)范型相關(guān)的方法、技術(shù)、規(guī)范、理論和支撐環(huán)境，業(yè)已成為IT領(lǐng)域當前最熱門的話題之一。研究者們普遍認為，相互協(xié)同的軟件服務(wù)將成為下一代因特網(wǎng)的核心之一［2］。為了使軟件服務(wù)具有自主協(xié)同的能力，一個自然的選擇就是軟件服務(wù)的Agent化，或者說是使Agent服務(wù)化，因為Agent具有的自治性、社會性、反應(yīng)性和主動性等特性是目前的服務(wù)所不具有的。規(guī)劃（Plan）作為Agent的重要組成部分，它將一系列原子活動組合起來形成更完整的活動。服務(wù)A－gent的能力也取決于其包含的服務(wù)規(guī)劃。為了開發(fā)服務(wù) Agent，可以利用JADE、JACK、JADEX等遵從FIPA規(guī)范的Agent平臺。然而，這些主流Agent平臺對規(guī)劃庫的管理都比較簡單，一般只是作為存儲規(guī)劃模型的集合，沒有考慮規(guī)劃庫作為規(guī)劃知識的存儲及優(yōu)化問題。本文提出了一種規(guī)劃庫的優(yōu)化方法，依據(jù)其行為規(guī)律動態(tài)優(yōu)化其中的規(guī)劃模型，從而提高搜索規(guī)劃、生成規(guī)劃的效率。

本文的安排如下：第2節(jié)簡要介紹了服務(wù)A-gent的模型及其運行機制；在此基礎(chǔ)上給出了服務(wù)規(guī)劃模型和規(guī)劃庫模型，為本文的研究奠定基礎(chǔ)。第3節(jié)給出了規(guī)劃模型的結(jié)構(gòu)化樹表示方法，它是后面優(yōu)化算法的基礎(chǔ)。第4節(jié)給出了兩個規(guī)劃之間公共部分的提取方法。第5節(jié)介紹了規(guī)劃庫的優(yōu)化方法。第6節(jié)對算法的復雜性進行了分析并進行了實驗。最后一節(jié)提出了進一步的研究方向。

2 服務(wù)Agent模型及其規(guī)劃庫

為了實現(xiàn)Agent模型，人們提出了BDI、AOP、3APL、SOAR等模型，其中BDI模型受到最廣泛的關(guān)注。BDI稱為信念－期望－意圖模型，Rao和Georgeff設(shè)計了BDI［3］模型的可執(zhí)行程序，將BDI演變成了信念、目標和規(guī)劃，其中，Agent信念集合描述了Agent所認知的知識，也是Agent內(nèi)部可以訪問的數(shù)據(jù)，抽象來說可以認為是Agent對知識的整體視圖；Agent目標是指Agent所要達成的目的，包括修改Agent所認知的世界，接近于BDI中的意圖模型；Agent規(guī)劃則是Agent內(nèi)部執(zhí)行能力的體現(xiàn)，根據(jù)目標的到來，Agent內(nèi)部通過一套控制機制選擇規(guī)劃去執(zhí)行，從而完成目標。通常，Agent將多個規(guī)劃保存在規(guī)劃庫中。

服務(wù)Agent的規(guī)劃模型是一組服務(wù)的有序集合，這些服務(wù)之間存在邏輯依賴關(guān)系和數(shù)據(jù)依賴關(guān)系。從模型的具體表現(xiàn)形式看，這些依賴關(guān)系和服務(wù)集合構(gòu)成了一個有向非循環(huán)圖（DAG），它由順序結(jié)構(gòu)、并行結(jié)構(gòu)和選擇結(jié)構(gòu)三種規(guī)劃的控制結(jié)構(gòu)構(gòu)成，如圖1所示。

圖1中B1組成了一個順序結(jié)構(gòu)，B2組成了一個并行結(jié)構(gòu)，而B3是一個順序結(jié)構(gòu)，B4是一個選擇結(jié)構(gòu)。

Figure 1 Map of service plan圖1 服務(wù)規(guī)劃示意圖

服務(wù)Agent規(guī)劃庫是一組規(guī)劃的有序集合。當特定事件發(fā)生后，由規(guī)劃調(diào)度引擎決定服務(wù)A-gent如何構(gòu)造規(guī)劃以處理事件。一般來說，規(guī)劃調(diào)度引擎的處理有以下幾種方式：

（1）規(guī)劃庫中有一個現(xiàn)有的規(guī)劃可以滿足其要求。

（2）將幾個規(guī)劃組合在一起滿足其要求。

（3）沒有現(xiàn)成的組合，嘗試根據(jù)現(xiàn)有的服務(wù)組合一個新的規(guī)劃來滿足需求。

（4）無解，無法滿足需求。

其中方式（1）是規(guī)劃庫中對于需求的規(guī)劃搜索問題；方式（2）和方式（3）是自動規(guī)劃問題，其區(qū)別在于方式（2）著重于規(guī)劃之間的再組合，方式（3）根據(jù)活動生成新的規(guī)劃。

因為規(guī)劃調(diào)度是一種非常消耗資源的工作，如果不能對規(guī)劃庫有所優(yōu)化，那么當同樣或者類似的需求到來時，服務(wù)Agent調(diào)度引擎只能重復地同樣耗時地工作。所以，本文提出一種規(guī)劃庫的優(yōu)化方法，在按方式（2）和方式（3）執(zhí)行時，可以提高生成規(guī)劃的速度。即將多個規(guī)劃中的相同部分提取出來單獨存儲，一方面可以減少存儲空間，另一方面也可以保證規(guī)劃生成的效率。

提取規(guī)劃中的相同部分與流程復用的研究類似。在流程復用方面，國內(nèi)外學者近年來進行了相關(guān)的研究工作。龔曉慶等［4］提出了基于領(lǐng)域本體檢索工作流模板的方法。在流程異同方面，也有基于流程模型進行挖掘的方法，譬如諸葛海［5］提出的基于圖節(jié)點的不精確流程匹配方法。也有學者基于Petri網(wǎng)對流程模型進行分析［6，7］，不過Petri網(wǎng)也有其自身的不足［8］。這些方法針對的是兩個流程之間的比較。還有學者從流程日志這個視角切入，比如文獻［9］中給出的方法等，但是其效率較低。與流程重用相關(guān)的更一般的是DAG的子圖檢索問題研究，有著名的Clique方法，包括Koch［10］給出的改進算法能更有效率地檢索公共子圖，雖然查找效率比較高，但是也只能做一一的比較，不能推廣到多個規(guī)劃流程之間的比較。

3 規(guī)劃模型的結(jié)構(gòu)樹表達

服務(wù)Agent的規(guī)劃從拓撲結(jié)構(gòu)上看，是由一組DAG圖的活動組成。本節(jié)給出兩個服務(wù)Agent中的規(guī)劃，兩個規(guī)劃都會調(diào)用若干本地服務(wù)活動和Web服務(wù)活動完成一個旅客的訂票。

一個是旅客預(yù)訂火車票的規(guī)劃（如圖2所示），另一個是旅客預(yù)訂飛機票的規(guī)劃（如圖3所示）。

在這兩個規(guī)劃模型中，其中預(yù)訂火車票服務(wù)規(guī)劃模型比較簡單，查詢火車票是否有，如果有則預(yù)訂火車票。而預(yù)訂飛機票的服務(wù)規(guī)劃還要視天氣狀況而定是否要訂機票。

以上的規(guī)劃模型可以根據(jù)文獻［11］中的方法被唯一地分解為一棵結(jié)構(gòu)化流程樹PST（Process Structured Tree）。入口和出口都只有1或者0的結(jié)構(gòu)稱之為結(jié)構(gòu)流程塊。基本的活動是一個流程塊。按照三種邏輯結(jié)構(gòu)可以組成三種結(jié)構(gòu)化流程塊。同樣，這些流程塊還可以不斷進行組合，最終就會形成PST中的根流程塊（Root Block）。顯然，根流程塊會包含開始和結(jié)束活動，并且根流程塊一定是一個順序流程塊，第一個子流程塊是開始活動塊，末子流程塊是結(jié)束活動塊。其余活動則填充于之間。

圖2和圖3中的規(guī)劃模型的PST樹結(jié)構(gòu)如圖4和圖5所示。

4 規(guī)劃模型公共部分提取

上一節(jié)給出了將規(guī)劃轉(zhuǎn)換成PST樹的概念。但是，在兩個規(guī)劃中提取公共規(guī)劃并不是簡單地等同于在PST樹中尋找最大公共子樹。因為在PST樹中的非葉節(jié)點代表規(guī)劃的流程邏輯塊的節(jié)點，比如順序塊、并行塊、選擇塊等；而PST樹的葉子節(jié)點都是代表規(guī)劃的活動節(jié)點，比如開始節(jié)點、結(jié)束節(jié)點、A1、A2等。兩個規(guī)劃的最大公共規(guī)劃應(yīng)該是擁有最多活動的公共部分，而不是包含活動和邏輯節(jié)點的最大公共部分。

為了便于提取公共部分，我們引入了PST樹的字符串表示方法。PST樹字符串是經(jīng)過對PST樹進行深度優(yōu)先搜索，并且在搜索的每次遞歸都加上特殊符號＃形成的一組字符串，它是PST樹的另一種表達。預(yù)訂火車票規(guī)劃的PST樹對應(yīng)的PST樹分析串（PST Analysis Series）如下：

Figure 3 Service plan of booking air tickets圖3 預(yù)訂飛機票服務(wù)規(guī)劃

SB＃PA1＃A2＃A3＃＃A4＃MA5＃A6＃＃E＃

預(yù)訂飛機票規(guī)劃的PST樹形成的PST樹分析串（PST Analysis Series）如下：

SB＃A7＃MSPA1＃A2＃A3＃＃A8＃MA9＃A6＃＃A6＃＃E＃

在得到PST樹字符串后，求解公共部分的問題被轉(zhuǎn)化成了求字符串之間最大有效子串的問題。這里求的是有效的最大公共子串，因為很有可能在這兩個字符串中最大公共子串是由許多公共的符號“＃”以及各種控制塊的符號“S”、“M”、“P”所組成。為了使獲取到的公共部分僅僅包含最多的活動，我們給出如下兩個定義：

定義1 （平衡字符串）平衡字符串是滿足有效活動的數(shù)目大于或等于“?！白址麛?shù)目的字符串。

例如，PA1＃A2＃A3＃＃就是一個平衡字符串。平衡字符串對應(yīng)PST樹中的一棵子樹。

定義2 （最大有效字符串）最大有效字符串是滿足以下條件的子串：

（1）該串必須以非＃字符開始；

（2）該串第一個平衡字符串所包含的有效活動數(shù)比任何其余的公共分析串的首個平衡分析子串包含的有效活動數(shù)多。

定義2中的最大有效字符串對應(yīng)于本節(jié)所求兩個規(guī)劃之間的最大公共子規(guī)劃。

求兩個PST字符串之間公共最大有效字符串可以使用后綴樹的方法加以計算。首先構(gòu)造聯(lián)合分析序列如下：

CommonAnalyzeSeries＝

AnalyzeSeries1＄N1AnalyzeSeries2＄N2

其中參數(shù)N1、N2分別取當前規(guī)劃庫中該規(guī)劃所對應(yīng)的PlanID。則對于圖4和圖5對應(yīng)的規(guī)劃的聯(lián)合分析序列為：

因為我們已經(jīng)將服務(wù)Agent規(guī)劃中的邏輯節(jié)點和活動映射為字符串中的字符，所以在構(gòu)建后綴樹的時候，需要做一層反映射。在這里反映射的關(guān)鍵技術(shù)就是正則表達式。服務(wù)Agent規(guī)劃中活動和邏輯節(jié)點的正則表達式如下：

活動表達式：［A［0-9］＋｜B｜E］；

流程塊以及＃表達式：［P｜M｜S｜＃］；

連接符：＄［0-9］＋；

構(gòu)造出基于聯(lián)合分析序列的后綴樹有助于解決本節(jié)一開始提到的問題。首先給出基于PST樹分析串構(gòu)造后綴樹的方法（算法2），然后給出基于該方法構(gòu)造聯(lián)合分析序列后綴樹的算法（算法3）。因為構(gòu)造后綴樹的目的是便于檢索和存儲規(guī)劃的公共部分，所以需要對后綴樹的節(jié)點做一定的標注從而引導搜索算法。以下給出節(jié)點標注的兩個重要參數(shù)：

（1）節(jié)點有效活動數(shù)：后綴樹節(jié)點的有效活動數(shù)是指該節(jié)點到根節(jié)點的邊所對應(yīng)的分析串的首個平衡字符串中包含的活動數(shù)。

（2）節(jié)點的覆蓋數(shù)組和頻繁指數(shù)：在一棵分析用的后綴樹中，葉子節(jié)點到根節(jié)點的路徑代表一個完整的后綴，而非葉節(jié)點到根節(jié)點的路徑代表一個規(guī)劃片段。假設(shè)一個非葉節(jié)點下接N個不同葉子節(jié)點，這就表示該節(jié)點到根節(jié)點的路徑所代表的規(guī)劃片段是這N個子節(jié)點所對應(yīng)的規(guī)劃的公共片段。而為了區(qū)分和計算這些節(jié)點對應(yīng)規(guī)劃片段的公共性的多寡，提出了節(jié)點的覆蓋數(shù)組和頻繁指數(shù)的參數(shù)。覆蓋數(shù)組是由布爾量組成的數(shù)組，每一位表示節(jié)點對應(yīng)規(guī)劃片段是否是規(guī)劃庫中某個規(guī)劃的子片段。而頻繁指數(shù)則是覆蓋數(shù)組中包含1的數(shù)量。例如，在一個由五個規(guī)劃組成的規(guī)劃庫的后綴樹上，某個非葉節(jié)點上的覆蓋數(shù)組是［10110］，則代表該節(jié)點到根節(jié)點所對應(yīng)的規(guī)劃片段分別是規(guī)劃1、規(guī)劃3和規(guī)劃4的子片段。并且由于這個數(shù)組中1的數(shù)量是3，所以其節(jié)點的頻繁指數(shù)也為3。頻繁指數(shù)越高，則代表這個節(jié)點到根節(jié)點對應(yīng)的規(guī)劃片段被引用的頻率越高。節(jié)點的覆蓋數(shù)組也可以由其子節(jié)點的覆蓋數(shù)組來計算，公式如下：

該公式表明父親節(jié)點的覆蓋數(shù)組的一位是由其各個兒子的該位做或運算而得的。而且通過覆蓋數(shù)組和頻繁指數(shù)的概念很容易得知，根節(jié)點的覆蓋數(shù)組為全1，并且頻繁指數(shù)為規(guī)劃庫的規(guī)劃數(shù)。而葉子節(jié)點因為其到根節(jié)點的片段僅僅代表一個規(guī)劃，所以其頻繁指數(shù)為1。

現(xiàn)階段的企業(yè)競爭是人、錢、物、信息、時間的綜合競爭，尤其以時間為競爭的核心。豐田公司很早就意識到了這點，并將時間要素統(tǒng)籌考慮進生產(chǎn)系統(tǒng)中。在豐田公司，生產(chǎn)時間的范圍相對較寬，從取得材料到制成產(chǎn)品，再到獲得現(xiàn)金收益，不僅包括加工產(chǎn)品的時間，而且包括產(chǎn)品停滯的時間，如產(chǎn)品在各個生產(chǎn)環(huán)節(jié)的停頓以及庫存時間。

下面給出基于PST字符串構(gòu)造后綴樹的算法：

算法1 Create Suffix Tree for PST Analyze Series

Input：String PSTAnalyzeSeries；

Output：SuffixTree。

SuffixTree SuffixTree CreateSuffixTree（String Se-ries）

For each（Suffix Sin Series）

if（Sbegin with“?！保?/p>

Continue；

else

1.Find the head of the suffix；

2.Find Balance Part and Calculate the active

number.

if（the head’s beginning part matches with one

leaf node’s edge）

Just extended with S’s unmatched part.

（update active number）

else if（the head’s beginning part matches with

one none-leaf node’s edge）

Create a leaf node and connect it to this

none-leaf node.Then extend with S’s un

matched part.（update active number）

else

Take the most matches edge，and part the

edge（u，v）to edge（u，w）and edge（w，

v）.The edge （u，w）is the matches part

and the edge（w，v）is the unmatched part.

Create edge （w，u）with the S’s un

matched part；（update active number）

Update active number

上面給出的算法是基于一個PST字符串構(gòu)造自身的一棵后綴樹?；诖怂惴ǎ瑢ST字符串改為聯(lián)合分析序列就可以構(gòu)造出分析兩個規(guī)劃公共部分的后綴樹。算法如下：

算法2 Create Joint Suffix Tree for PST Analyze Series

Input：String PSTAnalyzeSeries1，String PSTAna

lyzeSeries2；

Output：Suffix Tree。

SuffixTree SuffixTree CreateJointSuffixTree（String

Series1，String Series2）

Get unique PlanID from Plan Database；

NewAnalyzeSeries＝Series1＋“＄”＋PlanID1＋

Series2＋“＄”＋PlanID2；

Figure 6 Algorithm of construct conjoint analysis suffix tree圖6 構(gòu)造聯(lián)合分析后綴樹算法

SuffixTree temp ＝ CreateSuffixTree（NewAna

lyzeSeries）；

CleanTempForJointSuffixTree（temp，“＄ ”＋

PlanID1）；

return temp；

void CleanTempForJointSuffixTree （SuffixTree

node，String singal）

if（node.childlist.count＝＝0）

return

else

For each（SuffixTree childin node.childlist）

if（edge（node，child）contains（singal））

Delete all the child’s child.

Replace edge（node，child）＝edge（node，

child）’s suffix

else

CleanTempForJointSuffixTree（child）；

UpdateCoverArray（node.childlist）；

此算法會深度優(yōu)先搜索生成的PST樹，并且在發(fā)現(xiàn)與子節(jié)點的邊存在著例如“＄1”時刪除其所有子孫節(jié)點。因為其子孫節(jié)點的后綴部分已經(jīng)在計算”＄2”的時候被生成。最后更新節(jié)點的覆蓋數(shù)組。

圖4和圖5的聯(lián)合分析后綴樹如圖6和圖7所示。

在本節(jié)前半段提出分析后綴樹中節(jié)點的兩個重要參數(shù)，在圖6中均有標注。以加粗的節(jié)點為例，（PA1＃A2＃A3＃＃），其11（3）代表這個節(jié)點已經(jīng)覆蓋了分析串1和分析串2，因為PA1＃A2＃A3＃＃的首個平衡子串就是其本身，去除P不是有效的活動，因為P是邏輯節(jié)點，所以其有效活動就為3。

從圖6展示的后綴樹可以清晰看到規(guī)劃之間公共部分的分布，通過對節(jié)點參數(shù)的分析可以有效選取想要的公共部分。以查找最大公共部分為例，給出搜索最大匹配的算法（算法3）。

算法3 FindBiggestCommonPlan

Input：SuffixTree Root；

Figure 7 Result of algorithm圖7 算法的運行結(jié)果

Output：String CommonPlanSeries。

Static String CandidateBiggestCommonPlan＝""；

Static int biggestcommonnumber＝0；

String FindBiggestCommonPlan （SuffixTree node，

String rootpath）

if（node.coverarrayis“11”＆＆node.activenumber

＞biggestcommonnumber）

CandidateBiggestCommonPlan＝rootpath；

Biggestcommonnumber＝node.activenumber

if（node.childlist.count！＝0）

foreach（SuffixTree childin node.childlist）

FindBiggestCommonPlan（child，rootpath＋

edge（node，child））；

void main（）

FindBiggestCommonPlan（root）；

Print（CandidateBiggestCommonPlan）；

這里執(zhí)行的結(jié)果就是將兩個規(guī)劃的最大公共部分提取出來并且保存到了CandidateBiggest-CommonPlan中。通過調(diào)整算法3的參數(shù)，完全可以搜索任意自定義的公共部分，并不局限于最大公共規(guī)劃。

5 規(guī)劃庫的優(yōu)化

本節(jié)將擴展上節(jié)算法，引入更多規(guī)劃并且提出規(guī)劃庫的存儲模型以及運行特點。首先，在第三個規(guī)劃加入之后，由于后綴樹的結(jié)構(gòu)并沒有發(fā)生變法，所以對于查找規(guī)劃庫中公共片段的算法類同于算法3。而需要略作修改的是在已有后綴樹模型的情況下添加新規(guī)劃的方法。算法如下（算法4）。

算法4 Create Suffix Tree for PST Analyze Series

Input：String PSTAnalyzeSeries，SuffixTree Original-Tree；

Output：Suffix Tree。

void SuffixTree CreateBruteForceSuffixTree（String

Series，OriginalTree Suffix-Tree）

foreach（Suffix Sin Series）

if（Series begin with“＃”）

Continue；

else

Find the head of the suffix （The largest

match of the largest prefix and the path to

wards to the root）；

Find Balance Part and Calculate the active

number.

if（the head’s beginning part matches with one

leaf node’s edge）

Just extended with its unmatched part.（update active

number）

else if（the head’s beginning part matches with

one none-leaf node’s edge）

Create a leaf node and connect it to the s

none-leaf node.Then extended with its un

matched part.（update active number）

else

1.Take the most matches edge，and part the

edge（u，v）to edge（u，w）and edge（w，v）

2.The edge（u，w）is the match part and the

edge（w，v）is the unmatched part.

3.Create edge （w，u）with the Sunmatched

part；（update active number）

Update active number；

算法4完成了將一條新的規(guī)劃加入到以后綴樹為存儲形式的規(guī)劃庫中。接著本文參考上一小節(jié)中給出的后綴樹節(jié)點的兩個重要參數(shù)：有效活動數(shù)和頻繁指數(shù)，來選取規(guī)劃庫優(yōu)化中需要的公共片段。規(guī)劃庫優(yōu)先采納頻繁指數(shù)高的節(jié)點所代表的公共片段。因為頻繁指數(shù)高的片段會經(jīng)常被規(guī)劃到，提取出來放置在規(guī)劃庫中可以保證當需求來臨時無需再次做規(guī)劃計算而直接使用。接著采納有效活動數(shù)大的規(guī)劃。因為有效活動數(shù)大代表其包含許多活動和邏輯，一旦需求需要這種規(guī)劃，計算代價很大，如果提前放置在規(guī)劃庫中也可以避免此類計算。兩者就構(gòu)成了規(guī)劃庫中公共片段的組成成分。

接著給出基于上述理論的Agent規(guī)劃庫的優(yōu)化方案。首先給出我們Agent規(guī)劃庫的邏輯以及存儲模型，如圖8所示。

Figure 8 Logistic and store model of service agent plan library圖8 服務(wù)Agent規(guī)劃庫邏輯及存儲模型

如圖8所示，服務(wù)Agent規(guī)劃庫存在的目的是為了讓服務(wù)Agent提取以往規(guī)劃的知識，從而加快再次規(guī)劃的速度。圖中服務(wù)Agent規(guī)劃庫存儲的內(nèi)容包含兩部分，其中一部分是以前服務(wù)Agent運行的規(guī)劃實例，另外一部分是由這些實例所計算出的公共片段模型。采用的是FIFO替換策略。設(shè)置規(guī)劃庫為一定的規(guī)模，當有新的規(guī)劃加入時，將最末尾的規(guī)劃逐出規(guī)劃庫，最后更新規(guī)劃庫的公共片段模型即可。存儲模型按照本節(jié)提出的后綴樹模型存儲。其中規(guī)劃實例占據(jù)了后綴樹模型的樹葉節(jié)點，而公共片段模型則占據(jù)了后綴樹模型的中間節(jié)點。

對于不斷變化的需求而言，規(guī)劃庫通過FIFO替換策略能及時將規(guī)劃庫中的內(nèi)容更換成針對于當前的需求環(huán)境，產(chǎn)生當前需求比較普遍的公共片段等，加速規(guī)劃的生成。替換算法維護一個鏈表記錄其加入的新規(guī)劃實例，當鏈表的長度超過替換的容忍值后，將會把服務(wù)Agent規(guī)劃庫中最末加入的規(guī)劃從規(guī)劃庫中刪除，如果沒有超過容忍值將會持續(xù)加入到規(guī)劃庫中。最后規(guī)劃庫做一個更新操作，按照頻繁指數(shù)和有效活動數(shù)決定公共片段區(qū)域的存放。容忍值在這里決定了規(guī)劃庫存儲規(guī)劃實例的大小。

服務(wù)Agent規(guī)劃庫模型的空間大小是可以調(diào)整的。服務(wù)Agent能夠根據(jù)空間代價和時間代價關(guān)系適當調(diào)整規(guī)劃庫的大小，從而對規(guī)劃有所優(yōu)化的前提下有效節(jié)省空間。此外模型內(nèi)部的比例也是可以調(diào)整的。模型分為實例部分和片段部分。將規(guī)劃庫的規(guī)劃實例和規(guī)劃片段根據(jù)其目前規(guī)模設(shè)置為一個合適的比例同樣有助于空間和時間的效率提升。

6 算法實驗分析

在實驗中，分別選取兩組迥然不同的規(guī)劃需求，分為A需求區(qū)和B需求區(qū)，首先給服務(wù)Agent發(fā)送很多A需求，等到服務(wù)Agent規(guī)劃庫已經(jīng)適應(yīng)了A需求再發(fā)送很多B需求給服務(wù)Agent。觀察三種規(guī)模狀態(tài)下，服務(wù)Agent規(guī)劃庫的執(zhí)行效率。整個實驗采用了本課題組基于JADE環(huán)境開發(fā)的服務(wù)Agent平臺 。

實驗結(jié)果如圖9所示，其中圖表中的縱軸是相對于不使用規(guī)劃庫的規(guī)劃效率，而橫軸是需求總數(shù)。觀察三條曲線，首先能夠發(fā)現(xiàn)在使用優(yōu)化的規(guī)劃庫后比不使用記錄規(guī)劃實例而總是重新規(guī)劃的效率高。其次已經(jīng)如圖中標注，大規(guī)模規(guī)劃庫因為能夠存儲更多規(guī)劃知識，所以，可以在需求變化不大的情況下給出更多的優(yōu)化可能。所以在效率深度上，大規(guī)模規(guī)劃庫會比小規(guī)模規(guī)劃庫有效。但是，在需求環(huán)境變化比較大的情況下，小規(guī)模規(guī)劃庫敏感得多，因為其規(guī)劃庫規(guī)模小，所以清空和置換的效率就高很多，所以其調(diào)整時間比大規(guī)模規(guī)劃庫的調(diào)整時間短很多。

Figure 9 Performance analysis of different plan library圖9 不同規(guī)模的規(guī)劃庫性能分析

規(guī)劃庫占用的空間效率和在規(guī)劃穩(wěn)定期的時間效率是一對矛盾的關(guān)系，實驗結(jié)果如圖10所示，當規(guī)劃庫擁有比較大的規(guī)模時能存儲更多的知識，也能產(chǎn)生更多可能的公共規(guī)劃片段。所以，規(guī)模越大，其時間效率就越佳。但是，這個效率是有瓶頸的，因為當規(guī)模達到一定程度以后，對于規(guī)劃需求言，其擁有的知識已經(jīng)足夠，再多的規(guī)模也不能顯著地提高產(chǎn)生規(guī)劃效率。對于規(guī)劃庫模型內(nèi)公共片段和規(guī)劃實例比例問題，本文也進行了實驗。得到的效率結(jié)果如圖11所示。

從圖11中發(fā)現(xiàn)，當采取比較少的公共部分時，時間效率提升并不理想，并且還可能產(chǎn)生反復，因為比較少的公共部分難以覆蓋全部可能的規(guī)劃案例。但是，當采取比較多的公共部分時，規(guī)劃時間效率也不會提升，原因在于雖然直接命中規(guī)劃部分會提升時間效率，但是命中率會隨著公共部分的增多而下降，最終導致整合的時間效率還不如沒有加入公共規(guī)劃。但是，如果采取數(shù)量合適的規(guī)劃（經(jīng)過實驗認為合理值在20%～60%，建議取30%為宜），則可以明顯提高整個規(guī)劃的時間效率。

接著比較三種服務(wù)Agent規(guī)劃庫方案在生成規(guī)劃時的時空效率，分別是不使用規(guī)劃庫、記錄所有規(guī)劃實例以及使用本文提到的優(yōu)化的規(guī)劃庫，如圖12所示?？梢园l(fā)現(xiàn)，不使用規(guī)劃庫可以得到空間的極大節(jié)省。但是，生成規(guī)劃所需要的代價最高。在第二種方法中，將已經(jīng)生成的規(guī)劃方案都進行保存。當需求與上次相同時可以直接查詢到規(guī)劃庫中的規(guī)劃而不必再動態(tài)生成規(guī)劃，所以得到性能的提升，但是其占用的空間代價最高，因為其沒有選擇性的替換策略進行保存，相對而言本文所介紹的方案能夠有效提取公共片段，合理設(shè)定公共片段的比例，控制規(guī)劃庫的空間規(guī)模，而且重規(guī)劃的時間效率有很好的提升，所以是一種很好的選擇。

Figure 12 Comparison of space-time cost by 3kinds of methods圖12 三種方案的時空代價比較

7 結(jié)束語

本文提出的方法將服務(wù)Agent規(guī)劃庫中的規(guī)劃以PST的形式進行存儲，然后使用算法將PST森林轉(zhuǎn)換成一棵提供搜索功能的后綴樹，最后提出了平衡字符串和最大有效字符串的概念，使得可以在這棵特殊的后綴樹上的節(jié)點標注頻繁指數(shù)和有效活動數(shù)。這樣使用搜索算法可以在線性時間內(nèi)找出任意集合內(nèi)的規(guī)劃的共同部分。當服務(wù)A-gent面對需求無法直接調(diào)用某個規(guī)劃而需要重新生成規(guī)劃的時候，規(guī)劃搜索引擎在規(guī)劃的時候首先考慮到那些已經(jīng)被規(guī)劃庫提取并且存儲在其中的公共部分，這樣的規(guī)劃過程將會減少規(guī)劃的時間，并且由于可以控制規(guī)劃庫規(guī)模的大小，所以可以取得時間和空間效率的平衡。

我們今后的研究將在于如何進一步提高規(guī)劃庫組織這種后綴樹結(jié)構(gòu)的能力，如改造Ukkonen的構(gòu)造算法放置到服務(wù)Agent規(guī)劃庫的環(huán)境中，這樣可以進一步提高效率。還可以不僅僅利用規(guī)劃的活動拓撲信息，還利用規(guī)劃的語義信息，在一些常用語義搜索的應(yīng)用上進行學習和演化，從而更大程度地加強服務(wù)Agent規(guī)劃庫的能力和適應(yīng)范圍。

［1］ Papazoglou M P，Traverso P，Dustdar S，et al.Service-oriented computing：State of the art and research challenges［J］.IEEE Computer，2007，40（11）：38-45.

［2］ Huhns M N，Singh M P.Service-oriented computing：Key concepts and principles［J］.IEEE Internet Computing，2005，9（1）：75-81.

［3］ Jarvis J，Jarvis D，R?nnquist R，et al.A flexible plan step execution model for BDI agents［J］.Multiagent and grid systems，2008，4（4）：359-370.

［4］ Gong Xiao-qing，Liu Feng，Ge Wei.Workflow process definition tool based on reuse—PDTBR［J］.Computer Application，2009，20（1）：315-318.（in Chinese）

［5］ Hai Zhuge.A process matching approach for flexible workflow process reuse［J］.Information and Software Technology，2002，44（8）：445-450.

［6］ Qian Zhu-zhong，Lu Sang-lu，Xie Li.Automatic composition of Petri net based Web services［J］.Chinese Journal of Computers，2006，29（7）：1057-1066.（in Chinese）

［7］ van der Aalst W M P，Alves de Mederios A K，Weiijter A J M M.Process equivalence：Comparing two process models based on observed behavior［C］∥Proc of BPM’06，2006：129-144.

［8］ Jensen K.Coloured Petri nets：Basic concepts，analysis methods and practical use［M］.New York：Springer-Verlag，1997.

［9］ Dumas M.Process-aware information system：Bridging people and software through process technology［M］.New York：John Wiley＆Sons，2005.

［10］ Koch I.Enumerating all connected maximal common subgraphs in two graphs［J］.Theoretical Computer，2001，250（1-2）：1-30.

［11］ Vanhatalo J，V?lzer H，Koehler J.The refined process structure tree［C］∥Proc of BPM’08，2008：100-115.

附中文參考文獻：

［4］ 龔曉慶，劉鋒，葛瑋，等.基于復用的工作流過程定義工具—PDTBR［J］.計算機應(yīng)用，2009，20（1）：315-318.

［6］ 錢柱中，陸桑璐，謝立.基于Petri網(wǎng)的web服務(wù)自動組合研究［J］.計算機學報，2006，29（7）：1057-1066.