基于二进制粒子群与遗传算法的数据分配研究

李世文1，张红梅1，张向利1，班文娇2

（1.桂林电子科技大学 广西高校云计算与复杂系统重点实验室，广西 桂林541000；

2.桂林电子科技大学 教育部认知无线电与信息处理重点实验室，广西 桂林541000）

针对目前分布式数据库数据分配方法法存在寻求最优分配方案和运行效率等问题的不足，在基于改进的遗传算法的数据分配方法基础上，引入二进制粒子群算法，提出了一种基于二进制粒子群与遗传算法的数据分配方法，既具有二进制粒子群算法的运行速度快、记忆功能好等特点，又具有遗传算法的全局搜索能力、变异能力等特点。该分配方法能够提高搜索效率，并且快速有效地获得全局最优解。实验结果表明，所提出的数据分配方法在搜索全局最优解方面优于基于遗传算法的分配方法，在搜索速度方面比枚举法的分配方法和基于遗传算法的分配方法更快。

遗传算法；二进制粒子群算法；数据分配；搜索效率；最优解

中图分类 ：TP311

A

DOI：10.16157/j.issn.0258-7998.2016.07.031

中文引用格式：李世文，张红梅，陈鹤，等. 基于二进制粒子群与遗传算法的数据分配研究[J].电子技术应用，2016，42(7)：122-125，129.

英文引用格式：Li Shiwen，Zhang Hongmei，Chen He，et al. Research of data allocation problem based on hybrid binary particle swarm & genetic algorithm[J].Application of Electronic Technique，2016，42(7)：122-125，129.

0 引言

现今，分布式数据库系统^[1]应用广泛，数据分配对其性能影响极其重要。数据分配问题的描述：假设一个 络由站点集S=(S₁，S₂，…，S_n)构成，该 络上执行一个事务集T=(T₁，T₂，…，T_q)，存储着一个数据片段集F=(F₁，F₂，…，F_m)，按照一定的方式将每个片段F_j的不同副本分配到不同的站点S_k上，分配方案表示为D<F，S，T>。若能够从总分配方案中得到一种较优化的分配方案,整个分布式数据库系统的性能、可靠性都将会大大地提升。

1 研究现状

目前在国内外有许多文献对数据分配问题进行研究。基于得益代价优化的启发式分配方法^[2]设计复杂，计算开销大；文献[3]提出了基于数据片段访问特性的分配策略，但该策略不能解决搜索容易陷入局部最优解的问题。一些学者利用遗传算法(Genetic Algorithm，GA)来解决数据分配问题^[4-6]，其中文献[6]提出了基于遗传算法的数据分配方法，具有全局搜索能力，能够避免陷入局部最优搜索，但搜索过程是随机的，缺乏记忆功能，搜索速度较慢，且所求结果与最优解有一定差距。

2 基于HBPSOGA的分配方法分析

2.1 统计信息与代价公式

统计信息是解决数据分配的基本信息，用于计算检索代价、更新代价和个体适应度。根据统计信息的重要性、获取的难易程度以及对代价公式复杂度的影响，获取表1中的统计信息。

2.1.2 代价公式的选择

其中，片段F_j是在站点S_k上的执行事务T_i所访问的数据片段，S_f为F_j的任一副本所在站点，即所有拥有数据片段F_j副本的站点。

2.2 遗传算法及改进

(1)在初始化种群时，首先计算数据片段的更新检索比，再基于数据片段的更新检索比来初始化群体。通过式(4)和式(5)分别计算片段的检索访问量和更新访问量：

将所有站点对片段F_j的检索访问量相加得到的值为Q，将所有站点对片段F_j的更新访问量相加得到的值为U。若数据片段中U/Q<1，则在初始化群体时，需要多设置其副本分配给站点，以减少检索通信代价；若数据片段中U/Q>1，则需要少设置其副本，以减少多个副本间数据一致性的更新代价。

(2)个体进行交叉、变异操作时，采用自调整交叉算子和自调整变异算子^[8]，分别如式(6)和式(7)，能够提升算法的搜索速度和求解质量。

2.3 二进制粒子群算法

粒子群算法是一种模仿生物种群(鸟群和鱼群)觅食行为的搜索算法。然而标准PSO算法是只适用于连续搜索空间计算，对于离散的搜索空间，它无法直接使用。因此研究人员提出了粒子群算法的二进制版本(BPSO)，用来求解离散二进制空间的问题。

二进制PSO算法的速度更新公式为：

为了表示速度的值是位置取1的概率,速度的值被映射到区间[0，1]，映射的方法采用式(9)Sigmoid函数：

2.4 基于HBPSOGA的数据分配方法

(1)参数初始化，包括最大迭代次数N_max，种群规模PopSize，最大速度v_max，粒子群惯性因子w，学习因子c₁、c₂。

(2)计算数据片段的更新检索比，基于数据片段的更新检索比来初始化群体Pop=(x_ij)_N×m，其中N为PopSize，即个体的数目，m为所求问题的维数，即站点数目；每个个体采用二进制编码，编码长度等于站点的数目，当在站点S_j上分配数据片段时，x_ij=1，否则x_ij=0。

(3)定义个体的适应度为：

式中：T_Q、T_U表示查询总代价和更新总代价，详情参见式(2)、式(3)。

(4)计算种群Pop中的所有个体适应度，采用精英主义操作来选择个体，产生种群Pop′。其精英主义操作是保留适应度大的个体，淘汰适应度小的个体。

(5)计算种群Pop′中所有个体的适应度，并对其进行评价，使用轮盘赌方法选出染色体对，按照式(6)概率Pc进行交叉操作，得到种群Pop″。其交叉操作是随机设定一个交叉点，两个个体的基因在交叉点位置进行互换，生成两个新的个体。

(6)对种群Pop″中的个体，按照式(7)概率P_m进行变异操作，得到种群。其变异操作是：个体的基因若为1，则变成0；若为0，则变成1。

(7)计算种群中的所有个体适应度，得到个体最优位置Pbest和全局最优位置Gbest，并按照式(8)和式(10)分别对种群所有个体的速度和位置进行更新，产生种群Pop。

(8)若迭代次数已经达到最大迭代次数Nmax，则算法结束，转步骤(9)，否则转步骤(4)。

(9)输出最优个体作为问题最优解。

3 实验与分析

3.1 实验环境

在实验中，采用了3种分布式环境。第一种环境含有2个分片、3个事务、4个站点。第二种环境含有3个分片、3个事务、5个站点。第三种环境更为复杂，含有10个分片、5个事务、10个站点。若分布式环境中有n个片段，m个站点，则分配方案有(2^m-1)ⁿ种。因此在这3种环境下，数据的分配方案分别为225种、29 791种、(1 023)¹⁰种。

3.2 实验分析

4 结束语

参考文献

[1] 赖玲.分布式数据库系统研究[J].软件导刊，2009，8(9)：169-170.

[2] ISMAIL O H，MUTHU R，NICHOLAS B.A high-performance computing method for data allocation in distributed database systems[J].Springer Science，2007，39(1)：3-18.

[3] 杨洲.分布式数据库中数据分配策略的研究[D].哈尔滨：哈尔滨工程大学，2007.

[4] RAHMANI S，TORKZABAN V，T.HAGHIGHAT A.A new method of genetic algorithm for data allocation in distributed systems[C].Education Technology and Computer Science，First International Workshop on.Wuhan，Hubei：IEEE Press，2009.

[5] PORTALURI，PISA G U，ITALY.A power efficient genetic algorithm for resource allocation in cloud computing data centers[C].Cloud Networking(CloudNet)，2014 IEEE 3rd International Conference on.Luxembourg：IEEE Press，2014.

[6] 李想.分布式数据库数据分配策略研究[D].大连：大连理工大学，2009.

[7] 陈希祥，邱静，刘冠军.基于混合二进制粒子群_遗传算法的测试优化选择研究[J].仪器仪表学 ，2009，30(8)：1674-1680.

[8] 赫琳，马长林.改进的自适应遗传算法及其性能研究[C].哈尔滨：中国控制与决策学术年会，2005：895-898.