群體智能混合算法優化ＸＭＬ數據查詢策略

收稿日期：2007-11-26；修回日期：2008-03-03

基金項目：國防基礎研究基金資助項目（A1420061266）；江蘇省教育廳青年骨干教師計劃資助項目(2006)

作者簡介：翟學敏(1983-)，女，江蘇豐縣人，碩士研究生，主要研究方向為網絡信息管理系統（minmin0876@yahoo.com.cn）；劉淵（1967-），男，教授，主要研究方向為網絡流量、網絡安全；劉波（1969-），男，博士，主要研究方向為數據庫管理信息系統；畢蓉蓉（1983-），女，碩士研究生，主要研究方向為網絡信息管理系統*

(1江南大學 信息工程學院，江蘇 無錫 214122; 2南京理工大學 計算機學院，南京 210094;

3中南大學 信息學院，長沙 410083)

摘 要：采用路徑離散化規則，結合XML半結構化的特點及概率知識，融合粒子群算法與蟻群算法，提出一種優化XML數據查詢的概率方法，采用粒子群算法快速生成信息素分布，利用蟻群算法精確求解，達到了優勢互補，提高了數據查詢的范圍和收斂的效率。仿真實驗表明這種融合方法具有更好的查詢效果。

關鍵詞：粒子群算法；蟻群算法；信息素；路徑離散；可擴展標記語言概率查詢

中圖分類號：TP 301

文獻標志碼：A

文章編號：1001-3695(2008)10-2970-03

Optimized query strategy of XML data with swarm intelligent mix algorithms

ZHAI Xue-min¹，LIU Yuan¹，2， LIU Bo3， BI Rong-rong¹

( 1. College of Information Engineering， Southern Yangtze University， Wuxi Jiangsu 214122， China; 2. School of Computer， Nanjing University of Science Technology，Nanjing 210094， China; 3.College of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:This paper adopted path scatter rule to combine PSO with ACO to improve XML probabilistic query which adopted PSO to make pheromone distribution and made use of ASO to get a value accurately， as a result it developed enough advantages of the two algorithms and the data query range was widen and convergence efficiency was increased. Through simulation experiments， it shows this combine method has a preferable query effect.

Key words：particle swarm optimization；ant colong optimization；pheromone；path scatter；XML probabilistic query

XML作為一種具有靈活、開放、跨平臺、跨語種等特征的文本標記描述語言，被廣泛用于信息的表達與交換，由此產生海量的XML數據信息，但這些信息需要查詢、分析與利用。經過多年的發展，人們根據XML的特征提出了許多查詢算法，如XPath查詢最小化、X-RESTORE的XML視圖查詢等，特別是利用概率進行查詢，有助于減小XML查詢的搜索空間、循環比較次數，從而提高查詢的效率。文獻[1]根據樹的半結構化特點及DTD語法規則，利用條件概率對XML概率查詢進行統計分析，并提出概率關系式A=(N，Σ，R，ρ，P）；文獻[2]利用K-鄰域概率方法討論數據分類算法，加快XML的分類操作；文獻[3]利用滑動窗體進一步討論挖掘頻繁XML查詢模式的相關算法；而粒子群算法[4]與蟻群算法[5]近年來也廣泛用于分析XML路徑查詢優化問題，這些都是本文研究的重要基礎。

本文利用概率知識研究XML查詢問題，結合粒子群算法的快速分布與蟻群算法求精確解，期望能讓這兩種群智能算法優勢互補，讓XML查詢更具有智能性。

1 群體智能混合算法

11 問題描述

設N={N1，N2，…，Nn}表示XML相關節點的集合；E={E1，E2，…，Em}表示XML路徑的集合；P={P1，P2，…，Pn}表示每條路徑概率的集合。那么對于給定的一系列多次查詢要求，如何采用有效方法能從根節點快速定位到要查找的節點而查詢代價最小；對于多次查詢的一組節點，如何設計查詢路徑；對于不斷變化的XML文檔，如何維護其節點概率。

12 相關定義

定義1 XML查詢樹。XML文檔的路徑查詢可以描述為一棵查詢樹T=(N，E，root，predicate，P)。其中：N是樹中節點的集合;root是樹根；E是樹中路徑的集合，描述父子關系和祖先—后代關系；函數predicate是T中的每個節點的謂詞條件；P表示每個節點出現的概率集合。

XML查詢樹所表示的路徑表達式是XPath的子集，簡單起見，將路徑查詢的定義簡化為Q= (NT，ET，PT)。其中：NT表示節點集；ET表示邊集；PT表示節點對應的概率集。

定義2 路徑項目。給定一個XML路徑查詢Q=(NT，ET，PT)，一個路徑項目i是滿足如下條件的某條路徑的子路徑:

a)i中的節點之間的邊不表示祖先—后代關系，即i中不包含“//”；

b)i是最簡約的:對于一個給定的路徑集P，將其中一個路徑表達式t離散化后得到的任意路徑項目i1，i2，且i1≠i2，若i1i2，i2i1，則稱該路徑項目集是最簡約的；

c)任意vi，且v≠v[predicate]，即某個節點和帶有謂詞的該節點是不同的路徑項目；若v≠v[p]，即某個節點和帶有概率系數的該節點也是不同的路徑項目。

為了獲得路徑項目，需要將XML查詢樹中的所有路徑離散為路徑項目，常常根據XPath子集包含的孩子軸(/)、后裔軸(//)、謂詞和概率屬性進行簡單路徑分解。

定義3 簡單路徑。給定一個路徑查詢Q=(NT，ET，PT)，Q中的一條路徑p=(v1，v2，…，vn)為簡單路徑，那么：

a)vi∈NT，vi是vi+1的父親節點或祖先節點，i=1，2，…，n；

b)路徑中相鄰節點之間的邊(vi，vi+1)表示父子關系或祖先—后代關系；

c)v[predicate]∈NT，predicate僅針對屬性值和文本值，不包含相對路徑；

d)v[p]∈NT，p表示對應節點的查詢概率，且0≤p≤1；

e)表達式中不出現通配符“*”和“？”。

13 簡單路徑離散與智能查詢算法

基于上述定義，首先構建簡單路徑離散算法，其基本思想是遇到“//”或“/”進行分割，直到任何路徑片段不包含更小的路徑片段，并刪除重復項。

算法1 XML簡單路徑離散算法

輸入:XML路徑集P；

輸出:路徑項目集I；

Simple_Path_Scatter(P)

a)for each(t in P){//順序掃描，初步提取路徑項目

if (′//′or ′/′in t){

經′//′ or ′/′進行切割；

}

}

b)I′←{i1′，i′2，…，i′n}

c)I←Test_and_Disperse(I′);

//若I′未滿足“最簡約”要求，則進一步分割

d)return I;

算法2 路徑片段最簡約分割算法

輸入：路徑片段集合I′；

輸出：經過進一步離散化的路徑片段集合I′；

Test_and_Disperse(I′)

for each(i′in I′){//若不滿足“最簡約”要求，進一步離散化

if(i′是單一節點||( i′∈{ I′- i′}i′xi′)){

continue;

}

if(i′x∈{ I′- i′} i′xi){

以i′x為軸離散i′，得I′x;

I′←{I′-i′}∪I′x;

Test_and_Disperse(I′);

}

}

return I′;

例1 針對文獻[6]，若XML查詢文檔中存在如下簡單查詢路徑表達式：

Q1：/SigmodRecord/issues/issue/articles/article/title[@articleCode=\"152009\"];

Q2：articles/article//author[@AuthorPosition=\"01\"];

Q3：articles/article//title[@articleCode=\"152031\"]//initpage;

則執行算法1后的路徑項目集I={SigmodRecord，issues，issue，articles，article，title [@articleCode=\"152009\"]，title[@articleCode=\"152031\"]，author[@AuthorPosition= \"01\"]，initpage}。

求取離散的路徑項目后，就可以利用群體智能算法進行XML查詢操作了。

首先，根據路徑項目集中每個節點出現的次數確定節點的概率，粒子群算法無太多約束條件，適合前期隨機查詢。利用PSO產生一系列隨機粒子，并在約束條件下找出查詢結果的最優解，并記錄相應路徑。其次，利用ACO求解路徑上的信息素，當再次進行數據查詢時，就首先查詢已成功的路徑，若都不成功，再利用PSO產生新的粒子進行求解。

群體智能混合算法表述如下：

輸入：XML文檔集T，查詢語句P；

輸出：查詢結果R及時間time；

A XML Swarm Intelligent Mix Algorithm (T，P)//簡稱XSIMA

a)Simple_Path_Scatter(P);//離散化XML查詢語句

b)將路徑項目集I看成一個個粒子，并根據式(1)和(2)隨機初始化粒子群中粒子的速度和位置。

Vk+1i=wVki+ci R and ()(PBki-Xki)+

c2 R and()(GBk-Xki)(1)

Xk+1i=Xki+Vki(2)

c)根據PSO計算每個粒子的適應度，并與最優粒子的適應度比較，若好于最優值則更新最優粒子與適應度。

d) 用式（1）（2）更新粒子速度和位置，為防止局部最優，可進行雜交優化，當達到設定條件后結束，否則返回步驟c)。

e)計算出一組粒子的相應概率后，再利用ACO測試其余組數據。

f)根據式（3）（4），首先令Nc=0，設置Ncmax，并對查詢樹T有向邊賦信息素初始值τij(0)=τ0， Δτij(0)=0；τij(t+n)=(1-ρ)τij(t)+Δτij(t)(3)

Δτij(t)=∑m1Δτijk(t)(4)其中：Δτij(t)表示信息素增量；Δτkij(t)表示第k只螞蟻在循環過程中釋放邊ij上的信息素。Δτijk(t)=Q/DK

若k只螞蟻在本循環經過邊ij

0otherwise（5）其中：Q為常數，表示信息素強度；DK為本次循環第k只螞蟻所形成的代價單位和。

螞蟻在循環時，向哪個節點轉移由轉移概率Pkij(t)決定

Pkij(t)=ταir(t)ηβij(t)/∑r∈allowedkταir(t)ηβij(t) j∈allowedk

0otherwise(6)

其中：Pkij(t)為螞蟻由站點i選擇站點j的概率，最終達到螞蟻在所有的路徑上處于均勻分布的目的，使用基于均勻分布的選擇原則，有效地解決了ACO 加速收斂和早熟停滯；allowedk={C-tabuk}：螞蟻k為當前能選擇的節點集合；tabuk是禁忌表，記錄螞蟻k已走節點和不能走的節點，用來說明人工螞蟻的記憶性；ηij=1/dij：某種啟發信息；α、β為信息素和啟發信息對螞蟻決策的影響程度。

g)將m只螞蟻放置在當前解集上，將當前解節點放入禁忌表tabuk中，并設k=1。

h)t=0，螞蟻k開始爬行。

(a)螞蟻k根據式(6)計算的概率選擇下一個資源j節點并前進，j∈allowedk(t)，t←t+1;

(b)將螞蟻爬過的新節點號加入tabuk，并用式(13)求Δτkp，用式(7)執行局部更新；

τ(tabuk(t-1)，tabuk(t))=

(1-ρ)τ(tabuk(t-1)，tabuk(t)}+Δτkp(7)

(c)若t

τ(tabuk(i)，tabuk(i+1))=(1-ρ)τ(tabuk(i)，

tabuk(i+1))+Δτkg(8)

(d)若k

i)用式(17)求每只螞蟻被選擇的概率，按照賭盤選擇方式從蟻群中選出兩個父體進行雜交。

j)計算雜交生成后路徑的長度D1、D2 ，若D1＜min1≤k≤m(Dkg)，則用式(8)對D1或D2對應路徑執行信息素更新，否則不執行。

k)Nc←Nc+1，若Nc

算法涉及的雜交過程與信息素更新方法如下：

在每次迭代中，根據雜交概率選取一定的粒子放入一個池中。池中的粒子隨機雜交，產生同樣數目的孩子粒子，并用孩子粒子代替父母粒子，以保持種群的粒子數目不變。孩子粒子的位置由父母粒子位置的算術加權和計算，即child1(x)=p*parent1(x+(10-p*)parent2(x))(9)

child2(x)=p*parent2(x+(10)-p*)parent1(x))(10)其中：x為D維的位置向量；childk(x)和parentk(x) (k=1，2)為孩子粒子與父母粒子的位置；p*為D維均勻分布的隨機數向量，其每個分量都在[0，1]取值。

孩子粒子的速度即：child1(v)=parent1(v)+parent2(v)/|parent1(v)+

parent2(v)|parent1(v)(11)

child2(v)=paernt1(v)+parent2(v)/|parent1(v)+

parent2(v)|parent2(v)(12)其中：v為D維的速度向量；childk(v)和parentk(v)（k=1，2）為孩子粒子與父母粒子的速度。

為使求解問題適合ACO求解，需要更新信息素：Δτkp=Q1/Dkp(13)

Δτkp=Q2/Dkg(14)其中：Δτkp為局部信息素更新；Q1、Q2常數為信息素的強度；Dkp為該路程的長度設i，j分別為起點和終點Dkp(i，j)=Cj+trcij

(i，j)∈A

Cjo.w(15)其中：Cj為j的代價成本；trcij為i、j存在次序約束時的操作成本；A為有向邊集合；Δτkg為全局信息素更新；Dkg為該路徑的總長度；allowedk(t)為螞蟻k第t次允許爬行的節點；數組tabuk為螞蟻k爬過的節點，tabuk(0)=0，則Dkg=∑n-1t=0Dp(tabuk(t)，tabuk(t+1))(16)

為增強蟻群算法的尋優能力引入雜交算子，選擇父代螞蟻采用遺傳算法中輪盤賭方式，第k只螞蟻被選項中的概率為pk=Dkg/∑mk=1Dkg(17)

雜交過程先隨機選擇兩個雜交點，然后以鄰近正交的原則交換兩個父體。 此算法時間復雜度O(nc.n3)。

2 實驗仿真

從上面的分析可知，查詢策略的可用性與有效性取決于算法對最佳路徑的獲取和時間的響應，為此實驗劃分兩個部分。首先測試PSO、ACO與XSIMA對最佳路徑獲取的情況；再分別進行單次與多次重復測試，檢測各自的時間性能。

21 數據集與實驗設計

實驗使用C-M 1.73 GHz CPU，1 GB內存，80 GB SATA5400轉硬盤的筆記本，在Win2000專業SP4版操作系統上利用仿真軟件MATHLAB2007a與C#語言進行仿真測試。分別選用英文的ACMSIGMOD[6]中2006、2005、2002、1999年四個年度XML數據集進行實驗分析，每個ACMSIGMOD數據集由數千篇不同XML格式的ACMSIGMOD論文組成。實驗選用1 165個文檔如表1所示，且取c1=c2=2，α=1，β=0.5，Q1=10，Q2=12，ρ=0.9，采取隨機選取三次樣本，每次40個XML文檔，依次用Q1、Q2、Q3進行PSO、ACO與XSIMA算法操作。

表1 實驗中使用的數據子集年度文檔集Index

TermsPageOrdinary

IssuePageProceedings

PageSigmod

Record2006(ACM-1)0451632005(ACM-2)0451632002(ACM-3)0301711999(ACM-4)92051171XML鍵個數13914622 實驗結果分析

由表2和圖1實驗結果可知，利用路徑項目的離散化方法處理XML查詢，粒子群算法在初始查詢時，效果較好，但后續效果不佳；而蟻群算法正好相反。因此綜合這兩種算法用于XML數據查詢就能很好地體現各自的優越性。

表2 實驗測試結果類型重復一次迭代數時間/s重復一百次迭代數時間/s重復一千次迭代數時間/s常規0.328 12542.265 6416.125PSO1000.185 810022.129 2100237.812 0ACO1001.444 310024.057 8100165.016 9XSIMA1001.253 210013.035 5100139.342 63 結束語

本文通過對路徑項目的離散化處理，融合粒子群與蟻群算法，提出了對XML文檔進行路徑查詢的改進算法，有效地克服了XML查詢模式中重復比較的缺陷，使XPath查詢具有智能性，仿真表明對于多次重復查詢，其性能提升至少10%以上。

參考文獻：

[1]CARRASCO R C， RICO-JUAN J R. A similarity between probabilistic tree languages: application to XML document families[J].Pattern Recognition，2003，36(9):2197-2199.

[2]MANOCHA S， GIROLAMI M A. An empirical analysis of the probabilistic K-nearest neighbor classifier[J]. Pattern Recognition Letters，2007，28(13):1818-1824.

[3]YANG Liang-huai， LEE L M， HSUETC W. Efficient mining of frequent XML query patterns with repeating-siblings[J]. Information and Software Technology， 2008，50(5):375-389.

[4]王桐，劉大昕.一種基于改進粒子群優化的XML結構聚類方法[J].小型微型計算機系統，2007，28(5):871-875.

[5]廖飛雄，馬良.圖著色問題的啟發式搜索螞蟻算法[J]. 計算機工程，2007，33(16):191-192，195.

[6][EB/OL].(2007). http://www.sigmod.org/record/xml/index.xml.