陳金萍

（大連海洋大學(xué) 應(yīng)用技術(shù)學(xué)院，遼寧 瓦房店 116300）

基于基本果蠅算法改進(jìn)的數(shù)據(jù)庫(kù)查詢優(yōu)化策略

陳金萍

（大連海洋大學(xué) 應(yīng)用技術(shù)學(xué)院，遼寧 瓦房店 116300）

由于當(dāng)前很多常用的數(shù)據(jù)庫(kù)查詢優(yōu)化算法都存在查詢效率低的問題，很難找到能夠?qū)崿F(xiàn)全局最優(yōu)的數(shù)據(jù)庫(kù)查詢優(yōu)化算法，使得很多用戶在進(jìn)行數(shù)據(jù)庫(kù)查詢時(shí)，數(shù)據(jù)庫(kù)無(wú)法完全滿足其需求.為此，本文提出了一種基于基本果蠅算法改進(jìn)的數(shù)據(jù)庫(kù)查詢優(yōu)化方法，并通過仿真測(cè)試的方法驗(yàn)證其查詢優(yōu)化的效果，以求加快數(shù)據(jù)庫(kù)查詢優(yōu)化問題的效率和質(zhì)量.

兩階段；優(yōu)化方案；數(shù)據(jù)庫(kù)查詢；果蠅算法；仿真測(cè)試；查詢優(yōu)化

在數(shù)據(jù)庫(kù)應(yīng)用中，查詢是其中使用最為頻繁的操作.查詢操作需要在動(dòng)態(tài)組成的虛擬數(shù)據(jù)庫(kù)上進(jìn)行，在查詢過程中，服務(wù)是中心，整個(gè)查詢過程通過動(dòng)態(tài)組建服務(wù)以供用戶使用并完成查詢?nèi)蝿?wù).隨著信息技術(shù)的發(fā)展，數(shù)據(jù)庫(kù)在信息管理系統(tǒng)中的重要性與日俱增升，要想為用戶提供更好的信息管理系統(tǒng)功能，就必須使用優(yōu)化的查詢方案，以獲得更好的使用體驗(yàn).

1 數(shù)據(jù)庫(kù)查詢優(yōu)化研究簡(jiǎn)介

傳統(tǒng)的數(shù)據(jù)庫(kù)查詢方法一般而言都是通過依靠人工輸入對(duì)應(yīng)的指令的方式來(lái)實(shí)現(xiàn)的，但是這種方式的自動(dòng)化水平較低，使用效率十分不理想，無(wú)法完全滿足現(xiàn)代信息管理系統(tǒng)的查詢需求.在此背景下，很多研究人員又提出了一些查詢算法，如基于例子全優(yōu)化算法、螢火蟲算法等，但是雖然尋找全局最優(yōu)解的能力都很強(qiáng)，并且還兼帶搜索能力，都能以最快的速度找到最優(yōu)方案，也因此而成為數(shù)據(jù)庫(kù)優(yōu)化研究分析中的一個(gè)重要方向方向.但是這些算法都依然存在一些缺點(diǎn)，例如，后期收斂速度較慢，容易陷入局部最優(yōu)查詢方案等，也未能成為最優(yōu)方案.因此，必須對(duì)這些缺陷進(jìn)行彌補(bǔ)，找到更加卓越的數(shù)據(jù)庫(kù)查詢優(yōu)化策略.

為了獲得更好的數(shù)據(jù)庫(kù)查詢優(yōu)化方案，筆者在本文中提出了一種兩階段數(shù)據(jù)庫(kù)查詢優(yōu)化策略，這種優(yōu)化策略主要被分為兩個(gè)階段進(jìn)行.第一個(gè)階段是對(duì)基本的果蠅優(yōu)化算法進(jìn)行一定的改進(jìn)，并將其運(yùn)用到數(shù)據(jù)庫(kù)查詢優(yōu)化中；第二階段，對(duì)數(shù)據(jù)庫(kù)的查詢問題進(jìn)行更深一步的優(yōu)化，最后通過仿真對(duì)比試驗(yàn)驗(yàn)證其有效性，下面將對(duì)該數(shù)據(jù)庫(kù)查詢優(yōu)化方案的優(yōu)化過程進(jìn)行具體的敘述.

2 基本果蠅算法改進(jìn)分析

2.1 基本果蠅優(yōu)化算法介紹

果蠅優(yōu)化算法是一種新型的群智能算法，與其他群智能算法相比較來(lái)說(shuō)，具有能夠調(diào)整參數(shù)和簡(jiǎn)單容易實(shí)現(xiàn)的優(yōu)點(diǎn)，學(xué)習(xí)和理解起來(lái)更加容易.該算法的具體過程如下所示：參數(shù)初始化——設(shè)置果蠅個(gè)體嗅覺覓食的隨機(jī)方向和距離——估計(jì)與遠(yuǎn)點(diǎn)的距離，并計(jì)算下一位置的味道濃度判定值——將下一位置濃度的判定值帶入味道濃度判定值函數(shù)，再將果蠅個(gè)體所在位置的味道濃度計(jì)算出來(lái)——計(jì)算出整個(gè)群體中味道濃度最佳的果蠅——記錄最佳味道濃度值預(yù)期對(duì)應(yīng)的坐標(biāo)，這是，果蠅群體就會(huì)依靠其敏銳的視覺飛向該坐標(biāo)——持續(xù)重復(fù)上述幾個(gè)步驟，直到所得結(jié)果滿足終止條件為止.

2.2 現(xiàn)存的基本果蠅算法中存在的缺陷分析

該算法的工作原理和粒子群優(yōu)化算法十分相似，需要對(duì)果蠅種群進(jìn)行初始化處理，再依據(jù)移動(dòng)的步長(zhǎng)大小來(lái)更新果蠅種群的位置，之后果蠅種群中的其他個(gè)體逐步向適應(yīng)度最優(yōu)的個(gè)體的位置集中，并同時(shí)更新新種群果蠅的位置.這種優(yōu)化方式的不足可以簡(jiǎn)述為兩點(diǎn)：第一點(diǎn)，通過讓種群向當(dāng)前最優(yōu)位置的個(gè)體移動(dòng)的方式進(jìn)行種群的位置更新，容易使當(dāng)前的最優(yōu)個(gè)體陷入局部極值.而且缺乏有效可用的機(jī)制來(lái)跳出局部極值的局限，種群的進(jìn)化就會(huì)停止，以致無(wú)法找到問題的全局最優(yōu)解.第二點(diǎn)，果蠅群體的進(jìn)化過程都是通過固定步長(zhǎng)的方式來(lái)實(shí)現(xiàn)的，如果固定步長(zhǎng)設(shè)置得較大，果蠅就容易偏離最優(yōu)解，而且這種方式其過程的穩(wěn)定性較差，后期容易出現(xiàn)振蕩的不良現(xiàn)象.但是如果固定的步長(zhǎng)設(shè)置過短，又會(huì)導(dǎo)致果蠅群體陷入局部最優(yōu)解的惡性循環(huán)，使得算法的收斂精度達(dá)不到要求.因此，針對(duì)該算法的缺陷，筆者提出了一種效果更佳的優(yōu)化算法.

2.3 基本果蠅算法的優(yōu)化分析

（1）步長(zhǎng)自適應(yīng)調(diào)整：在算法的初期，保持一個(gè)較大的步長(zhǎng)；進(jìn)入迭代的后期，就可以移動(dòng)該步長(zhǎng)，將自適應(yīng)步長(zhǎng)減小，進(jìn)一步加快收斂的速度，同時(shí)獲得更高精度的全局最優(yōu)解.

（2）味道濃度判定值的修正：筆者在Si上加入一個(gè)參數(shù)，通過該參數(shù)的加入使得果蠅種群擺脫局部最優(yōu)解的局限，進(jìn)一步達(dá)到找出全局最優(yōu)解的目的.

（3）改進(jìn)后的果蠅算法穩(wěn)定性和魯棒性更強(qiáng)，查詢問題的求解速度的得到了巨大的提升，同時(shí)還能獲得更加精確的收斂精度.從根本原因分析，這主要是因?yàn)楦倪M(jìn)后的算法使用上一代最優(yōu)味道濃度判斷值和當(dāng)前的迭代次數(shù)自適應(yīng)調(diào)整進(jìn)化步長(zhǎng)，進(jìn)化到后期時(shí)，反而因此獲得了更好的收斂精度解，再通過對(duì)味道濃度判定值進(jìn)行的修正避免其陷入局部最優(yōu)解.

3 基于基本果蠅算法改進(jìn)的數(shù)據(jù)庫(kù)查詢優(yōu)化策略分析

3.1 數(shù)據(jù)庫(kù)查詢優(yōu)化的數(shù)學(xué)模型

在數(shù)據(jù)庫(kù)的查詢優(yōu)化過程中，查詢優(yōu)化的方案多種多樣，那么如何在這些方案中選出最優(yōu)的查詢方案十分重要，直接決定了數(shù)據(jù)庫(kù)查詢結(jié)果的精確度和查詢的效率是否能滿足用戶的需求.因此，本文使用兩階段策略，找到了最優(yōu)的數(shù)據(jù)庫(kù)查詢方案.使用“左深樹”為搜索策略空間.對(duì)于一個(gè)連接為J=RioinS的計(jì)算代價(jià)cost(J)而言，其計(jì)算式子如下圖一所示，在該式子當(dāng)中V（c，R）的計(jì)算式子如圖二所示.

圖一 計(jì)算代價(jià)式子

圖二 V（c，R）的計(jì)算式子

3.2 本文所述數(shù)據(jù)庫(kù)查詢優(yōu)化問題的求解過程

第一步，對(duì)一個(gè)數(shù)據(jù)庫(kù)的查詢問題的左深樹進(jìn)行編碼，以便進(jìn)一步得到數(shù)據(jù)庫(kù)的查詢序列L.第二步，對(duì)果蠅優(yōu)化算法的相關(guān)參數(shù)進(jìn)行初始化處理，相關(guān)參數(shù)有最大迭代次數(shù)以及群體的規(guī)模等.第三步，以得到的數(shù)據(jù)庫(kù)查詢序列L初始化的果蠅群體位置Si，再通過下圖三所示的式子計(jì)算出果蠅群體的適應(yīng)度值smelli，之后得到的果蠅的種群個(gè)體的狀態(tài)就是對(duì)應(yīng)的數(shù)據(jù)庫(kù)查詢的結(jié)果.第四步，在果蠅種群之中，找出味道濃度最佳的果蠅，并將其對(duì)應(yīng)的濃度值和對(duì)應(yīng)序列的Si保留下來(lái).第五步，更新整個(gè)算法過程的判定值，果蠅群體飛向最優(yōu)位置.第六步，不斷重復(fù)上述的幾個(gè)步驟，當(dāng)?shù)螖?shù)達(dá)到最大值時(shí)，果蠅群體的最優(yōu)位置就正好對(duì)應(yīng)了數(shù)據(jù)庫(kù)查詢方案.完成上述步驟之后，還需進(jìn)行最后一步，即通過遺傳算法更進(jìn)一步地進(jìn)行數(shù)據(jù)庫(kù)優(yōu)化查詢，從而找到最優(yōu)的方案，實(shí)現(xiàn)兩階段的數(shù)據(jù)庫(kù)最優(yōu)查詢.

圖三 適應(yīng)度函數(shù)定義式（其Si為個(gè)體i在t迭代中的序列編碼）

4 仿真實(shí)驗(yàn)介紹及結(jié)果分析

4.1 仿真實(shí)驗(yàn)環(huán)境介紹

本文將對(duì)上文所敘述的兩階段數(shù)據(jù)庫(kù)查詢優(yōu)化策略進(jìn)行仿真測(cè)驗(yàn)，以驗(yàn)證該方法是否能夠?qū)崿F(xiàn)最優(yōu)查詢.本次仿真測(cè)選擇基本的果蠅算法數(shù)據(jù)庫(kù)查詢優(yōu)化策略和粒子群優(yōu)化算法數(shù)據(jù)庫(kù)查詢優(yōu)化策略進(jìn)行對(duì)比分析，依據(jù)查詢所需的代價(jià)、搜索的代價(jià)以及查詢問題過程中所需的時(shí)間作為評(píng)價(jià)查詢結(jié)果好壞的評(píng)判標(biāo)準(zhǔn).

4.2 仿真實(shí)驗(yàn)結(jié)果與分析

4.2.1 代價(jià)結(jié)果分析

通過對(duì)上文所述的算法對(duì)數(shù)據(jù)庫(kù)的查詢優(yōu)化問題進(jìn)行求解，得到的搜索代價(jià)和查詢優(yōu)化代價(jià)結(jié)果，對(duì)所得的結(jié)果進(jìn)行分析，可得到如下結(jié)論：首先，如果數(shù)據(jù)庫(kù)的規(guī)模相對(duì)較小，那么基本果蠅算法、粒子群優(yōu)化算法以及本文所述的算法之間表現(xiàn)出來(lái)的性能差別不會(huì)十分明顯，都能夠得到較為理想的查詢結(jié)果.其次，隨著數(shù)據(jù)庫(kù)規(guī)模的增大，這三種算法的搜索代價(jià)和查詢代價(jià)都有不同程度的增加，其中本文所述算法增加的幅度較小，變化趨勢(shì)相對(duì)較為穩(wěn)定.通過對(duì)比試驗(yàn)的結(jié)果我們可以知道，在這三種算法當(dāng)中，文本算法的性能優(yōu)于其他兩個(gè)算法.

4.2.2 收斂速度和查詢效率的比較分析

通過仿真結(jié)果可知，隨著數(shù)據(jù)庫(kù)規(guī)模的增大，這三種算法找到最優(yōu)解所花費(fèi)的收斂時(shí)間逐漸加長(zhǎng)，分析其產(chǎn)生原因可知，主要是計(jì)算復(fù)雜度增加造成的.對(duì)于相同大小規(guī)模的數(shù)據(jù)庫(kù)，本文所述的算法所花費(fèi)的時(shí)間最短，粒子群優(yōu)化算法所需的時(shí)間長(zhǎng)度次之，基本果蠅算法所需的求解時(shí)間最長(zhǎng).本文所述算法之所以能夠取得如此好的效果，主要是因?yàn)榻鉀Q了另外兩種算法都存在的問題，即后期收斂速度慢且容易陷入局部最優(yōu)解，因此本文所述的算法在執(zhí)行速度上表現(xiàn)出明顯的優(yōu)勢(shì).

本文所述方法不僅可以得到數(shù)據(jù)庫(kù)查詢優(yōu)化問題中的最優(yōu)解，而且相對(duì)于穩(wěn)重所提到的其他算法而言，具有更好的查詢效率和查詢質(zhì)量，這對(duì)信息管理系統(tǒng)來(lái)說(shuō)無(wú)疑是一個(gè)巨大的進(jìn)步，在實(shí)際使用中的應(yīng)用前景十分廣闊.

5 結(jié)語(yǔ)

綜上所述，本文針對(duì)基本果蠅優(yōu)化算法及其數(shù)據(jù)庫(kù)查詢優(yōu)化算法存在的效率低下、難以找到全局最優(yōu)解的缺點(diǎn)，進(jìn)行了優(yōu)化，并提出了一種收斂效果佳、查詢速度及結(jié)果更合理的數(shù)據(jù)庫(kù)查詢優(yōu)化策略.通過對(duì)果蠅優(yōu)化算法進(jìn)行的修正，彌補(bǔ)了基本果蠅優(yōu)化算法的不足，再通過遺傳算法進(jìn)行查詢，進(jìn)而得到最優(yōu)解.這種算法能夠加快數(shù)據(jù)庫(kù)查詢優(yōu)化問題的速度和效率，而且使用質(zhì)量更有保證.但是科技的進(jìn)步步伐從未停止，更快更好的數(shù)據(jù)庫(kù)查詢優(yōu)化策略一定存在，還需要研究人員的不斷努力.

〔1〕曾理.數(shù)字有機(jī)體數(shù)據(jù)庫(kù)分布式查詢優(yōu)化與分布式事務(wù)處理的研究與實(shí)現(xiàn)[J].電子科技大學(xué)，2009，4（1）：98-99.

〔2〕李芳萍.基于半連接策略的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化理論研究及應(yīng)用[J].中南大學(xué),2008,6（30）：94-95.

〔3〕張琛.網(wǎng)絡(luò)數(shù)據(jù)庫(kù)查詢優(yōu)化策略的研究.[D].華中科技大學(xué)，2007，6（1）：59-60.

〔4〕宋麗娜.基于遺傳退火算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化研究與應(yīng)用[J].長(zhǎng)春理工大學(xué)，2009，6（1）：98-99.

TP18

A

1673-260X（2017）03-0031-02

2016-12-11