基于多蚁群遗传算法的分布式数据库查询优化

打开文本图片集

摘要：

针对单一普通算法在查询优化方面的不足，提出了一种结合遗传算法与蚁群算法优点的多蚁群遗传算法，克服了蚁群算法前期搜索的盲目性，并引入多蚁群概念，更好地防止了算法陷入局部最优的情况，以获取更优的查询路径.类比实验表明，该算法较传统蚁群算法，在查询方面，能获得更好的查询路径.

关键词：

分布式数据库; 多蚁群; 遗传算法; 查询优化

中图分类号： TP 311文献标志码： A文章编号： 1000-5137（2018）01-0037-06

Query optimization of distributed database based on

multiple ant colony genetic algorithm

Zhou Ying， Chen Junhua*

（The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China）

Abstract：

In the light of the defect of single algorithm of query optimization，this paper proposes a multiple ant colony genetic algorithm combining the advantages of ant colony algorithm and genetic algorithmwhich overcomes the blindness of early search of ant colony algorithm.Moreover the introduction of multi ant colony concept better prevents the algorithm falling into local optimal conditions as to obtain better query path..The final experiment results show that the improved optimization algorithm can find better query path in the query compared with the traditional ant colony algorithm.

Key words：

distributed database; multi ant-colony; genetic algorithm; query optimization

收稿日期： 2016-04-28

作者简介： 周莹（1991-），女，硕士研究生，主要从事数据库方面的研究.E-mail：200865689@qq.com

导师简介： 陈军华（1968-），男，副教授，主要从事数据库方面的研究.E-mail：chenjh@shnu.edu.cn

*通信作者

引用格式： 周莹，陈军华.基于多蚁群遗传算法的分布式数据库查询优化 [J].上海师范大学学报（自然科学版），2018，47（1）：37-42.

Citation format： Zhou Y，Chen J H.Query optimization of distributed database based on multiple ant colony genetic algorithm [J].Journal of Shanghai Normal University（Natural Sciences），2018，47（1）：37-42.

分布式数据库技术使数据在物理上呈现分布状态，在逻辑上融为整体的数据库技术.随着数据量的日益增长，分布式数据库技术的应用越来越广泛.为了尽可能地降低该技术的整体开销，需要寻找一个切入点对其进行优化.查询操作是分布式数据库中最常用，同时也是最有提升空间的一种操作，成为研究的重点.目前已经有许多学者提出了相关优化策略，如基于索引的SQL语句查询优化[1]，基于禁忌GEP的查询优化[2]，基于遗传模拟退火的查询优化[3]等策略.

考虑到单个算法的局限性及不足[4]，本文作者提出了一种遗传算法与多蚁群算法相结合的混合算法，多蚁群算法是在普通蚁群基础上进行改进的算法.该混合算法不但克服了蚁群算法前期搜索的盲目性，而且利用了平滑机制及多蚁群间互相学习机制来避免陷入局部最优和早熟现象，从而提高了整个算法的全局搜索能力.实验表明，该算法有效地提高了分布式数据库查询的效率.

1算法模型

多蚁群遗传算法的基本思想是：通过遗传算法处理，产生初始的信息素分布，多蚁群算法利用这个初始信息素分布开始寻优，多个蚁群间先互相独立寻优，当迭代数满足条件时，依照平滑机制跳出局部最优，并利用学习机制获得更好的全局最优解，这个解就是查询路径.

1.1遗传算法

利用传统遗传算法的步骤对查询问题初步求解.求解前需要根据待求解问题来设置各个参数和相关技术.其中几個重要概念定义如下：

（1） 目标函数.目标函数指的是解决问题所要关心的目标与相关因素的函数关系.对于所遇到的一些分布式数据库查询优化问题来说，最需要关注的目标就是总通信费用的问题.目标函数公式如下：

C=∑ni=1Ai+∑mi=1Eij，（1）

其中，C表示总通信费用，Ai为查询路径上的节点i对应的通讯费用，Eij为查询路径上的节点i以及节点j之间对应的通讯费用，n为查询路径上节点总个数，m为查询路径上所有节点之间路径的总条数.

（2） 适应度函数.适应度函数用来衡量一个解的好坏[5]，而在分布式数据库查询优化问题中，目的是获得通讯费用最少的查询路径，所以适应度函数定义如下：

fitness=1C.（2）

（3）初始信息素分布.即为蚂蚁搜索路径前各条路径上信息素浓度的分布，按照遗传算法找到的最优路径更新，产生多蚁群算法的初始信息素分布矩阵，蚂蚁初次运动的路径会受此影响.更新公式如下：

τij（0）=ρτij+Δτij（0）（3）

τij（0）是边ij上的初始信息素值，ρ是遗传算法优化信息素的更新因子，Δτij（0）是遗传算法找到的最优路径在边ij上释放的信息素值，

Δτij（0）=Q/l，（4）

其中，信息素总量值用Q进行表示，这个值是固定的;l是边的长度.Q/l可以理解为在单位距离上所具有的信息素浓度.

1.2多蚁群算法

在大自然中，蚁群的觅食活动往往不是单个蚁群独立进行的，通常在同一个环境中存在着多个蚁群，它们互相影响，互相学习，共同进化[6].在传统蚁群的基础上引入多蚁群的概念，这种概念指的就是采用划分的方法对一个总的蚁群进行有效地处理，用不同的参数控制着各个子蚁群，子蚁群间独立寻优，这样在每个子蚁群中就会产生不同的信息素分布，有着不同的进化方向.当迭代一定次数后，子蚁群内可能会陷入停滞状态，这时各个子蚁群间利用“学习算子”开始进行信息素的交流，打破停滞的僵局，推动蚁群再次进化，防止算法出现局部最优的现象.引入多蚁群的做法，意在让算法更贴近大自然实际规律，多蚁群能够实现互帮互助，共同进化，最终获得最优解.

前期利用遗传算法进行处理获得初始信息素分布之后，利用初始信息素分布开始多蚁群算法的寻优，多蚁群算法优化分布式数据库查询操作的相关参数及技术的设置如下：

（1） 转移概率.搜索时，蚂蚁对于下一个要访问节点的选择是非常随机的.蚂蚁在两个节点之间选择概率

pij=

[τij（t）]α[ηij]β∑k∈allowed[τik（t）]α[ηik]β，

if j∈allowed

0，otherwise

，（5）

其中，在概率计算的过程中信息素τij（t）所具有的权重用α来进行表示，这个值越大，信息素所占据的作用就会越明显.ηij为启发信息，β代表ηij在转移概率计算的过程中所占的权重，当这个值越大，蚂蚁选择节点时其所起到的作用就会越明显，k表示蚂蚁下一步允许走的节点.

（2） 目标函数.目标函数用来衡量蚁群找到的路径是否优秀，在分布式数据库中的设置与上述遗传算法一样，总通信费用多少就是衡量路径好坏的标准.

（3） 信息素的更新机制[7].采用传统的信息素更新机制，如果在循环的过程中每一个蚂蚁都搜寻到了路径，而且路径是合法的，那么就可以开始进行信息素的全局更新.

τij（t+1）=ρτij（t）+Δτij（t，t+1），（7）

其中在t次循环时，边ij上的信息素浓度用τij（t+1）表示;信息素维持因子用ρ表示，相應的信息素挥发因子用（1-ρ）表示.对于在边ij上所有蚂蚁所释放的信息素用Δτij（t，t+1）表示，k为在时刻t的第k只蚂蚁，m为爬过边ij上蚂蚁的总个数：

Δτij（t，t+1）=∑mk=1Δτkij（t，t+1）.（8）

（4） 信息素平滑机制.当各个子蚁群迭代了一定次数后，相比其他的路径，某一条路径上的信息素浓度会比较大[8]，信息素浓度通过正反馈传递给蚂蚁，蚂蚁感知到这个情况，会大概率地选择这条路径来觅食，对于这种情况可以使用信息素平滑机制来改变，计算方法为：

τij=τij-δ（τij-τmin），（9）

其中，在边ij上当前的信息素浓度值用τij进行表示;δ是平滑系数，控制着信息素平滑机制的影响程度.当δ=0，平滑机制关闭;当δ=1，平滑机制影响力最大，信息素值等于τmin，τmin表示事先设置好的信息素浓度最小值.

（5） 学习算子.大自然里的生物一直在进行优胜劣汰的进化，没有一种生物是可以依靠独自的能力生存，不同种群间会相互影响，同一个种群内更会相互交流融合，学习对方的长处，改进自己的短处，朝着更优的方向进化.这里引入学习算子，当迭代一定次数后，根据学习算子，更新各个子蚁群的全局信息素.学习算子：

τmij=τmij+γ×τnij，（10）

其中，τmij代表着当前子蚁群m在边ij上的信息素值，τnij是当前子蚁群n在边ij上的信息素值，γ是学习算子，主要作用是用来控制蚁群之间信息素交流作用的大小.

1.3算法步骤

作者提出的多蚁群遗传算法具体步骤如下：

（1） 对分布式数据库网络拓扑结构进行有效地设置;

（2） 初始化遗传算法相关参数值;

（3） 从初始起点开始，随机找下一个点，再找下一个点，如同人走路一样，以此来产生初始染色体种群;

（4） 开始进行迭代，对当代的染色体按概率进行变异以及交叉操作，在这个过程中产生新个体;

（5） 解码染色体，将染色体转换成查询路径，计算目标函数（也就是通信费用），以此来计算出染色体具体的适应度值;

（6） 利用轮盘赌法，依据各个染色体具体的适应度值进行选择操作，进入下一次迭代;

（7） 判断结束条件是不是得到了满足，如果满足的话，就输出最优路径，进入下一步骤;不满足，则返回步骤（4）;

（8） 用最优查询路径对信息素矩阵进行初始化处理;

（9） 初始化多蚁群算法相关参数值;

（10） 利用遗传算法来对初始信息素分布进行有效确定;

（11） 多个蚁群分别开始进行步骤（12）～（17）;

（12） 设置开始的节点，相当于发出查询请求的网络节点;

（13） 按照转移概率的公式进行节点的转移，同时更新路径;

（14） 判断蚂蚁是否已完成所有目的节点的搜索，如果是，再判断是否蚁群内所有的蚂蚁都已经完成，若没有，返回步骤（12）.如果蚁群内所有蚂蚁都进行了搜索，求得每条路径的具体目标函数值.

（15） 判断当前迭代数是否大于蚁群开始信息素平滑机制的迭代数，若是，则按照信息素平滑机制操作.

（16） 判断当前迭代数是否大于蚁群间开始学习信息素的迭代数，若是，则按照学习算子规则进行操作.

（17） 判断当前迭代数是不是符合了结束条件，如果没有符合，返回步骤（11）;否则，输出结果.

2实验仿真与分析

2.1相关参数的设置

在Matlab中对以上模型进行了仿真测试，并在相同环境下用传统蚁群算法测試来与之对比.通过翻阅相关文献，设置如下参数：

（1） 传统蚁群算法参数：蚁群的大小M=10，信息素的挥发因子ρ=0.1，信息素的重要程度因子α=2，启发函数重要程度的因子为β=3，蚁群最大迭代数imax=50.

（2） 多蚁群遗传算法参数：遗传算法相关参数设置：种群的大小M=20，最大的遗传代数为gmax=50，然后交叉率Pc=0.7，变异率Pm=0.1.

多蚁群算法设置相关参数的具体方法：蚁群大小M、信息素的重要程度因子α、启发函数重要程度的因子β、蚁群最大迭代数imax均与传统蚁群算法设置一致，遗传算法优化信息素的更新因子为ρ=0.1，蚁群1的信息素挥发因子为ρ1=0.1，蚁群2的信息素挥发因子ρ2=0.05，学习因子μ=0.05，蚁群间开始学习信息素的代数Nset1=10，蚁群开始信息素平滑机制的代数Nset2=10，信息素总量Q=10，信息素最大值Imax=0.5，信息素最小值Imin=0.01.

2.2实验结果及分析

利用改进的Salama开发平台随机产生数量具有30和60节点的网络进行测试.预设发出查询命令的网络节点是3，即源节点S，完成该查询命令所需要的所有查询数据分布在4、6、8、10、12这5个节点内，即目标节点E.如何从S通过一定的路径与E相连，且这个路径能使通信费用最低，这就是本次实验所要的结果.

2.2.130个节点的网络拓扑关系

从图1和2中可以看出，多蚁群遗传算法比传统蚁群算法找到解经过的路径更短，多蚁群遗传算法在经过遗传算法生成的初始信息素分布的指引下，经过的节点个数更少，优于传统蚁群算法.

图1多蚁群遗传算法最优解爬行路径（30节点）

图2传统蚁群算法最优解爬行路径（30节点）

从图3和4中可以看出，多蚁群遗传算法比传统蚁群算法找到的解在通信费用上更少.传统蚁群算法一开始通信代价是550左右，在算法初期下降的速度比较快，但是当迭代了4次之后，通信费用下降的速度明显减慢，到了第5代左右，就已经接近于收敛状态，陷入局部最优，通信费用已经不再下降了，为478左右.而多蚁群遗传算法在一开始通信费用下降的速度虽没有基础蚁群快，在第3代的时候有短暂的算法停滞，随着平滑机制和学习机制的运行，算法跳出停滞状态，继续搜寻，到了第10代左右才开始趋于收敛，此时的通信代价已经降低到了367，优于传统蚁群算法.

图3多蚁群遗传算法查询收敛曲线（30节点）

图4传统蚁群算法查询收敛曲线（30节点）

（2） 60个节点的网络拓扑关系

从图5和图6中看出，多蚁群遗传算法与传统蚁群算法找到解经过的路径，相比在30个网络节点下实验得到的，没有明显优势，是因为蚂蚁搜索路径存在一定的随机性.从通信费用角度来看，多蚁群遗传算法还是优于传统蚁群算法，详细见图7、图8.

从图7和8可以看出，两个算法开始的收敛速度是传统蚁群表现得较好，但这也是传统蚁群过早地陷入局部最优的表现.多蚁群算法经过第5、10、15代的短时间搜索停滞之后，在第23代得到最优解.在最终得到的最优路径的通信费用方面来讲，还是多蚁群遗传算法表现得更优.

图5多蚁群遗传算法最优解爬行路径（60节点）

图6传统蚁群算法最优解爬行路径（60节点）

图7多蚁群遗传算法查询收敛曲线（60节点）

图8传统蚁群算法查询收敛曲线（60节点）

3总结

本文作者提出了一种多蚁群遗传算法，该算法融合了遗传算法及蚁群算法的优点，并利用多蚁群概念来防止算法陷入局部最优的情况，同时使用平滑机制来克服蚁群算法早熟的缺点.在模拟的分布式数据库下进行仿真测试，结果表明该算法在查询优化方面较传统蚁群，有更好的表现.

参考文献：

[1]张鹏宇.分布式数据库查询处理和优化算法 [J].计算机光盘软件与应用，2014，1（19）：106-108.

Zhang P Y.Distributed database query processing and optimization algorithm [J].Computer Disk Software and Applications，2014，1（19）：106-108.

[2]邓松，林为民，张涛，马媛媛.基于禁忌GEP的分布式数据库查询优化算法 [J].计算机与数字工程，2013，41（10）：1552-1555.

Deng S，Lin W M，Zhang T，et al.A distributed query optimization algorithm based on tabu GEP database [J].Computer and Digital Engineering，2013，41（10）：1552-1555.

[3]刘亚欣.遗传-模拟退火算法在数据库查询优化中的应用 [J].大连交通大学学报，2009（1）：85-87.

Liu Y X.Application of genetic simulated annealing algorithm in database query optimization [J].Journal of Dalian Jiaotong University，2009（1）：85-87.

[4]夏鸿斌，须文波，刘渊.融合遗传算法改进的蚁群算法 [J].江南大学学报（自然科学版），2009（02）：149-153.

Xia H B，Xu W，Liu Y.Improved ant colony algorithm based on fusion genetic algorithm [J].Journal of Jiangnan University （Natural Science），2009（2）：149-153.

[5]李攀.基于遺传算法的分布式多连接查询优化系统设计与实现 [D].昆明：云南大学，2010.

Li P.Design and Implementation of a distributed multi join query optimization system based on genetic algorithm [D].Kunming：Yunnan University，2010.

[6]Zukhri Z，Paputungan I V.A hybrid optimization algorithm based on genetic algorithm and ant colony optimization [J].International Journal of Artificial Intelligence & Applications，2013，4（5）：63-75.

[7]Dorigo M，Gambardella L M.Ant Colony System：A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

[8]Crawford B，Soto R，Johnson F，et al.A Max-Min Ant system algorithm to solve the software project scheduling problem [J].Information Systems & Technologies，2014，41（15）：1-4.