基于小生境遗传算法的SDD-1分布式查询优化算法*

蒋 然

(扬州市职业大学信息工程学院 扬州 225000)



基于小生境遗传算法的SDD-1分布式查询优化算法*

蒋 然

(扬州市职业大学信息工程学院 扬州 225000)

SDD-1算法是一种分布式数据库的查询优化算法,遗传算法已经在许多领域得到了成功的应用。针对基于遗传算法的SDD-1算法中,遗传算法存在“早熟收敛”的问题,提出一种基于小生境遗传算法的SDD-1分布式查询优化算法,该算法能在尽可能短的时间内求解通信费用最小的查询计划。实验结果表明,该算法比单独使用SDD-1算法、基于遗传算法的SDD-1算法均有更优的性能。

小生境技术; 遗传算法; SDD-1算法; 早熟收敛; 查询优化; 分布式数据库

Class Number TP391

1 引言

在分布式数据库中,查询优化包括查询策略优化和局部处理优化[1]两个内容,其中查询策略优化尤为重要。查询执行开销主要包括I/O代价+CPU代价+通信代价。全局查询涉及多个站点的数据,为了执行全局查询和确定一个好的查询策略,首先需进行查询分解,然后再确定操作执行的次序,最后确定操作的执行方法,其中关键是确定操作执行的次序,即主要是确定连接操作的顺序。

2 研究现状

连接操作是影响分布式查询效率的关键因素。为了使分布式数据库能有效地处理连接操作,国内外学者一直在进行这方面的研究,形成了各种不同的算法。一般可分为两类：基于半连接策略的查询优化算法和基于直接连接策略的查询优化算法[2]。随着人工智能和各种工程优化方法的发展成熟,人们把很多新的算法引入到分布式数据库的查询领域。文献[3～11]中都提出用遗传算法对分布式数据库查询过程进行优化,其中文献[12]提出了一种改进的SDD-1算法(简称I-SDD-1算法),即把遗传算法引入进来,在基于半连接操作的基础上重新构造生成查询计划的方法。利用遗传算法的快速全局搜索能力,在较短的时间内求解最佳的半连接执行序列。但遗传算法存在“早熟收敛”的缺点,小生境技术是解决早熟收敛的一个有效方法,因此本文在基于遗传算法的SDD-1算法的基础上,结合小生境进化的优势构造了小生境混合遗传算法,提出一种基于小生境遗传算法的SDD-1分布式查询优化算法(简称NGA-SDD-1算法),有效地克服了遗传算法的“早熟”现象。

3 NGA-SDD-1算法

3.1 NGA-SDD-1算法基本思想

NGA-SDD-1算法试图用小生境遗传算法去寻找通信费用最小的查询计划。用通信费用作为衡量染色体优劣的指标；通过构造合适的遗传算子,对小生境群体进行一系列的选择、交叉和变异操作；以收敛率作为迭代结束的条件,有效缩减查询时间。算法的最终结果是一个通信费用最小的半连接序列。

为方便描述,引入定义如下：

定义1 相似度S,是指形态各异的染色体上的基因排列顺序的相似程度,以S(x,y)表示初始种群中某一个体的x和y两个染色体上的基因排列顺序的相似度；(2M-1)表示每条染色体所含基因的总量；x[N]表示在染色体x中位置N处的基因,y[N]表示在染色体y中位置N处的基因。则相似度S用如下公式表示[13]：

(1)

定义2 染色体的总相似度Sx,将该染色体与其他所有的染色体之间的相似度求和,用S(Ax,Ay)表示某一条染色体与另一条染色体的相似度,如果初始种群为M,假设存在2M个染色体,则某一条染色体的总相似度Sx用如下公式表示：

(2)

定义3 个体之间的距离dij,在解个体的n维空间内,令xi=(xi1,xi2,…,xin),xj=(xj1,xj2,…,xjn),其中M表示群体大小,则两者之间的距离用如下公式表示：

(3)

定义4 适应度函数f(x),适应度函数定义为

f(x)=104/g(x)

(4)

(5)

(6)

定义7 小生境群体的变异概率pim(1≤i≤N),f为参与变异操作的个体适应值,其余符号同定义6,则变异概率用如下公式表示[14]：

(7)

定义8 收敛率α,∑Imax表示群体中含有最大适应度的个体数目,∑I表示群体中的个体数目,则收敛率α用如下公式表示：

(8)

3.2 NGA-SDD-1算法具体描述

NGA-SDD-1算法就是将半连接操作和小生境遗传算法结合起来,在有效缩减通信费用的同时,兼顾查询计划的生成效率,即在尽可能短的时间内找到通信费用最小的查询计划。本文算法的步骤如下：

2) 初始种群的构造。为了将小生境遗传算法和SDD-1算法有效地结合,并使得所构造的初始种群具有多样性,从而进一步提高小生境技术的作用,为此引入了定义1及式(1),若初始种群的数量用M来表示,假设存在2M个染色体,利用式(2)求出2M个总相似度,并将2M个总相似度以升序的形式排序,选取前M个相似度较小的染色体构造初始种群。

3) 小生境群体的构造。小生境群体的大小,决定着遗传进化的效率。首先给出小生境的半径σ、小生境的容量Smax,任意选取一个元素xo,作为小生境群体的中心O,利用式(3)分别计算出该个体与其它个体xi之间的距离d,当d≤σ且小生镜群体中个体数小于其容量Smax时,把个体xi归为第一个小生镜群体中；在余下的群体个体中,选出一个个体作为另一个小生境群体的中心,构造第二个小生境群体,依次类推,直到所有的个体分配到相应的小生境群体中。计生成的小生境群体总数为N(N

6) 对相关联的小生境群体作最优个体替换。对相关联的小生境群体进行调整,具体方法是用一个群体内函数值最大的个体去替换另一个小生境群体中函数值最小的个体。这种方法使得优势个体资源得到了共享,加快了小生境群体的进化速度。

7) 对各个小生境群体进行独立的遗传操作。选择操作采用最佳个体保存方法,即当前群体中个体适应度最高的个体不参与交叉和变异运算,而是用它来替换掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体；利用式(6)进行交叉操作；利用式(7)进行变异操作。

8) 终止条件判断：满足条件结束运算,否则,继续迭代。收敛率是保障遗传算法收敛的一个重要依据,利用式(8)进行计算,当α值较大时(α>0.9)时,说明遗传算法己经收敛,可选择其最优个体为全局最优解。否则,继续迭代。

4 实验

4.1 实验内容及参数确定

根据SDD-1算法、I-SDD-1算法和NGA-SDD-1算法的流程,对它们分别进行了实验仿真,目的是对比SDD-1算法、I-SDD-1算法和NGA-SDD-1算法生成查询计划的时间和所生成查询计划的通信费用。程序的开发环境为VC++6.0,程序的测试环境为INTEL酷睿i5双核1.70GHzCpU,4GB内存,Microsoft Windows8操作系统。

本文实验中算法的参数设置为：种群规模为100,交叉概率和变异概率采用动态自适应技术,根据种群的实际情况随机调整大小,当收敛率大于0.9时算法终止。

4.2 实验结果及分析

针对相同的查询,在同样的实验条件下,对SDD-1算法、I-SDD-1算法和NGA-SDD-1算法所生成的半连接执行策略进行仿真实验测试。实验设计了6组数据,第1组到第6组数据涉及的半连接数目分别是6、10、20、50、100和1000,每一组数据中都包含50个代表不同站点属性的记录。

首先记录三种算法的仿真程序生成查询计划的时间,对每组数据中的50个结果求平均值。三种算法根据上述6组实验数据得到实验结果,每组数据生成查询计划所用时间平均值的情况如图1所示。

由图1的结果可以看出,SDD-1算法生成查询

计划的时间增长较快,特别是在半连接数为100时,是生成查询计划时间迅速增长的一个转折点,而I-SDD-1算法和NGA-SDD-1算法生成查询计划的时间增长比较缓慢,由于NGA-SDD-1算法较I-SDD-1算法引入了小生境技术,因而在寻求最优解的时间上略有增加。

然后记录三种算法的仿真程序所生成查询计划的通信费用,根据上述6组实验数据,三种算法所生成的查询计划的通信费用平均值的情况如表1所示。

表1 三种算法的通信费用对比情况

由表1可以看出,NGA-SDD-1算法生成的查询计划的通信费用的平均值要比SDD-1算法和I-SDD-1算法都要小。

最后在上述实验的基础上,对每组数据中的每条记录都重复10次,这10次实验中,若NGA-SDD-1算法和I-SDD-1算法所得的通信费用小于SDD-1算法,则记该算法收敛于最优解,用收敛于最优解的次数除以10,得到该记录收敛于最优解的概率。取每一组数据50个记录收敛概率的平均值为算法的收敛概率,结果如图2所示。

图2 两种算法在不同连接数下的收敛概率

由图2可知,随着连接数的增多,两种算法的收敛概率都呈下降趋势,主要原因是随着半连接数目的增多,初始种群的多样性受到限制,但NGA-SDD-1算法由于采用小生境遗传算法,应用定义1及采用自变异算子有利于进化过程中群体中个体的多样化,有效地克服了遗传算法的提前收敛。实验结果显示,NGA-SDD-1算法的收敛概率都在0.9以上,明显优于I-SDD-1算法的收敛概率。

综上所述,NGA-SDD-1算法生成查询计划的时间比SDD-1算法要短,而比I-SDD-1算法时间略长,但通信费用却比SDD-1算法和I-SDD-1算法小很多,因而NGA-SDD-1算法的综合查询效率要优于SDD-1算法和I-SDD-1算法。

5 结语

本文在以半连接操作为基础的分布式查询优化算法SDD-1算法和遗传算法相结合的基础上,引入小生境技术,结合小生境进化的优势构造了小生境混合遗传算法,提出一种基于小生境遗传算法的SDD-1分布式查询优化算法,该算法改变了遗传算法内部的搜索结构。实验表明,相比SDD-1算法和I-SDD-1算法,本文算法具有更优的性能。

[1] Patrik ONeil,Elizabeth ONeil.数据库原理、编程与性能[M].第2版.北京：机械工业出版社,2004. Patrik ONeil,Elizabeth ONeil.Database theory,programming and performance[M].Second Edition.Beijing：Machinery Industry Press,2004.

[2] 李芳萍.基于半连接策略的分布式数据库查询优化理论研究及应用[D].长沙：中南大学,2008. LI Fangping. Research and Application of Distributed Database Query Optimization Theory Based On Semi Join Strategy [D].Changsha：Centural South University,2008.

[3] 吴洋,温佩芝,邓星,等.一种改进的分布式数据库查询优化遗传算法[J].桂林电子科技大学学报,2015,35(3)：217-221. WU Yang, WEN Peizhi, DENG Xing, et al. An improved genetic algorithm for optimization of distributed database query[J].Journal of Guilin University of Electronic Technology,2015,35(3)：217-221.[4] 陈复兴.分布式数据库查询算法的改进与应用[D].南昌：江西师范大学,2014. Chen Fuxing. Improvement and Application an Query Algorithm of Distributed Database[D].Nanchang：Jiangxi Normal University,2014.

[5] 钱磊.分布式数据库多连接查询优化算法研究[D].哈尔滨：燕山大学,2011. QIAN Lei. A study of Multi-join Query Optimization Algorithm In Distributed Databse[D].Harbin：Yanshan University,2011.

[6] 李攀.基于遗传算法的分布式多连接查询优化系统设计与实现[D].昆明：云南大学,2010. LI Pan.Design and Implementation of Distributed Multi-join Query Optimization System Based On Genetic Algorithm[D].Kunming：Yunnan University,2010.

[7] 帅训波,马书男,周相广,等.基于遗传算法的分布式数据库查询优化研究[J].小型微型计算机系统,2009,30(8)：1600-1604. SHUAI Xunbo, MA Shunan, ZHOU Xiangguang, et al. Research of Query Optimization Based on Genetic Algorithm in Distributed Database[J].Journal of Chinese Computer Systems,2009,30(8)：1600-1604.

[8] 潘潁.自适应遗传算法的在分布式数据库查询优化中的应用[J].内蒙古师范大学学报,2016,45(1)：94-97. PAN Ying. Application of Query Optimization Based on Adaptive Genetic Algorithm in Distributde Database[J].Journal of Inner Mongolia Normal University,2016,45(1)：94-97.

[9] 牛园园.分布式数据库有关连接查询优化算法的研究[D].长沙：长沙理工大学,2010. NIU Yuanyuan. Researth on Join Query Optimization Algorithm in Distributed Database[D].Changsha：Changsha University of Science & Technology,2010.

[10] 林基明,班文娇,王俊义,等.基于并行遗传-最大最小蚁群算法的分布式数据库查询优化[J].计算机应用,2016,36(3)：675-680. LIN Jiming, BAN Wenjiao, Wang Junyi. Query optimization for distributed database based on parallel genetic algorithm and max-min ant system[J].Journal of Computer Applications,2016,36(3)：675-680.

[11] 曾莹莹.基于异构数据库的查询优化算法的改进[D].长春：吉林大学,2011. ZENG Yingying. An Improved Query Optimization Algorithm Based on Heterogeneous Database[D].Changchun：Jilin University,2011.

[12] 宋倩.SDD-1算法的改进及其应用研究[D].西安：西安电子科技大学,2010. SONG Qian. Researth of the SDD-1 Algorithm’s Improvement and its Appliation[D].Xi’an：XiDian University,2010.

[13] 邹汪平.基于NGSAA算法的分布式数据库查询优化研究[J].长江大学学报(自然版),2013,10(25)：46-52. ZOU Wangping. Research on Query Optimization of Distributed Database Based on NGSAA Algorithm[J].Journal of Yangtze University(Nat Sci Edit) ,2013,10(25)：46-52.

[14] 王亚子.小生境与并行遗传算法研究[D].郑州：中国人民解放军信息工程大学,2006. WANG Yazi. Research on the Niche and parallel Genetic Algorithm[D].Zhengzhou：Chinese people’s The PLA Information Engineering University,2006.

[15] 王亚子,贾利新.遗传算法的小生境技术改进[J].河南教育学院学报(自然科学版),2008,17(1)：28-29. WANG Yazi, JIA Lixin. Improvement of Niche Skill On Genetic Algorithm[J].Journal of Henan Institute of Education (Natural Science) ,2008,17(1)：28-29.

SDD-1 Distributed Query Optimization Algorithm Based on Niche Genetic Algorithm

JIANG Ran

(Faculty of Information Engineering,Yangzhou Ploytechnic College, Yangzhou 225000)

SDD-1 algorithm is a distributed query optimization algorithm,the genetic algorithm has been successfully applied in many fields .In the SDD-1 algorithm based on genetic algorithm, genetic algorithm has a problem of “premature convergence”.To solve this problem,SDD-1 distributed query optimization algorithm based on niche genetic algorithm is proposed in this research.This algorithm can solve the query plan of minimum communication cost in possible time.Experimental results show that this algorithm has a better performance than SDD-1 algorithm and SDD-1 algorithm based on genetic algorithm.

niche technique, genetic algorithm, SDD-1 algorithm, premature convergence, query optimization, distributed database

2016年5月20日,

2016年6月27日

蒋然,女,硕士研究生，讲师，研究方向：数据库、信息检索、查询优化。

TP391

10.3969/j.issn.1672-9722.2016.11.007