基于多群智能優化算法的數據庫查詢優化研究

劉春茂，張云崗

?

基于多群智能優化算法的數據庫查詢優化研究

劉春茂，張云崗

摘 要：查詢優化是提高數據庫性能的關鍵技術，針對數據庫查詢優化效率低的難題，提出了一種多群智能優化算法相融合的數據庫查詢優化算法。首先按照布谷鳥優化算法對鳥巢位置進行更新，然后利用蝙蝠算法的動態轉換策略對鳥巢位置進一步更新，避免算法陷入局部最優，最后通過仿真實驗對算法的性能進行測試。結果表明，其算法是解決數據庫查詢優化的有效途徑，能夠獲得理想的數據庫查詢計劃，具有實際意義。

關鍵詞：數據庫；查詢優化；布谷鳥搜索算法；蝙蝠算法

0　引言

隨著數據庫規模日益增大，數據查詢頻率增加，因此數據查詢效率至關重要，如何快速找到滿足用戶查詢條件的記錄，是現代大規模數據研究的熱點問題[1]。

針對數據庫查詢優化問題，國內外學者投入了大量時間和精度進行了研究[2]。數據庫查詢優化是一個典型的多約束的組合優化問題，傳統窮舉搜索算法存在效率低，效果差等缺陷，為此，一些學者將啟發式算法引入到數據庫查詢中[3]。出現了基于遺傳算法、蟻群算法、粒子群算法、模擬退火、蛙跳算法以及它們的組合算法[4-8]，一定程度上提高了查詢優化效果，獲得了比較理想的查詢效果，但是隨著數據庫規模的不斷擴大，這些算法的問題開始暴露出來，出現了收斂速度慢、易陷入局部最優、早熟現象，難以得到全局最優的數據庫查詢方案[9]。布谷鳥搜索算法（CS）具有原理簡單、參數少、易實現等優點，為數據庫查詢優化提供了一種新的研究算法[8-10]。

為了提高數據庫查詢的優化效率，提出一種多群智能優化算法的數據庫查詢優化算法，結果表明，本文算法加快了數據庫查詢優化求解的收斂速度，獲得了質量更高的查詢優化方案。

1　本文算法

1.1 BA算法

BA算法是模擬自然界中蝙蝠利用一種聲吶來探測獵物、避免障礙物的隨機搜索算法，即模擬蝙蝠利用超聲波對障礙物或獵物進行最基本的探測、定位能力，并將其和優化目標功能相聯系。對于目標函數為minf(X)，目標變量為的優化問題，BA算法的實施過程描述如下：

Step1 種群初始化，即蝙蝠以隨機方式在D維空間中擴散分布一組初始解。具體包括：初始種群個體數（蝙蝠數目）NP，最大脈沖音量，最大脈沖率，搜索脈沖頻率范圍，音量的衰減系數，搜索頻率的增強系數，搜索精度或最大迭代次數iter_max。

Step3 蝙蝠的搜索脈沖頻率、速度和位置更新。種群在進化過程中，每一代個體的搜索脈沖頻率、速度和位置按如下公式進行變化如公式（1）~（3）：

公式（1）中：β∈[0，1]是均勻分布的隨機數；fi是蝙蝠i的搜索脈沖頻率，分別表示蝙蝠時刻的速度；分別表示蝙蝠i在t和t-1時刻的位置；x*表示當前所有蝙蝠的最優解。

Step4 生成均勻分布隨機數rand，如果rand>ri，則對當前最優解進行隨機擾動，產生一個新的解，并對新的解進行越界處理。

Step5生成均勻分布隨機數 rand，如果 rand

Step6對所有蝙蝠的適應度值進行排序，找出當前的最優解和最優值。

Step7 重復Step2~Step6步驟，直至滿足設定的最優解條件或者達到最大迭代次數。

Step8 輸出全局最優值和最優解。

1.2 CS算法

在CS算法中，布谷鳥在每一次迭代中尋找鳥巢的路徑和位置進行更新為公式（6）：

為實現 CS算法，Yang Xin She和 Deb Suash采用Mantegna于1992年提出的模擬Lévy(λ)飛行跳躍路徑如公式（7）：

1.2 本文算法思想

基于基本CS算法，將蝙蝠算法融入到基本CS算法中，使各自的優點融合在一起，提出了一種蝙蝠算法和布谷鳥優化算法的混合優化算法（BACS）。

BACS算法具體實施步驟如下：

Step1 初始化 BACS算法的各個參數,脈沖音量衰減系數alf、鳥巢數量n、外來蛋的發現概率Pa以及隨機初始化鳥巢的位置等；

Step2 根據目標函數計算鳥巢的適應度值，并確定當前最優的鳥巢位置及最優值；

Step3 保留上代最優的鳥巢位置，利用Levy Flight機制的公式（6）～（9）對鳥巢的位置進行更新，得到新的鳥巢位置，并對鳥巢的位置進行越界處理；

Step4 利用目標函數計算Step3獲得的這組新鳥巢位置相應的適應度值，并與上代鳥巢位置對應的適應度值對比，若好，則用當前的適應度值替換上一代的適應度值，并更新其對應的鳥巢位置，然后確定當前的最優鳥巢位置和最優值；

Step5 用外來蛋的發現概率 pa與服從均勻分布的隨機數R∈[0,1]進行比較，如R>pa,隨機改變鳥巢的位置，從而得到一組新的鳥巢位置；

Step6 把Step5獲得這組新的鳥巢位置作為蝙蝠算法的初始點并利用公式（1）～（5）繼續對鳥巢的位置進行更新，得到一組新的鳥巢位置；

Step7 評估Step6獲得的鳥巢位置的適應度值，經比較后，確定當前最優的鳥巢位置及最優值；

Step8 一次迭代完成，進入下一次迭代，判斷是否滿足結束條件，滿足退出程序并輸出最優解及最優值，否則，轉Step3。

為了驗證本文算法的性能優于CS算法，采用Sphere函數[11]進行仿真測試，它們的收斂曲線如圖1所示：

圖1　本文算法和CS算法的性能對比

從圖1可知，本文算法收斂速度更快、收斂精度更高、迭代次數少。

2　本文算法的數據庫查詢求解

2.1 數學模型

對于一個連接 J=RjoinS，其計算代價 cost（J）如公式（10）[12]：

其中，V(c,R)的計算如公式（11）：

2.2 本文算法的數據庫查詢求解步驟

（1）參數初始化。

（2）計算鳥巢的適應度值，并確定當前最優的鳥巢位置及最優值。

（3）利用Levy Flight機制的公式（6）～（9）對鳥巢的位置進行更新，得到新的鳥巢位置。

（4）利用新鳥巢位置適應度值與上代鳥巢位置適應度值對比，確定當前的最優鳥巢位置和最優值。

（5）如R>pa，隨機改變鳥巢的位置，從而得到一組新的鳥巢位置。

（6）把獲得新的鳥巢位置作為蝙蝠算法的初始點進行更新，得到一組新的鳥巢位置。

（7）確定當前最優的鳥巢位置及最優值；

（8）判斷是否滿足終止條件，如果不滿足則轉到步驟（4），繼續循環迭代。

3　結果與分析

操作系統為Windows 7 ，CPU為Intel（R） Core（TM）i3-2120，主頻為 3.30GHz，內存為 2GB，編程語言為MATLAB R2012b。最優查詢方案的收斂情況和質量，如圖2和圖3所示：

圖2　各種數據庫查詢優化算法的迭代次數

圖3　各種數據庫查詢優化算法的執行時間對比

對圖2與圖3結果進行分析可知，相對CS算法，BACS算法提高了求解速度，獲得更優的查詢解，同時本文算法性能得到進一步提高，克服了對比算法存在的不足，是一種速度快、效率的數據庫查詢優化方法。

4　總結

針對當前數據庫查詢優化算法存在的效率低，難以獲得最優解的缺陷，提出一種BACS算法的數據庫最優查詢方法。實驗結果表明，BACS算法以提高算法的全局搜索能力，較好的克服BA算法存在的局部最優缺陷，獲得了更優的數據庫查詢方案，在數據庫中具有廣泛的應用前景。

參考文獻

[1] 張敏,馮登國,徐震. 多級多版本數據庫管理系統全局串行化[J]. 軟件學報,2007,18(2):346-347.

[2] 張麗平,李松,郝忠孝. 球面上的最近鄰查詢方法研究[J].計算機工程與應用, 2011, 47(5): 126-129.

[3] Zhang Jun, Huang De-Shuang, Lok Tat-Ming, et al. A novel adaptive sequential niche technique for multimodal function optimization [J]. Neurocomputing, 2006, 69(16): 2396-2401.

[4] 帥訓波,馬書南,周相廣,龔安. 基于遺傳算法的分布式數據庫查詢優化研究[J]. 小型微型計算機系統,2009,30(8):1600-1604.

[5] Zhou Zehai. Using heuristics and genetic algorithms for large scale database query optimization [J].Journal of Information and Computing Science,2007,2(4):261-280.

[6] Chen Po-Han, Shahandashti S M. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints [J]. Automation in Construction, 2009, 18(4):434-443.

[7] 郭聰莉,朱莉,李向. 基于蟻群算法的多連接查詢優化方法[J]. 計算機工程,2009,35(10):173-176.

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

[9] 林桂亞. 基于粒子群算法的數據庫查詢優化[J]. 計算機應用研究,2012,29(3):974-975.

[10] 鄭先鋒,王麗艷. 自適應逃逸動量粒子群算法的數據庫多連接查詢優化[J]. 四川大學學報(自然科學版),2013,50(3):100-103.

[11] 于洪濤,錢磊. 一種改進的分布式查詢優化算法[J]. 計算機工程與應用, 2013, 49(8): 151-155.

[12] Liu J, Sun J, Xu W B. Quantum-behaved particle swarm optimization with adaptive mutation operator [A]. LNCS, 2006, 4221: 959-967.

[13] 林鍵,劉仁義,劉南等. 基于查詢優化器的分布式空間查詢優化方法[J]. 計算機工程與應用, 2012, 48(22): 161-165.

中圖分類號：TP311

文獻標志碼：A

文章編號：1007-757X(2016)07-0025-04

收稿日期：（2016.03.20）

基金項目：河南省科技計劃項目（142102210557）

作者簡介：劉春茂（1979-），男（漢族），南陽人，河南工業職業技術學院，電子信息工程系，講師，碩士，研究方向：數據庫與知識庫方向，南陽，473000張云崗（1983-），男（漢族），南陽人，河南工業職業技術學院，電子信息工程系，講師，碩士，研究方向：數據庫與知識庫方向，南陽，473000

Research on Database Query Optimization Based on Multi Group Intelligent Optimization Algorithm

Liu Chunmao，Zhuan Yungang
(Department of Computer Engineering, Henan Polytechnic Institute, Nanyang 473000, China)

Abstract:Query optimization is a key factor to improve the performance of database systems. In order to solve low query problem of traditional database query optimization algorithm, a novel query optimization method of database is proposed based on multi group intelligent optimization algorithm. Firstly, nest location is updated according to the basic cuckoo search optimization algorithm, and then cuckoo nest location is further replaced according to the dynamic conversion strategy in the bat algorithm, avoiding falling into a local optimum. Finally it is applied to solve the query optimization problem of database, and the performance is tested by simulation experiments. The results show that the proposed algorithm is an effective method for database query optimization, and can obtain good query optimization plan.

Key words:Database; Optimization Query; Bat Algorithm; Cuckoo Search Algorithm