基于多子群螢火蟲算法的數據庫查詢優化

劉 東

LIU Dong

陜西理工學院 物理與電信工程學院，陜西 漢中 723001

School of Physics and Communication Engineering,Shaanxi University of Technology,Hanzhong,Shaanxi 723001,China

1 引言

隨著數據庫技術成熟和應用范圍的擴大，出現了許多大規模數據庫，而查詢優化是提高數據庫性能的關鍵技術之一，因此針對一個查詢問題，如何找到一種最優查詢計劃至關重要，成為數據庫研究中的重要課題[1-2]。

找到數據庫的最優查詢計劃就是要構造一棵代價最小的多連接查詢樹，為此針對數據庫查詢優化問題，國內外學者從不同角度做了大量的工作，提出許多查詢優化算法[3]。最傳統的查詢優化算法采用窮盡搜索算法或其他變形算法，當連接關系數目較小時，可以取得較好的查詢效果，但現代數據庫管理系統的查詢連接數目通常很大，這類算法毫無用處，沒有什么實際應用價值[4]。隨后有學者提出動態規劃算法解決數據庫查詢優化問題，但查詢效率低，不能滿足現代數據庫查詢要求[5]。大量研究表明，數據庫查詢優化包括了許多約束條件，實質上是一個組合優化問題，群智能算法具有搜索速度快的優點，因此一些學者將群智能算法應用于數據庫查詢優化問題的求解中[5]。文獻[6]等提出一種基于遺傳算法的數據庫查詢優化方法，采用遺傳算法對查詢執行計劃代價進行求解，取得了不錯的效果。Kumar等人根據查詢數據關聯度之間的關系，提出一種基于遺傳算法的數據庫查詢優化方法[7]。遺傳算法雖然具有尋優能力強的優點，但是對于不同問題需要設置不同的遺傳算子，存在局部搜索能力差等不足[8]。為此，一些學者基于組合優勢，如Zhou對遺傳算法進行改進，但對于不同問題，需要進行相應的改進，通用性差[9]。Po-Han Chen等將模擬退火算法引入遺傳算法的變異過程中，獲得比遺傳算法更優的數據庫查詢優化效果，但是存在尋優結果不穩定等缺陷[10]。林桂亞等利用蟻群算法對數據庫查詢優化問題進行求解，取得了不錯的效果[11]。螢火蟲群算法（Firefly Algorithm，FA）是一種模擬螢火蟲發光行為的群智能優化算法，多個螢火蟲被隨機散布于整個搜索空間內，所有螢火蟲都具有一個由被優化問題所決定的適應度值，對應于該螢火蟲的熒光亮度。然后每個螢火蟲個體都在其視覺范圍內追隨熒光亮度更強的螢火蟲飛行，經過多次群體運動后，所有個體將聚集在熒光亮度最強的螢火蟲附近，完成最終尋優，為解決數據庫查詢優化問題提供了一種新的研究方法[12]。

針對數據庫查詢優化效率低的難題，提出一種多子群螢火蟲群算法（MG-FA），并將其應用于數據庫查詢優化問題求解中。首先將數據庫查詢計劃左深樹看作一個螢火蟲，然后通過螢火蟲相互學習機制和信息交流找到數據庫查詢最優方案，并通過仿真實驗測試其性能。

2 多子群螢火蟲優化算法

螢火蟲優化算法是一種模擬螢火蟲發光行為的群智能優化算法，其基本思想為：用搜索空間中的點模擬自然界中的螢火蟲個體，將問題目標函數定義成螢火蟲所處位置的相應解，將尋優過程模擬成螢火蟲個體向更亮螢火蟲的移動過程。設共有m個螢火蟲，第i個螢火蟲在 N 維空間中的當前位置為 Xi=(xi1，xi2，…，xiN)，螢火蟲位置優劣通過螢火蟲亮度描述，并決定其移動方向，其相對熒光亮度為：

式中，I0為表示第i只螢火蟲最大熒光亮度；λ為光強度吸收參數；rij為螢火蟲i與 j之間的距離，定義為：

吸引度(β)決定了螢火蟲移動的距離，定義為：

式中，β0為最大吸引度因子。

螢火蟲i被螢火蟲 j吸引后移動的位置更新由式（4）決定：

式中，xi、xj為第i和第 j個螢火蟲所處的空間位置；α為步長因子；rand()是隨機數[13-14]。

在實際應用中，由于螢火蟲算法實質是一種隨機優化算法，因此存在一些不足，如果螢火蟲算法進化后期收斂速度慢，易陷入局部最優解等[15]。

2.1 保持種群的多樣性

種群多樣性對螢火蟲的尋優性能起著至關重要的作用，為此，首先將螢火蟲群分為n個子群，并為不同子群設置不同α、λ、β0等參數，各子群根據自己尋優方式進行并行尋優，以滿足全局尋優要求；然后為每個子群設置公告板，記錄每次迭代后的各子群最優值及相應個體位置，并將所有子群的最優個體組建為“決策層”，如果某子群最優值連續3次沒有發生變化，那么就認為該子群發生早熟，可能陷入局部最優，此時從“決策層”找到更優螢火蟲個體，并對早熟子群的最優個體將利用式（1）～（4）向其他子群的更優個體進行學習，從而完成位置轉移，跳出當前局部最優區域?！皼Q策層”構建了各子群之間的信息交流與相互學習的途徑，能夠對早熟子群提供更明確有效的指導；最后若發現某子群已陷入局部最優，但在“決策層”中找到更優的其他子群個體時，采用高斯變異因子對該子群進行擾動。高斯分布是一種工程常用的重要概率分布，其概率密度函數如式（5）所示：

式中，σ為高斯分布的方差，μ為期望。

將子群內的螢火蟲按照優劣大小排序，利用子群內的最優螢火蟲將排名最后的螢火蟲群體進行狀態替換更新，同時對更新螢火蟲群體的狀態進行高斯變異處理，如式（6）所示。

式中，N(μ，σ)為服從期望為 μ，方差為σ的高斯分布的隨機向量。

2.2 自適應變步長機制

步長因子α取值影響螢火蟲算法的收斂性能影響，為了提高算法收斂速度和全局尋優能力，在尋優過程中采用自適應變步長機制：初期α值較大，提高全局尋優能力；隨著迭代次數增加，逐步減小α值，加快后期收斂速度，具體調整方式為：

式中，Δα為步長衰減系數，在（0.95，1）內取值。

2.3 域約束

為保證螢火蟲個體始終在有效搜索空間進行搜索，對螢火蟲個體進行域約束處理，具體為：

式中，xmin和xmax分別為搜索空間下限和上限。

采用4個準測試函數：Sphere、Griewank、Ackley和Rastrigin對FA算法、粒子群優化（PSO）算法和MG-FA算法的性能進行測試，4個測試函數見表1所示。

圖1 不同算法的收斂性能比較

表1 用于測試算法性能的函數

FA、PSO和MG-FA算法的運行結果如圖1所示。從圖1可知，Sphere函數只有一個全局最優值，較容易求出；Griewank函數在全局最優值附近不是光滑連續的，增大了搜索難度；Ackle函數只有一個全局最優值，但在全局最優值的附近幾乎呈不連續狀態，在全局最優值附近搜索的難度很大。Rastrigin是一種病態函數，全局最優與局部最優有很深的狹縫，很多搜索算法幾乎無法找到全局最優值，由此可知，針對所有函數，MG-FA算法的進化迭代次數更少，收斂速度更快，并且具有更高的收斂精度，主要是由于在多子群相互學習機制的驅動下，MG-FA算法更容易跳出進化停滯狀態，當發生進化變慢或者停滯時，MG-FA算法能通過子群之間的信息傳遞，牽引進化受阻的螢火蟲重新進入進化狀態，具備一定的進化復蘇能力，從而能夠更好地滿足局部搜索和全局精度的全面尋優要求，具有更好的求解效率。

3 查詢優化的MG-FA設計模型

3.1 設計模型

數據庫查詢過程會涉及到多個關系表，不同表之間的連接次序導致查詢結果的多樣性。對于n個表，左、右深樹均含有n!個查詢優化計劃，查詢優化是找到一條最小查詢代價的執行計劃[11]。設一個查詢請求可能的查詢計劃集合為S，那么元素 s的相關聯代價為cost(s)， 若有 n 個關系 R={r1，r2，…，rn}參與連接運算，tm表示中間關系，那么cost(s)為中間關系tm代價的總和，數據庫查詢優化問題的數學模型為：

3.2 查詢優化的MG-FA設計

3.2.1 編碼

MG-FA算法第一個步驟是對所解問題進行編碼，因此，編碼好壞是MG-FA是否成功的一個關鍵因素。為了保留連接樹的特征，本文采用直接以樹的形式編碼。對于圖2的左深樹，螢火蟲的編碼方式為“653412”。

圖2 左深樹表示

3.2.2 適應度函數

查詢優化的目標是要獲得代價cost(Xi)最小的執行計劃，因此螢火蟲個體的適應度函數必須與cost(Xi)相關，因此適應度值函數定義如下：

3.2.3 MG-FA數據庫查詢優化算法的工作流程

MG-FA算法將數據庫查詢計劃左深樹看作一個螢火蟲，然后通過螢火蟲之間的協作找到數據庫查詢最優計劃，在螢火蟲搜索過程中，引入高斯變異策略，提高算法的全局搜索能力，避免陷入局部最優，具體工作步驟如下：

（1）對左深樹組成的解空間中的連接操作進行編碼，后續遍歷連接樹得到編碼序列L。

（2）初始化參數。設置螢火蟲數目m及螢火蟲子群數n，并為各子群分別設置光強吸收系數λ、最大吸引度因子 β0及步長因子α。設定收斂條件，并在求解空間內隨機生成各螢火蟲的初始位置 xij(i=1，2，…，n，j=1，2，…，m/n)。

（3）根據式（10）計算各子群螢火蟲的適應度值 f(xi)作為其最大熒光強度，并將各子群中的最佳適應度值記為 fibest，計入子群公告板。

（4）由式（2）計算各子群螢火蟲個體的相對熒光亮度Iij，比較所屬子群鄰域內螢火蟲的熒光亮度大小，并確定各螢火蟲的位置進化方向。

（5）由式（3）計算各子群螢火蟲的吸引度 βij，并根據式（4）更新螢火蟲的空間位置。

（6）查詢各子群公告板，判斷各子群是否出現迭代次數已達到3次，并且 fibest的連續變化量小于1e－3的現象，若是，則轉步驟（7），否則，轉步驟（8）。

（7）從其他子群公告板中尋找最優個體，若存在優于自身子群的最優值，則讓自身的最優螢火蟲向其他更優子群的最優個體進行位置轉移；若否，則在自身子群內進行高斯變異操作。

（8）根據式（5）收縮步長，并對所有螢火蟲個體進行域約束操作。

（9）如果滿足終止條件，最優螢火蟲位置對應的數據庫查詢計劃。

綜合上述可知，基于MG-FA具體流程如圖3所示。

4 仿真實驗

4.1 仿真環境

為了測試MG-FA算法的性能，在AMD Athlon II X46313.0 GHz，RAM 4 GB，Windows 7操作系統環境中進行仿真實驗，采用SQL Server 2005作為數據庫軟件，采用VC++編程數據庫查詢優化算法。對比算法為：螢火蟲優化算法（FA）、粒子群優化（PSO）算法。采用查詢和執行代價評估算法性能。

圖3 MG-FA算法的數據庫查詢流程

4.2 結果與分析

4.2.1 搜索和查詢消耗代價比

不同數據庫查詢優化方法的查詢和執行最優計劃的代價比如圖4、5所示。

圖4 各種算法的搜索代價比

圖5 各種算法的查詢代價比

從圖4和5的結果進行分析可以得到如下結論：

（1）PSO算法代價消耗比曲線變化幅度較大，說明PSO算法在求解數據庫查詢問題時，性能不穩定且求得最優查詢執行計劃的準確率不高。

（2）相對于PSO算法，FA的整體搜索代價比曲線并未出現明顯變化，變化相對平衡，對比結果表明，相對于PSO算法，FA算法加快了算法的收斂速度，隨著關系數的增加，FA算法的整體優化效果要優于FA算法。

（3）相對于PSO、FA算法，MG-FA算法的性能得到相應提升，主要是由于高斯變異算子增加了種群多樣性，有較地實現了算法全局與局部搜索的平衡，不僅提高了數據庫查詢效率，而且大幅度地減少了執行代價，能夠更快速地找到最優數據庫查詢計劃。

4.2.2 迭代次數和執行時間

不同算法的收斂速度和最優查詢計劃執行時間見表2和3。

表2 各算法的查詢優化計劃迭代次數

表3 各算法的執行時間對比 s

對表2和表3進行分析可知：

（1）對于數據庫的關系連接數n=20的查詢優化問題，當迭代476次時，PSO算法便找到了最優數據庫查詢計劃，其相應執行時間為250.77 s。

（2）相同條件下，當迭代370次時，螢火蟲優化算法（FA）便找到了最優數據庫查詢計劃，相應的數據查詢的執行時間為200.27 s，相對于PSO算法，FA加快了算法的收斂速度，提高了最優解的質量。

（3）MG-FA算法迭代240次后得到比FA和PSO算法更優的數據庫查詢計劃，其執行時間為185.05 s。

綜上可知，MG-FA算法的搜索速度更快，較好地防止了早熟收斂，提高了數據庫查詢效率。

5 結束語

數據庫查詢優化是一種要求速度快、效率高的優化問題，針對當前數據庫查詢優化算法存在的效率低，難以獲得最優解的缺陷，結合數據庫查詢的特點和螢火蟲算法的優點，提出一種多子群螢火蟲算法的數據庫查詢優化方法，首先將螢火蟲群分為不同參數的多個子群，各子群內的螢火蟲跟隨所屬子群的最優螢火蟲分別進行尋優操作，然后在各子群的最優螢火蟲之間構建相互學習機制，實現子群間的信息交流，最后采用數據庫查詢優化數據進行仿真實驗，實驗結果表明，MG-FA是一種性能良好的數據庫查詢優化方法，能夠獲得比其他算法更佳的查詢結果。

[1]許新華，胡世港，唐勝群，等.數據庫查詢優化技術的歷史、現狀與未來[J].計算機工程與應用，2009，45（18）：156-161.

[2]于洪濤，錢磊.一種改進的分布式查詢優化算法[J].計算機工程與應用，2013，49（8）：151-155.

[3]林鍵，劉仁義，劉南，等.基于查詢優化器的分布式空間查詢優化方法[J].計算機工程與應用，2012，48（22）：161-165.

[4]邱桃榮，葛寒娟，魏玲玲，等.基于相似度的粗關系數據庫的近似查詢[J].計算機工程與應用，2008，44（21）：195-198.

[5]史恒亮，任崇廣，白光一，等.自適應蟻群優化的云數據庫動態路徑查詢[J].計算機工程與應用，2010，46（9）：10-12.

[6]帥訓波，馬書南，周相廣，等.基于遺傳算法的分布式數據庫查詢優化研究[J].小型微型計算機系統，2009，30（8）：1600-1604.

[7]Kumar T V V，Singh V，Verma A K.Distributed query processing plans generation using genetic algorithm[J].International Journal of Computer Theory and Engineering，2011，3（1）：38-45.

[8]Zhou Z H.Using heuristics and genetic algorithms for large-scale database query optimization[J].Journal of Information and Computing Science，2007，2（4）：261-280.

[9]Chen P H，Seyed M.Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints[J].Automation in Construction，2009，18（4）：434-443.

[10]林桂亞.基于粒子群算法的數據庫查詢優化[J].計算機應用研究，2012，29（3）：974-975.

[11]Gandomi A H，Yang X S，Talatahari S.Firefly algorithm with chaos[J].Communications in Nonlinear Science and Numerical Simulation，2013，18（1）：89-98.

[12]劉長平，葉春明.一種新穎的仿生群智能優化算法：螢火蟲算法[J].計算機應用研究，2011，28（9）：3295-3297.

[13]Horng M H.Vector quantization using the firefly algorithm forimage compression[J].ExpertSystemswith Applications，2012，39（1）：1078-1091.

[14]Senthilnath J，Omkar S N，Mani V.Clustering using firefly algorithm：performance study[J].Swarm and Evolutionary Computation，2011，1（3）：164-171.

[15]Coelho L S，Mariani V C.Firefly algorithm approach based on chaotic Tinkerbell map applied to multivariable PID controller tuning[J].Computers&Mathematics with Applications，2012，64（8）：2371-2382.