基于NGSAA算法的分布式数据库查询优化研究

邹汪平 (池州职业技术学院信息技术系，安徽 池州 247000)

基于NGSAA算法的分布式数据库查询优化研究

邹汪平 (池州职业技术学院信息技术系，安徽 池州 247000)

针对遗传算法在分布式数据库查询优化中存在的不足之处，提出了一种基于小生境技术的遗传模拟退火算法。首先扩展了算法的搜索区域以避免早熟现象的出现，然后进行规则的简化以降低功能性冗余，再将算法应用于分布式数据库查询优化中。研究表明，该算法可以有效降低生成最优查询策略的总代价和时间，提高了查询优化的整体效率。

遗传算法；小生境技术；模拟退火算法；分布式数据库查询优化

遗传模拟退火算法(GSAA)在分布式数据库查询优化中的全局搜索中有较好的表现[1]，但其存在收敛速度慢、早熟收敛等缺陷。针对该算法中的不足，笔者提出了一种改进的基于小生境技术[2-3]的遗传模拟退火算法(NGSAA)，并将该算法应用于分布式数据库查询优化中，可以很好地保持种群的多样性，同时能够在保证全局搜索能力的前提下提高收敛速度，避免早熟现象的出现。

1 NGSAA算法概述

1.1GSAA算法与小生境技术的结合

为了将GSAA算法与小生境技术有效地结合，首先引入一个新的概念——相似度S，其指的是形态各异的染色体上的基因排列顺序的相似程度，以便于分布式数据可查询优化的应用，可用如下公式表示：

(1)

式中，S(x,y)是指初始种群中某一个体的x和y2个染色体上的基因排列顺序的相似度；(2M-1)是每条染色体所含基因的总量；x[N]是指在染色体x中位置N处的基因；y[N]是指在染色体y中位置N处的基因。

为了能够将小生境技术融入GSAA算法，必须对初始种群和选择算子[4]加以改进。其中，相似度S在初始种群的选择过程中起到至关重要的作用。若初始种群的数量用i来表示，假设存在2i个染色体，若要得出某一条染色体的总相似度Sx，应将该染色体与其他所有的染色体之间的相似度求和：

(2)

式中，S(Ax,Ay)表示某一条染色体与另一条染色体的相似度。

将求出的2i个总相似度以升序的形式排序并取前i个相似度较小的染色体构造初始种群，利用该机制构造的初始种群所具有的多样性来进一步提高小生境技术的作用。

在设定选择算子C时,首先计算出父代染色体和其子代的染色体的相似程度，如果最终得出的相似度超过染色体所含基因总量，就再将该父代染色体和其子代染色体的适应度继续进行对比。当子代染色体的适应度超过父代染色体时，就代替其父代染色体，反之亦然。其计算公式如下：

(3)

式中，Cfather表示父代染色体；Cson表示子代染色体；F()表示染色体的适应度。

1.2NGSAA算法

NGSAA算法以GSAA算法为其子算法，利用小生境技术进一步降低算法的功能性冗余。算法描述如下(其中，Ch表示染色体、ChArray表示染色体数组、BestCh表示最优染色体)。

Begin:

//从染色体数组中根据相似度大小构造初始种群Pop

PopSele [ChArray]→Pop

// 计算种群中每个染色体的适应度

F(Pop)

//搜索最优染色体

for the best Ch not appear do

// 对染色体进行相应的交叉运算

Cross(Pop) → Pop1

// 对染色体进行相应的变异运算

Mut(Pop1) →Pop2

//对种群中的染色体运用模拟退火算法并强化局部搜索

for each Ch in Pop2 do

SA(Ch) →NextChrom

nextCh →NextPop[index]

end for

//利用融入小生境技术的选择算子对种群进行选择

Pop←Sele (Pop，NextPop)

//判断是否产生最优的染色体

for each Ch in Pop do

if Ch is the best then

Ch →BestCh

end if

end for

end for

//返回最优染色体

return BestCh

End

2 分布式数据库查询优化

为了能够在分布式数据库查询优化中应用NGSAA算法，必须首先对存在的所有可行数据库查询策略进行相应的编码，构造遗传算法中的染色体结构。将关系节点作为叶子节点并以某个正整数表示；将中间节点作为连接操作用字符0表示，使用先序遍历方式排序后对于一个连接关系为N的查询二叉树可构造长度为2N-1编码，经过逐步规约后得到最终的叶子节点，再将规约倒序展开完成染色体结构的转化。另外，还必须对算法进行相应设定：适应度函数F()在此转换成根据染色体的链接顺序进行多连接查询的代价；对染色体进行整理产生新一组染色体的过程可采用交叉方式完成；对于变异算子采用染色体随机将2个非零基因进行互换来构造新染色体。上述设定可以降低适应度以防止遗传到下一代。

在进行分布式数据库查询优化时，使用数组结构通过查询条件及其数据库全局数据字典(GDD)构造染色体，在此基础上结合NGSAA算法搜索出最优查询策略，并利用该策略完成查询的过程，具体内容描述如下(其中，QDemand是用户查询要求；QStrategy是查询策略；Result是查询结果)。

Begin：

//输入用户的查询要求和加载全局数据字典

input(QDemand) →Condition

load(GDD) → Dictionary

// 对查询策略进行编码以形成染色体数组

for 2i Chs is not enough do

Code(Condition, Dictionary) →Ch

Ch→ ChArray[index]

end for

//调用NGSAA算法

NGSA(ChArray) →BestChr

//将最优染色体转换回相对应的查询策略

transform(BestChr) →QStrategy

//按最优策略进行查询并返回查询结果

query(QStrategy) → Result

return Result

End

3 仿真试验

为了验证基于NGSAA算法的分布式数据库查询优化性能，模拟实验环境利用虚拟局域网进行，在分布式数据库中设置10个存储有大数据量数据表的节点机，服务器上存有包含节点机各种信息的数据字典，每个节点机上的数据表中的数据记录数量在2200至15000条之间并随机分布，用于模拟整个网络的实时状态以及节点机中包含的数据表在互相连接时的数据选择率。在确定的最优查询策略下，比较NGSAA算法和GSAA算法的分布式数据库查询优化实质上就是比较两者搜索最优查询策略的总代价和总响应时间。设定查询过程中数据分布在2～9这8个节点机上并设定初始种群为19，分别用NGSAA算法和GSAA算法对分布式数据库查询优化进行最优查询策略的搜索，其结果如图1所示。由图1可知，基于NGSAA算法的分布式数据库查询优化搜索出最优查询优化策略所需的进化代数要远远低于GSAA算法。因此，在确定的最优查询策略下，使用NGSAA算法搜索该查询策略的总代价比使用GSAA算法更优。

将基于NGSAA算法和GSAA算法的分布式数据库查询优化搜索出最优查询优化策略所需时间进行对比。设定查询过程的查询条件为8个，即关系数为8，并设定初始种群为19，搜索数据的站点限制在2～9这8个节点机上并限制进化代数小于或等于30，即终止条件为30代进化内不再出现更优策略，记录多次试验下生成最优查询优化策略的时间的平均值。最优查询优化策略生成时间图如图2所示。由图2可知，在关系数相同的情况下基于NGSAA算法的分布式数据库查询优化生成最优查询优化策略的所耗费的时间更短。

图1 总代价与进化代数关系图 图2 最优查询优化策略生成时间图

4 结 语

将GSAA算法与小生境技术有效的结合到一起，引入相似度并应用于初始种群的建立，重新设定选择算子的方式以降低算法冗余，提出一种改进的NGSAA算法并将其应用于分布式数据库查询优化以改善查询优化的性能。试验结果表明，NGSAA算法在一定程度上降低了查询优化的总代价和总时间，提高了查询优化的整体效率。需要说明的是，进行仿真试验时是基于确定的最优查询策略，而实际上无论是GSAA算法还是NGSAA算法都是基于随机策略，因而对在搜索过程中会随机出现非最优解的情况还有待进一步分析研究。

[1]刘波，孟相如，麻海圆.一种用于分组调度的遗传模拟退火算法[J].通信技术，2009(2):91-93.

[2]Lingyun Wei, Mei Zhao.A niche hybrid genetic algorithm for global optimization of continuous multimodal functions[J]. Applied Mathematics and Computation，2005(3):649-661.

[3]陈皓,崔杜武,崔颖安,等.族群进化算法[J].软件学报，2010(5):978-990.

[4]姜彬峰.一种初始种群算法的应用研究[J].制造业自动化，2011(10):94-96.

[编辑] 李启栋

TP183

A

1673-1409(2013)25-0046-03

2013-06-12

邹汪平(1982-)，男，硕士，讲师，现主要从事算法设计方面的教学与研究工作。