服務(wù)Agent規(guī)劃庫(kù)的動(dòng)態(tài)優(yōu)化＊

徐錢元，曹 健，王 磊

（上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海201100）

1 引言

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

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

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

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

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

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

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

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

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

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

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

（4）無(wú)解，無(wú)法滿足需求。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CommonAnalyzeSeries＝

AnalyzeSeries1＄N1AnalyzeSeries2＄N2

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

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

活動(dòng)表達(dá)式：［A［0-9］＋｜B｜E］；

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

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

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

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

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

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

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

下面給出基于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“＃”）

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

上面給出的算法是基于一個(gè)PST字符串構(gòu)造自身的一棵后綴樹?；诖怂惴ǎ瑢ST字符串改為聯(lián)合分析序列就可以構(gòu)造出分析兩個(gè)規(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）；

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

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

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

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

算法3 FindBiggestCommonPlan

Input：SuffixTree Root；

Figure 7 Result of algorithm圖7 算法的運(yùn)行結(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?。?）

foreach（SuffixTree childin node.childlist）

FindBiggestCommonPlan（child，rootpath＋

edge（node，child））；

void main（）

FindBiggestCommonPlan（root）；

Print（CandidateBiggestCommonPlan）；

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

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

本節(jié)將擴(kuò)展上節(jié)算法，引入更多規(guī)劃并且提出規(guī)劃庫(kù)的存儲(chǔ)模型以及運(yùn)行特點(diǎn)。首先，在第三個(gè)規(guī)劃加入之后，由于后綴樹的結(jié)構(gòu)并沒有發(fā)生變法，所以對(duì)于查找規(guī)劃庫(kù)中公共片段的算法類同于算法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ī)劃加入到以后綴樹為存儲(chǔ)形式的規(guī)劃庫(kù)中。接著本文參考上一小節(jié)中給出的后綴樹節(jié)點(diǎn)的兩個(gè)重要參數(shù)：有效活動(dòng)數(shù)和頻繁指數(shù)，來(lái)選取規(guī)劃庫(kù)優(yōu)化中需要的公共片段。規(guī)劃庫(kù)優(yōu)先采納頻繁指數(shù)高的節(jié)點(diǎn)所代表的公共片段。因?yàn)轭l繁指數(shù)高的片段會(huì)經(jīng)常被規(guī)劃到，提取出來(lái)放置在規(guī)劃庫(kù)中可以保證當(dāng)需求來(lái)臨時(shí)無(wú)需再次做規(guī)劃計(jì)算而直接使用。接著采納有效活動(dòng)數(shù)大的規(guī)劃。因?yàn)橛行Щ顒?dòng)數(shù)大代表其包含許多活動(dòng)和邏輯，一旦需求需要這種規(guī)劃，計(jì)算代價(jià)很大，如果提前放置在規(guī)劃庫(kù)中也可以避免此類計(jì)算。兩者就構(gòu)成了規(guī)劃庫(kù)中公共片段的組成成分。

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

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

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

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

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

6 算法實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

附中文參考文獻(xiàn)：

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

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