蟻群算法在數(shù)據(jù)庫存儲(chǔ)過程中的應(yīng)用

樊紅珍

摘要；通過分析數(shù)據(jù)庫存儲(chǔ)過程的特點(diǎn)，作者提出了基于蟻群算法的分布式數(shù)據(jù)庫存儲(chǔ)模型。此模型根據(jù)應(yīng)用中心的海量數(shù)據(jù)的分布特性，以蟻群算法原理為基礎(chǔ)，在充分考慮負(fù)載均衡的前提下，完成了基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)模型的構(gòu)建。同時(shí)，該文將存儲(chǔ)容量均衡程度、吞吐量及響應(yīng)延時(shí)作為評(píng)價(jià)指標(biāo)。作者在Matlab仿真軟件中進(jìn)行數(shù)據(jù)庫存儲(chǔ)過程的仿真驗(yàn)證，進(jìn)而對(duì)所設(shè)計(jì)的數(shù)據(jù)庫存儲(chǔ)模型進(jìn)行性能驗(yàn)證。驗(yàn)證結(jié)果表明該文設(shè)計(jì)的基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)模型較順序數(shù)據(jù)庫存儲(chǔ)策略使數(shù)據(jù)庫在吞吐量方面增加了19.1%，響應(yīng)延時(shí)方面減少了12.9%，同時(shí)，能夠?qū)崿F(xiàn)各數(shù)據(jù)庫的存儲(chǔ)容量均衡分布。

關(guān)鍵詞：蟻群算法；數(shù)據(jù)庫；存儲(chǔ)過程

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)；1009-3044（2017）07-0006-02

數(shù)據(jù)應(yīng)用空間是通過互聯(lián)網(wǎng)技術(shù)和數(shù)據(jù)庫技術(shù)系統(tǒng)構(gòu)建的，其數(shù)據(jù)來源是海量互聯(lián)網(wǎng)應(yīng)用及相關(guān)服務(wù)，涉及各個(gè)領(lǐng)域，滲透到各個(gè)物品中。數(shù)據(jù)應(yīng)用空間可以劃分為感知層、網(wǎng)絡(luò)層以及數(shù)據(jù)應(yīng)用層三個(gè)層次，其中，數(shù)據(jù)應(yīng)用層負(fù)責(zé)對(duì)用戶產(chǎn)生的海量數(shù)據(jù)進(jìn)行傳輸和處理，因此，需要性能優(yōu)越的存儲(chǔ)模型對(duì)其性能進(jìn)行提升。換言之，對(duì)數(shù)據(jù)庫存儲(chǔ)過程的優(yōu)化即實(shí)現(xiàn)其分布式存儲(chǔ)。

目前，分布式數(shù)據(jù)庫存儲(chǔ)系統(tǒng)已經(jīng)逐漸被人們的所重視，其主要由各PC機(jī)及分布在云端的服務(wù)器資源系統(tǒng)配合完成的，通過研究發(fā)現(xiàn)，分布式數(shù)據(jù)庫存儲(chǔ)系統(tǒng)主要包含以下特點(diǎn)：

（1）擴(kuò)展性強(qiáng)。分布式數(shù)據(jù)存儲(chǔ)系統(tǒng)的容量范圍較大，從幾百臺(tái)數(shù)據(jù)庫系統(tǒng)到幾千臺(tái)都可以，而且可以根據(jù)具體的實(shí)際應(yīng)用進(jìn)行動(dòng)態(tài)添加，表現(xiàn)出的擴(kuò)展性極強(qiáng)，而且隨著數(shù)據(jù)庫規(guī)模的不斷擴(kuò)張，其性能也應(yīng)該呈線性增加趨勢(shì)。

（2）成本低。分布式數(shù)據(jù)庫存儲(chǔ)系統(tǒng)所具備的自動(dòng)糾錯(cuò)和自動(dòng)負(fù)載均衡功能可以使其部署在性能不必很突出的普通PC設(shè)備中。而且，且擴(kuò)展性使其能夠?qū)崿F(xiàn)設(shè)備的線性數(shù)量擴(kuò)張，不僅控制了硬件成本，而且控制了運(yùn)行維護(hù)成本。

（3）性能優(yōu)越。無論是針對(duì)整個(gè)分布式數(shù)據(jù)庫系統(tǒng)集群還是單臺(tái)數(shù)據(jù)庫服務(wù)器，數(shù)據(jù)庫的存儲(chǔ)過程通過多個(gè)優(yōu)化方法進(jìn)行協(xié)同配合，使其性能較一般的數(shù)據(jù)庫系統(tǒng)要強(qiáng)。

（4）易用性強(qiáng)。分布數(shù)據(jù)庫系統(tǒng)提供了第三方應(yīng)用的接口，方便管理員進(jìn)行功能擴(kuò)展，而且在運(yùn)行維護(hù)的過程中，提供了可視化的運(yùn)行維護(hù)、管理工具。

在本文中，作者提出了基于蟻群算法的分布式數(shù)據(jù)庫存儲(chǔ)模型。此模型根據(jù)應(yīng)用中心的海量數(shù)據(jù)的分布特性，以蟻群算法原理為基礎(chǔ)，在充分考慮負(fù)載均衡的前提下，完成了基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)模型的構(gòu)建。同時(shí)，本文將存儲(chǔ)容量均衡程度、吞吐量及響應(yīng)延時(shí)作為評(píng)價(jià)指標(biāo)。作者在Matlab仿真軟件中進(jìn)行數(shù)據(jù)庫存儲(chǔ)過程的仿真驗(yàn)證，進(jìn)而對(duì)所設(shè)計(jì)的數(shù)據(jù)庫存儲(chǔ)模型進(jìn)行性能驗(yàn)證。

1蟻群算法模型的建立

1.1基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)方法設(shè)計(jì)

1.1.1TSP蚊群算法模型

（1）

G=（C，L）表示某個(gè)有向圖，TSP主要負(fù)責(zé)從有向圖G中找出距離最小的Hamilton圈，此即一條對(duì)C={c₁，c₂，…，c_n）中被n個(gè)元素同時(shí)通過且僅通過一次的最短封閉了曲線。

為了更加準(zhǔn)確模擬螞蟻的實(shí)際運(yùn)動(dòng)軌跡，在蟻群算法模型中定義如下記號(hào)；b_i（t）描述了t時(shí)刻位于元素i處的螞蟻的總體數(shù)量；n描述了TSP蟻群的規(guī)模，m描述了蟻群中螞蟻的總數(shù)，d描述了節(jié)點(diǎn)i，j之間的距離，則以上參數(shù)滿足下式，

（2）

L_k描述了螞蟻k運(yùn)動(dòng)軌跡的總體長(zhǎng)度；本算法模型中通過禁忌表tabu_k（k=1，2，…，m）對(duì)螞蟻k當(dāng)前所走過的所有節(jié)點(diǎn)元素進(jìn)行記錄，螞蟻集合屬性隨著tabu_k的進(jìn)化更新過程進(jìn)行實(shí)時(shí)的動(dòng)態(tài)調(diào)整。Г={_ij（t）|c_i，c_j屬于C）描述了t時(shí)刻螞蟻集合C中任意元素兩兩連接鏈路l_ij中包含的殘留信息素的集合；τ_ij（t）描述了t時(shí)刻運(yùn)動(dòng)路徑（i，j）中殘留信息素的總體數(shù)量。在此模型中，假定在初始時(shí)刻所有路徑中包含的信息素濃度相等，且均勻分布，設(shè)初始信息素濃度τ_ij（0）一C（C為隨機(jī)正常數(shù)），而且需要說明的是蚊群算法尋求最優(yōu)解的過程主要是通過有向圖g=（C，L，Г）完成的，有向圖對(duì)螞蟻的運(yùn)動(dòng)路徑進(jìn)行規(guī)劃，同時(shí)對(duì)信息素進(jìn)行調(diào)整。

1.1.2路徑選擇機(jī)制

在蟻群算法模型中放置的人工螞蟻均處于離散狀態(tài)，螞蟻選擇下一移動(dòng)節(jié)點(diǎn)的依據(jù)是此路徑上的信息素濃度，選取信息素濃度大的路徑。螞蟻在整個(gè)移動(dòng)的過程中通過隨機(jī)策略實(shí)現(xiàn)游程的遍歷，而且在整個(gè)游程的遍歷過程中總能找到滿足要求的可行解。

首先，將m只螞蟻根據(jù)隨機(jī)分布原則將其分別安置在n個(gè)節(jié)點(diǎn)上，然后通過系統(tǒng)設(shè)定的狀態(tài)轉(zhuǎn)移規(guī)則在每個(gè)節(jié)點(diǎn)上循環(huán)實(shí)施。當(dāng)螞蟻處于節(jié)點(diǎn)i的位置，其通過執(zhí)行隨機(jī)轉(zhuǎn)移策略對(duì)另一個(gè)尚未經(jīng)過的節(jié)點(diǎn)j間的運(yùn)動(dòng)軌跡進(jìn)行確定，該策略的判斷依據(jù)主要包含兩方面內(nèi)容，一是節(jié)點(diǎn)i，j之間路徑上分布信息素的含量τ_ij（t），二是兩個(gè)節(jié)點(diǎn)間的距離。P^k_ij（t）描述了在t時(shí)刻螞蟻k從節(jié)點(diǎn)i向節(jié)點(diǎn)j移動(dòng)的狀態(tài)轉(zhuǎn)移概率，計(jì)算過程如下式所示：

（3）

在公式中，allowd_k={{1，2，…，n}-tabu_k）描述了螞蟻k在下一時(shí)刻能夠選擇的節(jié)點(diǎn)集合；η^β_ij描述了系統(tǒng)的啟發(fā)函數(shù)，而且對(duì)于螞蟻k來說，d_ij的取值越小，k則越大，轉(zhuǎn)移概率P^k_ij（t）也就越大。

（4）

從數(shù)學(xué)的角度來看，啟發(fā)函數(shù)能夠準(zhǔn)確描述螞蟻從節(jié)點(diǎn)i向節(jié)點(diǎn)j移動(dòng)的期望程度，即系統(tǒng)中路徑（i，j）的期望程度；α，β分別負(fù)責(zé)描述τ，η因子對(duì)此的作用程度。其中，α作為系統(tǒng)的信息啟發(fā)式因子，能夠?qū)壽E的重要性進(jìn)行描述，等價(jià)于其值能夠描述此路徑中包含的信息素的含量，信息素含量越大，α值越大，意味著螞蟻選擇其他螞蟻已經(jīng)運(yùn)動(dòng)過的路徑的可能性就越大，但α值過大會(huì)給系統(tǒng)帶來陷入局部最優(yōu)解的困難之中；β是系統(tǒng)的期望啟發(fā)式因子，描述了能見度的相對(duì)重要性，其取值的大小直接關(guān)系到啟發(fā)式信息的重要程度。如果α=0，蟻群算法越接近于典型的貪婪算法。如果β=0，蟻群算法越接近于正反饋啟發(fā)式算法。綜上所述，算法的螞蟻會(huì)選擇路徑相對(duì)較短、信息素含量相對(duì)較高的路徑作為下一時(shí)刻的運(yùn)行路徑。

2應(yīng)用測(cè)試

本文在Matlab軟件中構(gòu)建仿真實(shí)驗(yàn)場(chǎng)景，仿真場(chǎng)景主要由兩臺(tái)服務(wù)器組成，同時(shí)，每臺(tái)服務(wù)器與五個(gè)存儲(chǔ)單元連接，服務(wù)器之間以及存儲(chǔ)單元之間均使用有線網(wǎng)絡(luò)實(shí)現(xiàn)信息交互，同時(shí)配備了10個(gè)數(shù)據(jù)終端向服務(wù)器的存儲(chǔ)單元進(jìn)行寫操作，即實(shí)現(xiàn)了存儲(chǔ)過程。寫操作的數(shù)據(jù)傳輸速率10 M/ms，將蟻群算法融入到該仿真場(chǎng)景中，使其能夠根據(jù)讀寫操作的內(nèi)容合理地選擇目標(biāo)存儲(chǔ)器，仿真時(shí)間設(shè)置為20分鐘，實(shí)驗(yàn)完成后，對(duì)未使用蟻群算法和使用過蟻群算法的使用結(jié)果進(jìn)行分析對(duì)比。

本實(shí)驗(yàn)的目的是實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)的均衡分布，圖1對(duì)10臺(tái)數(shù)據(jù)庫存儲(chǔ)單元在完成了寫操作后的存儲(chǔ)容量結(jié)果，通過實(shí)驗(yàn)結(jié)果可以看到，使用了蟻群算法的數(shù)據(jù)庫存儲(chǔ)過程，各存儲(chǔ)單元的容量基本維持在11 928 M左右，說明本文設(shè)計(jì)的基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)方法能夠有效地分布數(shù)據(jù)的存儲(chǔ)壓力，真正實(shí)現(xiàn)了分布式存儲(chǔ)的思想，不會(huì)造成數(shù)據(jù)的擁堵。

而且在吞吐量及響應(yīng)延時(shí)方面，與典型的順序分布的存儲(chǔ)器模型比較，性能也有所提升，據(jù)統(tǒng)計(jì)，本文設(shè)計(jì)的基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)方法在吞吐量方面增加了19.1%，在響應(yīng)延時(shí)方面，減少了大約12.9%。性能分析可能會(huì)很復(fù)雜，因?yàn)椴煌闆r下系統(tǒng)的瓶頸點(diǎn)不同，有的時(shí)候是網(wǎng)絡(luò)，有的時(shí)候是磁盤，有的時(shí)候甚至是機(jī)房的交換機(jī)或者CPU，另外，負(fù)載均衡以及其他因素的干擾也會(huì)使得性能更加難以量化。

3總結(jié)

在本文中，作者通過分析數(shù)據(jù)庫存儲(chǔ)過程的特點(diǎn)，作者提出了基于蟻群算法的分布式數(shù)據(jù)庫存儲(chǔ)模型。此模型根據(jù)應(yīng)用中心的海量數(shù)據(jù)的分布特性，以蚊群算法原理為基礎(chǔ)，在充分考慮負(fù)載均衡的前提下，完成了基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)模型的構(gòu)建。同時(shí)，本文將存儲(chǔ)容量均衡程度、吞吐量及響應(yīng)延時(shí)作為評(píng)價(jià)指標(biāo)。作者在Matlab仿真軟件中進(jìn)行數(shù)據(jù)庫存儲(chǔ)過程的仿真驗(yàn)證，進(jìn)而對(duì)所設(shè)計(jì)的數(shù)據(jù)庫存儲(chǔ)模型進(jìn)行性能驗(yàn)證。驗(yàn)證結(jié)果表明本文設(shè)計(jì)的基于蟻群算法的數(shù)據(jù)庫存儲(chǔ)模型較順序數(shù)據(jù)庫存儲(chǔ)策略使數(shù)據(jù)庫在吞吐量方面增加了18.3%，響應(yīng)延時(shí)方面減少了14.2%，同時(shí)，能夠?qū)崿F(xiàn)各數(shù)據(jù)庫的存儲(chǔ)容量均衡分布。