《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于二進(jìn)制粒子群與遺傳算法的數(shù)據(jù)分配研究
基于二進(jìn)制粒子群與遺傳算法的數(shù)據(jù)分配研究
2016年電子技術(shù)應(yīng)用第7期
李世文1，張紅梅1，張向利1，班文嬌2
1.桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541000； 2.桂林電子科技大學(xué) 教育部認(rèn)知無(wú)線電與信息處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541000
摘要： 針對(duì)目前分布式數(shù)據(jù)庫(kù)數(shù)據(jù)分配方法法存在尋求最優(yōu)分配方案和運(yùn)行效率等問題的不足，在基于改進(jìn)的遺傳算法的數(shù)據(jù)分配方法基礎(chǔ)上，引入二進(jìn)制粒子群算法，提出了一種基于二進(jìn)制粒子群與遺傳算法的數(shù)據(jù)分配方法，既具有二進(jìn)制粒子群算法的運(yùn)行速度快、記憶功能好等特點(diǎn)，又具有遺傳算法的全局搜索能力、變異能力等特點(diǎn)。該分配方法能夠提高搜索效率，并且快速有效地獲得全局最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，所提出的數(shù)據(jù)分配方法在搜索全局最優(yōu)解方面優(yōu)于基于遺傳算法的分配方法，在搜索速度方面比枚舉法的分配方法和基于遺傳算法的分配方法更快。
中圖分類號(hào)： TP311
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2016.07.031
中文引用格式： 李世文，張紅梅，陳鶴，等. 基于二進(jìn)制粒子群與遺傳算法的數(shù)據(jù)分配研究[J].電子技術(shù)應(yīng)用，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.
Research of data allocation problem based on hybrid binary particle swarm & genetic algorithm
Li Shiwen1，Zhang Hongmei1，Zhang Xiangli1，Ban Wenjiao2
1.Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems， GuiLin University of Electronic Technology，Guilin 541000，China； 2.Key Laboratory of Cognitive Radio & Information Processing, the Ministry of Education， Guilin University of Electronic Technology，Guilin 541000，China
Abstract： In response to the deficiencies of optimal allocation seeking and efficiency in distributed database allocation algorithm, a data allocation method based on hybrid binary particle swarm & genetic algorithm is proposed. The method introduces binary particle swarm optimization algorithm to the data distribution method of improving genetic algorithm, which inherits from binary particle swarm optimal algorithm the feature of speedy and memory ability, and also keeps the global search and mutation capability features of genetic algorithm. The allocation algorithm improves the search efficiency, and gets global optimal solution quickly and efficiently. Experimental results show that the proposed data allocation method is better than the method based on genetic algorithm in global optimal solution searching, and its searching speed is faster than Enumeration and the method based on genetic algorithm.
Key words : genetic algorithm；binary particle swarm optimization algorithm；data distribution；the search efficiency；optimal solution

0 引言

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

1 研究現(xiàn)狀

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

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

2 基于HBPSOGA的分配方法分析

2.1 統(tǒng)計(jì)信息與代價(jià)公式

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

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

jsj3-b1.gif

2.1.2 代價(jià)公式的選擇

    代價(jià)的度量標(biāo)準(zhǔn)是Min(TotalCost)。假設(shè)各個(gè)站點(diǎn)有相同的處理能力，則用訪問的總數(shù)據(jù)量來(lái)表示代價(jià)公式，所以本文采用的代價(jià)公式為：

jsj3-gs1-3.gif

其中，片段Fj是在站點(diǎn)Sk上的執(zhí)行事務(wù)Ti所訪問的數(shù)據(jù)片段，Sf為Fj的任一副本所在站點(diǎn)，即所有擁有數(shù)據(jù)片段Fj副本的站點(diǎn)。

2.2 遺傳算法及改進(jìn)

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

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

     jsj3-gs4-5.gif

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

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

jsj3-gs6-7.gif

2.3 二進(jìn)制粒子群算法

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

    二進(jìn)制PSO算法的速度更新公式為：

jsj3-gs8.gif

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

jsj3-gs9-10.gif

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

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

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

    (1)參數(shù)初始化，包括最大迭代次數(shù)Nmax，種群規(guī)模PopSize，最大速度vmax，粒子群慣性因子w，學(xué)習(xí)因子c1、c2。

    (2)計(jì)算數(shù)據(jù)片段的更新檢索比，基于數(shù)據(jù)片段的更新檢索比來(lái)初始化群體Pop=(xij)N×m，其中N為PopSize，即個(gè)體的數(shù)目，m為所求問題的維數(shù)，即站點(diǎn)數(shù)目；每個(gè)個(gè)體采用二進(jìn)制編碼，編碼長(zhǎng)度等于站點(diǎn)的數(shù)目，當(dāng)在站點(diǎn)Sj上分配數(shù)據(jù)片段時(shí)，xij=1，否則xij=0。

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

    jsj3-gs11.gif

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

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

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

    (6)對(duì)種群Pop″中的個(gè)體，按照式(7)概率Pm進(jìn)行變異操作，得到種群jsj3-gs11-x1.gif。其變異操作是：個(gè)體的基因若為1，則變成0；若為0，則變成1。

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

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

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 實(shí)驗(yàn)分析

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

jsj3-b2.gif

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

jsj3-b3.gif

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

jsj3-b4.gif

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

jsj3-b5.gif

jsj3-t1.gif

jsj3-t2.gif

jsj3-t3.gif

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1] 賴玲.分布式數(shù)據(jù)庫(kù)系統(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ù)庫(kù)中數(shù)據(jù)分配策略的研究[D].哈爾濱：哈爾濱工程大學(xué)，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ù)庫(kù)數(shù)據(jù)分配策略研究[D].大連：大連理工大學(xué)，2009.

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

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

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。