基于NGSAA算法的分布式數據庫查詢優化研究

鄒汪平 (池州職業技術學院信息技術系，安徽 池州 247000)

基于NGSAA算法的分布式數據庫查詢優化研究

鄒汪平 (池州職業技術學院信息技術系，安徽 池州 247000)

針對遺傳算法在分布式數據庫查詢優化中存在的不足之處，提出了一種基于小生境技術的遺傳模擬退火算法。首先擴展了算法的搜索區域以避免早熟現象的出現，然后進行規則的簡化以降低功能性冗余，再將算法應用于分布式數據庫查詢優化中。研究表明，該算法可以有效降低生成最優查詢策略的總代價和時間，提高了查詢優化的整體效率。

遺傳算法；小生境技術；模擬退火算法；分布式數據庫查詢優化

遺傳模擬退火算法(GSAA)在分布式數據庫查詢優化中的全局搜索中有較好的表現[1]，但其存在收斂速度慢、早熟收斂等缺陷。針對該算法中的不足，筆者提出了一種改進的基于小生境技術[2-3]的遺傳模擬退火算法(NGSAA)，并將該算法應用于分布式數據庫查詢優化中，可以很好地保持種群的多樣性，同時能夠在保證全局搜索能力的前提下提高收斂速度，避免早熟現象的出現。

1 NGSAA算法概述

1.1GSAA算法與小生境技術的結合

為了將GSAA算法與小生境技術有效地結合，首先引入一個新的概念——相似度S，其指的是形態各異的染色體上的基因排列順序的相似程度，以便于分布式數據可查詢優化的應用，可用如下公式表示：

(1)

式中，S(x,y)是指初始種群中某一個體的x和y2個染色體上的基因排列順序的相似度；(2M-1)是每條染色體所含基因的總量；x[N]是指在染色體x中位置N處的基因；y[N]是指在染色體y中位置N處的基因。

為了能夠將小生境技術融入GSAA算法，必須對初始種群和選擇算子[4]加以改進。其中，相似度S在初始種群的選擇過程中起到至關重要的作用。若初始種群的數量用i來表示，假設存在2i個染色體，若要得出某一條染色體的總相似度Sx，應將該染色體與其他所有的染色體之間的相似度求和：

(2)

式中，S(Ax,Ay)表示某一條染色體與另一條染色體的相似度。

將求出的2i個總相似度以升序的形式排序并取前i個相似度較小的染色體構造初始種群，利用該機制構造的初始種群所具有的多樣性來進一步提高小生境技術的作用。

在設定選擇算子C時,首先計算出父代染色體和其子代的染色體的相似程度，如果最終得出的相似度超過染色體所含基因總量，就再將該父代染色體和其子代染色體的適應度繼續進行對比。當子代染色體的適應度超過父代染色體時，就代替其父代染色體，反之亦然。其計算公式如下：

(3)

式中，Cfather表示父代染色體；Cson表示子代染色體；F()表示染色體的適應度。

1.2NGSAA算法

NGSAA算法以GSAA算法為其子算法，利用小生境技術進一步降低算法的功能性冗余。算法描述如下(其中，Ch表示染色體、ChArray表示染色體數組、BestCh表示最優染色體)。

Begin:

//從染色體數組中根據相似度大小構造初始種群Pop

PopSele [ChArray]→Pop

// 計算種群中每個染色體的適應度

F(Pop)

//搜索最優染色體

for the best Ch not appear do

// 對染色體進行相應的交叉運算

Cross(Pop) → Pop1

// 對染色體進行相應的變異運算

Mut(Pop1) →Pop2

//對種群中的染色體運用模擬退火算法并強化局部搜索

for each Ch in Pop2 do

SA(Ch) →NextChrom

nextCh →NextPop[index]

end for

//利用融入小生境技術的選擇算子對種群進行選擇

Pop←Sele (Pop，NextPop)

//判斷是否產生最優的染色體

for each Ch in Pop do

if Ch is the best then

Ch →BestCh

end if

end for

end for

//返回最優染色體

return BestCh

End

2 分布式數據庫查詢優化

為了能夠在分布式數據庫查詢優化中應用NGSAA算法，必須首先對存在的所有可行數據庫查詢策略進行相應的編碼，構造遺傳算法中的染色體結構。將關系節點作為葉子節點并以某個正整數表示；將中間節點作為連接操作用字符0表示，使用先序遍歷方式排序后對于一個連接關系為N的查詢二叉樹可構造長度為2N-1編碼，經過逐步規約后得到最終的葉子節點，再將規約倒序展開完成染色體結構的轉化。另外，還必須對算法進行相應設定：適應度函數F()在此轉換成根據染色體的鏈接順序進行多連接查詢的代價；對染色體進行整理產生新一組染色體的過程可采用交叉方式完成；對于變異算子采用染色體隨機將2個非零基因進行互換來構造新染色體。上述設定可以降低適應度以防止遺傳到下一代。

在進行分布式數據庫查詢優化時，使用數組結構通過查詢條件及其數據庫全局數據字典(GDD)構造染色體，在此基礎上結合NGSAA算法搜索出最優查詢策略，并利用該策略完成查詢的過程，具體內容描述如下(其中，QDemand是用戶查詢要求；QStrategy是查詢策略；Result是查詢結果)。

Begin：

//輸入用戶的查詢要求和加載全局數據字典

input(QDemand) →Condition

load(GDD) → Dictionary

// 對查詢策略進行編碼以形成染色體數組

for 2i Chs is not enough do

Code(Condition, Dictionary) →Ch

Ch→ ChArray[index]

end for

//調用NGSAA算法

NGSA(ChArray) →BestChr

//將最優染色體轉換回相對應的查詢策略

transform(BestChr) →QStrategy

//按最優策略進行查詢并返回查詢結果

query(QStrategy) → Result

return Result

End

3 仿真試驗

為了驗證基于NGSAA算法的分布式數據庫查詢優化性能，模擬實驗環境利用虛擬局域網進行，在分布式數據庫中設置10個存儲有大數據量數據表的節點機，服務器上存有包含節點機各種信息的數據字典，每個節點機上的數據表中的數據記錄數量在2200至15000條之間并隨機分布，用于模擬整個網絡的實時狀態以及節點機中包含的數據表在互相連接時的數據選擇率。在確定的最優查詢策略下，比較NGSAA算法和GSAA算法的分布式數據庫查詢優化實質上就是比較兩者搜索最優查詢策略的總代價和總響應時間。設定查詢過程中數據分布在2～9這8個節點機上并設定初始種群為19，分別用NGSAA算法和GSAA算法對分布式數據庫查詢優化進行最優查詢策略的搜索，其結果如圖1所示。由圖1可知，基于NGSAA算法的分布式數據庫查詢優化搜索出最優查詢優化策略所需的進化代數要遠遠低于GSAA算法。因此，在確定的最優查詢策略下，使用NGSAA算法搜索該查詢策略的總代價比使用GSAA算法更優。

將基于NGSAA算法和GSAA算法的分布式數據庫查詢優化搜索出最優查詢優化策略所需時間進行對比。設定查詢過程的查詢條件為8個，即關系數為8，并設定初始種群為19，搜索數據的站點限制在2～9這8個節點機上并限制進化代數小于或等于30，即終止條件為30代進化內不再出現更優策略，記錄多次試驗下生成最優查詢優化策略的時間的平均值。最優查詢優化策略生成時間圖如圖2所示。由圖2可知，在關系數相同的情況下基于NGSAA算法的分布式數據庫查詢優化生成最優查詢優化策略的所耗費的時間更短。

圖1 總代價與進化代數關系圖 圖2 最優查詢優化策略生成時間圖

4 結 語

將GSAA算法與小生境技術有效的結合到一起，引入相似度并應用于初始種群的建立，重新設定選擇算子的方式以降低算法冗余，提出一種改進的NGSAA算法并將其應用于分布式數據庫查詢優化以改善查詢優化的性能。試驗結果表明，NGSAA算法在一定程度上降低了查詢優化的總代價和總時間，提高了查詢優化的整體效率。需要說明的是，進行仿真試驗時是基于確定的最優查詢策略，而實際上無論是GSAA算法還是NGSAA算法都是基于隨機策略，因而對在搜索過程中會隨機出現非最優解的情況還有待進一步分析研究。

[1]劉波，孟相如，麻海圓.一種用于分組調度的遺傳模擬退火算法[J].通信技術，2009(2):91-93.

[2]Lingyun Wei, Mei Zhao.A niche hybrid genetic algorithm for global optimization of continuous multimodal functions[J]. Applied Mathematics and Computation，2005(3):649-661.

[3]陳皓,崔杜武,崔穎安,等.族群進化算法[J].軟件學報，2010(5):978-990.

[4]姜彬峰.一種初始種群算法的應用研究[J].制造業自動化，2011(10):94-96.

[編輯] 李啟棟

TP183

A

1673-1409(2013)25-0046-03

2013-06-12

鄒汪平(1982-)，男，碩士，講師，現主要從事算法設計方面的教學與研究工作。