0 引言

    現(xiàn)今，分布式數(shù)據(jù)庫系統(tǒng)^[1]應(yīng)用廣泛，數(shù)據(jù)分配對其性能影響極其重要。數(shù)據(jù)分配問題的描述：假設(shè)一個網(wǎng)絡(luò)由站點集S=(S₁，S₂，…，S_n)構(gòu)成，該網(wǎng)絡(luò)上執(zhí)行一個事務(wù)集T=(T₁，T₂，…，T_q)，存儲著一個數(shù)據(jù)片段集F=(F₁，F(xiàn)₂，…，F(xiàn)_m)，按照一定的方式將每個片段F_j的不同副本分配到不同的站點S_k上，分配方案表示為D<F，S，T>。若能夠從總分配方案中得到一種較優(yōu)化的分配方案,整個分布式數(shù)據(jù)庫系統(tǒng)的性能、可靠性都將會大大地提升。

1 研究現(xiàn)狀

    目前在國內(nèi)外有許多文獻對數(shù)據(jù)分配問題進行研究?；诘靡娲鷥r優(yōu)化的啟發(fā)式分配方法^[2]設(shè)計復(fù)雜，計算開銷大；文獻[3]提出了基于數(shù)據(jù)片段訪問特性的分配策略，但該策略不能解決搜索容易陷入局部最優(yōu)解的問題。一些學者利用遺傳算法(Genetic Algorithm，GA)來解決數(shù)據(jù)分配問題^[4-6]，其中文獻[6]提出了基于遺傳算法的數(shù)據(jù)分配方法，具有全局搜索能力，能夠避免陷入局部最優(yōu)搜索，但搜索過程是隨機的，缺乏記憶功能，搜索速度較慢，且所求結(jié)果與最優(yōu)解有一定差距。

    二進制粒子群算法^[7](Binary Particle Swarm Optimization，BPSO)具有記憶功能，能夠提高搜索速度。本文對遺傳算法稍加改進，并結(jié)合二進制粒子群算法，針對分布式數(shù)據(jù)庫數(shù)據(jù)分配的代價公式與適應(yīng)度函數(shù)，提出了一種基于混合二進制粒子群與遺傳算法(Hybrid BPSO and GA，HBPSOGA)的數(shù)據(jù)分配方法。

2 基于HBPSOGA的分配方法分析

2.1 統(tǒng)計信息與代價公式

2.1.1 本文采用的統(tǒng)計信息

    統(tǒng)計信息是解決數(shù)據(jù)分配的基本信息，用于計算檢索代價、更新代價和個體適應(yīng)度。根據(jù)統(tǒng)計信息的重要性、獲取的難易程度以及對代價公式復(fù)雜度的影響，獲取表1中的統(tǒng)計信息。

2.1.2 代價公式的選擇

    代價的度量標準是Min(TotalCost)。假設(shè)各個站點有相同的處理能力，則用訪問的總數(shù)據(jù)量來表示代價公式，所以本文采用的代價公式為：

其中，片段F_j是在站點S_k上的執(zhí)行事務(wù)T_i所訪問的數(shù)據(jù)片段，S_f為F_j的任一副本所在站點，即所有擁有數(shù)據(jù)片段F_j副本的站點。

2.2 遺傳算法及改進

    遺傳算法是一種模擬生物學的遺傳和進化演變過程所建立的全局性概率搜索算法。由于運用經(jīng)典的遺傳算法來解決數(shù)據(jù)分配問題，未能快速地找到最優(yōu)分配方案。因此本文對經(jīng)典的遺傳算法做如下改進：

    (1)在初始化種群時，首先計算數(shù)據(jù)片段的更新檢索比，再基于數(shù)據(jù)片段的更新檢索比來初始化群體。通過式(4)和式(5)分別計算片段的檢索訪問量和更新訪問量：

    將所有站點對片段F_j的檢索訪問量相加得到的值為Q，將所有站點對片段F_j的更新訪問量相加得到的值為U。若數(shù)據(jù)片段中U/Q<1，則在初始化群體時，需要多設(shè)置其副本分配給站點，以減少檢索通信代價；若數(shù)據(jù)片段中U/Q>1，則需要少設(shè)置其副本，以減少多個副本間數(shù)據(jù)一致性的更新代價。

    (2)個體進行交叉、變異操作時，采用自調(diào)整交叉算子和自調(diào)整變異算子^[8]，分別如式(6)和式(7)，能夠提升算法的搜索速度和求解質(zhì)量。

2.3 二進制粒子群算法

    粒子群算法是一種模仿生物種群(鳥群和魚群)覓食行為的搜索算法。然而標準PSO算法是只適用于連續(xù)搜索空間計算，對于離散的搜索空間，它無法直接使用。因此研究人員提出了粒子群算法的二進制版本(BPSO)，用來求解離散二進制空間的問題。

    二進制PSO算法的速度更新公式為：

    為了表示速度的值是位置取1的概率,速度的值被映射到區(qū)間[0，1]，映射的方法采用式(9)Sigmoid函數(shù)：

2.4 基于HBPSOGA的數(shù)據(jù)分配方法

    二進制粒子群算法結(jié)構(gòu)簡單，運行速度快，具有記憶功能，但容易陷入局部最優(yōu)，出現(xiàn)了所謂的早熟收斂現(xiàn)象。而遺傳算法具有大范圍的搜索全局能力，不容易陷入局部最優(yōu)，但是搜索速度較慢，缺乏記憶功能。本文在基于改進的遺傳算法的數(shù)據(jù)分配方法基礎(chǔ)上，引入二進制粒子群算法，提出一種混合算法的數(shù)據(jù)分配方法，既增強了搜索速度，又避免陷入局部最優(yōu)，提高成功率。

    針對每個數(shù)據(jù)片段,采用本文的HBPSOGA獲得該數(shù)據(jù)片段的分配方案,最終得到整體分配方案。下面詳細介紹針對某個片段運用該方法進行分配的具體步驟：

    (1)參數(shù)初始化，包括最大迭代次數(shù)N_max，種群規(guī)模PopSize，最大速度v_max，粒子群慣性因子w，學習因子c₁、c₂。

    (2)計算數(shù)據(jù)片段的更新檢索比，基于數(shù)據(jù)片段的更新檢索比來初始化群體Pop=(x_ij)_N×m，其中N為PopSize，即個體的數(shù)目，m為所求問題的維數(shù)，即站點數(shù)目；每個個體采用二進制編碼，編碼長度等于站點的數(shù)目，當在站點S_j上分配數(shù)據(jù)片段時，x_ij=1，否則x_ij=0。

    (3)定義個體的適應(yīng)度為：

式中：T_Q、T_U表示查詢總代價和更新總代價，詳情參見式(2)、式(3)。

    (4)計算種群Pop中的所有個體適應(yīng)度，采用精英主義操作來選擇個體，產(chǎn)生種群Pop′。其精英主義操作是保留適應(yīng)度大的個體，淘汰適應(yīng)度小的個體。

    (5)計算種群Pop′中所有個體的適應(yīng)度，并對其進行評價，使用輪盤賭方法選出染色體對，按照式(6)概率Pc進行交叉操作，得到種群Pop″。其交叉操作是隨機設(shè)定一個交叉點，兩個個體的基因在交叉點位置進行互換，生成兩個新的個體。

    (6)對種群Pop″中的個體，按照式(7)概率P_m進行變異操作，得到種群。其變異操作是：個體的基因若為1，則變成0；若為0，則變成1。

    (7)計算種群中的所有個體適應(yīng)度，得到個體最優(yōu)位置Pbest和全局最優(yōu)位置Gbest，并按照式(8)和式(10)分別對種群所有個體的速度和位置進行更新，產(chǎn)生種群Pop。

    (8)若迭代次數(shù)已經(jīng)達到最大迭代次數(shù)Nmax，則算法結(jié)束，轉(zhuǎn)步驟(9)，否則轉(zhuǎn)步驟(4)。

    (9)輸出最優(yōu)個體作為問題最優(yōu)解。

3 實驗與分析

3.1 實驗環(huán)境

    在實驗中，采用了3種分布式環(huán)境。第一種環(huán)境含有2個分片、3個事務(wù)、4個站點。第二種環(huán)境含有3個分片、3個事務(wù)、5個站點。第三種環(huán)境更為復(fù)雜，含有10個分片、5個事務(wù)、10個站點。若分布式環(huán)境中有n個片段，m個站點，則分配方案有(2^m-1)ⁿ種。因此在這3種環(huán)境下，數(shù)據(jù)的分配方案分別為225種、29 791種、(1 023)¹⁰種。

    在每種分布式環(huán)境下隨機生成一組統(tǒng)計信息，根據(jù)每組統(tǒng)計信息分別使用枚舉法的分配方法、本文的分配方法和基于遺傳算法的分配方法來進行數(shù)據(jù)分配，并計算出檢索和更新的總代價，統(tǒng)計分配方法所運行的時間。枚舉算法的分配方法是循環(huán)所有的分配方案，目的是得到最優(yōu)解的分配方案，進而與本文提出的分配方法和基于遺傳算法的分配方法進行比較?；谶z傳算法的分配方法是參考文獻[6]。3種數(shù)據(jù)分配方法都是在同一機器上運行比較，機器的配置：CPU i3-2323M 2.20 GHz，內(nèi)存4 GB。

3.2 實驗分析

    針對第1組統(tǒng)計信息(見表2)，采用本文的分配方法進行數(shù)據(jù)分配時，設(shè)參數(shù)取值如下：PopSize=5，w=0.8，c₁=c₁=2，vmax=4，Nmax=50。

    針對第2組統(tǒng)計信息(見表3)，采用本文的分配方法進行數(shù)據(jù)分配時，設(shè)參數(shù)取值如下：PopSize=6，w=0.8，c₁=c₁=2，v_max=4，N_max=50。

    針對第3組統(tǒng)計信息（見表4），采用本文的分配方法進行數(shù)據(jù)分配時，設(shè)參數(shù)取值如下：PopSize=11，w=0.8，c₁=c₁=2，v_max=4，N_max=100。

    對3組統(tǒng)計信息進行實驗，得到實驗結(jié)果如表5。在得到總代價方面，本文提出的分配方法和枚舉法的分配方法一樣，能夠得到最小總代價的分配方案。而基于遺傳算法的分配方法無法做到。在時間花費方面，本文的分配方法運行時間最短。將本文的方法和基于遺傳算法的方法在每次種群迭代時進行性能比較，結(jié)果如圖1、2、3所示，可以看出，基于HBPSOGA的方法比基于GA的方法獲得的總代價值更小，并且在相同的總代價值情況下所運行的迭代次數(shù)更少，這說明基于HBPSOGA的方法搜索速度更快。實驗表明，采用本文的方法所得到的解是最優(yōu)解，并且能更快地搜索到最優(yōu)解。這說明本文采用的分配方法要比枚舉法的分配方法和基于遺傳算法的分配方法更優(yōu)。

4 結(jié)束語

    本文分析了遺傳算法和二進制粒子群算法各自的優(yōu)點，并對遺傳算法稍加改進，在解決分布式數(shù)據(jù)庫數(shù)據(jù)分配問題上，提出了基于混合二進制粒子群與遺傳算法的數(shù)據(jù)分配方法，通過實驗測試了該方法在數(shù)據(jù)分配方面效果。在獲得最優(yōu)解和搜索速度等方面，分別與枚舉法的分配方法和基于遺傳算法的分配方法做了比較。實驗結(jié)果充分說明該方法相比其他兩種方法具有搜索效率更高、求解速度更快等特點，并且能夠獲得全局最優(yōu)解。

參考文獻

[1] 賴玲.分布式數(shù)據(jù)庫系統(tǒng)研究[J].軟件導(dǎo)刊，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] 楊洲.分布式數(shù)據(jù)庫中數(shù)據(jù)分配策略的研究[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，F(xiàn)irst 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] 李想.分布式數(shù)據(jù)庫數(shù)據(jù)分配策略研究[D].大連：大連理工大學，2009.

[7] 陳希祥，邱靜，劉冠軍.基于混合二進制粒子群_遺傳算法的測試優(yōu)化選擇研究[J].儀器儀表學報，2009，30(8)：1674-1680.

[8] 赫琳，馬長林.改進的自適應(yīng)遺傳算法及其性能研究[C].哈爾濱：中國控制與決策學術(shù)年會，2005：895-898.