融合語義知識庫的流程匹配算法

常關(guān)羽, 楊海成, 孫　鵬

(西北工業(yè)大學(xué) 機電學(xué)院， 西安 710072)

融合語義知識庫的流程匹配算法

常關(guān)羽, 楊海成, 孫鵬

(西北工業(yè)大學(xué) 機電學(xué)院， 西安 710072)

摘要:為在流程相似度計算中加入流程間深層語義關(guān)聯(lián)的度量，同時在流程節(jié)點較多的情況下，實現(xiàn)流程匹配算法在尋優(yōu)時間復(fù)雜度和相似度匹配輸出值兩方面的綜合優(yōu)化，提出一種面向流程的遺傳匹配算法，將遺傳算法引入并應(yīng)用在流程語義和結(jié)構(gòu)的相似度計算尋優(yōu)過程中. 確定遺傳算法的參數(shù)編碼方式，并利用貪婪算法進行初始種群的設(shè)置，定義各個遺傳算子，提出有效的簡化策略，解決了流程節(jié)點較多時流程匹配過程尋優(yōu)問題. 實驗研究表明，在流程節(jié)點數(shù)較多時，本文算法在尋優(yōu)時間花費和相似度值兩方面的折中優(yōu)化性能明顯優(yōu)于其他兩種算法. 將遺傳算法應(yīng)用到流程的相似度計算及其尋優(yōu)過程，可以有效地控制時間復(fù)雜度并保證較好的匹配輸出結(jié)果.

關(guān)鍵詞:業(yè)務(wù)流程; 文本相似度; 語義知識庫; 匹配相似度; 遺傳算法

海量流程資產(chǎn)的有效利用取決于信息系統(tǒng)的流程管理技術(shù)水平，而有效的流程相似度查詢技術(shù)則成為提升業(yè)務(wù)流程管理水平的關(guān)鍵技術(shù)之一[1]. 在相似性計算方面，標(biāo)注于流程節(jié)點上的文本標(biāo)簽的相似度是進行流程相似性分析的基礎(chǔ)[2-3]. 傳統(tǒng)的基于文本的匹配檢索可以用來索引和搜尋業(yè)務(wù)流程模型知識庫. 但這類匹配和檢索是以關(guān)鍵詞和字符匹配[4-5]或其特征值[6]的近似程度為基礎(chǔ)，若模型標(biāo)記的文本標(biāo)簽包含特定的關(guān)鍵詞或字符，那么這種方式是確有成效的[7]. 但是，這種相似的應(yīng)用沒有考慮語義異構(gòu)性的存在. 這使得采用以關(guān)鍵詞和字符匹配為基礎(chǔ)的傳統(tǒng)流程相似匹配難以實現(xiàn)更加準(zhǔn)確的語義查詢[8]. 基于語義知識庫的語義相似度是一種計算文本與文本間在其概念關(guān)聯(lián)上相似程度的度量方法. 因此，本文引入基于語義知識庫的概念相似度計算方法，將其應(yīng)用在流程匹配中的文本標(biāo)簽的相似度計算中，以提高流程匹配的準(zhǔn)確度.

在流程匹配過程的尋優(yōu)算法上，現(xiàn)存的幾種流程匹配算法都具備各自的特點，但在流程節(jié)點較多時，都表現(xiàn)出各自的不足. 例如貪婪算法[9]，可以在很短時間內(nèi)得到一個匹配結(jié)果以及匹配的相似度值，但很可能得到的不是最優(yōu)匹配. 而作為典型的啟發(fā)式算法的A*算法[10]，雖然可以確保找到最優(yōu)解，但其耗時代價可能會隨著節(jié)點數(shù)增加而急劇增長. 因此，本文提出一種基于遺傳算法[11-12]的折中優(yōu)化的算法，旨在節(jié)點數(shù)較多時，既能在相似度上達到較為滿意的值，又可以在匹配尋優(yōu)過程的時間耗費上處于可以接受的范圍.

1節(jié)點語義相似度計算模型

1.1語義相似度及其關(guān)鍵定義

定義1義原相似度[13]. 設(shè)s1與s2為兩個義原,義原間距離記為D(s1,s2)，相似度記為Ssem(s1,s2)，則

其中:d1和d2分別是義原s1和義原s2所處的層次，α>0,且α是相似度為0.5時s1和s2之間的距離.

定義2義原最佳匹配[14]. 設(shè)S1={s11,s12,…,s1m} 和S2={s21,s22,…,s2n}分別為包含m和n個義原的集合，且有m≤n. 定義從S1到S2的一個單射集合為M. 則義原的最佳匹配是指一個單射集合Mopt,對于所有其他的單射集合M都有

其中Ssem為兩個義原間的相似度.

定義3義項相似度. 設(shè)C1、C2為兩個義項，C1由m 個義原描述s11,s12,…,s1m，C2由n個義原描述s21,s22,…,s2n，且m≤n . Mopt為描述兩個義項的義原集合的最佳匹配，則C1、C2的相似度為[15]

其中wi是為不同的義原映射賦予的不同權(quán)值.

定義4概念相似度. 設(shè)概念S1的名稱L1有m個義項C11，C12，…，C1m，概念S2的名稱L2有n個義項C21，C22，…，C2n，則概念S1和概念S2的相似度為[16-17]

其中SConcept(C1i,C2j)表示義項C1i、C2j之間的相似度. 1.2流程節(jié)點的語義相似度計算

定義6文本標(biāo)簽的語義相似度. 設(shè)l1,l2∈Ω為文本標(biāo)簽，W為所有詞語或單詞的集合，w∶Ω→P(W)為分離文本標(biāo)簽成單詞集合的函數(shù). sword是基于語義知識庫的一個詞匯相似度函數(shù). 令w1=w(l1),w2=w(l2)，M為詞匯集合w1與w2的詞匯單射集合. Mopt為使得詞匯映射相似度值之和最大的映射. S(l1,l2)為文本標(biāo)簽l1和l2的語義相似度，即

其中:|w1|、|w2| 分別表示w1和w2中的詞匯數(shù)， w1i、w2j分別表示w1和w2中的一個詞語.

定義7節(jié)點特性相似度. 設(shè)B1(N1,E1,τ1,λ1,α1)和B2(N2,E2,τ2,λ2,α2)是兩個流程圖，令n1∈N1和 n2∈N2分別為B1和B2的一個節(jié)點. S為相似度函數(shù). 那么可以定義節(jié)點n1和n2特性的相似度為

特性相似度一般與其他相似度結(jié)合起來使用.

定義8節(jié)點類型相似度. 設(shè)有流程圖B1(N1,E1,τ1,λ1,α1)和B2(N2,E2,τ2,λ2,α2)，令n1∈N1和 n2∈N2分別為B1和B2的節(jié)點. 令t∶ T×T→[0,1]為節(jié)點類型的相似度函數(shù)，則

為節(jié)點類型相似度函數(shù). t是預(yù)先定義的. 可選擇以下參考定義形式：

綜上，本文設(shè)計了如圖1的節(jié)點相似度計算模型.

圖1　節(jié)點相似度計算模型

2流程相似度計算模型

第2種要研究的相似度是業(yè)務(wù)流程的結(jié)構(gòu)相似度. 結(jié)構(gòu)相似度基于圖編輯距離來定義[19].

定義9圖的編輯距離. 設(shè)B1(N1,E1,τ1,λ1,α1)和B2(N2,E2,τ2,λ2,α2)是兩個流程圖,S為相似度函數(shù)，M∶(N1→/ N2)為一個局部單射. n∈(N1→N2)為一個節(jié)點. 當(dāng)且僅當(dāng)n∈dom(M)或n∈cod(M)時，n 是被“替換”的. 若n不是被“替換”時，則n為“插入”或“刪除”. sn為所有“插入”或“刪除”的節(jié)點集. (n,m)∈E1為邊，當(dāng)且僅當(dāng)不存在(n,n′)∈M或(m,m′)∈M以及Eedge(n′,m′)∈E2. se是所有“插入”或“刪除”的邊集. 圖編輯距離表示如下：

圖的編輯距離是由兩個流程導(dǎo)出的最小化距離. 其計算方法是：1減去“插入”或“刪除”節(jié)點“插入”或“刪除”邊集以及“替換”節(jié)點平均距離的平均值的分?jǐn)?shù)部分的差.

定義10圖編輯距離相似度. 設(shè)B1=(N1,E1,τ1,λ1,α1)和B2=(N2,E2,τ2,λ2,α2)為兩個流程圖，S為相似度函數(shù)，令M∶ (N1→/ N2) 為導(dǎo)出兩個流程圖編輯距離的局部單射,sn和se同定義9中所述，圖的編輯距離相似度為

定義11等價映射和最優(yōu)等價映射. 設(shè)B1(N1,E1,τ1,λ1,α1)和B2(N2,E2,τ2,λ2,α2)為兩個流程圖，設(shè)節(jié)點對相似度函數(shù)為S∶N1×N2→[0,1]. 一個局部單射MS∶(N1→/ N2) 為等價映射的條件是，當(dāng)且僅當(dāng)對于所有的n1∈N1和n2∈N2∶(n1,n2)∈M可使S(n1,n2)>0.

|{n|n∈N1,τ1(n)?ts}|+

|{n|n∈N2,τ2(n)?ts}|.

基于以上定義，流程相似度計算模型如圖 2.

圖2　流程相似度計算模型

3流程匹配過程尋優(yōu)算法設(shè)計

本文設(shè)計了一種基于遺傳算法的匹配過程尋優(yōu)算法，使得計算效率和匹配效果都能滿足應(yīng)用需求. 算法關(guān)鍵設(shè)計細(xì)節(jié)如下.

3.1流程編碼

設(shè)一個有n 個節(jié)點的流程Pn，采用編碼1,2,…,n-1,n對每個節(jié)點進行編碼. 設(shè)另一個有m個節(jié)點的流程Pm，則其編碼為1,2,…,m-1,m. 任意兩個流程的節(jié)點數(shù)總有n≥m. 因為，總可用n表示節(jié)點數(shù)較多的流程節(jié)點數(shù). 當(dāng)兩個節(jié)點數(shù)分別為n和m的流程Pn和流程Pm進行匹配時，編碼的位數(shù)便為n，編碼每一個基因位上的取值范圍是1～n,且每一個基因位上的取值不重復(fù). 編碼中每個基因位代表Pn的一個節(jié)點，而該基因位的取值代表Pm中的一個節(jié)點. 注意到n≥m，因此在基因位的取值中，超過m的值m+1,…,n-1,n是沒有意義的. 因此，當(dāng)某基因位的取值為m+1,…,n-1,n中的一個時，表示該基因位代表的流程Pn的節(jié)點不能與Pm中節(jié)點匹配. 3.2種群初始化

首先，可以確定一個表示節(jié)點間的相似度的矩陣S. 以P9和P7為例，則有相似度矩陣S9×7為

式中，sij為P9的第i個節(jié)點和P7中的第j個節(jié)點的相似度值.

3.3適應(yīng)度函數(shù)

匹配的目標(biāo)在于求解相似度最大的匹配. 根據(jù)定義11中的節(jié)點匹配相似度定義,可以將適應(yīng)度函數(shù)設(shè)為個體m中所有節(jié)點映射相似度之和，因此節(jié)點匹配的相似度適應(yīng)度函數(shù)定義如下：

其中:m(i)為所求個體第i基因位上的值，si,m(i)為兩流程節(jié)點相似度矩陣中第i行第m(i)列的值. 求這些匹配上的節(jié)點的相似度之和，是最簡單的一種適應(yīng)度函數(shù).

根據(jù)流程的結(jié)構(gòu)相似度定義，可以分別得

式中：m(i) 為所求個體第i基因位上的值，si,m(i)為兩流程節(jié)點相似度矩陣中第i行第m(i)列的值. 進一步得到結(jié)構(gòu)相似度的適應(yīng)度函數(shù)：

3.4遺傳算子設(shè)計

由于采用了非二進制編碼，所以變異算子需要采用對應(yīng)離散數(shù)字的變異方法. 在此采用映射互換模式的變異方法、基因段逆轉(zhuǎn)、互換位置相結(jié)合的方法進行遺傳處理以提高遺傳多樣性.

3.5參數(shù)設(shè)定

種群規(guī)模根據(jù)問題的節(jié)點數(shù)進行設(shè)定. 例如，匹配中，節(jié)點較多的流程節(jié)點數(shù)為n，則相應(yīng)的種群規(guī)模可設(shè)為n～2n. 迭代代數(shù)為節(jié)點數(shù)3～5倍，或者采用某個估計函數(shù)Af(n) ，其中A為一個基準(zhǔn)常數(shù)，f(n)為一個節(jié)點數(shù)的增函數(shù). 交叉概率可設(shè)為Pc=0.9，變異概率為Pm=0.01.

最終的算法運行流程如下：

圖3　遺傳匹配算法流程圖

4實驗

根據(jù)前述工作，該節(jié)根據(jù)流程節(jié)點數(shù)不同，將流程庫中的流程分成98類，即2～99個節(jié)點的流程根據(jù)其節(jié)點數(shù)各成一類. 每一類流程一般有8～12個. 通過對不同類別流程的匹配計算,觀察算法的性能表現(xiàn). 在語義相似度的計算上采用了基于《知網(wǎng)》的語義知識庫及其詞匯語義相似度計算方法，并結(jié)合前文的分析實現(xiàn)流程配對和相似度計算. 實驗時,首先通過確定截斷值對測試結(jié)果的影響來確定合適的實驗參數(shù);其次,在確定的截斷值條件下，通過匹配的相似度結(jié)果和匹配過程的時間消耗來確定匹配綜合效果.

式中:t為所耗費的時間，A為比例調(diào)節(jié)常數(shù)，s為求解的相似度值，s0為通過貪婪算法得到的相似度值，α為一較小的常數(shù)，以避免分母為零；Cn為兩流程節(jié)點數(shù)的減函數(shù). 通過函數(shù)Cn的調(diào)節(jié)，使得在節(jié)點增多時，函數(shù)成本適當(dāng)減小.Cn的確定與常數(shù)A和α相關(guān)，例如可取Cn=-Aeαn. 根據(jù)實驗數(shù)據(jù)特點，也可采用以下變形：

(1)

實驗證明，截斷值(δ)的選取對流程匹配算法的實用性具備重要影響，特別是A*算法在節(jié)點數(shù)逐漸增大約到15個節(jié)點時，平均耗時會開始超過1s/百對. 增加至54個節(jié)點時，程序耗時已經(jīng)超過2d，因此采用文獻[9]建議，δ的下界取0.6，此時得到的A*算法在相似度值和耗時兩方面都處于可接受范圍內(nèi). 實驗中對貪婪算法、A*算法、遺傳算法進行包括時間復(fù)雜度、匹配結(jié)果以及時間成本代價等指標(biāo)的對比，截斷參數(shù)δ可選0.6、0.8, 當(dāng)δ=0.6時，對比較果明顯. 由于流程的相似度值差異值較小，為了清晰地表達實驗結(jié)果，將3種算法得到的相似度值減去貪婪算法得到的值繪圖,結(jié)果見圖4. 由圖4可知，與δ=0.6相比，δ取0.8時，流程匹配相似度的絕對值整體下降了. 因為δ的變大,直接忽略相似度值較小的節(jié)點匹配，從而導(dǎo)致整體相似度值下降.

(b) δ=0.8

從圖4可以清楚地看到3種算法得到的相似度值的差異. 由于貪婪算法自身減掉自身的值得到的值始終是0，因此，貪婪算法表現(xiàn)為一條恒為0的直線，延伸于坐標(biāo)軸橫軸方向上. 在δ為0.6時，可以看到遺傳算法和A*算法大約在節(jié)點數(shù)達到45及其之前的匹配輸出是完全重合的；當(dāng)節(jié)點數(shù)>45時，遺傳算法的值開始處于A*算法之下. 這說明遺傳算法在節(jié)點數(shù)超過45時，不能再保證相似度值是最優(yōu)解. 當(dāng)δ為0.8時，遺傳算法和A*算法得到的相似度值與貪婪算法相同，減掉貪婪算法的值后結(jié)果都為一條恒為0的直線，延伸于橫軸方向上，如圖4(b)所示. 因此，δ超過0.8時，貪婪算法是最好的. 即當(dāng)δ超過0.8時，截斷值過于簡化了算法. 然而如果實際需要，可以將δ設(shè)得比較大，如0.8. 但δ設(shè)得過大,可能使得匹配不到真正的最優(yōu)解,從而導(dǎo)致匹配算法失去優(yōu)勢.

5算法時間復(fù)雜度結(jié)果分析

在測試了截斷值對匹配結(jié)果的影響后，實驗取δ=0.6對3種算法的時間復(fù)雜度進行測試. 圖5為3種算法隨著節(jié)點數(shù)增加，時間復(fù)雜度的情況. 橫軸表示節(jié)點數(shù)，縱軸表示每100對流程匹配所耗費的時間. 由于時間跨度較大，圖中縱軸采用時間對數(shù)坐標(biāo).

圖5　算法平均時間復(fù)雜度隨節(jié)點增多變化趨勢

由圖5可知，貪婪算法在時間上表現(xiàn)最好. 同時，A*算法在起初節(jié)點數(shù)較少時，時間和貪婪算法相當(dāng). 當(dāng)節(jié)點數(shù)>5時，A*算法時間復(fù)雜度急劇增長，并在節(jié)點數(shù)為37附近，超越遺傳算法呈劇烈上升趨勢. 在節(jié)點數(shù)為37處，A*算法的時間耗費約為11(e11ms約為12s).A*算法的時間復(fù)雜度基本保持隨著節(jié)點數(shù)逐漸增長而增長，偶爾出現(xiàn)時間耗費降低或者突然增大的情況，說明A*算法的波動性較大. 遺傳算法的時間復(fù)雜度基本穩(wěn)定，始終保持在11附近并緩慢增長. 出現(xiàn)以上實驗現(xiàn)象是因為A*算法受啟發(fā)策略的影響很大，同時其復(fù)雜度隨著節(jié)點數(shù)的增加會呈現(xiàn)指數(shù)增長趨勢，最終總體上體現(xiàn)出快速增長并偶有波動. 而采用貪婪算法,隨著節(jié)點數(shù)的提升,時間復(fù)雜度呈對數(shù)增長模式，因此能有效避免狀態(tài)空間爆炸問題. 遺傳算法的復(fù)雜度取決于其迭代次數(shù)和進化過程，具備復(fù)雜度小且可控的特性.

6時間成本評比

基于式(1)，參數(shù)采用了如下的取值：A=0.01,α=0.001，Cn=-Aeαn. 對實驗數(shù)據(jù)進行二次處理，得出時間成本效果對比曲線.

可以看到，圖 6的趨勢與圖5是一致的. 從圖 6可得貪婪算法的成本基本上一直維持在最低. 因為貪婪算法的時間復(fù)雜度很小，使得貪婪算法在一些應(yīng)用場景下始終具有優(yōu)勢. 遺傳算法在節(jié)點數(shù)<37時，成本函數(shù)始終大于A*算法；超過37時，與A*算法相當(dāng)，超過43個節(jié)點時，遺傳算法相對于A*算法表現(xiàn)出優(yōu)勢，而且時間成本相對穩(wěn)定，增長緩慢. 即當(dāng)節(jié)點數(shù)超過43時，采用A*算法來求解匹配的最優(yōu)值是不如遺傳算法“劃算”的. 綜合前述實驗結(jié)果，當(dāng)流程節(jié)點達到一定數(shù)量時，采用遺傳算法進行流程最優(yōu)匹配是一個能兼顧匹配輸出效果和時間成本的選擇，對于實際應(yīng)用來說，具備明顯的折中優(yōu)勢.

圖6　相似度計算綜合代價隨節(jié)點增多的變化趨勢對比

7結(jié)論

1)從流程節(jié)點的語義相似度和流程結(jié)構(gòu)匹配算法兩方面進行了研究. 結(jié)合流程節(jié)點語義相似度和流程結(jié)構(gòu)相似度的相關(guān)定義, 導(dǎo)出了本文的流程相似度計算模型.

2)針對流程相似度尋優(yōu)過程，設(shè)計了一種基于遺傳算法的過程尋優(yōu)算法.

3)對目標(biāo)算法進行了實驗驗證，通過對實驗數(shù)據(jù)的分析，證明了本文設(shè)計的流程匹配算法在匹配的時間復(fù)雜度和匹配輸出方面的綜合優(yōu)化能力，對比已有的匹配過程尋優(yōu)算法，本文算法體現(xiàn)出很好的實用價值.

鑒于時間和實驗條件，本文雖然在流程匹配中嘗試了對語義的考察，但還有進一步深入的空間，如實現(xiàn)本體語義的語義匹配，嘗試其他新算法在匹配尋優(yōu)過程中的應(yīng)用等.

參考文獻

[1] JIN T, WANG J, LA ROSA M, et al. Efficient querying of large process model repositories[J]. Computers in Industry,2013, 64(1): 41-49.

[2] WANG P, LIU H. Assessing sentence similarity using wordnet based word similarity[J]. Journal of Software,2013, 8(6): 1451-1458.

[3] LI H, TIAN Y, CAI Q. Improvement of semantic similarity algorithm based on WordNet[C]// 2011 6th IEEE Conference on Industrial Electronics and Applications (ICIEA). Beijing: IEEE, 2011：564-567.

[4] 郭永利，盧穎穎. 基于Lucene對文件全文檢索的研究與應(yīng)用[J]. 微型電腦應(yīng)用, 2014(1): 51-54.

[5] 李永春，丁華福. Lucene的全文檢索的研究與應(yīng)用[J]. 計算機技術(shù)與發(fā)展,2010, 20(2): 12-15.

[6] 付永貴. 一種改進的余弦向量度量法文本檢索模型[J]. 圖書情報工作,2011(19): 115-119.

[7] BERRETTI S, DELBIMBO A, VICARIO E. Efficient match-ing and indexing of graph models in content-based retrieval[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(10): 1089-1105.

[8] COLOMOPALACIOS R, GOMEZBERBIS J M, GARCIAC-RESPO A, et al. SeMatching: using semantics to perform pair matching in mentoring processes[C]//2nd World Summit on the Knowledge Society. Chania: Springer Verlag, 2009：137-146.

[9] DIJKMAN R, DUMAS M, GARCIABANUELOS L. Graph matching algorithms for business process model similarity search[C]//7th International Conference on Business Process Management. Ulm: Springer Verlag, 2009：48-63.

[10]THANUJA M K, MALA C. A search tool using genetic algorithm[M]//Information Technology and Mobile Communication. Chania: Springer, 2011: 138-143.

[11]HONDA K, NAGATA Y, ONO I. A parallel genetic algorithm with edge assembly crossover for 100,000-city scale TSPs[C]// 2013 IEEE Congress on Evolutionary Computation (CEC). Cancun: IEEE,2013：1278-1285.

[12]CEKMEZ U, OZSIGINAN M, SAHINGOZ O K. Adapting the GA approach to solve Traveling Salesman Problems on CUDA architecture[C]// 2013 IEEE 14th International Symposium on Computational Intelligence and Informatics (CINTI). Budapest: IEEE, 2013：423-428.

[13]葛斌，李芳芳，郭絲路，等. 基于知網(wǎng)的詞匯語義相似度計算方法研究[J]. 計算機應(yīng)用研究, 2010(9): 3329-3333.[14]周生寶，郭俊芳. 本體映射中概念相似度計算的改進[J]. 山西大同大學(xué)學(xué)報(自然科學(xué)版), 2008(4): 38-40.[15]王婷. 本體相似度研究[J], 電腦知識與技術(shù)(學(xué)術(shù)交流), 2007(6): 1609-1611.

[16]張艷霞，張英俊，潘理虎，等. 一種改進的概念語義相似度計算方法[J]. 計算機工程, 2012(12): 176-178.

[17]胡哲，鄭誠. 改進的概念語義相似度計算[J]. 計算機工程與設(shè)計,2010(5): 1121-1124.

[18]DIJKMAN R, DUMAS M, DONGEN B V, et al. Similarity of business process models: Metrics and evaluation[J]. Information Systems,2011, 36(2): 498-516.

[19]ZHU J, PUNG H K. Process matching: A structural approach for business process search[C]//Computation World: Future Computing, Service Computation, Adaptive, Content, Cognitive, Patterns, Computation World 2009. Athens: IEEE Computer Society, 2009：227-232.

(編輯楊波)

Process matching method based on semantic repository

CHANG Guanyu, YANG Haicheng, SUN Peng

(School of Mechanical Engineering, Northwestern Polytechnical University, Xi′an 710072, China)

Abstract:To calculate the process similarity with consideration of deep semantics correlation between business processes, and to optimize the time complexity and matching result when the node number of business process becomes larger and larger, a process matching method based on GA (Genetic Algorithm) is put forward. This method is applied in similarity calculation for both process semantic and process structure, in which encoding is determined, and greedy algorithm is utilized to initialize the population of GA. By defining genetic operations and adopting some strategies for simplifying, the optimization of business process matching with large node number is fulfilled. As is expected, the experiments prove that the overall performance of algorithm proposed in this paper is better than the others that exist, especially when the count of process nodes grows to a large number. So it is concluded that the application of GA in business process similarity calculation and corresponding process optimization can effectively control the time complexity, meanwhile ensure the quality of the matching result, which shows a good practicability.

Keywords:business process; text similarity; semantic repository; match similarity; genetic algorithm

doi：10.11918/j.issn.0367-6234.2016.07.025

收稿日期:2015-03-26

基金項目:國家自然科學(xué)基金(51375395)

作者簡介:常關(guān)羽(1985—)，男，博士研究生; 楊海成(1959—)，男，教授，博士生導(dǎo)師

通信作者:常關(guān)羽，dengxiao@mail.nwpu.edu.cn

中圖分類號:TP315

文獻標(biāo)志碼:A

文章編號:0367-6234(2016)07-0150-06