改进布谷鸟算法的数据库查询优化

席洁

(陕西国防工业职业技术学院，户县 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)