基于多群智能優(yōu)化算法的數(shù)據(jù)庫查詢優(yōu)化研究

劉春茂，張?jiān)茘?/p>

?

基于多群智能優(yōu)化算法的數(shù)據(jù)庫查詢優(yōu)化研究

劉春茂，張?jiān)茘?/p>

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

關(guān)鍵詞：數(shù)據(jù)庫；查詢優(yōu)化；布谷鳥搜索算法；蝙蝠算法

0　引言

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

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

為了提高數(shù)據(jù)庫查詢的優(yōu)化效率，提出一種多群智能優(yōu)化算法的數(shù)據(jù)庫查詢優(yōu)化算法，結(jié)果表明，本文算法加快了數(shù)據(jù)庫查詢優(yōu)化求解的收斂速度，獲得了質(zhì)量更高的查詢優(yōu)化方案。

1　本文算法

1.1 BA算法

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

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

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

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

Step4 生成均勻分布隨機(jī)數(shù)rand，如果rand>ri，則對當(dāng)前最優(yōu)解進(jìn)行隨機(jī)擾動(dòng)，產(chǎn)生一個(gè)新的解，并對新的解進(jìn)行越界處理。

Step5生成均勻分布隨機(jī)數(shù) rand，如果 rand

Step6對所有蝙蝠的適應(yīng)度值進(jìn)行排序，找出當(dāng)前的最優(yōu)解和最優(yōu)值。

Step7 重復(fù)Step2~Step6步驟，直至滿足設(shè)定的最優(yōu)解條件或者達(dá)到最大迭代次數(shù)。

Step8 輸出全局最優(yōu)值和最優(yōu)解。

1.2 CS算法

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

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

1.2 本文算法思想

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

BACS算法具體實(shí)施步驟如下：

Step1 初始化 BACS算法的各個(gè)參數(shù),脈沖音量衰減系數(shù)alf、鳥巢數(shù)量n、外來蛋的發(fā)現(xiàn)概率Pa以及隨機(jī)初始化鳥巢的位置等；

Step2 根據(jù)目標(biāo)函數(shù)計(jì)算鳥巢的適應(yīng)度值，并確定當(dāng)前最優(yōu)的鳥巢位置及最優(yōu)值；

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

Step4 利用目標(biāo)函數(shù)計(jì)算Step3獲得的這組新鳥巢位置相應(yīng)的適應(yīng)度值，并與上代鳥巢位置對應(yīng)的適應(yīng)度值對比，若好，則用當(dāng)前的適應(yīng)度值替換上一代的適應(yīng)度值，并更新其對應(yīng)的鳥巢位置，然后確定當(dāng)前的最優(yōu)鳥巢位置和最優(yōu)值；

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

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

Step7 評估Step6獲得的鳥巢位置的適應(yīng)度值，經(jīng)比較后，確定當(dāng)前最優(yōu)的鳥巢位置及最優(yōu)值；

Step8 一次迭代完成，進(jìn)入下一次迭代，判斷是否滿足結(jié)束條件，滿足退出程序并輸出最優(yōu)解及最優(yōu)值，否則，轉(zhuǎn)Step3。

為了驗(yàn)證本文算法的性能優(yōu)于CS算法，采用Sphere函數(shù)[11]進(jìn)行仿真測試，它們的收斂曲線如圖1所示：

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

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

2　本文算法的數(shù)據(jù)庫查詢求解

2.1 數(shù)學(xué)模型

對于一個(gè)連接 J=RjoinS，其計(jì)算代價(jià) cost（J）如公式（10）[12]：

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

2.2 本文算法的數(shù)據(jù)庫查詢求解步驟

（1）參數(shù)初始化。

（2）計(jì)算鳥巢的適應(yīng)度值，并確定當(dāng)前最優(yōu)的鳥巢位置及最優(yōu)值。

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

（4）利用新鳥巢位置適應(yīng)度值與上代鳥巢位置適應(yīng)度值對比，確定當(dāng)前的最優(yōu)鳥巢位置和最優(yōu)值。

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

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

（7）確定當(dāng)前最優(yōu)的鳥巢位置及最優(yōu)值；

（8）判斷是否滿足終止條件，如果不滿足則轉(zhuǎn)到步驟（4），繼續(xù)循環(huán)迭代。

3　結(jié)果與分析

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

圖2　各種數(shù)據(jù)庫查詢優(yōu)化算法的迭代次數(shù)

圖3　各種數(shù)據(jù)庫查詢優(yōu)化算法的執(zhí)行時(shí)間對比

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

4　總結(jié)

針對當(dāng)前數(shù)據(jù)庫查詢優(yōu)化算法存在的效率低，難以獲得最優(yōu)解的缺陷，提出一種BACS算法的數(shù)據(jù)庫最優(yōu)查詢方法。實(shí)驗(yàn)結(jié)果表明，BACS算法以提高算法的全局搜索能力，較好的克服BA算法存在的局部最優(yōu)缺陷，獲得了更優(yōu)的數(shù)據(jù)庫查詢方案，在數(shù)據(jù)庫中具有廣泛的應(yīng)用前景。

參考文獻(xiàn)

[1] 張敏,馮登國,徐震. 多級多版本數(shù)據(jù)庫管理系統(tǒng)全局串行化[J]. 軟件學(xué)報(bào),2007,18(2):346-347.

[2] 張麗平,李松,郝忠孝. 球面上的最近鄰查詢方法研究[J].計(jì)算機(jī)工程與應(yīng)用, 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] 帥訓(xùn)波,馬書南,周相廣,龔安. 基于遺傳算法的分布式數(shù)據(jù)庫查詢優(yōu)化研究[J]. 小型微型計(jì)算機(jī)系統(tǒng),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] 郭聰莉,朱莉,李向. 基于蟻群算法的多連接查詢優(yōu)化方法[J]. 計(jì)算機(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] 林桂亞. 基于粒子群算法的數(shù)據(jù)庫查詢優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用研究,2012,29(3):974-975.

[10] 鄭先鋒,王麗艷. 自適應(yīng)逃逸動(dòng)量粒子群算法的數(shù)據(jù)庫多連接查詢優(yōu)化[J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,50(3):100-103.

[11] 于洪濤,錢磊. 一種改進(jìn)的分布式查詢優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 林鍵,劉仁義,劉南等. 基于查詢優(yōu)化器的分布式空間查詢優(yōu)化方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(22): 161-165.

中圖分類號：TP311

文獻(xiàn)標(biāo)志碼：A

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

收稿日期：（2016.03.20）

基金項(xiàng)目：河南省科技計(jì)劃項(xiàng)目（142102210557）

作者簡介：劉春茂（1979-），男（漢族），南陽人，河南工業(yè)職業(yè)技術(shù)學(xué)院，電子信息工程系，講師，碩士，研究方向：數(shù)據(jù)庫與知識庫方向，南陽，473000張?jiān)茘彛?983-），男（漢族），南陽人，河南工業(yè)職業(yè)技術(shù)學(xué)院，電子信息工程系，講師，碩士，研究方向：數(shù)據(jù)庫與知識庫方向，南陽，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