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]提出了基于遺傳算法的數據分配方法，具有全局搜索能力，能夠避免陷入局部最優搜索，但搜索過程是隨機的，缺乏記憶功能，搜索速度較慢，且所求結果與最優解有一定差距。

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

2 基于HBPSOGA的分配方法分析

2.1 統計信息與代價公式

2.1.1 本文采用的統計信息

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

2.1.2 代價公式的選擇

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

其中，片段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的數據分配方法

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

    針對每個數據片段,采用本文的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)¹⁰種。

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

3.2 實驗分析

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

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

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

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

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.