基于基本果蠅算法改進的數據庫查詢優化策略

陳金萍

（大連海洋大學 應用技術學院，遼寧 瓦房店 116300）

基于基本果蠅算法改進的數據庫查詢優化策略

陳金萍

（大連海洋大學 應用技術學院，遼寧 瓦房店 116300）

由于當前很多常用的數據庫查詢優化算法都存在查詢效率低的問題，很難找到能夠實現全局最優的數據庫查詢優化算法，使得很多用戶在進行數據庫查詢時，數據庫無法完全滿足其需求.為此，本文提出了一種基于基本果蠅算法改進的數據庫查詢優化方法，并通過仿真測試的方法驗證其查詢優化的效果，以求加快數據庫查詢優化問題的效率和質量.

兩階段；優化方案；數據庫查詢；果蠅算法；仿真測試；查詢優化

在數據庫應用中，查詢是其中使用最為頻繁的操作.查詢操作需要在動態組成的虛擬數據庫上進行，在查詢過程中，服務是中心，整個查詢過程通過動態組建服務以供用戶使用并完成查詢任務.隨著信息技術的發展，數據庫在信息管理系統中的重要性與日俱增升，要想為用戶提供更好的信息管理系統功能，就必須使用優化的查詢方案，以獲得更好的使用體驗.

1 數據庫查詢優化研究簡介

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

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

2 基本果蠅算法改進分析

2.1 基本果蠅優化算法介紹

果蠅優化算法是一種新型的群智能算法，與其他群智能算法相比較來說，具有能夠調整參數和簡單容易實現的優點，學習和理解起來更加容易.該算法的具體過程如下所示：參數初始化——設置果蠅個體嗅覺覓食的隨機方向和距離——估計與遠點的距離，并計算下一位置的味道濃度判定值——將下一位置濃度的判定值帶入味道濃度判定值函數，再將果蠅個體所在位置的味道濃度計算出來——計算出整個群體中味道濃度最佳的果蠅——記錄最佳味道濃度值預期對應的坐標，這是，果蠅群體就會依靠其敏銳的視覺飛向該坐標——持續重復上述幾個步驟，直到所得結果滿足終止條件為止.

2.2 現存的基本果蠅算法中存在的缺陷分析

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

2.3 基本果蠅算法的優化分析

（1）步長自適應調整：在算法的初期，保持一個較大的步長；進入迭代的后期，就可以移動該步長，將自適應步長減小，進一步加快收斂的速度，同時獲得更高精度的全局最優解.

（2）味道濃度判定值的修正：筆者在Si上加入一個參數，通過該參數的加入使得果蠅種群擺脫局部最優解的局限，進一步達到找出全局最優解的目的.

（3）改進后的果蠅算法穩定性和魯棒性更強，查詢問題的求解速度的得到了巨大的提升，同時還能獲得更加精確的收斂精度.從根本原因分析，這主要是因為改進后的算法使用上一代最優味道濃度判斷值和當前的迭代次數自適應調整進化步長，進化到后期時，反而因此獲得了更好的收斂精度解，再通過對味道濃度判定值進行的修正避免其陷入局部最優解.

3 基于基本果蠅算法改進的數據庫查詢優化策略分析

3.1 數據庫查詢優化的數學模型

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

圖一 計算代價式子

圖二 V（c，R）的計算式子

3.2 本文所述數據庫查詢優化問題的求解過程

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

圖三 適應度函數定義式（其Si為個體i在t迭代中的序列編碼）

4 仿真實驗介紹及結果分析

4.1 仿真實驗環境介紹

本文將對上文所敘述的兩階段數據庫查詢優化策略進行仿真測驗，以驗證該方法是否能夠實現最優查詢.本次仿真測選擇基本的果蠅算法數據庫查詢優化策略和粒子群優化算法數據庫查詢優化策略進行對比分析，依據查詢所需的代價、搜索的代價以及查詢問題過程中所需的時間作為評價查詢結果好壞的評判標準.

4.2 仿真實驗結果與分析

4.2.1 代價結果分析

通過對上文所述的算法對數據庫的查詢優化問題進行求解，得到的搜索代價和查詢優化代價結果，對所得的結果進行分析，可得到如下結論：首先，如果數據庫的規模相對較小，那么基本果蠅算法、粒子群優化算法以及本文所述的算法之間表現出來的性能差別不會十分明顯，都能夠得到較為理想的查詢結果.其次，隨著數據庫規模的增大，這三種算法的搜索代價和查詢代價都有不同程度的增加，其中本文所述算法增加的幅度較小，變化趨勢相對較為穩定.通過對比試驗的結果我們可以知道，在這三種算法當中，文本算法的性能優于其他兩個算法.

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

通過仿真結果可知，隨著數據庫規模的增大，這三種算法找到最優解所花費的收斂時間逐漸加長，分析其產生原因可知，主要是計算復雜度增加造成的.對于相同大小規模的數據庫，本文所述的算法所花費的時間最短，粒子群優化算法所需的時間長度次之，基本果蠅算法所需的求解時間最長.本文所述算法之所以能夠取得如此好的效果，主要是因為解決了另外兩種算法都存在的問題，即后期收斂速度慢且容易陷入局部最優解，因此本文所述的算法在執行速度上表現出明顯的優勢.

本文所述方法不僅可以得到數據庫查詢優化問題中的最優解，而且相對于穩重所提到的其他算法而言，具有更好的查詢效率和查詢質量，這對信息管理系統來說無疑是一個巨大的進步，在實際使用中的應用前景十分廣闊.

5 結語

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

〔1〕曾理.數字有機體數據庫分布式查詢優化與分布式事務處理的研究與實現[J].電子科技大學，2009，4（1）：98-99.

〔2〕李芳萍.基于半連接策略的分布式數據庫查詢優化理論研究及應用[J].中南大學,2008,6（30）：94-95.

〔3〕張琛.網絡數據庫查詢優化策略的研究.[D].華中科技大學，2007，6（1）：59-60.

〔4〕宋麗娜.基于遺傳退火算法的數據庫多連接查詢優化研究與應用[J].長春理工大學，2009，6（1）：98-99.

TP18

A

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

2016-12-11