改進布谷鳥算法的數據庫查詢優化

席潔

(陜西國防工業職業技術學院，戶縣 710300)

改進布谷鳥算法的數據庫查詢優化

席潔

(陜西國防工業職業技術學院，戶縣 710300)

針對布谷鳥算法局部搜索能力弱、尋優精度低等缺陷，提出了一種改進布谷鳥算法的數據庫查詢優化算法(BACS)。按照布谷鳥優化算法對鳥巢位置進行更新，然后利用蝙蝠算法的動態轉換策略對鳥巢位置進一步更新，避免算法陷入局部最優，將BACS應用于數據庫查詢優化問題求解，并通過仿真實驗對BACS的性能進行測試。結果表明，BACS加快了數據庫查詢優化求解的收斂速度，獲得了質量更高的查詢優化方案。

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

0 引言

隨著數據庫規模日益增大，數據查詢頻率增加，如何找到滿足用戶查詢要求方案，提高數據庫查詢效率，成為當前研究的熱點問題[1]。

針對數據庫查詢優化問題，國內外學者投入了大量時間和精力進行了研究[2]。由于數據庫查詢優化問題是一個多約束的組合優化問題，是一個NP難題，一些學者將啟發式算法引入到數據庫查詢中[3]。帥訓波等提出了一種遺傳算法的查詢優化方法[4]。Zhou等人提出了進化算法的數據庫查詢策略[5]。Chen利用模擬退火和遺傳算法的組合式查詢優化方法，但是該算法仍然容易產生早熟現象，難以得到最優解[6]。郭聰莉提出基于蟻群算法的數據庫查詢優化方法，但查詢效果欠優[7]。布谷鳥搜索算法(CS)具有原理簡單、參數少、易實現等優點，為數據庫查詢優化提供了一種新的研究算法[8]。但基本CS算法存在著后期收斂速度慢、收斂精度不高、易陷入局部極小等不足[9]。蝙蝠算法(BA)是一種新興的啟發式群智能算法，可以實現動態控制局部搜索和全局搜索間的相互轉換過程，避免算法陷入局部最優，具有更好的收斂性[10]。

為了提高數據庫查詢的優化效率，提出改進布谷鳥算法的數據庫查詢優化算法(BACS)。首先按照基本布谷鳥優化算法對鳥巢的位置進行更新，然后利用蝙蝠算法中的動態轉換策略對鳥巢位置進一步更新，從而在一定程度上避免算法陷入局部最優，最后通過仿真實驗對BACS的性能進行測試。結果表明，BACS加快了數據庫查詢優化求解的收斂速度，獲得了質量更高的查詢優化方案。

1 BACS算法

1.1 BA算法

BA算法是模擬自然界中蝙蝠利用一種聲吶來探測獵物、避免障礙物的隨機搜索算法，其將種群數量為NP的蝙蝠個體映射為D維問題空間中的可行解，將優化過程和搜索模擬成種群蝙蝠個體移動過程和搜尋獵物，利用求解問題的適應度函數值來衡量蝙蝠所處位置的優劣，將個體的優勝劣汰過程模擬為優化和搜索過程中用好的可行解替代較差可行解的迭代過程。為了模擬蝙蝠探測獵物、避免障礙物，需假設三個近似或理想化的規則：

(1) 所有蝙蝠利用回聲定位的方法感知距離，并且它們采用一種巧妙的方式來區別獵物和背景障礙物之間的不同。

(2) 蝙蝠在位置xi以速度vi隨機飛行，以固定的頻率fmin、可變的波長λ和音量A0來搜索獵物。蝙蝠根據自身與目標的鄰近程度來自動調整發射的脈沖波長(或頻率)和調整脈沖發射率r∈[0，1]。

(3) 雖然音量的變化方式有多種，但在蝙蝠算法中，假定音量A是從一個最大值A0(整數)變化到固定最小值Amin[11]。

1.2 BA算法工作步驟

對于目標函數為minf(X)，目標變量為X=(x1，x2，…，xd)T的優化問題，BA算法的實施過程描述如下：

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

Step2：隨機初始化蝙蝠的位置xi，并根據適應度值的優劣尋找當前最優解x*。

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

(1)

(2)

(3)

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

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

(4)

(5)

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

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

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

1.3 CS算法

在基本CS算法中，在目標函數定義的可行解空間內對N個鳥巢位置隨機初始化，在進化過程中，首先適應度值最優的鳥巢位置被保留到下一代，再利用Levy Flight機制對鳥巢的位置進行更新，得到新的鳥巢位置，最后用外來蛋的發現概率pa與服從均勻分布的隨機數R∈[0,1]進行比較，如R>pa,隨機改變鳥巢的位置，從而得到一組新的鳥巢位置，并確定當前最優的鳥巢位置及最優解。

在CS算法中，布谷鳥在每一次迭代中尋找鳥巢的路徑和位置按式(6)進行更新。

(6)

為實現CS算法，學者提出的模擬Lévy(λ)飛行跳躍路徑的公式，見式(7)。

(7)

式中，s為Lévy飛行跳躍路徑；μ、ν為正態分布隨機數，服從正態分布即為式(8)。

(8)

式中，σμ，σν值分別為式(9)。

(9)

2.4 BACS算法思想

針對基本CS算法的不足，將蝙蝠算法融入到基本CS算法中，使各自的優點融合在一起，提出了一種蝙蝠算法和布谷鳥優化算法的混合優化算法(BACS)。具體步驟為：

(1) 用一個均勻分布隨機數與脈沖的發射速率對比，如條件成立，則對當前最優的鳥巢位置進行隨機擾動，得到新的鳥巢位置，并對其進行越界處理及評估其對應的適應度值。

(2) 利用響度與均勻分布隨機數比較，如果條件得到滿足，用新的鳥巢位置更新基本布谷鳥算法中得到的鳥巢位置，并同時更新響度和脈沖的發射速率。

(3) 最后評估鳥巢的適應度值，找出當前最優的鳥巢位置和最優值，并進入下一次迭代，繼續利用基本的布谷鳥算法進行搜索和位置更新。

2 BACS的數據庫查詢優化問題求解

2.1 數據庫查詢優化的數學模型

對于含有n個關系表的數據查詢優化問題，就是左深樹和右深樹共有n!個數據庫查詢方案，從中找到一條查詢代價最小的查詢方案。本文選擇“左深樹”作為搜索策略空間。對于一個連接J=RjoinS，其計算代價cost(J)如式(10)。

(10)

其中，V(c,R)的計算如式(11)。

(11)

2.2 BACS的數據庫查詢求解步驟

(1) 對左深樹組成的解空間中的連接操作進行編碼，后續遍歷連接樹得到編碼序列L。

(2) 參數初始化：初始化BACS算法的各個參數，如最大迭代次數等。

(3) 根據式(13)目標函數計算鳥巢的適應度值，并確定當前最優的鳥巢位置及最優值。

(4) 保留上代最優的鳥巢位置，利用Levy Flight機制的式(6)～(9)對鳥巢的位置進行更新，得到新的鳥巢位置，并對鳥巢的位置進行越界處理。

(5) 利用目標函數計算步驟(4)獲得的新鳥巢位置適應度值，并與上代鳥巢位置適應度值對比，若好，則替換上一代的適應度值，并更新其對應的鳥巢位置，然后確定當前的最優鳥巢位置和最優值。

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

(7) 把獲得新的鳥巢位置作為蝙蝠算法的初始點并利用式(1)～(5)繼續對鳥巢的位置進行更新，得到一組新的鳥巢位置。

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

(9) 一次迭代完成，進入下一次迭代，判斷是否滿足終止條件，最優粒子對應的數據庫查詢計劃。如果不滿足則轉到步驟(4)，繼續循環迭代。

3 仿真實驗

3.1 仿真環境

為了測試BACS算法的性能，在CPU為Intel CoreTM 2 Quad 2.5 GHz，RAM為4.0 GB，操作系統為Windows XP的平臺下，采用VC++編程數據庫查詢優化算法實現仿真實驗。數據庫來自一個大型人事系統的數據，共有1萬條記錄，每條記錄包括多個子字段。同時為了使本文算法具有可對比性，選擇的對比算法為：基本布谷鳥算法(CS)算法、文獻[13]改進的布谷鳥優化(MCS)算法。

3.2 結果與分析

最優查詢方案的收斂情況和質量，如圖1和圖2所示。對圖1與圖2結果進行分析，可以得到如下結論：

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

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

(1) 對于10個關系的數據查詢問題，當迭代490代時，CS算法才找到最優數據庫查詢方案，對應的執行時間為280.22 s；

(2) 在相同條件，當迭代377代時，MCS算法找到最優數據庫查詢方案，其執行時間為210.25 s，相對于CS算法，性能更優。

(3) 對于相同問題，BACS算法迭代230次后得到比CS算法和MCS算法更優的數據庫查詢方案，其執行時間為175.29 s。

(4) 相對CS算法，MCS算法提高了求解速度，獲得更優的查詢解，同時BACS算法性能得到進一步提高，克服了對比算法存在的不足，是一種速度快、效率的數據庫查詢優化方法。

4 總結

數據庫查詢優化是一個NP問題，針對CS算法查詢代價高，效率低的問題，為此提出基于BACS算法的數據庫查詢優化方法。結果表明，相對于比算法，BACS算法可以獲得更優的數據查詢效果。

[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] Yang X S. A new metaheuristic bat-inspired algorithm[J]. Springer,2010,28(10):65-74.

[11] Amir Hossein Gandomi, Xin-She Yang, Amir Hossein Alavi. Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems [J]. Springer, 2013, 30(2):17-35.

[12] 石偉. 混沌粒子群算法在數據庫查詢優化中的應用[J]. 科技通報,2012,28(4):116-118.

[13] 王凡,賀興時,王燕.基于高斯擾動的布谷鳥搜索算法[J]. 西安工程大學學報,2011,25(4): 566-569.

Database Query Optimization Based on Improved Cuckoo Search Algorithm

Xi Jie

(Shanxi Institute of Technology, Huxian 710300, China)

In order to solve the problems of Cuckoo algorithm including low optimizing accuracy, weakly local search ability, a novel query optimization method for database is proposed based on imrpoved Cuckoo search algorithm (BACS). Firstly, nest location is updated according to the basic Cuckoo search algorithm, and then Cuckoo nest location is further replaced according to the dynamic conversion strategy in the Bat algorithm to avoid falling into a local optimum, finally it is applied to solve the query optimization problem of database. The performance of BACS is tested by simulation experiments. The results show that, BACS accelerates the convergence speed of database query optimization, and can obtain higher quality query optimization scheme.

Database； Optimization query; Cuckoo algorithm; Bat algorithm

席 潔(1983-)，講師，碩士，研究方向：計算機網絡技術。

1007-757X(2017)08-0043-03

TP311

A

2017.06.05)