李国芳;李静
【摘 要】In order to solve the defect of quantum particle swarm algorithm, mutation operator of the genetic algorithm is introduced into quantum particle swarm optimization algorithm. It produces a novel query optimization method of database(GM-QPSO). Firstly, the mathematic model is established for database query optimization problems. And then the optimal scheme of database query optimization problems is found by the sharing message of quantum particle. Finally, the simulation experiments is carried out on Matlab 2012. The results show that the proposed algorithm has solved the defect of quantum particle swarm algorithm, and improved query speed of database and can obtain better query scheme.%针对量子粒子算法存在的不足，将变异算子引入其中，提出一种高斯变异量子粒子算法(GM-QPSO)，并将其应用于数据库查询优化中。首先建立数据库查询优化数学模型，然后采用量子粒子代表一个可行的数据库查询方案，然后通过量子粒子之间的信息交流，到数据库查询最优解，最后在 Matlab 2012上进行了仿真实验。仿真结果表明， G M-QPSO克服了量子粒子算法存在的不足，不仅提高了数据库查询速度，而且获得了更加理想的查询优化方案。
【期刊名称】《计算机系统应用》
轨道根数【年(卷),期】2014(000)008
【总页数】5页(P184-188)
【关键词】数据库查询;变异算子;遗传算法;粒子算法
【作 者】李国芳;李静
【作者单位】广州医科大学 卫生职业技术学院，广州 510450;广州医科大学 卫生职业技术学院，广州 510450
【正文语种】中 文
随着数据库规模日益增大, 数据查询频率增加, 因此数据查询效率至关重要, 如何快速到满足用户查询条件的记录, 是现代大规模数据研究的热点问题[1].
针对数据库查询优化问题, 国内外学者投入了大量时间和精度进行了研究[2]. 数据库查询优化是一个典型的多约束的组合优化问题, 传统穷举搜索算法存在效率低, 效果差等缺陷. 为了解决该难题, 一些学者将启发式算法引入到数据库查询中[3]. 如: 出现了基于遗传算法、蚁算法、粒子算法、模拟退火、蛙跳算法以及它们的组合算法[4-8], 一定程度上提高了查询优化效果, 获得了比较理想的查询效果, 但是随着数据库规模的不断扩大, 这些算法的问题开始暴露出来, 出现了收敛速度慢、易陷入局部最优、早熟现象, 难以得到全局最优的数据库查询方案[9]. 近年来, 随着量子计算的发展, Sun 等人在粒子算法的基础上, 引入量子行为, 提出了量子粒子算法(quantum-behaved particle swarm optimization, QPSO)算法[10]. 量子粒子是粒子在进化过程中加入了量子行为, 因此, 相比标准的粒子算法具有较好的全局收敛性. 但是, 该算法仍旧不可避免早熟[11]. 通俗喜剧
长春304案件
为了提高数据库查询的优化效率, 提出一种高斯变异量子粒子算法的数据库查询优化方法(Gaussian mutation quantum behaved particle swarm optimization,GM-QPSO)的数据库查询优化算法, 并通过仿真实验对GM-QPSO算法在数据库查询优化问题求解中的性能.
1.1 量子粒子优化算法
粒子优化算法是1995年由美国学者J.Kennedy和R.C.Eberhart受鸟觅食行为的启发而提出的[7],是一种基于迭代的优化算法, 但是, 标准粒子算法还存在一些有待于改进的问题, 主要有搜索空间有限、容易出现早熟、收敛精度不高、容易陷入局部优化等[12]. J.Sun等人2004年在标准的PSO基础上引入量子行为, 提出了量子粒子(QPSO), 使得粒子可以在整个可行解的空间中进行搜索, 从而寻求全局最优解, QPSO算法比标准PSO算法具有更好的全局收敛性和搜索能力. QPSO是以DELTA势阱为基础, 认为粒子具有量子的行为, 该算法的迭代公式为:
其中, 为平均最优位置; 为粒子的数目; 第i个粒子的个体最优位置; 为第i个粒子的位置, 、、是介于(0,1)之间的
1.2 高斯变异量子粒子优化算法(GM-QPSO)
为了增加粒子的多样性, 避免陷入局部极值, 把高斯分布融合到量子粒子算法中, 用高斯分布变异代替随机数变异操作, 具体步骤如下:
1) 初始化粒子中粒子的位置, 并把每个粒子位置的设置为个体最优位置.
2) 计算每个粒子的适应度值, 如果, 则更新粒子的个体最优位置.
3) 更新粒子的全局最优位置.
4) 利用公式(3)计算平均最优位置mBest;
5) 利用公式(8)和(9)分别对mBest和Pg进行扰动.
式中, 是变异大小, 是一个柯西分布的随机变量,
6) 对每个粒子利用式(3)更新粒子的位置;
7) 如果满足结束条件, 则算法结束; 否则, 返回步骤2).
采用4个准测试函数: Sphere、Griewank、Rosenbrock和Rastrigin对QPSO算法和GM-QPSO算法的性能进行测试, 所有算法的运行结果如图1所示. 从图1可知, 对所有函数, 相对于QPSO算法, GM-QPSO获得更优的全局搜索能力、收敛精度和收敛速度, 这主要是由于当粒子因为陷入局部最优而出现早熟现象的时候, 高斯变异使得粒子有机会在小范围内进行搜索, 获得了更优的结果.
阿伐斯汀
2.1 数据库查询优化的数学模型
对于一个含有n个关系的连接树, (j1,j2,…,ji)为连接树内部节点(即非叶子节点), 其代价评估模型为: 查询优化方案可以描述为4种情况, 具体如图5所示, 此处选用(a) “左深树”搜索策略空间为例进行分析.
对于一个连接J=RjoinS, 其计算代价cost(J)如式(13)所示:
(7)中V(c,R)的计算方式如公式(8):
式中, |R|表示关系R的元组数; C表示关系R和关系S的公共属性集合; V(c,R)表示关系R中属性c的不同取值的个数.
2.2 适应度函数设计
量子粒子优劣通过适应度函数进行评价, 数据库查询优化目标是到一个cost(Xi)代价最小的查询计划. 由于每一个量子粒子与一个连接查询树对应, 对于粒子Xi, 采用计算其cost(Xi), 然后对cost(Xi)取倒数作为量子粒子的适应度值, 具体为:
2.3 GM-QPSO的数据库查询优化求解步骤
1) 参数初始化: 初始化GM-QPSO算法的各个参数, 如最大迭代次数等.
2) 初始量子粒子, 根据式(9)计算量子粒子适应度值并将个体的历史最优位置Pid设为当前位置, 而体中最优的个体作为当前的Pgd.
3) 根据粒子的适应度更新Pid和Pgd.
4) 并根据式(4)、(5)对mbest进行变异, 同时, 根据式(3)更新量子粒子的位置.
集成功放
5) 如果达到最大迭次数, 输出最优粒子对应的数据库查询方案, 不然, 返回骤3)继续迭代.
3.1 仿真环境
为了测试GM-QPSO算法的性能, , 在CPU为Intel CoreTM 2 Quad 3.0GHz, RAM为2.0GB, 操作系统为Windows 7的平台下, 采用Matlab 2012工具箱进行仿真实验. 采用QPSO算法, 遗传算法(GA)、粒子算法(PSO)进行对比实验. 采用搜索最优查询方案和执行最优查询方案两个方面的代价进行性能评估算法性能, 具体定义如下:
3.2 结果与分析
3.2.1查询结果比较
嘉兴秀洲中学经多次实验并求取平均值, QPSO、GM-QPSO、GA、PSO算法搜索最优查询方案代价比变化曲线如图3所示. 执行最优查询方案代价比变化曲线如图4所示. 从图3和4的结果进行分析可以得到如下结论:
1) 当数据库查询连接数较少时, 所有算法查询和执行代价均较小, 查询效率相当高的, 获得理想的查询结果, 因此, 它们性能几乎没有什么差异, 均可以应用于较小的数据库查询连接数查询.
2) 连接数大于20时, 相对于GA、PSO算法, QPSO、GM-QPSO算法优势得到体现, 这主要由于QPSO、GM-QPSO具有较好的全局和局部搜索能力, 克服了传统智能算法的存在不足, 可以算法快速、准确到数据库查询, 可以满足现代大规模数据库在线查询优化要求.
3) 相对于QPSO算法, GM-QPSO算法降低了数据库查询和执行代价, 这主要因为, GM-QPSO引入了遗传算法的变异算子, 高斯变异产生微小随机数的几率比较大, 使得粒子的位
置在近似最优解的小范围内进行变动, 以提高算法的全局搜索能力, 较好的克服QPSO算法存在的局部最优缺陷, 获得了更优的数据库查询方案.
3.2.2查询速度比较比较
为进一步分析GM-QPSO算法的优越性, 对它们的最优查询方案的迭代次数和运行时间进行仿真对比实验, 结果如图5和6所示. 从图5与图6可知, GM-QPSO算法的性能明显优于对比算法, 迭代280次后, MG-QPSO算法到了更优的数据库查询方案, 其执行时间为128.23ms, 远远低于GA的200.24ms, PSO算法的195.23ms, QPSO算法的175.23ms, MG-QPSO不仅迭代次数大幅度减少, 而且执行时间急剧下降, 获得更优的数据库查询方案.
针对当前数据库查询优化算法存在的效率低, 难以获得最优解的缺陷, 提出一种高斯变异量子粒子算法的数据库最优查询方法. 实验结果表明, GM-QPSO引入了遗传算法的变异算子, 高斯变异产生微小随机数的几率比较大, 使得粒子的位置在近似最优解的小范围内进行变动, 以提高算法的全局搜索能力, 较好的克服QPSO算法存在的局部最优缺陷, 获得了更优的数据库查询方案, 在数据库中具有广泛的应用前景.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议